Skip navigation

Category Archives: Path Finding

When I first sat down to implement train path finding on placed tracks I had an overly complicated model in my head of how tracks connected and how one might sniff out a path on the track.  It involved allowing “turning around” at a station that was not the train’s destination – how do you indicate that it’s “OK” to be traveling the same path but now the other direction… Then, in the spirit of MVP and my original “simplify it if you can and the game is still fun” mentality I realized that trains don’t need to be able to turn around at stations.  The rules I put in place for track layout guarantee that a train can get from any hex to any other hex without backtracking on hexes it has already visited.  With that understanding there are no circumstances where turning around at a station nets a shorter path or opens up solutions that wouldn’t have otherwise existed.  It was just me wanting to solve the hardest, juiciest problem.

After throwing out the idea of non-destination station turnarounds the entire problem got way easier.  A simple “bucket fill” path solving algorithm nets all possible solutions and then I just ask for the one that costs the least.  Cost is a combination of distance and type of terrain the solution has to pass though.

Here we see a train following a solved-for path from Charlotte to Donald’s Tree Farm.  Sorry about the gif artifacts, those are not there in the real rendering.



Next steps:

  • Box cars
  • Supply/Demand netting from train deliveries
  • Player Goals

I have spent the last two and a half weeks working diligently on my MVP for project Cat Phone.  The plan I described in my first MVP post has been paying off.  I have worked on the project casually and have focused on my MVP one item at a time.

I purchased a hex framework a long time ago when I first got interested in re-booting this project and have been sitting on it ever since.   This gave me a very easy way to implement item number 1 on the MPV list: a hex map.  From there, I have added random resource nodes around the map, and most importantly, added path finding and track layout.   I have put into place rules like: Only one branch or resource node per hex tile.  The hex map and these rules allow me to simplify track path finding and layout quite a lot.

If you look closely at the bottom left of these screen captures, you can see the track layout working with branching.  In these pictures, new track to be placed is rendered in a purple color and track that has been placed is rendered in a yellow-brown.  Resources are spheres rendered in a color depicting their type (green for timber, off-white for color, etc.)

Next on the list to tackle is station placement, then train path finding.

screenshot2 screenshot3 screenshot4 screenshot5 screenshot6

I added Cities to my game tonight.  They know their population and base how “big” they are based on it.  Each city has a number of buildings based on the population as well.  The number and size of the buildings grows with the population.  At the moment these buildings are represented by white boxes, but that can change if I ever get some real assets.


The really cool trick is that that when a road is placed near a city, all the buildings in that city check themselves and make sure they are not over the road.  If the building does exist over the road, it re-position’s itself.

I have updated my previous example program with textures on the terrain and road generation.

In screen shot 1, you will see the road drawn with a line along the path generated from my previous post about path generation on height mapped terrains.

In screen shot 2, the example program has been upgraded to generate vertex information for the “sides of a road”.  These are marked with small while pylons.

In screen shot 3, a mesh has been generated out of the vertex info and a texture has been applied to it.


This brings me to a good starting point for putting together the CatPhone project.  The next step will be making the road segments interact with each other well.


Wish me luck.

I have had a game idea brewing in the back of my head for quite some time.  The game involves at some point, being able to place (something like) a road on a terrain.  The player would need to decide when placing a road between two points is advantageous.  Once the decision has been made to place such a road, the player should be able to select a start and end point to the path and have the game do the rest.  Now, its not good enough just to draw a road as the bird flies – obstacles might be in the way and it might be more “expensive” to climb a hill than cross flat land.  Obstacles might be anything from ponds, to buildings, to hill sides too steep to build a road over.

Pair this desire to learn Unity 3D ever since my partner left for a AAA game company causing me to not want to maintain our Game Framework and you get this demo:

As you can see, a path has been drawn around the hill because climbing over that hill would have been more expensive than going around it.


Program Download (PC): TerrainExample


The terrain is 2000×2000 world units large (4M nodes in graph if taken like that, but I step by 5 units when solving).

Arrow keys to move the camera.

First click sets start point and solves the graph. Once graph is solved, mouse move calculates the path from start point to position under mouse. Second click sets the end point as the final path solution – mouse movements will not recalculate after 2nd mouse click. Subsequent mouse clicks start the process over.