I wanted to implement basic procedural terrain generation ever since I took the AI classes at the university, where we used Prolog and console output for the implementation of AI algorithms. Needless to say, everything looked very unimpressive and lame. Several years later, I revisited the basic AI algorithms in Flash and applied them to the concept of the classic 2d platform game. I’ve used three algorithms to generate a terrain for a side-scrolling game:
- Randomized depth-first search to generate a maze-like terrain. The algorithm is very straightforward, every cell is filled at the start and the searcher randomly digs corridors (think of a classic arcade game Dig Dug). At every cell, the digger has an equal chance to dig in any direction that hasn’t been dug before. The only parameter of this algorithm is which one of the cells at the top will be the start of the search. This cell is also the exit of the maze.
- Random walk to generate a cave-like terrain, where all cells are connected. Another very straightforward algorithm that also starts with a filled terrain. The walker always starts at the top left corner (an unnecessary constraint) and randomly digs to any direction, also visiting cells that were already visited. The walker does not have an equal chance choosing the direction to walk to. The wandering parameter controls the chance to stay at the designated direction or to wander off. Random walking with no constraints will never finish, the end condition could be the number of cells (re)visited, the cells left to visit, or the combination of both. I chose the cells left to visit, or nicely put, the percentage of the land mass, for the end condition. Depending on the size of the terrain and the percentage of the land mass, this implementation may take an unpredictable amount of time or even take forever.
- Cellular automaton to generate a cave-like terrain, where all cells may not be connected. This is probably the hardest algorithm to implement in theory but in practice I simplified it and was the easiest to do. It has two passes. In the first pass, every cell is randomly filled or not. Again, the percentage of the land mass parameter controls the chance of filling the cell. In the second pass, the neighbouring cells of every cell are checked and the cell is set according to the majority. This resembles the bilinear filtering where the point is to ease the edges and remove the isolated cells. The second pass could also be used at the end of the random walk algorithm. The implementation gives very random results, the same parameter can either yield a very believable cave or a horrible looking terrain.
After the fundamentals have been laid down, I wanted to nicely visualise them, meanwhile exploring other game development concepts. The majority of side-scrolling games are tile-based. The generated terrain would fit well into this category.
The terrain would have looked plain if only two different tiles were used for every cell. Instead, the cell is rendered according to how the neighbouring cells are laid out. Auto-tiling is a simple method to arrange neighbour sensitive tiles. I am not very good at drawing, so I’ve used a tileset from one auto-tiling tutorial. Tile number 15 is not very well designed, so the auto-tiling might look a bit off to a sharp eye. It’s the graphics, not the code.
Next, I wanted a big terrain with parallax scrolling, so I introduced a backdrop (background layer) that scrolls slower than the tilemap in the foreground. I ripped the backdrop from Metroid Fusion (the SRX sector), one of my all time favourite games.
While I was at ripping the Metroid, I also ripped Samus Aran in all her suits (default, varia, gravity, zero) and wanted to see how she looks in the generated terrain. To exercise the power of the Flash player, I’ve put various instances of animating Samus on every wide enough platform.
Next, I added some environmental effects such as rain and lightning; the graphics for these were ripped from Radiant Historia and Thor: God of Thunder, both fine Nintendo DS games. Finally, I also wanted to aurally appease me with Jochen Hippel‘s famous Future Composer tune from Rings of Medusa, a game that I used to load only to listen to this tune for hours and hours.
You can see the result below. Use cursor keys to scroll around and GUI to regenerate the terrain. The GUI is made with Minimal Comps that I wanted to put to some good use (read: learn how to use them).
[swf:/wp-content/uploads/2011/10/cave.swf 640 360]