Hello,
I’ve been watching the Coding Trains Maze Generation videos (https://www.youtube.com/watch?v=_p5IH0L63wo) that uses the depth-first search and recursive backtracking method to generate a maze. The video covers the method in p5.js but I’ve been wondering how you could do it only in processing.
The pseudocode they use is as follows:
- Make the initial cell the current cell and mark it as visited
- While there are unvisited cells
A. If the current cell has any neighbours which have not been visited
i. Choose randomly one of the unvisited neighbours
ii. Push the current cell to the stack
iii. Remove the wall between the current cell and the chosen cell
iv. Make the chosen cell the current cell and mark it as visited
B. Else if stack is not empty
** i. Pop a cell from the stack**
** ii. Make it the current cell**
The code below almost has it but I wasn’t sure how to go about implementing the recursive backtracking steps - the bold sections above.
The Coding Train uses this code to make it work in p5.js:
var stack = [];
stack.push(current);
else if (stack.length > 0) {
current = stack.pop();
}
Any idea how this could be implemented in processing?
// Maze Generation Algorithm - Depth First Search and Recursive Backtracking
int i = 0;
int j = 0;
int w = 100;
int cols = floor(600/w);
int rows = floor(600/w);
int m = 1;
int p = 0;
int checker = 0;
int current = 0;
int timer = 1000;
int picker [] = new int [4];
int x = 0;
int y = 0;
int [][] visited = new int [cols + 1][rows + 1];
int [][] wallPos1 = new int [cols + 1][rows + 1];
int [][] wallPos2 = new int [cols + 1][rows + 1];
int [][] wallPos3 = new int [cols + 1][rows + 1];
int [][] wallPos4 = new int [cols + 1][rows + 1];
void setup() {
size(600, 600);
frameRate(400);
for (int i = 0; i < rows; i++) { //nested loop to create cell objects in a grid
for (int j = 0; j < cols; j++) {
visited[i][j] = 0;
wallPos1[i][j] = 1;
wallPos2[i][j] = 1;
wallPos3[i][j] = 1;
wallPos4[i][j] = 1;
}
for (int k = 0; k < 4; k++) {
picker[k] = 0;
}
}
visited[0][0]=1;
nest();
}
int index(int s, int t) {
if (s < 0 || t < 0 || s > cols - 1 || t > rows - 1) {
return -1;
}
return s+t*cols;
}
void nest() {
if (index(i, j-1)!=-1) {
if (visited[i][j-1] == 0)
{
picker[0] = 1;
checker = 1;
}
}
if (index(i+1, j)!=-1) {
if (visited[i+1][j] == 0)
{
picker[1] = 1;
checker = 1;
}
}
if (index(i, j+1)!=-1) {
if (visited[i][j+1] == 0)
{
picker[2] = 1;
checker = 1;
}
}
if (index(i-1, j)!=-1) {
if (visited[i-1][j] == 0)
{
picker[3] = 1;
checker = 1;
}
}
if (checker == 1) {
p=round(random(3));
while (picker[p]!=1) {
p=round(random(3));
}
if (p==0) {
visited[i][j-1] = 1;
wallPos1[i][j] = 0;
wallPos3[i][j-1] = 0;
current=index(i, j-1);
j = j-1;
}
if (p==1) {
visited[i+1][j] = 1;
wallPos2[i][j] = 0;
wallPos4[i+1][j] = 0;
current=index(i+1, j);
i = i+1;
}
if (p==2) {
visited[i][j+1] = 1;
wallPos3[i][j] = 0;
wallPos1[i][j+1] = 0;
current=index(i, j+1);
j = j+1;
}
if (p==3) {
visited[i-1][j] = 1;
wallPos4[i][j] = 0;
wallPos2[i-1][j] = 0;
current=index(i-1, j);
i = i-1;
}
}
for (int k = 0; k < 4; k++) {
picker[k] = 0;
}
if (checker==0) {
m = 0;
}
checker = 0;
}
void draw() {
int r = 0;
int q = 0;
background(65, 81, 69);
for (r = 0; r < rows; r++) {
for (q = 0; q < cols; q++) {
x = q*w;
y = r*w;
if (visited[q][r]==1 && current!=index(q, r)) { //once visited fill cell
fill(255, 0, 255);
rect(x, y, w, w);
fill(0, 0, 0);
}
if (current==index(q, r)) { //current cell fill
fill(0, 255, 0);
rect(x, y, w, w);
fill(0, 0, 0);
}
if (wallPos1[q][r]==1) stroke(255); //remove top cell wall
if (wallPos1[q][r]==0) stroke(255, 0, 255);
line(x, y, x+w, y);
if (wallPos2[q][r]==1) stroke(255); //remove right cell wall
if (wallPos2[q][r]==0) stroke(255, 0, 255);
line(x+w, y, x+w, y+w);
if (wallPos3[q][r]==1) stroke(255); //remove bottom cell wall
if (wallPos3[q][r]==0) stroke(255, 0, 255);
line(x+w, y+w, x, y+w);
if (wallPos4[q][r]==1) stroke(255);
if (wallPos4[q][r]==0) stroke(255, 0, 255); //remove left cell wall
line(x, y+w, x, y);
if (timer>0 && m==1) {
timer-=1;
if (timer<=0) {
timer = 1000;
nest();
}
}
}
}
}
