CODEWITHSUNDEEP
javascriptgraphgraphicsp5.jsa-star
Heidar-An
Heidar-An

Reputation: 109

why does my a star algorithm not work in javascript?

function algorithm(){
if(startPoint === true && endPoint === true){
//add the heuristic distance to the start position from the final position
startPosition.h = distance([startPosition.x, startPosition.y]);

let openList = []

openList.push(startPosition)
let closedList = []
  while (openList.length > 0){
    //print(openList)
    lowPos = 0;
    for(let i = 0; i < openList.length; i++){
      if(openList[i].f < openList[lowPos].f){
        lowPos = i;
      }
    }
    let currentPosition = openList[lowPos];
    //currentPosition.check()
    //if the currentPosition is the endPosition, retrace steps and find the path, then return this path
    if(currentPosition === endPosition){
      let curr = currentPosition;
      let ret = [];
      while(curr.parent != null){
        curr.path()
        ret.push(curr);
        curr = curr.parent;
      }
      endPosition.end()
      return ret.reverse();
    }
    openList.splice(lowPos, 1);
    closedList.push(currentPosition);
    let neighbours = neighbors(currentPosition);
    for(let i = 0; i < neighbours.length; i++){
      let neighbour = neighbours[i];
      if(closedList.includes(neighbour) || neighbour.colour == "black"){
        continue;
      }
      neighbour.check()
      let gScore = currentPosition.g + 1;
      let gScoreBest = false;
      if(openList.includes(neighbour) == false){
        gScoreBest = true;
        neighbour.h = distance([neighbour.x, neighbour.y]);
        openList.push(neighbour);
      }
      else if(gScore < neighbour.g){
        gScoreBest = true;
      }
      if(gScoreBest == true){
        neighbour.parent = currentPosition;
        neighbour.g = gScore;
        neighbour.f = neighbour.g + neighbour.h;
      }
    }
  }
}
 //meaning that either the path is not possible or the final node/initial node 
 has not yet been placed.
 return [];
}

this is my a star algorithm in p5, i'm trying to make an a star visualisation project, but for some reason a lot more of blocks are highlighted than expected. [what my algorithm shows me: https://i.sstatic.net/ILlOr.png In reality it is supposed to be something like this: what it's supposed to be: https://i.sstatic.net/nsF5r.png

The second picture isn't mine, its from someone else's implementation: https://qiao.github.io/PathFinding.js/visual/ = link to the second picture

I think it's something to do with the order of the line: neighbour.check() which changes the colour of the block.

Here is a diagonal solution, as you can see for some reason there is purple in the top left, that is my issue. The top left should not be searched, but it is for some reason. diagonal case

If you need more of my code, please let me know.

Upvotes: 2

Views: 186

Answers (2)

Heidar-An
Heidar-An

Reputation: 109

I got it to fix, surprisingly the thing that was wrong was my distance formulae, I called the wrong variable. enter image description here

here's what it looks like now! :)

Upvotes: 1

DavidWeiss2
DavidWeiss2

Reputation: 405

It looks like you are not checking the diagonals. It is not a mistake. You are doing great.

Upvotes: 1

Related Questions