Recursive Backtracking

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:

1. Make the initial cell the current cell and mark it as visited
2. 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();
}
}
}
}
}
``````
1 Like

Never mind, I was being silly and missed that they’d already converted it to processing. Heres the link to their github page with both the p5 and processing scripts in case anyone was interested!

2 Likes

Thanks for sharing the link to that example!

To follow up on the initial question of how the stack is managed in Processing(Java) the stack is modeled in their example like this:

``````ArrayList<Cell> stack = new ArrayList<Cell>()
``````

and push/pop are done with

• push: `stack.add(current)`
• pop: `stack.remove(stack.size()-1)`

Arrays in JS are powerfully super flexible.

In Java, the container class which comes close to a JS array is LinkedList: