From an idea to a working game in 7 days — part 1

As a Launch School student, you build lots of smaller projects that test your knowledge of certain course topics. They’re helpful and often motivating enough, but they don’t spark the joy of a real side project: one that you’re excited and almost too enthusiastic about. So, during my Christmas vacation I found myself having a few quiet days ahead —a great time for such a side project!

My initial inspiration came from the Advent of Code competition, an annual event that gives 24 coding puzzles which test your problem solving skills and algorithmic thinking. I enjoyed two puzzles in particular: one dealing with Cellular Automata and one simulating turn-based battles between elfs and goblins in a cave (yeah, there’s usually some nonsensical background story to the puzzles).

Cellular Automata: a simple yet clever algorithm

I read up on Cellular Automata after solving that particular Advent of Code puzzle. One of the most popular variants of a Cellular Automaton is Conway’s Game of Life. It simulates a grid with living cells that evolve according to a set of rules.

After reading the Wikipedia page, I built my own implementation in Ruby and it was easier than expected, because there’s actually not much complexity to it. You can see my Game of Life in action:

A few generations of evolution in Conway’s Game of Life

So what exactly is a Cellular Automaton? In general, it describes the transformation of a two-dimensional structure by a set of rules. Sounds too abstract? Let’s have a look at what Game of Life entails.

We start with an empty grid. Ideally, it would be infinitely large, but we can limit it by defining a simple two-dimensional array of cells, like so:

rows, cols = x, y 
Array.new(rows) { Array.new(cols) }

Then, we need an initial configuration. That is, we randomly assign each of the cells in that grid one of two states, like dead or alive in the Game of Life. In the following sketch, the light grey cells are alive, while the dark cells dead.

The initial configuration of a 4 x 4 grid. Light cells are alive, dark cells are dead.

At the core of a Cellular Automaton sit the transformation rules that determine the fate of each cell in the grid for the next evolutionary step. Those rules look at the neighbors of each cells.

The neighbors (in red) of a single cell in our grid (in grey).

Each cell has exactly eight neighbors. The number of neighbors can be determined with an adjacency matrix:

adjacent = [
  [-1,-1], [0, -1], [1, -1],
  [-1, 0],          [1, 0],
  [-1, 1], [0, 1],  [1, 1]
]

Looking at those relative positions of each cell, we can simply count the number of living cells. Afterwards, we apply four simple rules to see whether a cell lives or dies in the following generation. Those rules are:

1. a living cell with less than two neighbors dies in the next generation. This is called starvation.
2. a living cell keeps existing in the next generation when it has exactly two or three neighbors.
3. a living cell dies in the next generation if it has more than three neighbors. This is called overpopulation.
4. if a dead cell has exactly three neighbors, it gets born anew in the following generation.

In this configuration, for example, all living cells (colored in grey) would live in the following generation, because each of them has exactly two or three neighbors. This configuration would result in a stable cell organism that does not change over the course of the simulation, except when another organism comes too close and disturbs the equilibrium.

In this setup, however, the hatched living cells would die of overpopulation in the following generation, because they have more than three neighbors.

And that’s it, translating those four rules into code is all there is to the implementation of Conway’s Game of Life.

From “Game of Life” to generating dungeons

I would’ve left it at that if it wasn’t for the other Advent of Code puzzle a few days later. The puzzle itself dealt with the simulation of a bunch of goblins and elfs, but it featured a complex environment that was uniquely generated for each Advent of Code participant. It reminded me of a certain type of video game that I enjoyed: so-called Rogue-likes.

One of the grand-daddies of the genre: NetHack (originally released in 1987)

Rogue-likes are named after their oldest ancestor: a game called Rogue. In it, you control a hero character, usually represented with the @ symbol in-game, and you explore dungeons and caves, slaying monsters and finding treasures on the way. All Rogue-like games share one important core principle (besides being fiendishly hard): large portions of the game are procedurally generated, meaning, for example, that each level map would be randomly created by an algorithm. The end result is usually displayed with simple ASCII characters. These aesthetics reminded me of the Game of Life implementation and I started to wonder: with a few modifications to my Game of Life algorithm, can I generate random dungeons and caves, too? And if so, could I code a small Rogue-like game myself?

The initial result I was aiming for: a grid with two kinds of cells: walkable floor cells (marked with the dot), and impassable walls (marked with the hash symbol).

I wanted to verify my assumption before making any big plans, so I modified my Game of Life algorithm. I removed the rule for overpopulation, because I wanted to get massive structures with walls instead of tiny floating cell organisms. I then created a set of parameters based on the remaining rules that I could tweak and see if the result would be something close to what I had imagined:

WALL_CHANCE = 0.25 # chance for an initial wall
ITERATIONS = 7     # no. of generations to simulate
WALL_EVOLUTION = 5 # minimum neighbor walls to grow a new one
WALL_STARVE = 2    # minimum neighbor walls to not vanish

There was a sweet spot for most of those parameters and it didn’t take much tweaking to get astonishing results:

Results from different runs of the algorithm with the same set of parameters

Those looked indeed like cave maps! And the variety of generated maps was amazing. I was happy, and my side project idea took shape.

I later found out, that Cellular Automata are used in game development for very similar purposes (although often in a more refined and clever way). Plus, they are used for the simulation of the natural behavior in certain biological or chemical models, so they are pretty versatile.

Well, now I had a cool map, but not much more. How could I turn this into a complete game experience?

Continue with part 2 or look at the project’s GitHub repository (my cave-generating algorithm can be found in the lib/cavegen.rb file). Just follow the instructions in the Readme to install and play it.