Some of my favorite games? Toejam & Earl, Diablo II, Warcraft II, and Sim City 2000. What do they all have in common? Some semblance of random. Each game had a way of increasing playability by adding some sort of procedurally generated game map. You never played the same game twice. Awesome.

(Okay, maybe War2 didn’t have random. Did the map generator have a random button? Whatever.)

I’ve been meaning to investigate how some of these games worked their magic for awhile, but only recently really revved up the ol’ braingears to figure out how they worked. Here now I provide some links in regards to my research, and an experiment I tried. Hit the jump for more.

I started with a little bit of looking into random maze generation. Research on this is a little easier to come by — there’s even some Flash implementations out there. Emanuele Feronato and Jobe Makar both have implementations of the same basics concept:

- Create a multidimensional array to serve as a “grid” of “cells”.
- Remove a wall from one side of a cell at random. Tell it’s neighbor to remove the corresponding adjacent wall.
- Recursively move to neighboring cells and tell them to remove a wall.

That might be a bit of an oversimplification, but the jiist of it is using recursion to generate a complete maze. Jobe Makar’s implementation even goes into pathfinding algorithms.

That’s great for a tile based maze, but I kept thinking about the later levels in Diablo 2 and well… the whole game for Toejam and Earl. Those weren’t simple corridor maps, those maps had large open spaces to walk around in that seemed to be walled in (lava or outer space respectively).

A couple of google searches and I stumbled upon some interesting knowledge — fractals, and noise equations could be used to generate space! Who knew?! Exciting times.

Let’s take a simple one — perlin noise. First, we’ll create a simple small bitmapdata and generate some noise.


_bmd = new BitmapData(30,30,false,0);
_bmd.perlinNoise(_bmd.width,_bmd.height,_2,MathUtils.getRandom(0,_perlinSeed),false,true,0,true,null);


If we displayed it, it’s output would look a lil’ something like this:

Right? Right. Now let’s take the maze concepts from above and mash ‘em together with this noise. Something like this:

- Generate a grid like the mazes I linked to. 30×30, the same dimensions of my BitmapData.
- Now we’ll loop through the BitmapData and analyze each pixel. Anything that goes beyond a certain threshold will be a “walkable” area, anything below will be a “fence”.
- Once we know what cells are walkable and what aren’t, only display the fence where walkable neighbors nonwalkable.

We get something that looks kinda like this (click on the map to generate a new one):

In this case, I actually picked a range above #666666 and below #8f8f8f… just sorta found that by experimenting.

Do you see the Toejam and Earl map in there? No? Well, whatever. I do. I’m using 10×10 tiles right now, and they’re… well, they’re just squares. They could easily be filled with Boogeymen and Phantom Ice Cream trucks.

We can compare the BitmapData pixel values to create topography too… so a dark color might mean a river, where a lighter color is a hill… make some isometric tiles and you’ve got an SC2000 map.

Pretty neat, right? I’ve got more refining to do on this myself… there’s a lot left to explore and optimize. Connecting the islands (or blobs, if you will) is where I think I’m going to go next.

In the meanwhile, here’s some more research out there for you to take a look at:

This link discusses using turbulence to create maps, but isn’t in ActionScript.

This one will definitely get you to see how SimCity might look under the hood. (isn’t the source out there anyway?)

I need to port this and see what it’s doing.

There’s more out there. Just google things like “Procedurally Generated Game Map” and such and the results will spring up.