Recursive Backtracking


#1

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();
        }
      }
    }
  }
}

#2

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!


#3

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)

#4

Arrays in JS are powerfully super flexible. :muscle:

In Java, the container class which comes close to a JS array is LinkedList: :link:
Docs.Oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedList.html

Of course it’s the slowest container there is in Java standard API! :snail: