A* Algorithm for Path Finding

An implementation of the a* (spoken: a star) algorithm for path finding. Bright grey fields can be used to travel. The randomly generated dark grey fields are obstacles.
The alogorithm starts at the yellow field in the top left corner and searches a path to the blue target fields. The red fields show the path found. The green fields are used during computation. They are yet to process as long as the destination is not reached.

To start click on two cells to pick start and target.

The algorithm is divided into two steps. The first step is to find a path from start to destination. The second path is to track back the path from destination to start.
You need three array: One with the yet to compute fields (openSet), one with the already computed fields (closedSet) and the path array.

At first I created a grid of cells of type Acell, which is a class i defined in aclass.js. The class own following attributes:

constructor(x, y, w, h) {
 this.x = x;
 this.y = y;
 this.wi = w;
 this.he = h;
 this.f;
 this.g;
 this.h;
 this.neighbors = [];
 this.prev = undefined;
 this.obstacle=false;
}

Where x and y are the indices of the cell in the grid and wi and he are its width and height. f, g, h are valkues used in the the a* algorithm. Where

• f is the sum of g and h of a given cell
• g is the cost of the path from the start node. As this example is based on a grid and you can only step from one cell to another, I only add 1 (in words: one) the the g value of the previous cell.
• h is a estimation of the cost from the current cell to the goal. The letter h stands for heuristic, which is just a fancy sounding word for estimation. In my example I just use the cartesian distance from the current cell to the goal.

neighbors is a array containing the neighbor cell of this cell. I know that this is a rather memory consuming implementation, but it works.
prev is are reference to the previous cell. This is used to track the path reversely.
The boolean flag obstacle indicates if this cell is an obstacle if true;
The listing below gives the important part of the algorithm. I deleted everything that is used for displaying only.

function draw() {
 let current;

 if(openSet.length === 0) {
  noLoop(); // no solution available
 } else {
  let c = getLowestScoreCell();
  current = openSet[c];

  if(current === goal) { // found the goal
   let temp = current;
   for(let i = 0; i < 25; i++ ) {
    temp = temp.getPrevious();
   }
   noLoop();
  }

  // remove current cell from openSet, add it to closedSet and
  // process every neighbor of current
  openSet.splice(current, 1);
  closedSet.push(current);

  var neighbors = current.getNeighbors();
  for(let i = 0; i < neighbors.length; i++) {
   var neighbor = neighbors[i];
   if(neighbor != undefined && neighbor.obstacle==false) {
    if( !closedSet.includes(neighbors) ) {
     // add one to the g value (grid)
     var tempG = current.getG() + 1;
     if( openSet.includes(neighbor) ) {
      // If open set contains this cell and the calculated g value
      // is smaller than its value, update the cell
      if( tempG < neighbor.getG() ) {
       neighbor.setG(tempG);
      }
     } else {
      neighbor.setG(tempG);
      openSet.push(neighbor);
     }
   }

   // Compute the h and f values for the current cell.
   neighbor.setH( heuristic(neighbor, goal) );
   neighbor.setF( neighbor.getG() + neighbor.getH() );
   neighbor.setPrevious(current);
   }
  }
 }
}

One important function that is used in the above algorithm is function getLowestScoreCell() which returns the cell whith the lowest score (the lowest f value), i.e. the cell with which the algorithm will proceed its calculation.

function getLowestScoreCell() {
 lowest = 0;
 for(let i =0; i < openSet.length; i++) {
  if(openSet[i].getF() < openSet[lowest].getF()) {
   lowest = i;
  }
 }

 return lowest;
}