Assignment 1 – Ayush

 

My inspiration for this project comes from this video by Veritasium.

Pathfinding have a ubiquitous presence in the real world. Their applications range from everyday navigation tools like Google Maps and logistics optimization for companies like Amazon. They are also used in guiding the movements of autonomous vehicles.

Through this project I wanted to experiment with more than just a random walk. I wanted to see if we can put some brain into our walker, so it doesn’t just go towards random directions, but makes some decision in order to find the destination.

Here’s the p5.js sketch:

https://editor.p5js.org/ap6178/sketches/Wi7864pjq

 

The walker performs multiple succeeding walks, from one cell to the other. But then it realizes that the direction it’s taking is not the correct one. When this happens, it tries a new path. Each of these paths have some metrics that tell the walker whether it’s going towards the correct direction or not.

To put brain into the walker, I have used the A* search algorithm. It basically takes two things into consideration in order to be able to make decisions:

• The cost it took for the walker to get to the current point.
• An estimate of how far the walker thinks it is from the destination.

This estimate is called the heuristic function in A* search algorithm. The total estimated cost is given by the following equation:

f(n) = g(n) + h(n)

At any node n, the estimated cost of the path is calculated i.e. f(n)
f(n) requires two other costs: the cost to reach node n i.e. g(n) and the estimated cost to reach the goal node i.e. h(n)

h(n) in this equation is called the heuristic function. There are many heuristic functions we can use, but in this project, I decided to use the Manhattan distance heuristic since we’re dealing with cells on the grid. The Manhattan distance is the sum of horizontal and vertical cell distances to the goal node.

This idea of calculating heuristic for each step makes the walker intelligent.

 

Code

Each node has the following properties as described by the Node class.

class Node {
  constructor(i, j) {
    this.i = i;
    this.j = j;
    this.f = 0;
    this.g = 0;
    this.h = 0;
    this.wall = random(1) < 0.30; // there's a 30% chance of being a wall
    this.previous = undefined;
  }

  show(col) {
    fill(col);
    if (this.wall) {
      fill(59, 25, 25);
    }
    rect(this.i * cellSize, this.j * cellSize, cellSize, cellSize);
  }

  getNeighbors() {
    const neighbors = [];
    const i = this.i;
    const j = this.j;

    if (i < cols - 1) {
      neighbors.push(grid[i + 1][j]);
    }
    if (i > 0) {
      neighbors.push(grid[i - 1][j]);
    }
    if (j < rows - 1) {
      neighbors.push(grid[i][j + 1]);
    }
    if (j > 0) {
      neighbors.push(grid[i][j - 1]);
    }

    return neighbors;
  }
}

The main brain of the walker lies on this heuristic measure. It calculates the Manhattan distance between two nodes nodeA and nodeB required for our estimation function.

function heuristic(nodeA, nodeB) {
  // Manhattan distance (sum of horizontal and vertical distances)
  const dx = abs(nodeA.i - nodeB.i);
  const dy = abs(nodeA.j - nodeB.j);
  return dx + dy;
}

With the help of this heuristic, the function values: f, g, and h are then updated and required actions are taken.

// check neighbors and update their f, g, h values
const neighbors = current.getNeighbors();
for (let neighbor of neighbors) {
  if (!visited.includes(neighbor) && !neighbor.wall) {
    const g = current.g + 1;
    let newPath = false;
        
    if (unexplored.includes(neighbor)) {
      if (g < neighbor.g) {
        neighbor.g = g;
        newPath = true;
      }
    } else {
      neighbor.g = g;
      unexplored.push(neighbor);
      newPath = true;
    }
        
    // update values if path is new
    if (newPath) {
      neighbor.h = heuristic(neighbor, endNode);
      neighbor.f = neighbor.g + neighbor.h;
      neighbor.previous = current;
    }
  }

Future Improvements

An improvement to this project would be to be able to connect the path with lines and show a more artistic version of how the walker is choosing new paths. I would also want to add some kind of animation when it reverts back a few steps to continue to a new path.