DEV Community

Cover image for Pathfinding with Javascript: The A* Algorithm
Simon Pfeiffer for Codesphere Inc.

Posted on • Edited on

18 2

Pathfinding with Javascript: The A* Algorithm

There has been no shortage of academic research into finding efficient ways to find paths. Its use in games, logistics, and mapping makes it an important topic for any aspiring programmer to try their hand in.

One of the most famous algorithms for computing the quickest route between two points is the A* algorithm. In this article, we’ll go over how A* works and even do a quick implementation of the algorithm in Javascript.


What is the A* algorithm?

A* is an improved version of Dijkstra’s search algorithm that was developed at the Stanford Research Institute. It makes use of heuristics(educated guesses that help reduce the time taken to compute the result) to increase its performance and efficiency. Unlike Dijkstra, this algorithm is specific i.e. it only finds the shortest path from one point to another instead of all possible end-points. It is used in online maps, video games, artificial intelligence, and other similar applications.


Implementation

In our Javascript implementation, we will use arrays to track our path over a grid but we can use other data structures like a heap or a graph to improve the overall performance of our code. You can find the complete code below:

let cols = 5; //columns in the grid
let rows = 5; //rows in the grid
let grid = new Array(cols); //array of all the grid points
let openSet = []; //array containing unevaluated grid points
let closedSet = []; //array containing completely evaluated grid points
let start; //starting grid point
let end; // ending grid point (goal)
let path = [];
//heuristic we will be using - Manhattan distance
//for other heuristics visit - https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
function heuristic(position0, position1) {
let d1 = Math.abs(position1.x - position0.x);
let d2 = Math.abs(position1.y - position0.y);
return d1 + d2;
}
//constructor function to create all the grid points as objects containind the data for the points
function GridPoint(x, y) {
this.x = x; //x location of the grid point
this.y = y; //y location of the grid point
this.f = 0; //total cost function
this.g = 0; //cost function from start to the current grid point
this.h = 0; //heuristic estimated cost function from current grid point to the goal
this.neighbors = []; // neighbors of the current grid point
this.parent = undefined; // immediate source of the current grid point
// update neighbors array for a given grid point
this.updateNeighbors = function (grid) {
let i = this.x;
let j = this.y;
if (i < cols - 1) {
this.neighbors.push(grid[i + 1][j]);
}
if (i > 0) {
this.neighbors.push(grid[i - 1][j]);
}
if (j < rows - 1) {
this.neighbors.push(grid[i][j + 1]);
}
if (j > 0) {
this.neighbors.push(grid[i][j - 1]);
}
};
}
//initializing the grid
function init() {
//making a 2D array
for (let i = 0; i < cols; i++) {
grid[i] = new Array(rows);
}
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j] = new GridPoint(i, j);
}
}
for (let i = 0; i < cols; i++) {
for (let j = 0; j < rows; j++) {
grid[i][j].updateNeighbors(grid);
}
}
start = grid[0][0];
end = grid[cols - 1][rows - 1];
openSet.push(start);
console.log(grid);
}
//A star search implementation
function search() {
init();
while (openSet.length > 0) {
//assumption lowest index is the first one to begin with
let lowestIndex = 0;
for (let i = 0; i < openSet.length; i++) {
if (openSet[i].f < openSet[lowestIndex].f) {
lowestIndex = i;
}
}
let current = openSet[lowestIndex];
if (current === end) {
let temp = current;
path.push(temp);
while (temp.parent) {
path.push(temp.parent);
temp = temp.parent;
}
console.log("DONE!");
// return the traced path
return path.reverse();
}
//remove current from openSet
openSet.splice(lowestIndex, 1);
//add current to closedSet
closedSet.push(current);
let neighbors = current.neighbors;
for (let i = 0; i < neighbors.length; i++) {
let neighbor = neighbors[i];
if (!closedSet.includes(neighbor)) {
let possibleG = current.g + 1;
if (!openSet.includes(neighbor)) {
openSet.push(neighbor);
} else if (possibleG >= neighbor.g) {
continue;
}
neighbor.g = possibleG;
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
}
}
}
//no solution by default
return [];
}
console.log(search());
view raw Astar.js hosted with ❤ by GitHub

A* works by considering all the adjacent points around our starting point and computing a cost function(Which you can think of as time or distance) for each of the adjacent points. Since our goal in pathfinding is to find the path that requires the least cost, we will then explore the option that has the least cost, and repeat this process until we reach our end point.

The cost value of a point is computed by adding the distance from that point to our starting point, to the distance from that point to the ending point. Note that since we are working over a grid, we are using what’s called the taxicab norm to measure distance(The sum of horizontal and vertical differences between the points). The way you choose to measure distance is going to depend on the problem you are working on. For example, if your agent is able to move diagonally on the grid, you probably would use the euclidean norm.


There you have it! We just implemented a basic version of the A* search algorithm in JavaScript. You can take this to the next level by adding obstacles, allowing diagonals, etc. You can even create an animation that shows the path being traced from the starting point to the end.

No matter what you’re developing, you don’t want to be bogged down by your computer’s infrastructure. At Codesphere, we’re building an all-in-one development platform that lets you develop with the full power of the cloud behind you.

Let us know in the comments how you plan to use this algorithm.
Happy coding!

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (6)

Collapse
 
djmisterjon profile image
DjMisterJon

what is this if (openSet[i].f < openSet[lowestIndex]) { ?
Compare number and obj instance ?

Collapse
 
simoncodephere profile image
Simon Pfeiffer

Good catch! It should be openSet[lowestIndex].f, since we are comparing the cost values. Fixing the gist now

Collapse
 
pmcorrea profile image
pmcorrea

Small question, is it pronounced “A star”?

Collapse
 
simoncodephere profile image
Simon Pfeiffer

Yep!

Collapse
 
georgewl profile image
George WL

I've never seen it pronounced out loud to be honest

Collapse
 
ajbrickhouse profile image
Tony

I converted it to use a canvas, added diagonal movement, and added obstacles. It works well. I'm hoping to use it to draw lines in a flow chart script. Thanks for the help!
code with additions

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more