Author Topic: Random graphs  (Read 939 times)

Offline Hearteater

  • Core Member
  • *****
  • Posts: 2,334
Random graphs
« on: September 16, 2014, 10:45:33 PM »
Question on maps, specifically how you do AIW's random maps. Do you make a random graph of nodes and edges and then lay out all the node positions, or do you position the nodes and figure out the edges after? The first way seems to make more sense, but I'm torn on whether to create a generic layout method that works for any graph, or making a custom layout method for each random map generator. I'm wondering if I'm missing something and the second method might not have other advantages (besides avoiding a need to layout the nodes) I'm not seeing. I figure this is probably well tread ground for you guys :) .

Offline x4000

  • Chris Park, Arcen Games Founder and Lead Designer
  • Administrator
  • Zenith Council Member Mark III
  • *****
  • Posts: 30,621
Re: Random graphs
« Reply #1 on: September 17, 2014, 08:54:09 AM »
Well, we have a huge number of kinds of graph generators, honestly, so we could probably say "yes" to every variant of your question, heh.

The original map types that I coded were all based around laying down nodes first, then creating linkages after that.  In some versions proximity was valued, in others it was not.  In some versions it attempted not to overlap, in others it did not.  In some versions it had strict limits on how many linkages a single node could have, in others it had a certain number of planets that it would let have far more.

That was the original approach.  Then later I did some that used general maze creation methods by laying down pegs and driving a maze through them, for instance.  The snake I did by I believe laying down one node and then laying down the next and immediately linking them.  The tree was similar, but with little branches periodically.

Then Keith got into things and started doing the really cool maps, which are more shape-based.  All the stuff you see in the last two or three expansions.  I'm not sure how he did those exactly, but it's an entirely different approach from mine.
Have ideas or bug reports for one of our games?  Mantis for Suggestions and Bug Reports. Thanks for helping to make our games better!

Offline Draco18s

  • Resident Velociraptor
  • Core Member Mark IV
  • *****
  • Posts: 3,882
Re: Random graphs
« Reply #2 on: September 17, 2014, 10:03:17 AM »
I know that Space Empires (4?) did it by both proximity and a minimum angle from other connections.  It's been so long I can't even figure out where I read the details.