Problems with translating c to javascript-CodePudding

I was trying to replicate this c code in javascript. https://github.com/OneLoneCoder/videos/blob/master/OneLoneCoder_PathFinding_AStar.cpp

The code should draw a yellow line from the red point to the green point.

I checked my implementation multiple times but I still can't figure out why it is not working.

For some reason it won't set the parent for my objects correctly.

Which results in the path not getting drawn.

Could really need some help here.

width = 11;
height = 9;

s = 50;

c = document.createElement("canvas");
document.body.appendChild(c);
ctx = c.getContext("2d");
c.width = width * s;
c.height = height * s;

nodes = [];

for (x = 0; x < width; x  ) {
  row = [];
  nodes.push(row);
  for (y = 0; y < height; y  ) {
    row.push(new Node(x, y));
  }

}

SetNeighbours();

function SetNeighbours() {
  for (x = 0; x < width; x  ) {
    for (y = 0; y < height; y  ) {
      if (x > 0) {
        nodes[x][y].neighbours.push(nodes[x - 1][y])
      }
      if (x < width - 1) {
        nodes[x][y].neighbours.push(nodes[x   1][y])
      }
      if (y > 0) {
        nodes[x][y].neighbours.push(nodes[x][y - 1])
      }
      if (y < height - 1) {
        nodes[x][y].neighbours.push(nodes[x][y   1])
      }
    }

  }
}

nodes[3][0].obstacle = true;
nodes[3][1].obstacle = true;
nodes[3][2].obstacle = true;
nodes[3][3].obstacle = true;
nodes[3][4].obstacle = true;
nodes[3][5].obstacle = true;


nodes[7][3].obstacle = true;
nodes[7][4].obstacle = true;
nodes[7][5].obstacle = true;
nodes[7][6].obstacle = true;
nodes[7][7].obstacle = true;
nodes[7][8].obstacle = true;

start = nodes[1][1];
end = nodes[9][7];

//end.parent = nodes[9][6];
//nodes[9][6].parent = nodes[9][5]

current = start;
start.localGlobal = 0;
start.globalGoal = heuristic(start, end);

notTested = [];
notTested.push(start);

while (notTested.length > 0 && current != end) {

  notTested.sort(function(a, b) {
    return a.globalGoal < b.globalGoal
  });
  while (notTested.length > 0 && notTested[0].visited) {
    notTested.shift();
  }

  if (notTested.length == 0) {
    break;
  }

  current = notTested[0];
  current.visited = true;

  for (let n of current.neighbours) {
    if (!n.visited && !n.obstacle) {
      notTested.push(n);
    }

    newGoal = current.localGoal   distance(current, n);

    if (newGoal < n.localGoal) {
      n.parent = current;
      n.localGoal = newGoal;
      n.globalGoal = n.localGoal   heurisitc(n, end);
    }

  }
}

DrawCanvas();

function DrawCanvas() {

  for (x = 0; x < width; x  ) {
    for (y = 0; y < height; y  ) {
      for (let node of nodes[x][y].neighbours) {
        ctx.beginPath();
        ctx.moveTo(x * s   (s / 2), y * s   (s / 2));
        ctx.lineTo(node.x * s   (s / 2), node.y * s   (s / 2));
        ctx.lineWidth = 5;
        ctx.strokeStyle = "navy";
        ctx.stroke();
      }
    }
  }

  for (x = 0; x < width; x  ) {
    for (y = 0; y < height; y  ) {
      if (nodes[x][y] == start) {
        ctx.fillStyle = "crimson";
      } else if (nodes[x][y] == end) {
        ctx.fillStyle = "green";
      } else if (nodes[x][y].visited) {
        ctx.fillStyle = "blue";
      } else if (nodes[x][y].obstacle) {
        ctx.fillStyle = "grey";
      } else {
        //ctx.fillStyle = x % 2 != y % 2 ? "lightgrey" : "darkgrey";
        ctx.fillStyle = "navy";
      }
      ctx.fillRect(x * s   5, y * s   5, s - 10, s - 10);

    }
  }
}

if (end != null) {
  p = end;
  while (p.parent != null) {
    ctx.beginPath();
    ctx.moveTo(p.x * s   (s / 2), p.y * s   (s / 2));
    ctx.lineTo(p.parent.x * s   (s / 2), p.parent.y * s   (s / 2));
    ctx.lineWidth = 5;
    ctx.strokeStyle = "yellow";
    ctx.stroke();
    p = p.parent;
  }
}


function Node(x, y) {
  this.obstacle = false;
  this.visited = false;
  this.globalGoal = 1000000;
  this.localGoal = 1000000;
  this.x = x;
  this.y = y;
  this.neighbours = [];
  this.parent = null;
}

function distance(a, b) {
  return Math.sqrt((b.x - a.x) ** 2   (b.y - a.y) ** 2)
}

function heuristic(a, b) {
  return distance(a, b);
}

body
{
  background: black;
}

CodePudding user response：

In line where you set current variable you have a typo
There should be start.localGoal = 0; and not start.localGlobal = 0;

width = 11;
height = 9;

s = 50;

c = document.createElement("canvas");
document.body.appendChild(c);
ctx = c.getContext("2d");
c.width = width * s;
c.height = height * s;

nodes = [];

for (let x = 0; x < width; x  ) {
    nodes[x] = [];
    for (let y = 0; y < height; y  ) {
        nodes[x].push(new Node(x, y));
    }
}

SetNeighbours();

function SetNeighbours() {
    for (let x = 0; x < width; x  ) {
        for (let y = 0; y < height; y  ) {
            if (x > 0) {
                nodes[x][y].neighbours.push(nodes[x - 1][y])
            }
            if (x < width - 1) {
                nodes[x][y].neighbours.push(nodes[x   1][y])
            }
            if (y > 0) {
                nodes[x][y].neighbours.push(nodes[x][y - 1])
            }
            if (y < height - 1) {
                nodes[x][y].neighbours.push(nodes[x][y   1])
            }
        }

    }
}

nodes[3][0].obstacle = true;
nodes[3][1].obstacle = true;
nodes[3][2].obstacle = true;
nodes[3][3].obstacle = true;
nodes[3][4].obstacle = true;
nodes[3][5].obstacle = true;


nodes[7][3].obstacle = true;
nodes[7][4].obstacle = true;
nodes[7][5].obstacle = true;
nodes[7][6].obstacle = true;
nodes[7][7].obstacle = true;
nodes[7][8].obstacle = true;

start = nodes[1][1];
end = nodes[9][7];

//end.parent = nodes[9][6];
//nodes[9][6].parent = nodes[9][5]

start.localGoal = 0;
start.globalGoal = heuristic(start, end);
current = start;

notTested = [];
notTested.push(start);

while (notTested.length > 0 && current !== end) {

    notTested.sort(function (a, b) {
        return a.globalGoal < b.globalGoal
    });
    while (notTested.length > 0 && notTested[0].visited) {
        notTested.shift();
    }

    if (notTested.length === 0) {
        break;
    }

    const current = notTested[0];
    current.visited = true;

    for (let n of current.neighbours) {
        if (!n.visited && !n.obstacle) {
            notTested.push(n);
        }

        const newGoal = current.localGoal   distance(current, n);

        if (newGoal < n.localGoal) {
            n.parent = current;
            n.localGoal = newGoal;
            n.globalGoal = n.localGoal   heuristic(n, end);
        }

    }
}

DrawCanvas();

function DrawCanvas() {

    for (let x = 0; x < width; x  ) {
        for (let y = 0; y < height; y  ) {
            for (let node of nodes[x][y].neighbours) {
                ctx.beginPath();
                ctx.moveTo(x * s   (s / 2), y * s   (s / 2));
                ctx.lineTo(node.x * s   (s / 2), node.y * s   (s / 2));
                ctx.lineWidth = 5;
                ctx.strokeStyle = "navy";
                ctx.stroke();
            }
        }
    }

    for (let x = 0; x < width; x  ) {
        for (let y = 0; y < height; y  ) {
            if (nodes[x][y] === start) {
                ctx.fillStyle = "crimson";
            } else if (nodes[x][y] === end) {
                ctx.fillStyle = "green";
            } else if (nodes[x][y].visited) {
                ctx.fillStyle = "blue";
            } else if (nodes[x][y].obstacle) {
                ctx.fillStyle = "grey";
            } else {
                //ctx.fillStyle = x % 2 != y % 2 ? "lightgrey" : "darkgrey";
                ctx.fillStyle = "navy";
            }
            ctx.fillRect(x * s   5, y * s   5, s - 10, s - 10);

        }
    }
}

if (end != null) {
    p = end;
    while (p.parent != null) {
        ctx.beginPath();
        ctx.moveTo(p.x * s   (s / 2), p.y * s   (s / 2));
        ctx.lineTo(p.parent.x * s   (s / 2), p.parent.y * s   (s / 2));
        ctx.lineWidth = 5;
        ctx.strokeStyle = "yellow";
        ctx.stroke();
        p = p.parent;
    }
}


function Node(x, y) {
    this.obstacle = false;
    this.visited = false;
    this.globalGoal = 1000000;
    this.localGoal = 1000000;
    this.x = x;
    this.y = y;
    this.neighbours = [];
    this.parent = null;
}

function distance(a, b) {
    return Math.sqrt((b.x - a.x) ** 2   (b.y - a.y) ** 2);
}

function heuristic(a, b) {
    return distance(a, b);
}

body
{
  background: black;
}