Custom Variant and Optimization of Depth-first Search Maze Algorithm Part 2

This is the link for the part 1 if you're interested:
https://steemit.com/programming/@jkazuto/custom-variant-and-optimization-of-depth-first-search-maze-algorithm

In this post we will explore the code behind my simple variant of depth-first search which was made with javascript and p5js framework for rendering in canvas.

1. Variables
2. setup()
3. draw()
4. depthFirst()
   a. this.start()
   b. this.run()
   c. this.merge()

You can download the source code here: https://github.com/jepsuCoded/Optimized-Depth-first-Search-Maze-Algorithm

What I've used

• Javascript
• p5js
• Spck Editor (Android App)

---

Variables

Global variables before the setup

---

cellX is the number of cells in the x-axis and cellY in the y-axis
let cellX = 91, cellY = 41;


The size of each cells
let s = 7;


Maximum steps before backtracking
let maxStep = cellX+cellY;


Numbers of cell to check per frame
let cycle = 60;


Stroke weight of the cell walls
let strokeSize = 1;


Color variables for displaying
FORMAT: [Red, Green, Blue, Alpha];

let bg = [60, 47, 47, 255];
let color_cellWalls = [255, 244, 230, 255];
let color_movingCell = [133, 68, 66, 255];
let color_unvisited = [190, 155, 123, 255];

Other variables that must not be touched

let _width = s*cellX, _height = s*cellY;
let grid = [];
let cols, rows;
let startPos;
let endPos;

Setup

This setup function is part of the p5js and will run once, upon starting the javascript file.

---

In this setup function,

1. The canvas will be created based on the computed width and height.
2. All of the cell will be created and stored in a one dimensional array list called grid.
3. Create two algorithms/maze runner, one for the starting cell and one for the exit cell.

function setup() {
  createCanvas(_width, _height);
  
  cols = floor(width/floor(width/cellX));
  rows = floor(height/floor(height/cellY));
  
  // Initialized all cells in an array called grid
  for (let j = 0; j < rows; j++) {
    for (let i = 0; i < cols; i++) {
      grid.push(new Cell(i, j));
    }
  }
  
  // First maze generator
  startPos = new depthFirst();
  // This is the starting cell
  startPos.start(grid[0], "start");
  
  // Second maze generator
  endPos = new depthFirst();
  // This is the ending cell
  endPos.start(grid[grid.length-1], "end");
}

Draw

The draw function is also part of the p5js and will run a set of frames per second.

---

In this draw function,

1. If one of the two maze runners is not yet finished
   1. Draw each walls of all the cells
   2. Loop for cycle times and run the algorithm for two maze runners
2. If all of the cells are visited and are done running
   1. Connect the two maze together to create one whole maze
   2. Draw everything again
   3. Stop this function, forever

function draw() {
  if (startPos.done === 0 || endPos.done === 0) {
    // Draw every cells per frame
    background(bg[0], bg[1], bg[2], bg[3]);
    grid.forEach(item => item.show());
    
    // For every cycle per frame
    for(let i = 0; i < cycle; i++) {
      // Run the depth-first search algorithm
      startPos.run();
      endPos.run();
    }
  }
  // If everything is done and all cells are visited
  else if (startPos.done === 1 && endPos.done === 1) {
    // Combine two generated mazes
    startPos.merge(endPos);
    
    // Draw every frame
    background(bg[0], bg[1], bg[2], bg[3]);
    grid.forEach(item => item.show());
  }
}

DepthFirst

This is where the algorithm run everytime the run() function begins

---

The top part of this function is the declaration of variables.

function depthFirst() {
  
  // Group of cells
  this.group;
  
  // List of visited cells used for backtracking
  this.stack = [];
  
  // List of all visited cell used for merge function
  this.track = [];
  
  // Current position of running cell
  this.pos;
  
  // Starting cell
  this.startPos;
  
  this.done = 0;
  
  // Current steps made
  this.steps = 0;

  // . . .
}

DepthFirst.start()

// Initialization
  this.start = function(pos, name) {
    this.pos = pos;
    this.startPos = pos;
    this.stack.push(pos);
    this.group = name;
  };

DepthFirst.run()

1. Store all unvisited neighbor cells in the unvisited array variable
2. Set this current cell as visited
3. If the steps are greater than the maximum step
   1. Reset this.steps to zero
   2. Backtrack maxStep/2 times
4. Else Pick a random cell in unvisited
   1. Store that cell to the next variable
   2. Add that cell to the group maze
   3. Remove wall between the current cell and the next cell
   4. Set this cell to next cell
   5. Push this cell to the stack and tracks
   6. Increment this.steps
5. Else if there is no available cell to visit
   1. Decrement this.steps
   2. Backtrack one step
   3. Pop the stack
6. Else set done to 1 since there is no more cell to visit

// Start the algorithm
  this.run = function() {
    
    // If not done then proceed
    if(this.done === 0) {
      // Draw current position of running cell
      fill(color_movingCell[0], color_movingCell[1], color_movingCell[2], color_movingCell[3]);
      noStroke();
      rect(this.pos.a*s, this.pos.b*s, s, s);
      
      // Return all unvisited neighbor of current cell
      let unvisited = checkNeighbors(this.pos.a, this.pos.b);
      
      // Make this cell visited
      this.pos.visited = true;
      
      // If maximum steps are reached then
      if(this.steps >= maxStep - 1) {
        // Reset steps to zero
        this.steps = 0;
        // Go back to old cell to find another path
        this.pos = this.stack[this.stack.length-(floor(maxStep*0.5))-1];
      }
      // Else randomly choose new cell to visit
      else if(unvisited && this.steps < maxStep) {
        
        // Pick a new cell randomly
        let next = unvisited[floor(random(0, unvisited.length))];
        
        // Set this cell to this group
        next.group = this.group;
        
        // Remove wall between this cell and the chosen cell to visit
        removeWalls(this.pos, next);
        
        /* this.pos.show(); */
        
        //Set the chosen cell as the current cell
        this.pos = next;
        
        // Add this new cell into the tracking list
        this.track.push(this.pos);
        this.stack.push(this.pos);
        
        this.steps++;
      }
      // Else if there is no neighbor cell to visit
      else if(this.stack.length > 1) { // Also checking for the length of stack array to prevent out of bound error
        this.steps--;
        
        // Set the current cell to previous visited cell
        this.pos = this.stack[this.stack.length-2];
        
        // Remove the last visited cell on the stack
        this.stack.pop();
      }
      // Else everything is visited and is now done
      else if (this.done === 0) this.done = 1;
    }
    
  };

DepthFirst.merge()

This function is responsible for connecting two mazes together with one argument needed, a path maze to connect with this maze.

// Merge two generated maze as one whole maze
  this.merge = function(path) {
    let cells = [];
    
    // Set all cells as unvisited
    for (let i = 0; i < grid.length; i++) {
      grid[i].visited = false;
    }
    
    // Loop through all cells in a generated maze
    for(let i = path.track.length-1; i > 0; i--) {
      let current = path.track[i];
      
      // Return neighbors
      let possible = checkNeighbors(current.a, current.b);
      if (possible) {
        for(let j = 0; j < possible.length; j++) {
          
          // If that cell is not in this group then
          if(possible[j].group == this.group) {
            // Add that cell to possible cells
            cells.push([current, possible[j]]);
          }
        }
      }
    }
    
    for (let i = 0; i < grid.length; i++) {
      grid[i].visited = true;
    }
    
    let r = floor(random(0, cells.length));
    
    // Remove wall between that cell in this group and another cell from the given other group
    removeWalls(cells[r][0], cells[r][1]);
    
    // Done, this function will not run anymore
    this.done++;
  };

---

And that is all the main functionality of this variation of depth-first search, I hope you understand most of it even though I didn't explain it very very well :3

You can see more of the other functions I've used on the source code link given above.

If you enjoy reading this please upvote, share and leave a comment for any feedback!