Half-Elven Programming: February 2015

I had the bright idea recently whilst avoiding work - "I should write a maze generator". Not very good timing, I know, but I did it. And I liked it. I thought I'd show people, because it's kind of cool, and I'll also walk you through it.

Here is the working example:

I'll walk you through the basics of the code. I've never really worked with generating things before, so I'm not sure of the technical name for this approach, and honestly I'm not sure that there is one. If there isn't, I'm naming it The Fail Safe, and you'll see why.

I used a cell type approach to the map - so I started off by defining a basic cell object, and made a 2D array that filled up the entire canvas with them. Every cell has 2 important attributes: isAlive and isMaze. Those are self explanatory. On default

Cell.prototype.isMaze = false;

and

Cell.prototype.isAlive = true;

The whole **algorithm** is only a few lines long, so go ahead and check it out and I'll walk through it:

var generateMaze = function(x, y) {
    //Select starting point, make it into maze
    var point = cells[x][y];
    point.makeIntoMaze();
    failsafe = [];
    //Make sure our start has places to move to
    while (point.hasAliveAdjacent()) {
        //Gather all adjacent spots
        var adjacent = point.getAliveAdjacent();
        //Select a random adjacent, make that our point and make it into a maze
        //the update all the cells so they can adjust accordingly
        var randomAdjacent = randomInt(0, adjacent.length - 1);
        point = adjacent[randomAdjacent];
        point.makeIntoMaze();
        updateCells();
        adjacent = adjacent.splice(randomAdjacent, 1);
        if (adjacent.length > 0) failsafe = failsafe.concat(adjacent);
        failsafe = getValidFromArray(failsafe);
        if (!point.hasAliveAdjacent() && failsafe.length > 0) {
            point = failsafe.pop();
            point.makeIntoMaze();
            updateCells();
        }
    }
};

We start by grabbing a cell from the inputted x and y (these are just random x and y's in range), make it into a cell, and setup our failsafe variable. That's easy.

We want to continually create a maze whilst our current point has places to expand to. Hm... continually... sounds like a loop, so let's throw together a while loop. We then grab all of our alive adjacent cells (a cell is dead if has more than one maze adjacent to it), then select a random one, and make that our new point for the next iteration, that's easy. That part took all of 10 minutes setting up. The failsafe took some more thinking, although it's logical when put all together. We treat our failsafe like a stack, where basically any leftover values get thrown onto it, and when our main point can no longer continue, we pop the top value off the stack and use that instead. Easy peasy. So then we end up continually iterating until every available value is used. Sweet.

For a while I was getting problems because I hadn't updated all of the cells on the map after setting the main point to the fail safe. The problem that arose from this is that many values that shouldn't have been considered alive, were, so it made some really crappy looking mazes.

Feel free to play with the source, you can view it all up on github: https://github.com/tanishalfelven/MazeGenerator

Half-Elven Programming

Tuesday, February 10, 2015

Generating a Maze