Understanding perfect maze generation row after row with Eller algorithm, using a pure JavaScript class

Read all posts about "" game

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.

Get the most popular Phaser 3 book

Through 202 pages, 32 source code examples and an Android Studio project you will learn how to build cross platform HTML5 games and create a complete game along the way.

Get the book

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 100 rounds
// 10000000
// 2 Cars
// 2048
// A Blocky Christmas
// A Jumping Block
// A Life of Logic
// Angry Birds
// Angry Birds Space
// Artillery
// Astro-PANIC!
// Avoider
// Back to Square One
// Ball Game
// Ball vs Ball
// Ball: Revamped
// Balloon Invasion
// BallPusher
// Ballz
// Bar Balance
// Bejeweled
// Biggification
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Boom Dots
// Bouncing Ball
// Bouncing Ball 2
// Bouncy Light
// BoxHead
// Breakout
// Bricks
// Bubble Chaos
// Bubbles 2
// Card Game
// Castle Ramble
// Chronotron
// Circle Chain
// Circle Path
// Circle Race
// Circular endless runner
// Cirplosion
// CLOCKS - The Game
// Color Hit
// Color Jump
// ColorFill
// Columns
// Concentration
// Crossy Road
// Crush the Castle
// Cube Jump
// CubesOut
// Dash N Blast
// Dashy Panda
// Deflection
// Diamond Digger Saga
// Don't touch the spikes
// Dots
// Down The Mountain
// Drag and Match
// Draw Game
// Drop Wizard
// DROP'd
// Dudeski
// Dungeon Raid
// Educational Game
// Elasticity
// Endless Runner
// Erase Box
// Eskiv
// Farm Heroes Saga
// Filler
// Flappy Bird
// Fling
// Flipping Legend
// Floaty Light
// Fuse Ballz
// GearTaker
// Gem Sweeper
// Globe
// Goat Rider
// Gold Miner
// Grindstone
// GuessNext
// Helicopter
// Hero Emblems
// Hero Slide
// Hexagonal Tiles
// HookPod
// Hop Hop Hop Underwater
// Horizontal Endless Runner
// Hundreds
// Hungry Hero
// Hurry it's Christmas
// InkTd
// Iromeku
// Jet Set Willy
// Jigsaw Game
// Knife Hit
// Knightfall
// Legends of Runeterra
// Lep's World
// Line Rider
// Lumines
// Magick
// MagOrMin
// Mass Attack
// Math Game
// Maze
// Meeblings
// Memdot
// Metro Siberia Underground
// Mike Dangers
// Mikey Hooks
// Nano War
// Nodes
// o:anquan
// One Button Game
// One Tap RPG
// Ononmin
// Pacco
// Perfect Square!
// Perfectionism
// Phyballs
// Pixel Purge
// PixelField
// Planet Revenge
// Plants Vs Zombies
// Platform
// Platform game
// Plus+Plus
// Pocket Snap
// Poker
// Pool
// Pop the Lock
// Pop to Save
// Poux
// Pudi
// Pumpkin Story
// Puppet Bird
// Pyramids of Ra
// qomp
// Quick Switch
// Racing
// Radical
// Rebuild Chile
// Renju
// Rise Above
// Risky Road
// Roguelike
// Roly Poly
// Run Around
// Rush Hour
// SameGame
// SamePhysics
// Save the Totem
// Security
// Serious Scramblers
// Shrink it
// Sling
// Slingy
// Snowflakes
// Sokoban
// Space Checkers
// Space is Key
// Spellfall
// Spinny Gun
// Splitter
// Spring Ninja
// Sproing
// Stabilize!
// Stack
// Stairs
// Stick Hero
// String Avoider
// Stringy
// Sudoku
// Super Mario Bros
// Surfingers
// Survival Horror
// Talesworth Adventure
// Tetris
// The Impossible Line
// The Moops - Combos of Joy
// The Next Arrow
// Threes
// Tic Tac Toe
// Timberman
// Tiny Wings
// Tipsy Tower
// Toony
// Totem Destroyer
// Tower Defense
// Trick Shot
// Tunnelball
// Turn
// Turnellio
// TwinSpin
// vvvvvv
// Warp Shift
// Way of an Idea
// Whack a Creep
// Wheel of Fortune
// Where's my Water
// Wish Upon a Star
// Word Game
// Wordle
// Worms
// Yanga
// Yeah Bunny
// Zhed
// zNumbers