We’ve been through the cellular automata algorithm before. I said some things back then that were mostly theory — things I’ve now been able to test in the wild.

So how does one take a grid of noise and turn it into a functional RPG? Well, lucky for you, I’m getting close…

Automata-ic Lover

Let’s recap: the cellular automata algorithm is a cheap and cheerful way to computer-generate natural-seeming spaces. You take a grid where every tile is randomly a wall or a space, then walk across every tile and turn it from a space into a wall or a wall into a space depending on how many walls or spaces surround it. Basically, peer pressure.

Caveats with the algorithm: you have no guarantee of connectedness between areas. Cellular automata can produce one big open area or multiple islands and you’ve got no way to know which is which without doing insane pathfinding magic.

Whew. Caught up now?

Completist Tendancies

Why does connectedness matter? Because if I place an objective somewhere, and a player in another, and those two open spaces don’t actually connect, then I cannot win the level. That would be a pretty shitty level.

I’ve waved my hand in the general direction of a solution before. Consider what I said earlier: the initial tiles of noise turn into walls or spaces based on their neighbours. That means we can bias the output of the algorithm by deliberately printing structures rather than noise. Note that I say bias here: there is no such thing as absolute control, but we don’t really want that — we want the variety of randomness, with enough control that we can guarantee certain properties.

My first cellular implementation was an AoS-style scenario, with two known base locations and two known lanes. These never changed position, only the terrain changed around them. I created these by carving clear spaces out of the noise grid — because the clear spaces were surrounded by clear spaces, they stayed clear spaces and just rumpled up around the edges a little. Perfect.

Reach and Flexibility

That was a very constrained experience. Now I want to bring that out to hosting a fully-fledged RPG, with objectives scattered around a large world platter.

At this stage, I basically ignore the noise grid. I know it exists, and I know it’ll make fairly pretty, well-rounded terrain at the end of the day. I also know that it’s an unreliable bedfellow, and so I must lay my level out in some known way regardless of how the algorithmic dice will fall.

First I introduce the concept of a hotspot. A hotspot is a clear space where Something Happens. It might be the home of a quest giver or it might be the target of his affections, or just a shop or some other unremarkable point of interest. Either way, these points we will deliberately clear.

If You Can’t Stand the Hotspot, Get Out of the Kitchen

The problem with hotspots comes in how to distribute them. If we take one for a quest giver and one for a quest objective, we naturally can’t have the two hotspots overlapping. Indeed, we want to distribute all of our hotspots almost regularly, so that we make maximum use of the map area. Throw in a variable number of hotspots and that isn’t as easy as it sounds.

I started off with a circular solution. From the centre of the map, place a hotspot at a random radius; then move around within a slide and place another hotspot at a different radius. It sounded like a good idea at the time but the spots always seemed to cluster, most likely because it could never place a hotspot in one of the four corners of the map area.

The more promising approach is to round up the number of hotspots to a square, and distribute them at perfect intervals to form a grid. Then, based on the radius of each hotspot and the distance between each in the grid, apply a random offset. This gives us just what we need: hotspots that proportionally use up the right amount of map area, but are positioned unpredictably nonetheless.

It also gives us too many hotspots, but that’s a good thing. If we randomly choose a subset of those hotspots, then we should get a good spread of clearings using a good amount of the map, if not all of it.

That’s pretty much what I’ve done. Once the hotspots are distributed, the generator decides what quests are going to be added to the level. Each quest then “claims” a number of hotspots on which to position its components. Eat up enough hotspots and you should have a scenario.

Making a Connection

Then, of course, comes connecting the hotspots. I haven’t really thought this through yet, so at the moment, I draw clear paths between them in sequence — not in sequence of generation, though, but in sequence of being claimed. This leads to lots of paths curving across half the world, but I’m kind of okay with this in the short term.

In the long term… I don’t know. It almost feels like a candidate for running a growing tree maze, but that wouldn’t allow “diagonal” connections across the hotspot grid and might even expose that underlying grid a little too much for comfort.

That’ll be another story for another day, at any rate.