I started programming on 8-bit machines. Back then it was normal to do amazing things with a mere 64 kilobytes of memory on a CPU that clocked in at 2.6 Megahertz. No, those aren’t typos, and I meant “mega-” not “giga-”. In those days we were forced to do a lot with a little, and “optimizing code” meant choosing op codes based on how many cycles they took to execute.
It is amazing to me to look back and see what we were able to accomplish. Software exists to perform everything from advanced compression to generating a fractal Mandelbrot set. In addition to programming I spent plenty of time playing adventure games. One of my favorite games I referenced in a recent talk. It rendered a 3D landscape for a first-person view. The sky would change color from day to night and it could even rain in this Alternate Reality.
To create fun and playable games, developers often had to resort to creative coding techniques such as using algorithms to generate the game world. Disk access was notoriously slow (how many of you remember playing the Ultima series and spending most of your time waiting to load the next city or dungeon?) so generating terrain or worlds “on the fly” made for better game play.
I remember an old arcade game called Berserker and was reminded of the game when I watched a documentary called Chasing Ghosts. It followed video game “champions” (or perhaps addicts) from 1982 to present. In it, they reviewed the game and talked briefly about how it generated its famous mazes. There is a great write-up at the Robotron site about the algorithm.
To create a “room” the game essentially assumed entrances on all four walls with eight “pillars” in the middle. Each pillar was assigned a random number, and the number determined if a wall would extend from the pillar in the north, south, east, or west position. The concept is so simple, I decided to implement it in Excel. To generate new mazes or see the underlying formulas, simply choose the Data option and select “Calculate Workbook” or edit any cell if you open it locally.
Once that was done, it was fairly straightforward to move the concept to AngularJS. The bulk of the solution is more related to the algorithm and Angular is more the means to display it. I decided to use pure CSS to draw the maze, rather than SVG or some other technology, so really all that I need are a pillar and a wall:
.pillar {
width: 15px;
height: 5px;
margin: 0;
background: red;
}
.wall {
width: 15px;
height: 5px;
margin: 0;
background: green;
}
In the game mazes are exhaustive and interconnect “rooms.” For this example I decided to create two “rooms” so there is a single maze with an entrance and exit (always rendered on the top middle and lower right). The maze is 26 x 16 with 16 columns, represented as an array of rows that each contain an array of columns. Generating the basic maze is as simple as:
for (row = 0; row < 25; row += 1) {
cells = [];
maze.push(cells);
for (col = 0; col < 16; col += 1) {
border = row === 0 || row === 24 ||
row === 12 || col === 0 ||
col === 15;
cells.push(border ? 1 : 0);
}
}
The convention is a “0” for empty space, a “1” for a wall and a “2” for a pillar. Using the CSS and Angular, this is easily rendered with the following HTML:
<table>
<tr ng-repeat="row in ctrl.maze track by $index">
<td ng-repeat="col in row track by $index"
ng-class="{ 'wall' : col === 1, 'pillar' : col === 2 }">
</td>
</tr>
</table>
I then “knock out” the doors (defined as an array of row/col coordinates):
angular.forEach(doors, function (door) {
maze[door[0]][door[1]] = 0;
});
After that, it’s a simple question of iterating through the pillars to build the walls. Initially I wasn’t concerned about each pillar having a unique wall (i.e. they can overlap) just to keep the code simple. I store an array of values for each “direction” that indicates how to draw a wall relative to a pillar. For example, “up” means the previous three rows of the same column for the pillar:
up:
[{
row: -1,
col: 0
}, {
row: -2,
col: 0
}, {
row: -3,
col: 0
}]
For each pillar, I draw the pillar on the map, then generate a random number. Based on the random number, I return a direction:
function getDirection(seed) {
if (seed < 0.25) return dirs.left;
if (seed < 0.5) return dirs.up;
if (seed < 0.75) return dirs.right;
return dirs.down;
}
From the direction, I can then build the wall. The initial code for the “pillar” loop looked like this:
angular.forEach(pillarCoords.row,
function (pillarRow) {
angular.forEach(pillarCoords.col,
function (pillarCol) {
var dir, rand = Math.random();
maze[pillarRow][pillarCol] = 2;
dir = getDirection(rand);
angular.forEach(dir,
function (offset) {
maze[pillarRow + offset.row]
[pillarCol + offset.col] = 1;
});
});
});
I then enhanced the algorithm beyond the Excel implementation to ensure each pillar gets a unique wall that doesn’t overlap with another pillar’s wall. This is done in a simple loop that checks to see if a wall already exists in that direction, then asks for a new direction. The way it is implemented, there is a low probability a pillar could end up without a wall due to the random generator (in the rare case it always returns the same direction).
That’s it. The majority of the implementation is done in pure JavaScript (my preference), so Angular just seeds the maze with a call to the generator, and binds a click event to generate a new maze. The controller code looks like this:
function MazeController() { } angular.extend(MazeController.prototype, {
maze: mazeGenerator(),
newMaze: function () {
this.maze = mazeGenerator();
}
});
app.controller('mazeCtrl', MazeController);
You can view all of the source and see the working fiddle here.
I love this approach. A simple algorithm can generate a practically limitless configuration of mazes that are all solvable. In the 8-bit days we were forced to find simple, elegant solutions to complex problems and I see that trend happening all over again with the popularity of mobile platforms. After all, this maze will run without hesitation right on your phone!
