Prims Maze

Maze generation code using Prim's algorithm
en.wikipedia.org/wiki/Maze_generation_algorithm#Randomized_Prim's_algorithm

Start: top left, Finish: bottom right

Log in to post a comment.

/*
Start with a grid full of walls.
Pick a cell, mark it as part of the maze. Add the walls of the cell to the wall list.
While there are walls in the list:
    Pick a random wall from the list. If only one of the two cells that the wall divides is visited, then:
        Make the wall a passage and mark the unvisited cell as part of the maze.
        Add the neighboring walls of the cell to the wall list.
    Remove the wall from the list.
*/

let size = 35; // min=3, max=155, step=2

var opacity = -.6

// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(opacity);

// Global code will be evaluated once.
const turtle = new Turtle();

var grid = [];

if(size % 2 == 0) {
    size++;
}

for(var i = 0; i < size; i++) {
    grid[i] = [];
    for(var j = 0; j < size; j++) {
        grid[i][j] = 0;
    }
}

var canvasSize = size * (200 / (size + 2));

var walls = [];

// The walk function will be called until it returns false.
function walk(i) {
    var newCell = null;
    if(i == 0) {
        newCell = [0, 0];
        drawCell([0, -1]);
    } else {
        var idx = getRandomInt(0, walls.length);
        var wall = walls[idx];
    
        var visited = getVisitedCells(wall);
        if(visited.length == 1) {
            grid[wall[0]][wall[1]] = 1;
            drawCell(wall);
            switch(visited[0]) {
                case 'left':
                    newCell = [wall[0] + 1, wall[1]];
                    break;
                case 'right':
                    newCell = [wall[0] - 1, wall[1]];
                    break;
                case 'up':
                    newCell = [wall[0], wall[1] + 1];
                    break;
                case 'down':
                    newCell = [wall[0], wall[1] - 1];
                    break;
            }
        }
    
        walls.splice(idx, 1);
    }
    if(newCell != null) {
        addWalls(newCell);
        grid[newCell[0]][newCell[1]] = 1;
        drawCell(newCell);
    }
    
    if(walls.length == 0) {
        drawCell([grid.length - 1, grid.length]);
    }
    return walls.length > 0;// && i < 100;
}

function drawCell(cell) {
    var cellSize = canvasSize / size;
    turtle.penup();
    for(var x = 0; x < cellSize; x+=.125 / Math.abs(opacity)) {
        turtle.goto((cell[0] * cellSize) - (canvasSize / 2), (cell[1] * cellSize) + x - (canvasSize / 2));
        turtle.pendown();
        turtle.forward(cellSize);
    }
}

function getVisitedCells(cell) {
    var visited = [];
    if(cell[0] > 0) {
        if(grid[cell[0] - 1][cell[1]] == 1) {
            visited.push('left');
        }
    }
    if(cell[0] < size - 1) {
        if(grid[cell[0] + 1][cell[1]] == 1) {
            visited.push('right');
        }
    }
    if(cell[1] > 0) {
        if(grid[cell[0]][cell[1] - 1] == 1) {
            visited.push('up');
        }
    }
    if(cell[1] < size - 1) {
        if(grid[cell[0]][cell[1] + 1] == 1) {
            visited.push('down');
        }
    } 
    return visited;
}

function addWalls(cell) {
    var wallCell = null;
    if(cell[0] > 0) {
        addWall([cell[0] - 1, cell[1]]);
    }
    if(cell[0] < size - 1) {
        addWall([cell[0] + 1, cell[1]]);
    }
    if(cell[1] > 0) {
        addWall([cell[0], cell[1] - 1]);
    }
    if(cell[1] < size - 1) {
        addWall([cell[0], cell[1] + 1]);
    }
}

function addWall(wall) {
    for(var i = 0; i < walls.length; i++) {
        if(walls[i][0] == wall[0] && walls[i][1] == wall[1]) {
            return;
        }
    }
    walls.push(wall);
}

function getRandomInt(min, max) {
  return Math.floor(Math.random() * Math.floor(max - min)) + Math.floor(min);
}

function wait(ms) {
  var start = new Date().getTime();
  do { var end = new Date().getTime(); } while(end < start + ms);
}