Blog 443: Procedural Generation Y4 (Take 2)

I have always been interested in procedural generation of game content, but had always been too scared of the maths to ever try it.

Then, with the dawn of Project Y4 (and the desire to shoehorn every trick in the damn book into a single Warcraft map), I finally indulged my desire to produce pseudo-random content and started work on a procedural maze mini-game.

After finishing that (or at least, the terrain production part of it), I maintained my interest in some of the procedural generation resources I had come across and looked a little further…

Cellular Automata Caves

Mazes are great for man-made structures (duh), but what about natural formations? Yes, you can make a maze and then use prefabs to make it look like a cave system, but ultimately it’ll still be very straight-edged and unnatural (oh Saboteur… wait, they’re man m– never mind).

Then I stumbled across the “cellular automata” algorithm for generating natural-looking cave systems.

The algorithm is pretty much thus:

1. Make every tile either a floor or wall (choosing by a given, constant probability)
2. Iterate over all tiles:
   1. If the tile has 3 or more neighbouring walls, close it.
   2. Or, if the tile has 3 or more neighbouring floors, open it.
   3. Otherwise do nothing.

The second step should be run a few times to smooth things out a bit. Out of nothing but noise, the beautifully simple algorithm causes pretty caves form.

I whipped it up in C# for shits and giggles and the results are really rather nice for not a lot of effort.

The Final Frontier

While Project Y4 does have some caves, I’m not convinced that I want to procedurally generate them — I need them for offence missions, with pre-set enemy patrol routes and events and secrets and items and things. Too many factors to play with, too many things I’d rather not think about trying to procedurally generate — generating the node hacking game components gives me enough headaches as it is.

But I got to thinking: I have this huge blank, alpha-tile plap up in the corner for the node hacking, computer screen and keypad sub-systems… Maybe, just maybe, there’s something else I can do in there…

Do you remember Asteroid Wars?

You probably shouldn’t, because I never finished it (let alone released it). But it did produce a few screenshots that I enjoy harking back to now and again.

Fun fact: Asteroid Wars is where the blast shields first entered the RDZ Industries style vocabulary, as those plates on the TIE Fighter rip-off got folded into the ground units.

• Original promotional screenshots: 1, 2, 3, 4, 5, 6, 7, 8

There wasn’t much to it, and it never had prospects of developing into much more (hence it sinking without trace), but it had quite enough material to harvest into a bonus mini-mission.

Besides, I’ve always wanted to do my own take on the Battleships-style AoS — the desire for Asteroid Wars has surfaced at least once more than all the other conversion attempt archetypes, from scratch-builds to a brief try to overlay RDZ Industries on Sked’s final open source version of Battleships. Hopefully with a miniaturised feature set, I can quickly and confidently add it to the ever-growing Project Y4 pile.

And let’s face it, I need something other than the introduction cinematic to show off that dramatic skybox.

No Man Is an Island

The one disadvantage of the cellular automata algorithm is that, while it can generate lots of nice caves, it can’t guarantee that you can get between those caves (as in the first image above). It would be a bit nasty if you were placed in one room with the exit in another and no way to reach it.

I did find a tutorial that had some frightful mathemagical additions to connect unconnected rooms in a decent way (and not just draw a straight line between some points and hope for the best), but it required scary maths and graph madness I couldn’t even begin to implement in C#, let alone consider implementing in Warcraft‘s crippleware scripting language.

Luckily, the premise of Asteroid Wars made this problem go away very easily. There are two teams, two known base locations at opposite corners of the map, and the need for a guaranteed path between them. Easy peasy — just take the intial randomised grid, then draw a path of open tiles between the two bases. These open tiles will then spread out (or not) during the cellular automata passes, producing a path with nice natural edges.

But a line is boring, so I decided to do two bezier curves into the corners of the rectangular plap of tile-space, giving the map two neat loops to battle down. As long as the two bases are connected, the rest of the map doesn’t matter; luckily, with the parameters I’m using, side chambers do end up connected most of the time.

Asteroid Wars Y4

This will need a reasonable amount of new artwork (what with it being in space and everything else being on the ground), but hopefully not too much — I’ve got previous spacecraft and space props that can be reconditioned, and the only animation work necessary is the addition of funky particle contrails and explosions.

This is only a small diversion, so I don’t think it’ll actually take that long to make and finish. It’s just a bonus mission, remember — I don’t need it to last particularly long or have a billion options, though obviously I will do my best to keep it busy busy busy and balls-to-the-wall action.

And you can have infinite respawns for this one, since the defeat condition is going to be your mine base getting blown to kingdom come by pirates.