Generating Mazes

I’ve been doing some thinking about the battlefields recently, for a couple of reasons. First players are going to be doing a lot of fighting, and it’s going to get old pretty quickly if you’re always facing off in a big empty arena. And second, I’m setting up the scripting so that hopefully events will be able to occur in randomly generated battlefields and still make sense. So suppose that you have a story event where you get ambushed, the mission scripting will have to be able to specify a ‘ambush position’ for the enemy ships without having any control over the layout of the battlefield. So if I can generate an interesting battlefield with built in ambush positions, etc. then the scripted missions will be able to work with whatever type of battlefield they are given.

So, to that end I did a lot of thinking, what sort of structure does a good battlefield have? My first thought was to do something like what Spelunky does with their randomly generated levels. It’s some pretty clever stuff, but it didn’t take long to realize that the layout that makes a good platformer level is very different from what makes a good strategy battlefield.

So my next thought was to take a look at levels in strategy games. I took a look at multiplayer maps for Command & Conquer and Warhammer: Dawn of War. But again they serve different purposes. In multiplayer strategy games a lot of the game is capturing and holding resources, which requires several resource locations that are interesting to capture and hold. But my game doesn’t play like that, you don’t have any resources on the battlefield, you enter the battlefield with all of the units and resources you will ever have.

Finally, I realized that the best comparison would be the single player maps for games like Warhammer: Dawn of War II, especially the maps from Retribution. And those maps are essentially mazes. Which really works well, all of the battlefields in the game take place at jump nodes, where ships jump in, move a relatively short distance, then jump to the next point. One or more entrances, one or more exits, sounds like a classic maze to me.

Which is a really long winded way of saying that I started looking into map generating algorithms for generating the battlefields. And I found this lovely page that describes a multitude of algorithms, along with their strengths and weaknesses. I know you’re dying to know what algorithm finally ended up choosing, and it was Wilson’s algorithm. Chosen primarily because it generates all possible maps with equal probability. Which is really a pretty interesting property if you think about it.

So, after an implementation frenzy, I told it to generate asteroids, and got the following results:  Asteroid fields with sharply defined corners, very natural looking. After a bit of tweaking to round out the corners I started getting results like the following:

It’s a bit better, especially when you’re not viewing it from a distance. Up close it looks quite a bit better, and more confusing too, which is good, I think. From there it was a short jump to have it vary the size and density of the rocks, as well as the occasional field of deadly space gas, and it looks like this:Honestly, it still looks kind of funny, again up close it looks better, but still not quite where I want it. Still, it’s been fun, and it’s looking promising, and it’s pretty fun to fly ships through. Next up is to have the maze generator add multiple paths through the maze, which should make it more like a field of random debris and less like a contrived obstacle for you to bypass. And some efforts to get it to look a bit more natural.