Introduction

We’re working on an old-school sort of game for Mad Ogre Games. Without going into too much detail, imagine fantasy characters racing in a path across a hexagonal board, with players vying to both be the first one to get to the ending and collect as much treasure as possible. They would run across a landscape of fallen towers, forests and rivers, possibly taking branching paths to collect extras.

To keep it fresh, we want to have many different boards available. Since we don’t want to go about having to hand craft an extremely large number of boards, it would be optimal to have them randomly generated for each game, so I sat down and came up with some simple rules for board generation.

• The board must not be more than 40% filled with road tiles, since we want scenery and decorations.
• There must be a connecting road from beginning to end.
• We must have branching paths that connect to the main road.

Reviewing these, some other things came apparent as well. For instance it would be better if the scenery wasn’t all lumped in one side of the board, but distributed among the roads. This make me come up with some additional rules:

• For each 5×5 block of tiles, at least 3 should be decorations.
• There can’t be two road tiles side by side.

Getting fancy

Now this got me thinking… could the board be generated using a process similar to cellular automata? Cellular automata are a grid of cells, each one with a possible state, and they change states depending on both its own state and that of those around it. If this sounds way too abstract, you may want to see a few animations for Conway’s Game of Life. I’ve always been infatuated with them, and they do seem like they would lend themselves well for systems where you want to achieve a certain balance (even if not necessarily a static one), so it was worth a shot.

The thinking was that this map generation could be done in stages, the first of which is a cellular automata (CA) that has two states: either it’s a road, or it’s scenery. So what I would do would be:

1. Completely randomize board state.
2. Apply a few CA rules to transform the board into an acceptable distribution of roads and scenery, until the map stabilizes (by my standards, that meant reaching a map with the acceptable distribution and a valid road).
3. For those road tiles that lead from the beginning to the end, pick a series of twists and turns to create the main path.
4. For the rest of the road tiles, make them into random twists and turns.

Yes, point #3 hides a very likely pathfinding requirement, but the thinking was that since there can’t be parallel roads, we won’t get a cluster of road tiles, so the path would be relatively easy to trace.

And how did that work out, Mr. fancy pants?

It worked beautifully, Tubbs!

Well, it kind of did, actually. After some tweaking of the rules, I had a working version where you could see a lot of hex tile flipping going on for a while, until an abstract version of the a board matching our requirements stabilized. Huge success! Off to write a great academic article on cellular automata and board games!

Well, hold on for a moment, Wolfram Jr. It kind of worked, but had several drawbacks:

• Too slow. Yes, I did end up with a randomized map that fit all my nice tile distribution rules, but at the price of speed. It sometimes stabilized in only a few seconds, but all too often it too it hundreds of generations to come up with a working map, and the larger the map, the longer this would take.
• That whole assumption that the main path would be fairly obvious? Yeah, nice try. In order to validate a working path with twists and turns, an actual pathfinding algorithm had to be applied to the road tiles. Yes, we would end up needing a pathfinding algorithm in the end for the computer-controlled players, but it’s not something I should be needing at this stage.

Keeping it simple

Drunk

By now some of you are probably shaking your heads, wondering at the overly complicated approach. So was I, I confess – but not before I came up with an even more complicated approach: I’d generate many boards, evaluate them for fitness, then do crossover and mutation between them on top of the CA rules, to come up with optimal boards… and then after a few generations…

And then I got a reality check, considering I’m not doing this for academic credits, and decided to take the complete opposite direction. Simplicity itself: a drunkard’s walk. The plan would be:

1. Do a drunkard’s walk from the beginning tile to the end tile. Define that as the main path.
2. Pick a random spot, do a drunkard’s walk to another point of the road. This would define an alternate road.
3. Repeat the last step until we have the desired road fill rate.

I wasn’t even checking for parallel roads, which could in theory emerge – I planned to clean that up in a second step. You can see the results of a sample run on this movie, where a debug line will connect the two tiles that the walk is moving between. That worked, but I didn’t particularly like the paths that it generated, and it would end up requiring a lot of post-processing to make them useful.

Two drunks, looking for each other

So I decided to try not one, but two drunkard’s walks – one of them going from start to finish, the other one from finish to start. If at any point they run into each other, a path has been formed. Tadá! That did work better and faster, but I still didn’t like the paths – as you can see it doubles back on itself all too often, and creates knots of connections that would later need to be cleaned up.

Building up

But it’s better. It seemed that by limiting the direction towards which the drunks can walk, they would be a lot more likely to find each other – therefore I forced the first one to walk only towards the right and up, and the second one only to down and to the left (insert obscure JFK joke here). Not only did that work faster, but it also allowed me to add some tentative alternate roads, each going off in a random direction subset.

We’re getting somewhere. On that video, the tile types being set represent the direction subset, not actual tile connections – those are shown by the debug lines.

And finally…

Skip forward a few code generations, and the final approach ends up being a hybrid, but leaning more towards the basic side of things. I did add some rules, particularly pertaining towards making only turns that would create valid connections as defined by the tiles we had – that alone created the effect of large empty spaces and avoiding grid roads, since it could be almost impossible for such a tile combination to show up.

You can see a sample road in this movie. After the first road is generated, a couple side roads are added as well. Much better, isn’t it?

Lessons re-learned

Keep it simple. It’s a lesson one sometimes needs to learn again. The final path generation is much better than the CA-based one, even if the algorithm is much dumber – a reminder that we shouldn’t consider that worse is better only when working on large systems. Why go all fancy, when a simple approach will do?