Last week or so I dug up something very amazing on The Piratebay. Someone packed up good old DOS classics into a Dosbox wrapper for Mac OS X, so I could start and run those games in a window on my Mac. Simply amazing. So, I started up Settlers II, one of the best games I’ve ever played. (Don’t gimme any crap about pirating games! I own this game. And the expansion. What do you think I have been doing during my childhood? )

So, for all that don’t know the game here’s Settlers II in a nutshell: every player starts out with a headquarter, a limited amount of building materials, goods, tools, settlers with different skills and a small strip of land. The surroundings offer everything you need to build up your small empire: woods that can be cut down by lumberjacks, granite that can be cut by stone cutters, mountains that offer coal, ore and gold and flat land that can be used to grow crops. On of the major challenges of this game is to get all the production chains right: let’s take for example a lumberjack.

A lumberjack cuts down trees. The logs then need to be transported to a sawmill where they get cut into handy boards. (Picture 1 shows such a production chain.) These boards in turn then need to get to a stock or to construction sites. And if you don’t build a forester your lumberjack will run out of trees very soon. That was one of the easier production chains.

Let’s look at something more sophisticated: production of meat. You’ll start of with a farm that grows crops. Then you need a pigfarm that takes the crops grown by the farm and water from a well to breed pigs. And finally, to get to your tasty meat, you’ll need a slaughterhouse. So, all in all, getting those production chains right is tricky and very rewarding. Nothing better than seeing wares running smoothly from source to destination (at least for me ).

Picture 1: A production chain for lumber. On the bottom left there is the forrester. The guy living in that building just keeps planting trees. The building at the top left and to the right are lumberjacks.They cut down trees. Those trees then get transported to the building to the top right, the sawmill where they get cut up.

The other big challenge, and actually the reason why I’m blogging about this, is the way system. All the production facilities mentioned above are connected by a road system. Each of those buildings has a flag in front it and whenever a building “finishes” producing an item, the item gets dropped at the flag (I won’t go into the hygienically implications of dropping food on flag on a dusty road… ). Connected to the flag is a road that leads to another flag and standing on that road is a carrier, a poor guy who’s job it is to just carry stuff from the one flag to the other flag. See Picture 2 to get a better understanding. So eventually this road leads to another building that actually needs what has been produced. In the picture below that would be the small pig on the flag to the right that needs to get to the slaughterhouse to the left (Hey, it’s biological after all!).

Picture 2: Flags, roads and items. Notice the pig on the flag on the right.

So getting the way system right is crucial to your success in that game. If your roads are too long, it will take forever to complete things. If you don’t set enough flags, the actual capacity of a given road segment will drop - after all there is only one guy standing between two flags and he can carry only one item at once (an exception are the donkeys that you get after a road has been in heavy use but that still only gives you two items per segment).

Now, you have an understanding of what that game is about. If you don’t, get yourself a copy and play it a bit. But be careful, it’s addictive.

So while I was playing a bit I started to wonder, how all this worked. How do wares get routed from one flag to another flag. How to flags eventually reach their destination? How is ensured that wares don’t run in circles? How is ensured that best possible route is taken? All those thoughts kind of reminded me of my excellent algorithms and data structures lessons at the Hochschule München, where graphs and different algorithms on graphs where a big subject. So I got really curious how to implement something like that. After all, at university we implemented a lot of the data structures and algorithms but never for a “real” problem.

Later that night I started up Eclipse and churned out some code to actually represent a hexgonal map (Settlers 2 uses a hexagonal grid as opposed to most modern games that just use isometric rectangular maps), render out that map to the screen and some classes to represent flags and roads. And then the fun started…

My first goal was to implement a pathfinding algorithm that actually finds a good route from one given hexagon to another hexagon. Sounds easy but is a really hard problem. There are a couple of algorithms out there that actually solve that problem but I decided to go with the simplest one, Dijsktras algorithm that is guaranteed to produce the best solution. However implementing that algorithm wasn’t as easy as I anticipated. My first test run produced some rather… unexpected results:

Picture 3: Pathfinding done wrong. The goal was to find the shortest possible route from the one green flag to the other green flag… The gray zig-zag line is the path my implementation found…

Obviously that was not the best possible solution! Eventually it took me a couple of hours to get my implementation right. But then I got it right:

Picture 4: Pathfinding done right! Made the paths red in that screenshot for better visibility. Note how the red paths connecting the green flags are the shortest possible.

My conclusion after a couple of hours trying to get that right: It was a lot of fun and kudos to the developers of Settlers 2! I did not spend too much time on that but it became quickly obvious that building a game as “simple” as this old DOS game is all but easy. Building even simple pathfinding imposed quite a challenge on me. Building a whole game like that seems one hell of a task…

The next step is now to build a pathfinder that is actually aware of terrain (you can’t build roads on water!) and won’t allow to cross roads. With that in place i can finally start to play around with the actual routing of goods in this graph. The technical more adept might argue that I actually don’t need all the stuff that I wrote so far to calculate some spanning trees on a graph. And they’re right. But otherwise it wouldn’t be as much fun!

Depending on how much spare time I have I’ll keep playing around with this and keep you posted…

This post originally appeared on my personal blog: http://www.jakusys.de/blog/2009/03/settlers-2-pathfinding-and-writing-code-for-fun/