javascriptreactjsdata-structuresgrapha-star
A*(A-star) algorithm gives wrong path and crashes
I'm implementing A*(A-star) algorithm in react.js but my program crashes whenever startNode(green) or destinationNode(blue) have more than one neighbour or if there is a cycle in the graph. There is something wrong when adding and deleting the neighbours from/to openList or when updating the parentId in the getPath() function. I cant even see the console because the website goes down. Each node has: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null. I'm sending the path to another component "TodoList" which prints out the path. My program should not return the path but keeps updating the path as i'm adding nodes and edges to the list. Please help, I've been stuck for hours now:/
My code:
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
this.state = { shortestPath: [] }
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
let path = []
if (destinationLocationId != null && originLocationId != null) {
if (originLocationId == destinationLocationId) { //check if the startNode node is the end node
return originLocationId;
}
var openList = [];
let startNode = getNodeById(originLocationId);
let destinationNode = getNodeById(destinationLocationId)
if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) { //check if start and destination nodes are connected first
startNode.gcost = 0
startNode.heuristic = manhattanDistance(startNode, destinationNode)
startNode.fcost = startNode.gcost + startNode.heuristic;
//perform A*
openList.push(startNode); //starting with the startNode
while (openList.length > 0) {
console.log("inside while")
var currentNode = getNodeOfMinFscore(openList); //get the node of the minimum f cost of all nodes in the openList
if (currentIsEqualDistanation(currentNode)) {
path = getPath(currentNode);
}
deleteCurrentFromOpenList(currentNode, openList);
for (let neighbourId of currentNode.connectedToIds) {
var neighbourNode = getNodeById(neighbourId);
currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
if (currentNode.gcost < neighbourNode.gcost) {
neighbourNode.parentId = currentNode.id; // keep track of the path
// total cost saved in neighbour.g
neighbourNode.gcost = currentNode.gcost;
neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic; //calculate f cost of the neighbourNode
addNeighbourNodeToOpenList(neighbourNode, openList);
}
}
}
path = path.reverse().join("->");
}
}
function addNeighbourNodeToOpenList(neighbourNode, openList) {
//add neighbourNode to the open list to be discovered later
if (!openList.includes(neighbourNode)) {
openList.push(neighbourNode);
}
}
function deleteCurrentFromOpenList(currNode, openList) {
const currIndex = openList.indexOf(currNode);
openList.splice(currIndex, 1); //deleting currentNode from openList
}
function currentIsEqualDistanation(currNode) {
//check if we reached out the distanation node
return (currNode.id == destinationLocationId)
}
function getNodeById(nid) {
var node;
for (let i = 0; i < locations.length; i++) {
if (locations[i].id == nid) {
node = locations[i]
}
}
return node
}
function getPath(destNode) {
console.log("inside getpath")
var parentPath = []
var parent;
while (destNode.parentId != null) {
parentPath.push(destNode.name)
parent = destNode.parentId;
destNode = getNodeById(parent);
}
//adding startNode to the path
parentPath.push(getNodeById(originLocationId).name)
return parentPath;
}
function getNodeOfMinFscore(openList) {
var minFscore = openList[0].fcost; //initValue
var nodeOfminFscore;
for (let i = 0; i < openList.length; i++) {
if (openList[i].fcost <= minFscore) {
minFscore = openList[i].fcost //minFvalue
nodeOfminFscore = openList[i]
}
}
return nodeOfminFscore
}
//manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean
//because in this example we dont have diagnosal path.
function manhattanDistance(stNode, dstNode) {
var x = Math.abs(dstNode.x - stNode.x);
var y = Math.abs(dstNode.y - stNode.y);
var dist = x + y;
return dist;
}
return (
<div className="turn-by-turn-component">
<TodoList
list={"Shortest path: ", [path]}
/>
<TodoList
list={[]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};Update new issue Pictures of before and after linking a new node. When I update the graph and add a new node the path disappears. And sometimes come back and so on if I still add new nodes and edges to the graph. As I said, each node has: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null. My new code now is:
export default class TurnByTurnComponent extends React.PureComponent {
constructor(props) {
super(props);
this.state = { shortestPath: [] }
}
render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
let path = []
if (destinationLocationId != null && originLocationId != null) {
console.log(JSON.stringify(locations))
path = [getNodeById(originLocationId).namne];
if (originLocationId != destinationLocationId) {
var openList = [];
let startNode = getNodeById(originLocationId);
let destinationNode = getNodeById(destinationLocationId)
if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {
startNode.gcost = 0
startNode.heuristic = manhattanDistance(startNode, destinationNode)
startNode.fcost = startNode.gcost + startNode.heuristic;
openList.push(startNode); //starting with the startNode
while (openList.length > 0) {
var currentNode = getNodeOfMinFscore(openList); //get the node of the minimum f cost of all nodes in the openList
if (currentIsEqualDistanation(currentNode)) {
path = getPath(currentNode);
break;
}
deleteCurrentFromOpenList(currentNode, openList);
for (let neighbourId of currentNode.connectedToIds) {
var neighbourNode = getNodeById(neighbourId);
let gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
if (gcost < (neighbourNode.gcost ?? Infinity)) {
neighbourNode.parentId = currentNode.id;
// keep track of the path
// total cost saved in neighbour.g
neighbourNode.gcost = gcost;
neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic; //calculate f cost of the neighbourNode
addNeighbourNodeToOpenList(neighbourNode, openList);
}
}
}
}
}
}
path = path.reverse().join("->");
function addNeighbourNodeToOpenList(neighbourNode, openList) {
//add neighbourNode to the open list to be discovered later
if (!openList.includes(neighbourNode)) {
openList.push(neighbourNode);
}
}
function deleteCurrentFromOpenList(currentNode, openList) {
const currIndex = openList.indexOf(currentNode);
openList.splice(currIndex, 1); //deleting currentNode from openList
}
function currentIsEqualDistanation(currentNode) {
//check if we reached out the distanation node
return (currentNode.id == destinationLocationId)
}
function getNodeById(id) {
var node;
for (let i = 0; i < locations.length; i++) {
if (locations[i].id == id) {
node = locations[i]
}
}
return node
}
function getPath(destinationNode) {
console.log("inside getpath")
var parentPath = []
var parent;
while (destinationNode.parentId != null) {
parentPath.push(destinationNode.name)
parent = destinationNode.parentId;
destinationNode = getNodeById(parent);
}
//adding startNode to the path
parentPath.push(getNodeById(originLocationId).name)
return parentPath;
}
function getNodeOfMinFscore(openList) {
var minFscore = openList[0].fcost; //initValue
var nodeOfminFscore;
for (let i = 0; i < openList.length; i++) {
if (openList[i].fcost <= minFscore) {
minFscore = openList[i].fcost //minFvalue
nodeOfminFscore = openList[i]
}
}
return nodeOfminFscore
}
//manhattan distance is for heuristic and gScore. Here I use Manhattan instead of Euclidean
//because in this example we dont have diagnosal path.
function manhattanDistance(startNode, destinationNode) {
var x = Math.abs(destinationNode.x - startNode.x);
var y = Math.abs(destinationNode.y - startNode.y);
var dist = x + y;
return dist;
}
return (
<div className="turn-by-turn-component">
<TodoList
title="Mandatory work"
list={[path]}
/>
<TodoList
title="Optional work"
list={[]}
/>
</div>
);
}
}
TurnByTurnComponent.propTypes = {
destinationLocationId: PropTypes.number,
locations: PropTypes.arrayOf(PropTypes.shape({
id: PropTypes.number.isRequired,
name: PropTypes.string.isRequired,
x: PropTypes.number.isRequired,
y: PropTypes.number.isRequired,
connectedToIds: PropTypes.arrayOf(PropTypes.number.isRequired).isRequired
})),
originLocationId: PropTypes.number
};
Solution
There are a few issues in your code:
return originLocationId;should not happen. When the source is equal to the target, then set the path, and make sure the finalreturnof this function is executed, as you want to return thedivelement.When the target is found in the loop, not only should the
pathbe built, but the loop should be exited. So add abreakcurrentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);is not right: you don't want to modifycurrentNode.gcost: its value should not depend on the outgoing edge to that neighbour. Instead store this sum in a temporary variable (likegcost)The comparison with
neighbourNode.gcostwill not work when that node does not yet have agcostmember. I don't see in your code that it got a default value that makes sure this condition is true, so you should use a default value here, like(neighbourNode.gcost ?? Infinity)path = path.reverse().join("->");should better be executed always, also when there is no solution (sopathis a string) or when the source and target are the same node.
Here is a corrected version, slightly adapted to run here as a runnable snippet:
function render() {
const {
destinationLocationId,
locations,
originLocationId
} = this.props;
let path = [];
if (destinationLocationId != null && originLocationId != null) {
path = [originLocationId]; // The value for when the next if condition is not true
if (originLocationId != destinationLocationId) {
var openList = [];
let startNode = getNodeById(originLocationId);
let destinationNode = getNodeById(destinationLocationId)
if (startNode.connectedToIds.length > 0 && destinationNode.connectedToIds.length > 0) {
startNode.gcost = 0
startNode.heuristic = manhattanDistance(startNode, destinationNode)
startNode.fcost = startNode.gcost + startNode.heuristic;
openList.push(startNode);
while (openList.length > 0) {
var currentNode = getNodeOfMinFscore(openList);
if (currentIsEqualDistanation(currentNode)) {
path = getPath(currentNode);
break; // Should end the search here!
}
deleteCurrentFromOpenList(currentNode, openList);
for (let neighbourId of currentNode.connectedToIds) {
var neighbourNode = getNodeById(neighbourId);
// Should not modify the current node's gcost. Use a variable instead:
let gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
// Condition should also work when neighbour has no gcost yet:
if (gcost < (neighbourNode.gcost ?? Infinity)) {
neighbourNode.parentId = currentNode.id;
neighbourNode.gcost = gcost; // Use the variable
neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
addNeighbourNodeToOpenList(neighbourNode, openList);
}
}
}
}
}
}
// Convert the path to string in ALL cases:
path = path.reverse().join("->");
function addNeighbourNodeToOpenList(neighbourNode, openList) {
if (!openList.includes(neighbourNode)) {
openList.push(neighbourNode);
}
}
function deleteCurrentFromOpenList(currNode, openList) {
const currIndex = openList.indexOf(currNode);
openList.splice(currIndex, 1);
}
function currentIsEqualDistanation(currNode) {
return (currNode.id == destinationLocationId)
}
function getNodeById(nid) {
var node;
for (let i = 0; i < locations.length; i++) {
if (locations[i].id == nid) {
node = locations[i]
}
}
return node
}
function getPath(destNode) {
var parentPath = []
var parentId;
while (destNode.parentId != null) {
parentPath.push(destNode.name)
parentId = destNode.parentId;
destNode = getNodeById(parentId);
}
parentPath.push(getNodeById(originLocationId).name)
return parentPath;
}
function getNodeOfMinFscore(openList) {
var minFscore = openList[0].fcost;
var nodeOfminFscore;
for (let i = 0; i < openList.length; i++) {
if (openList[i].fcost <= minFscore) {
minFscore = openList[i].fcost
nodeOfminFscore = openList[i]
}
}
return nodeOfminFscore
}
function manhattanDistance(stNode, dstNode) {
var x = Math.abs(dstNode.x - stNode.x);
var y = Math.abs(dstNode.y - stNode.y);
var dist = x + y;
return dist;
}
return "Shortest path: " + path;
}
// Demo
let props = {
locations: [
{ id: 1, x: 312, y: 152, connectedToIds: [4,2], name: "Thetaham" },
{ id: 2, x: 590, y: 388, connectedToIds: [1,3], name: "Deltabury" },
{ id: 3, x: 428, y: 737, connectedToIds: [2], name: "Gammation" },
{ id: 4, x: 222, y: 430, connectedToIds: [1], name: "Theta City" },
],
originLocationId: 1,
destinationLocationId: 3,
};
console.log(render.call({props}));- Any difference between await Promise.all() and multiple await?
- do <something> N times (declarative syntax)
- Current time formatting with Javascript
- Delete related records using pre middleware in mongoose
- Redirecting mobile users according to their OS
- Organise imports for all files in project
- How do you add non-text parts to a multiturn chat with Gemini / Vertex AI?
- How to test if a RegExp contains capturing groups in its definition?
- How to pass my createReadStream of an image file into a HTTP Post Request Body?
- JSON from api to html
- Scan QR Code value into an input field after successful scan
- Trigger a re-render when window.location.search changes
- How to use getComputedStyle with DOMParser produced document (no defaultView or window objects)?
- run javascript function on griview pageindexchanging event
- Returning a Promise from "describe" is not supported. Tests must be defined synchronously
- vue 3 both helper and comosable functions return "is not a function"
- How to capture DOM animations as lossless 60fps video with code only approach
- Listen on multiple input tags and concatenate inputs to a single output field without need to click a button
- How to use a custom font in react native with nativewind?
- React.js passing one components variables to another component and vice-versa
- Reversing words in a string using JavaScript
- This type parameter might need an `extends` constraint in typescript
- How to make text bold with sweetalert in 2018?
- React Audio Player Change current time of Audio
- Mocking a useragent in javascript?
- How can I see the event that is attached to an html element?
- Is there a way to find the event handlers of an element with Javascript?
- How to find event listeners on a DOM node using JavaScript
- Get all events handlers attached to an element
- Changing the color of a <select> depending on its value - CSS only(?)