Blog 638: Continuing to Make Sense of Cellular Automata

When it comes to modding, I have to admit to a masochistic streak. I could use the 3rd party pre-processor to get structs and pseudo-object-orientated syntax that would make this a whole heap easier, but no, I’ve got to use the bare metal to feel alive.

So, that procedurally generated Warcraft III side project I’ve been fiddling with during lunch hour is a whole barrel of laughs. This episode’s consternation surrounds creature spawning.

The Issue of Animals

My animal spawning system was always going to end in tears. I started by using the worst brute-force method possible:

For every tile in the world
    If that tile is open AND a random number is above a threshold
        Create an animal on that tile

Yeah, bite me. This had the advantage of creating animals fairly evenly across the entire world, with the downside that they couldn’t be conveniently “respawned” — cleaning out the map would empty it forever. That’s fine for a linear dungeon crawl, but this is an open landscape that is going to require some exploration, and exploration inevitably brings backtracking. Respawning animals are an absolute necessity to ensure the odd retread is not devoid of interest.

The player now starts in a town, which contains some (if not all) of the quest givers. Creatures will (should) avoid the town.

The player now starts in a town, which contains some (if not all) of the quest givers. Creatures will (should) avoid the town.

So I had to start wondering: how can I know where it’s safe to place animals during play time?

The primary issue comes back to the same old cellular chestnut — if I spawn an animal on a random open tile, there is no guarantee that it can walk from that tile to any other open tile; i.e. one containing the player.

With an even distribution of animals, you can just about get away with this. We know from previous discussions that the hero definitely is in the connected part of the world, and if we spawn over every open tile then the open connected areas will contain some of those animals. Having some spare animals that cannot be reached is an acceptable trade-off for ease of implementation in that case.

That is not acceptable for respawning animals, though. Eventually, all the animals in the world might have been spawned at points that cannot be reached, which would be no fun at all.

New gameplay mechanics means new banter items!

New gameplay mechanics means new banter items!

So I needed to hook onto some other mechanism that would guarantee that my animal spawn points are on clear, connected areas. Now, I can’t use the hotspot system I discussed last time, because hotspots are for points of interest — you don’t want creatures piling up against a lone merchant out in the wilds, for example (although it should be safe to let a few wander by now and again).

I can, however, use the paths that I draw between the hotspots. Specifically, their mid-points: as long as I can guarantee that the mid-point of a path is definitely not on top of another hotspot, then I know that it is a clear space connected to all other game-relevant spaces but reasonably distant from any one of them.

You’d think paths wouldn’t overlap hotspots, but, well, that wasn’t quite the case until a strong bout of hammering and chiselling.

Creatures created for quests are exempt from all of this -- they will hold position and will not respawn. Don't worry, you won't have to chase all 14 of those Mur'gul around the map.

Creatures created for quests are exempt from all of this — they will hold position and will not respawn. Don’t worry, you won’t have to chase all 14 of those Mur’gul around the map.

Previously, I drew paths between hotspots in the order in which they were claimed. This could lead to hotspot 1 connecting to hotspot 16 — drawing a path right across the entire map and naturally going straight through several other hotspots. I couldn’t use the mid-point of that because I had no idea whether it was safe or not.

The solution is actually to go back to drawing lines across a bitmap again. Ignoring the randomised offsets of their actual world positions, hotspots are laid out on a smaller grid (in my case 4×4) on top of the real world (which is 92×92). Instead of drawing the path between hotspot 1 and 16 as a single path, I now draw several paths that connect the intervening hotspots — the path segments are assigned by drawing a line across the hotspot grid instead of the real world grid, connecting each pixel to the previous one on the line rather than setting the state of the current pixel.

Confused? You should see my implementation. 2D grids in non-existent 1D arrays, lists in 1D arrays, indexing arrays to get indices for other arrays…

Now that creatures are spawning in reasonable amounts, it's much easier to carve through them. Maybe too easy, eurgh.

Now that creatures are spawning in reasonable amounts, it’s much easier to carve through them. Maybe too easy, eurgh.

On the plus side, though, it seems to work rather well. Because this method creates more paths, even joining unclaimed hotspots that are on routes between claimed hotspots, it means the creature spawn points are fairly well distributed — just like the hotspots themselves.

The last piece of the puzzle is simply to ensure that creatures spawn at points that are not currently within sight of the player. Naturally I have camlock engaged for this purpose at a short range, but we still kind of want to concentrate respawns quite far away from the hero — so that clearing out an area will leave it clear for a short while before the creatures start to repopulate. That repopulation can happen either by pure spawning, or by randomised migration of creatures from other areas, but you shouldn’t be in constant battle.

With that, the map is finally taking on some semblance of a viable scenario. Success!

Advertisements

And you tell me...

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s