// ============================================================
// Daniel Shiffman
// Depth-First Search Maze Generator Algorithm
// with Recursive Backtracking
// ============================================================
//
// Cell Corners and Sides
//
// (x,y) top (x+w,y)
// +----------+
// | |
// left | CELL | right
// | |
// | |
// +----------+
// (x,y+w) bottom (x+w,y+w)
//
//
// Adjacent Cells
//
// +-------+
// | |
// | i,j-1 |
// | |
// +-------+-------+--------+
// | | | |
// | i-1,j | i,j | i+1,j |
// | | | |
// +-------+-------+--------+
// | |
// | i,j+1 |
// | |
// +-------+
//
// ============================================================
// ============================================================
// Note: This is copied from the YouTube videos. It is a
// slightly different (older) version of the current
// Wikipedia article "Maze generation algorithm".
// ------------------------------------------------------------
//
// ------------------
// Depth-First-Search
// ------------------
//
// This algorithm is a randomized version of the
// depth-first-search algorithm. Frequently implemented with
// a stack, this approach is one of the simplest ways to
// generate a maze using a computer. Considered the space
// for a maze being a large grid of cells (line a large chess
// board), each cell starts with four walls. Starting from
// a random cell, the computer then selects a random
// neighboring cell that has not yet been visited. The
// computer removes the wall between the two cells and
// marks the new cell as visited, and adds it to the stack
// to facilitate backtracking. The computer continues this
// process, with a cell that has no unvisited neighbors being
// considered a dead-end. When at a dead-end it backtracks
// through the path until it reaches a cell with unvisited
// neighbors, continuing the path generation by visiting this
// new, unvisited cell (creating a new junction). This
// process continues until every cell has bee visited,
// causing the computer to backtrack all the way back to
// the beginning cell. We can be sure every cell is visited.
//
// As given above this algorithm involves deep recursion
// which may cause stack overflow issues on some computer
// architectures. This algorithm can be rearranged into a
// loop by storing backtracking information in the maze
// itself.
//
// Mazes generated with a depth-first search have a low
// branching factor and contain many long corridors, because
// the algorithm explores as far as possible along each
// branch before backtracking.
//
// To add difficulty and a fun factor the depth-first
// generated mazes, you can influence the likelihood of
// which neighbor to visit, instead of it being completely
// random. By making it more likely to visit neighbors to
// your sides, you can have a more horizontal maze generation.
// Experimenting with directional passage "bias" in certain
// places could lead to creating fun designs, such as
// checkerboard pattern, and X, and more.
//
// ---------------------
// Recursive Backtracker
// ---------------------
//
// The depth-first search algorithm of maze generation is
// frequently implemented using backtracking:
//
// 1. Make the initial cell the current cell and
// mark it as visited
//
// 2. While there are unvisited cells
//
// 1. If the current cell has any neighbors which
// have no been visited
//
// 1. Chose randomly one of the unvisited neighbors
// 2. Push the current cell onto the stack
// 3. Remove the wall between the current cell and
// the chosen cell
// 4. Make the chosen cell the current cell and
// mark it as visited
//
// 2. Else if stack is not empty
//
// 1. Pop a cell from the stack
// 2. Make it the current cell
//
// ============================================================
This code Is From The YouTube Videos
The code is JavaScript and uses the p5js graphics library.
The code is incomplete. Look thru the videos and complete it,
or wait until I finish copying it.
// ============================================================
// Create a Maze
// ============================================================
var cols, rows; // number of columns and rows
var current; // the current cell
var w = 40; // cell size width and height (pixels)
var grid = []; // grid (of cells) array
// ------------------------------------------------------------
// ---- setup
// ----
// ---- note: the canvas size is a multiple of the cell size
// ------------------------------------------------------------
function setup()
{
createCanvas(400,400); // drawing canvas
frameRate(5); // frames per second
cols = floor(width/w); // number of columns
rows = floor(height/w); // number of rows
// ---- create the cell objects
for (var j = 0; j < rows; i++)
{
for (var i = 0; i < cols; i++)
{
var cell = Cell(i,j);
grid.push(cell);
}
}
// ---- select a starting cell
current = grid[0];
current.checkNeighbors()
}
// ------------------------------------------------------------
// ---- draw cells
// ------------------------------------------------------------
function draw()
{
background(51);
for(var i = 0; grid.length; i++)
{
grid[i].show();
}
current.visited = true;
var neighbor = current.checkNeighbors();
if (next)
{
// ---- step 1
next.visited = true;
// ---- step 2
// ---- step 3
// ---- step 4
current = next;
}
}
// ------------------------------------------------------------
// ---- calculate a cell's (grid) array index
// ----
// ---- note: a. the grid array (cell storage) is one
// ---- dimensional and not multi-dimensional
// ---- b. the cells are a two dimensional array
// ---- (col,row)
// ---- c. the canvas is a two dimensional array
// ---- (x,y) of pixels
// ------------------------------------------------------------
function index(i,j)
{
if (i < 0 || j < 0 || i > cols-1 || j > rows-1)
{
return -1
}
return i + j * cols;
}
// ------------------------------------------------------------
// ---- constructor function for a cell object
// ----
// ---- i is column number
// ---- j is row number
// ------------------------------------------------------------
function Cell(i,j)
{
this.i = i; // column number (grid x)
this.j = j; // row number (grid y)
this.walls = [true,true,true,true]
this.visited = false;
// ---------------------------------------------------------
// ---- check for neighbor cells
// ---------------------------------------------------------
this.checkNeighbors = function()
{
// ---- get the array (grid) index of neighbor cells
var neighbors = [];
var top = grid[index(i,j-1)];
var right = grid[index(i+1,j)];
var bottom = grid[index(i,j+1)];
var left = grid[index(i-1,j)];
// neighbor exists and has not been visited?
if (top && !top.visited)
{
neighbors.push(top);
}
if (right && !right.visited)
{
neighbors.push(right);
}
if (bottom && !bottom.visited)
{
neighbors.push(bottom);
}
if (left && !left.visited)
{
neighbors.push(left);
}
// ---- select a neighbor to process next
if (neighbors.length > 0)
{
var r = floor(random(0,neighbors.length));
return neighbors[r];
}
else
{
return undefined;
}
}
// ---------------------------------------------------------
// ---- draw the maze
// ---------------------------------------------------------
this.show = function()
{
var x = this.i*w;
var y = this.j*w;
// ---- draw cell walls
stroke(255);
if this.walls[0])
{
line(x,y,x+w,y) // top cell wall
}
if this.walls[1])
{
line(x+w,y,x+w,y+w) // right cell wall
}
if this.walls[2])
{
line(x+w,y+w,x,y+w) // bottom cell wall
}
if this.walls[3])
{
line(x,y+w,x,y) // left cell wall
}
// ---- draw cell rectangle (square)
if (this.visited)
{
fill(255,0,255,100);
rect(x,y,w,w)
}
}
}