This is a very simple implementation of a maze generation algorithm in JavaScript. It is written for a friend of mine who is writing a game for an old Amstrad. He was looking for a simple maze generator that he could translate into Amstrad-compatible C-code. Because of this, it has to be reasonably conservative with memory, and not use too much recursion.
I recalled finding an old maze generation algorithm in a PC user group magazine many years ago, written in BASIC. At the time, I was fascinated with it and translated it into Java code. When my friend brought up his maze-generation algorithm, I decided to see if I could remember how it went, and write it in JavaScript.
The maze is drawn on a grid of boxes. Each box can be empty or filled. Filled boxes represent walls, while empty boxes represent the maze. There is only one possible path through the maze. That is, there are never any loops.
Usually, I would refactor my code a lot more than you see here. I would remove all my loops, and replace them with map/filter/reduce etc. And I would strive to minimise the use of mutable data and global variables. But, since this is going to be translated into Amstrad-C anyway, I thought I would leave it as is.
## Maze Generator
We'll start by setting the size of the maze. Normally, I would make these parameters to a function, but for now we'll just declare them as constants.
const W = 60;
const H = 22;
Next we need to create a board. It's just a two-dimensional array. I've configured it so that you access it with the x-coordinate first. This makes it slightly easier to read, but as we'll see later, makes generating output less effient. The board is filled-in with `false` values. A false value represents a wall or filled-in grid box.
let board = [];
for (let i=0; i<W; i++) {
board[i] = [];
for (let j=0; j<H; j++) {
board[i][j] = false;
}
}
Next, we'll define directions like North, South, East and West. These are represented as plain ol' JS objects. Each one has an x property and a y property.
const NORTH = {x: 0, y: 1};
const SOUTH = {x: 0, y: -1};
const EAST = {x: 1, y: 0};
const WEST = {x: -1, y: 0};
const directions = [NORTH, SOUTH, EAST, WEST];
Now we have a definition of North, South, East and West. With that in place, we can create a function that will take a point, and will give us a new point, one step in a given direction. For example, given a point `p` and `NORTH`, it would give us the point one step to the north of `p`.
function pointAdd(a, b) {
return {x: (a.x + b.x), y: (a.y + b.y)};
}
This allows us to move around the board. Given a point object, we can move one step in any direction by adding one of the direction constants.
We'll also define a function for giving us the value of the board for a given point. That way we can tell if a given point is a wall or a space.
function getBoardPoint(board, point) {
return board[point.x][point.y];
}
The algorithm works by starting with a given empty space. From there it tests one of the four directions at random to see if it would be a valid space. A space is valid if:
1. It's on the board;
2. It isn't already a space; and
3. It wouldn't cause a loop. That is, it's not next to another space.
Tests 1 and 2 are fairly easy to check. The third check we can do by looking at each point *around* the point we're considering. For a *new* point, it should only have a single space adjacent to it. All the others should be walls. So, we can write a function to test a new potential maze space like so:
function boolToInt(val) {
return (val) ? 1 : 0;
}
function add(a, b) {
return a + b;
}
function countBranches(board, point) {
return directions
.map(d => pointAdd(d, point))
.map(p => getBoardPoint(board, p))
.map(boolToInt)
.reduce(add);
}
function isValidPath(board, point) {
const {x, y} = point;
return (x > 0) && (y > 0) && (x < W-1) && (y < H-1)
&& (board[x][y] === false)
&& (countBranches(board, point) <= 1);
}
When we're picking points to test, we pick a direction at random. But we only need to test each direction once. In other words, we test each direction in a random order. To help make this easier, we will write a function that will take a copy of the Directions array and shuffle it.
function shuffle (a) {
let j = 0,
temp = null,
array = a.slice(0); // a.slice(0) takes a copy of the array.
for (let i = array.length - 1; i > 0; i -= 1) {
j = Math.floor(Math.random() * (i + 1))
temp = array[i]
array[i] = array[j]
array[j] = temp
}
return array;
}
With all those helper functions in place, we're now ready to start our main algorithm. First, we set up a starting point and a working array called `branchPoints`.
const START = {x: 0, y: 1};
let branchPoints = [START];
board[START.x][START.y] = true;
Whenever we add a new space to the maze, we add its coordinates to the `branchPoints` array. Then, we expand the maze by picking one of the branch points at random to see if we can branch off it. If there are no valid branch directions from a branch point, then we remove it from the `branchPoints` array. We keep doing this until there are no points left in `branchPoints` at that point, we have tested every square on the board and our maze is complete.
let pointToTest = null;
let directionsToTest;
let direction;
let newBranchPoint;
let newPointFound = false;
while (branchPoints.length > 0) {
i = Math.floor(Math.random() * Math.floor(branchPoints.length - 1));
pointToTest = branchPoints[i];
directionsToTest = shuffle(directions);
newPointFound = false;
while (!newPointFound && directionsToTest.length > 0) {
direction = directionsToTest.shift();
newBranchPoint = pointAdd(pointToTest, direction);
if (isValidPath(board, newBranchPoint)) {
branchPoints.push(newBranchPoint);
board[newBranchPoint.x][newBranchPoint.y] = true;
newPointFound = true;
}
}
if (!newPointFound) {
// Delete item from branchPoints array
branchPoints.splice(i, 1);
}
}
We added an entry point at the start, but right now our maze doesn't have an exit. We add one by starting at the bottom-of the right-hand wall. We work our way up, looking for a square that has a space to the west.
function addExit(board) {
var j = H - 1;
while ((board[W - 2][j] === false) && j >= 0) {
j -= 1;
}
if (j >= 0) {
board[W -1][j] = true;
}
return board;
}
board = addExit(board);
We now have a maze. But an array of booleans isn't easy to look at. So, we want to create a function to print it. To make that easier, we'll first transpose the board.
function transposeBoard(board) {
let newBoard = [];
for (let j=0; j<H; j++) {
newBoard[j] = [];
}
for (let i=0; i<W; i++) {
for(let j=0; j<H; j++) {
newBoard[j][i] = board[i][j];
}
}
return newBoard;
}
const transposedBoard = transposeBoard(board);
With that in place, it's easy to create a text-based rendering:
function boolToMazeChar(b) {
return (b) ? '░' : '▓';
}
function boardToString(board) {
return board.map(col => col.map(boolToMazeChar).join('')).join("\n");
}
console.log(boardToString(transposedBoard));
no comments
sign in to comment