Pathfinding Visualizer

Skills used:

  • JavaScript
  • React.js
  • Pathfinding Algorithms

This project uses various pathfinding algorithms to find the shortest path between two points on a grid.

When the website is loaded, a grid is generated using a 2D array. Each square in the grid contains a JavaScript object. These objects have attributes such as “square.distance”, “square.isStart”, etc. These attributes are used by algorithms to scan the grid.

In the Dijkstra’s Algorithm example shown here, all the squares are given a distance of “Infinity,” except for the start, which is set to 0. The array is sorted by these distances. Next, the squares above, below, to the left, and to the right of the start are checked. The weight of this neighbor square is added to its distance of the current square. The current square is then set as “isVisited”. If not a wall or the final node, the neighbor squares are then checked as well. Once the final node is reached, all visited nodes are returned. The fastest path can be tracked backward to the start by using the final square's “previous-node” attribute.



There is also a maze generation button that can be used to create unique pathing options.

The maze is generated with a Depth-first recursion algorithm. First, every square is filled with a wall. Then, a random start point is found. This point is marked as visited. Then, one of the neighbor squares are picked at random, and the wall is erased. If all the neighbors have been visited, then the function backtracks. It continues to check for unvisited squares until every square has been visited. The path is then returned and animated.

Dijkstra's Pathfinding Algorithm Code:
          
export default function dijkstra(originalGrid) {
  const visitedNodes = [];
  const grid = updateGrid(originalGrid);
  const unvisitedNodes = getAllNodes(grid);
  const startNode = getStartNode(grid);
  if (startNode) {
    startNode.distance = 0;
    while (unvisitedNodes.length) {
      sortNodesByDistance(unvisitedNodes);
      const currentNode = unvisitedNodes.shift();

      if (currentNode.isWall) continue;
      if (currentNode.distance === Infinity) return visitedNodes;
      currentNode.isVisited = true;
      visitedNodes.push(currentNode);
      if (currentNode.isFinish) return visitedNodes;

      const neighbors = getNeighbors(currentNode, grid);
      updateNeighbors(currentNode, neighbors);
    }
  } else {
    console.log("No start node set!");
    return visitedNodes;
  }
  console.log("No finish node set!");
  return visitedNodes;
}
Depth-first Recursion Maze Generation Code:
          
export default function buildDepthFirstMaze(grid) {
  const visitedNodes = [];
  clearBoard(grid);
  initialWallFill(grid);
  const availableNodes = getAvailableNodes(grid);
  const startNode = getRandomStartNode(availableNodes);
  carvePath(startNode, grid, visitedNodes);
  console.log(visitedNodes);
  return visitedNodes;
}

function carvePath(currentNode, grid, visitedNodes) {
  if (currentNode.isMazeVisited) return;
  currentNode.isMazeVisited = true;
  visitedNodes.push(currentNode);
  const neighbors = getAvailableNeighbors(currentNode, grid);
  for (let neighbor of neighbors) {
    if (!neighbor.isMazeVisited) {
      neighbor.previousMazeNode = currentNode;
      carvePath(neighbor, grid, visitedNodes);
    }
  }
}