astar.js

  // Define the A* search function
  function aStar(start, goal) {
    // Create an empty data structure to store the explored paths
    let explored = [];
  
    // Create a data structure to store the paths that are being explored
    let frontier = [{
      state: start,
      cost: 0,
      estimate: heuristic(start)
    }];
  
    // While there are paths being explored
    while (frontier.length > 0) {
      // Sort the paths in the frontier by cost, with the lowest-cost paths first
      frontier.sort(function(a, b) {
        return a.estimate- b.estimate;
      });
  
      // Choose the lowest-cost path from the frontier
      let node = frontier.shift();
  
      // Add this nodeto the explored paths
      explored.push(node);
      // If this nodereaches the goal, return thenode 
      if (node.state.x == goal.x && node.state.y == goal.y) {
        return explored
      }
  
  
      // Generate the possible next steps from this node's state
      let next = generateNextSteps(node.state);
  
      // For each possible next step
      for (let i = 0; i < next.length; i++) {
        // Calculate the cost of the next step by adding the step's cost to the node's cost
        let step = next[i];
        let cost = step.cost + node.cost;
  
        // Check if this step has already been explored
        let isExplored = (explored.find( e => {
            return e.state.x == step.state.x && 
                e.state.y == step.state.y
        }))

        //avoid repeated nodes during the calculation of neighbors
        let isFrontier = (frontier.find( e => {
            return e.state.x == step.state.x && 
                e.state.y == step.state.y
        }))


        // If this step has not been explored
        if (!isExplored && !isFrontier) {
          // Add the step to the frontier, using the cost and the heuristic function to estimate the total cost to reach the goal
          frontier.push({
            state: step.state,
            cost: cost,
            estimate: cost + heuristic(step.state)
          });
        }
      }
    }
  
    // If there are no paths left to explore, return null to indicate that the goal cannot be reached
    return null;
  }