A* Pathfinding

Introduction

This project is an interactive visualization of the A* pathfinding algorithm implemented using JavaScript and the p5.js library. A* (pronounced “A-star”) is one of the most popular pathfinding algorithms used in services like Google Maps to find the shortest path between two points while avoiding obstacles. Compared to Dijkstra’s algorithm, A* is faster and more efficient, but will not find all paths to the end, making it a greedy algorithm.

How It Works

Overview

In a nutshell, the algorithm works by maintaining two sets:

• An open set of neighbor nodes to explore
• A closed set of nodes that have already been explored

The A* algorithm combines the best aspects of Dijkstra’s algorithm and greedy best-first search to efficiently find optimal paths. It works by intelligently exploring the most promising paths first, using a combination of:

1. Known Cost: How far we’ve already traveled from the start
2. Estimated Cost: A prediction of how far we still need to go

The algorithm maintains two lists - one for nodes it plans to visit, and another for nodes it has already checked. As it explores, it continuously updates its understanding of the best path by:

• Examining the most promising locations first
• Keeping track of the path taken so far
• Using predictions to guide the search toward the goal
• Avoiding unnecessary exploration of unpromising areas

What makes A* particularly powerful is its ability to balance thoroughness with efficiency. It will always find the shortest possible path if one exists, while typically examining far fewer locations than simpler algorithms would need to check.

This implementation uses a simple distance calculation (grid-based Manhattan distance) to help predict which paths are most promising, which works well for our grid-based environment where movement is limited to up, down, left, and right.

The Grid

The visualization creates a 100x100 grid where:

• Each cell is represented by a Node object
• Random cells are designated as walls (with 20% probability)
• Start and end points are randomly placed on the grid
• The grid is displayed using p5.js

The Node

Here we define what a node is:

function Node(i, j) {
  this.f = 0; // total cost
  this.g = 0; // cost from start
  this.h = 0; // heuristic
  this.i = i; // column
  this.j = j; // row
  this.wall = false; // boolean indicating if node is an obstacle
  // 20% chance to be a wall
  if (random(1) < 0.2) {
    this.wall = true;
  }
  this.neighbors = []; // array of adjacent nodes
  this.cameFrom = null; // so we can trace back to the start
}

The Algorithm

The A* implementation follows these main steps:

1. Initialize open and closed sets
2. Start from the beginning node
3. For each iteration:
   • Find the node with lowest f-score in the open set
   • If it’s the end node, we’re done
   • Otherwise, evaluate all neighbors and update their scores
   • Move current node from open to closed set

The core pathfinding and drawing logic can be found here:

  if (openSet.length > 0) {
    // find node with lowest f in open set
    var lowest = 0;
    for (var i = 0; i < openSet.length; i++) {
      // if f is less than current lowest, set it
      if (openSet[i].f < openSet[lowest].f) {
        lowest = i;
        // tie breaking
      } else if (openSet[i].f == openSet[lowest].f) {
        if (openSet[i].h < openSet[lowest].h) {
          lowest = i;
        }
      }
    }
    var q = openSet[lowest];
    // if current node is the end, we're done
    if (q === end) {
      noLoop();
      console.log("DONE");
      beginShape();
      noFill();
      stroke(252, 238, 33);
      strokeWeight(w / 4);
      vertex(path[0].i * w + w / 2, path[0].j * h + h / 2); // draw path
      vertex(end.i * w + w / 2, end.j * h + h / 2); // draw end
      endShape();
      fill(0, 255, 0);
      stroke(0);
      ellipse(end.i * w, end.j * h, 10, 10);
      return;
    }
    removeFromArray(q, openSet); // remove current node from open set
    closedSet.push(q); // add it to closed set

    var neighbors = q.neighbors;
    for (var i = 0; i < q.neighbors.length; i++) {
      var neighbor = neighbors[i];

      
      if (!closedSet.includes(neighbor) && !neighbor.wall) {
        var tempG = q.g + heuristic(neighbor, q);
        var newPath = false;
        if (openSet.includes(neighbor)) {
          if (tempG < neighbor.g) {
            neighbor.g = tempG;
            newPath = true;
          } 
        } else {
          neighbor.g = tempG;
          newPath = true;
          openSet.push(neighbor);
        }
        if (newPath) {
          neighbor.h = heuristic(neighbor, end);
          neighbor.f = neighbor.g + neighbor.h;
          neighbor.cameFrom = q;
        }
      }
    }

Credits

This project was inspired by The Coding Train’s educational content, with some tweaks here and there to make it my own.