Talking about Maze game, Game development and Javascript.
Sometimes, ideas for a new post happen by chance. I was playing Entombed on an emulator and I was wondering how could it be possible to store such a big maze on such an elementary machine.
Obviously I knew it wasn’t an actual, perfect maze, but I asked myself if there could be a way to generate a perfect maze row after row, and stumbled upon Eller and Sidewinder algorithms.
I already published some work about mazes, but I really wanted to give a try to Eller algorithm to see it in action.
I found this page explaining all the steps, which are very basic, and started coding, as I wasn’t able to find a pure JavaScript class to build Eller mazes.
So I wrote my own maze class, which actually is not a maze class but a row class, since it’s able to build a perfect maze row by row.
Look at the example:
You can add a row with “Add a row” button which simply adds a new row to the maze, and when your maze is big enough, close it with “Close the maze” button.
How can a maze be generated row by row? By using sets, and building a new row starting from the previous one, in these simple steps:
1 – For first maze row, give each cell a unique set. First cell can have set 0, second cell set 1, and so on. It doesn’t matter if the set are ordered in any way, but remember each cell must have an unique set.
2 – Moving from left to right, look at a cell and its adjacent cell on the right. If they have the same set – which is not possible on the first row – add a wall between the cells. If they don’t have the same set, randomly decide if you want to add a wall between the cells.
3 – If you decided not to add a wall, the cell on the right and all other cells in the row with the same set as the cell on the right, change their set becoming of the same set as the cell on the left
4 – Move right by one cell and repeat from step 2 until you looped through all cells.
5 – For each cell, randomly decide if you want to add a bottom wall, keeping in mind each set must have at least one passage, that means there must be at least one cell for each set which does not have a bottom wall. At this time, you completed the generation of a row
6 – If you want to add another row, don’t give the new row a unique set for each cell, but copy the set of the cell above it in the previous row if there isn’t a wall between them. If there is a wall, assign the cell a unique set.
7 – Repeat from step 2 until you want to close the maze
8 – To close the maze, each cell of the last row must have a wall only between cells of the same set.
In the source code of the class, each step is explained:
// row of an Eller maze
class EllerRow {
constructor(configObj) {
this.rowLength = configObj.length ? configObj.length : 8; // default length configuration
this.isLastRow = configObj.closeMaze ? configObj.closeMaze : false; // default last row of the maze configuration
this.previousRow = configObj.previousRow ? configObj.previousRow : null; // default previous row of the maze configuration
this.verticalBias = configObj.verticalBias ? configObj.verticalBias : 0.5; // default vertical bias configuration, 0..1, the higher, the less vertical walls
this.horizontalBias = configObj.horizontalBias ? configObj.horizontalBias : 0.5; // default horizontal bias configuration, 0..1, the higher, the less horizontal walls
this.sets = Array(this.rowLength).fill(0);
this.cells = [];
if (this.previousRow != null) {
this.copyRowSets();
}
this.buildCells();
this.assignRightWalls();
this.assignBottomWalls();
}
// method to copy the sets from previous row
copyRowSets() {
for (let i = 0; i < this.rowLength; i ++) {
if (!this.previousRow.cells[i].bottomWall) {
this.sets[this.previousRow.cells[i].set] ++;
}
}
}
// method to build cells and assign them a set
buildCells() {
for (let i = 0; i < this.rowLength; i ++) {
let set = (this.previousRow == null || this.previousRow.cells[i].bottomWall) ? -1 : this.previousRow.cells[i].set;
this.cells.push(new EllerCell(set));
this.assignUniqueSet(this.cells[i]);
}
}
// method to assign right walls
assignRightWalls() {
for (let i = 0; i < this.rowLength; i ++) {
this.cells[i].rightWall = (i == this.rowLength - 1) || (this.cells[i].set == this.cells[i + 1].set) || (Math.random() >= this.verticalBias && !this.isLastRow);
if (!this.cells[i].rightWall) {
this.mergeSets(i, i + 1);
}
}
}
// method to assign bottom walls
assignBottomWalls() {
for (let i = 0; i < this.rowLength; i ++) {
this.cells[i].bottomWall = (this.sets[this.cells[i].set] != 1 && Math.random() >= this.horizontalBias) || this.isLastRow;
if (this.cells[i].bottomWall) {
this.sets[this.cells[i].set] -= 1;
}
}
}
// method to assign "cell" a set, if it doesn't have one already
assignUniqueSet(cell) {
if (cell.set == -1) {
for (let i = 0; i < this.rowLength; i ++) {
if (this.sets[i] == 0) {
cell.set = i
this.sets[i] ++;
break;
}
}
}
}
// method to merge two sets
// all cells in the same set as "cellTo" are placed in the same set as "cellFrom"
mergeSets(cellFrom, cellTo) {
let setFrom = this.cells[cellFrom].set;
let setTo = this.cells[cellTo].set;
for (let i = 0; i < this.rowLength; i ++) {
if (this.cells[i].set == setTo) {
this.cells[i].set = setFrom;
this.sets[setFrom] ++;
this.sets[setTo] --;
}
}
}
// export the row in JSON format to use it in your projects
exportToObj() {
let row = {
walls: []
}
for (let i = 0; i < this.rowLength; i ++) {
row.walls.push({
up: this.previousRow == null || this.previousRow.cells[i].bottomWall,
down: this.cells[i].bottomWall,
left: i == 0 || this.cells[i - 1].rightWall,
right: this.cells[i].rightWall
})
}
return row
}
}
class EllerCell {
constructor(set) {
this.bottomWall = true;
this.rightWall = true;
this.set = set;
}
}
A row is created this way:
var row = new EllerRow(config);
Where config object can have these properties:
length – length of the row, in cells.
closeMaze – Boolean to tell if this row should close the maze.
previousRow – previous row.
verticalBias – vertical bias configuration, from zero to 1, the higher the bias, the less vertical walls.
horizontalBias – horizontal bias configuration, from zero to 1, the higher the bias, the less horizontal walls.
And now you can create a perfect maze line by line. Download the class and the source code of the entire project.
Never miss an update! Subscribe, and I will bother you by email only when a new game or full source code comes out.