Creating a node based routing table for pathfinding and fastest / best route decision making AI in your game

In our upcoming game Interstellar Transport Company you take the reins of a Space Transportation Company tasked with transporting goods and passengers throughout the galaxy and financially crushing your rivals.  One of our goals when designing the game was to have intelligent passengers that could utilize a “hub and spoke” transportation network.  This is rarely done in transportation tycoon games (Cities in motion is one of the better examples of proper implementation) and we thought this would help separate our game from others in the genre.

routes

I am a network engineer / administrator by day and a game programmer by night.  This is one of those situations where the two disciplines collided.  Network design and transportation systems both use a strikingly similar hub / spoke layout.  Whether you’re dealing with passengers traveling from a small town to another small town  on the other side of the world (or planet to planet in our game’s case) or a network packet traveling from one end user to another the base logic is nearly the same.  The packet and passenger both must decide the most efficient way to get from the start to end point utilizing multiple hops along the way.  I decided to use network engineering’s concept of dynamic routing tables and adapt it to an AI pathfinding algorithm.  It is somewhat similar to A* pathing if you have ever dealt with that but also different since we need to present multiple paths for the AI to choose from.  For some quick background on network routing tables, you can read this wikipedia article which does a good job giving the basics of how it works.

internet_marc
A visualization of all the connections in the internet.

There are 5 main steps in setting this logic up:

  • 1  Setup route weights and data classes
  • 2  Build direct connections between nodes (planets in our case)
  • 3  Loop through all nodes, let connected neighbors know of routes -Only broadcast lowest cost routes to a neighbor.
  • 4  Loop through all nodes in reverse, let connected neighbors know of routes that they didn’t get in step 2 -Only broadcast lowest cost routes to a neighbor.
  • 5  Make sure that a node in the table isn’t pointing back to itself.

 

Step 1, Setup route weights and data classes:

The first thing you must decide is how your route hops will be weighted.  In Interstellar Transport Company I decided to use this arrangement.  If the nodes (planets / moons / stations in my case) are less than 10 Million miles apart the hop weight is 1, this is supposed to represent hops between planets and moons or planets and space stations.  If the two are still within the same star system but beyond 10 Million miles I use a weight of 2.  If the two nodes are separated by interstellar space I take the number of light years the stars are separated and add three to that number.  This seems to give good balanced weights to my hops.  You can decide on any arrangement that makes sense to your game.  Just remember that the higher the weight, the less likely the AI is to choose that path, so give this step some thought.  I setup a simple function at this point that returned a weight as a float value when given the two nodes.

Next you should define your routing table class.  This will be a member class of your node classes.  So think of it as node[x].routing_table[].  You should have the following information at very least:

  • final_destination_node_id
  • directly_connected_node_id_to_reach_final_destination
  • weight_of_hop

For Interstellar Transport Company we also needed to include lowest_fare and highest_luxury so that the AI passengers waiting at a spaceport could decide whether to board a flight to their next hop or not depending on how expensive and luxurious it is compared to their wait time and original expectations.  Next we move on to populating these data tables.

routing_table_code_snippet

Step 2, Build direct connections between nodes:

In this step you will simply loop through all of your nodes and find what other nodes they are directly connected to.  In our case we needed to verify there were routes setup between the planets and that there was seating available on the ships assigned to those routes.  Your situation will likely be different than ours, whatever the criteria in your game for validating a route, this is where you place that logic.  Whenever a valid route is found place the route in the originating node’s routing_table list, being sure to check for (and not adding) duplicates.  Now you should have a list of every valid neighbor at every node and the weight of those individual hops.  final_destination_node_id will be the neighbor’s node_id, directly_connected_node_id_to_reach_final_destination will also be the neighbors node_id, and the weight_of_hop will be the hop weight as determined by the logic described in step 1.

3-3-2017_1

Step 3, Loop through all nodes, let connected neighbors know of routes -Only broadcast lowest cost routes to a neighbor:

Loop through your list of nodes, you are going to send all outgoing routes from a node to it’s upstream neighbors.  For example in the figure below B already knows that it has a route to C and a route to A, however A does not know it has a route to C through B and E does not know it has a route to A or C through B.  So when the loop reaches B, it must find all routes of it’s neighbors that point to B (A and E) and send them it’s own outgoing routes.

routing_blog_step 3

Following this same logic, B will also have knowledge of a route from C to D and D will have knowledge of a route from E to B.

We will be populating the routing table a little differently this time however, let’s use the example of B telling A it can reach C through B.  A will add an entry to it’s routing table with C as the final_destination_node_id, B will be the directly_connected_node_id_to_reach_final_destination, and the hop_weight will be the sum of the A-B and B-C hops.

 

Step 4, Loop through all nodes again, but in reverse, let connected neighbors know of routes -Only broadcast lowest cost routes to a neighbor:

You will now loop through all of the nodes again, in reverse this time, thus imparting knowledge of all possible routes to all nodes.  Using the same example from above:

routing_blog_step 4

Say we wanted to know if a passenger could get from A to E, after step 3 the passenger AI would still have no idea this is possible since B-C, C-D, D-E, E-B are all one way connections and A will only have knowledge of being able to get to C after step 3; C will only have knowledge of being able to get as far as E.  However, as soon as you run the same loop in reverse, suddenly all the knowledge that was distributed in step 3 gets fully extrapolated so D will tell C it can get to B, C will tell B it can get to E and D, B will then tell A it can get to C, D, and E through B.  I know it is a little confusing, but read through steps 3 and 4 again if you’re still confused at this point.

 

Step 5, Make sure that a node in the table isn’t pointing back to itself:

Notice in the example in Step 4, I do not say that C will tell B it can get to B through D.  This is because you never want to create a loop in this design, it will break things instantly.  So if the final_destination is ever the same as the origination, disregard that entry completely.

 

I will leave it up to you on how your AI agents best decide how to utilize these lists, in ITC we used the lowest_fare and highest_luxury rates and the time since the passenger started waiting to help determine if they take a flight that has a ship land at their node or not.  The situation will likely be different for you.

Hopefully this information has been helpful, please like and follow for more articles like this one and feel free to leave any comments or questions below and I will try to answer them as soon as I can.

Thank you,

Mike Stankiewicz

Founder, CEO, and Lead Developer at MT Worlds

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s