The misleading A*(A-star) algorithm inaccurately produces faulty routes and ultimately collapses

Question

The misleading A*(A-star) algorithm inaccurately produces faulty routes and ultimately collapses

I am currently working on implementing the A*(A-star) algorithm in react.js, but I am facing a problem. Whenever the startNode (green) or destinationNode (blue) have more than one neighbour or if there is a cycle in the graph, my program crashes. There seems to be an issue with adding and deleting neighbours from/to the openList or when updating the parentId in the getPath() function. Unfortunately, I cannot even see the console output because the website goes down. Each node has the following properties: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null. I am sending the path to another component called "TodoList" which then prints out the path. However, instead of returning the path, my program keeps updating the path as I add nodes and edges to the list. Any help would be greatly appreciated, as I have been stuck on this for hours:/

Here is 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 the destination 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 used for heuristic and gScore. Here I am using Manhattan distance instead of Euclidean 
        //because in this example we don't have diagonal paths.
        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 on new issue:

Pictures of before and after linking a new node. When I update the graph and add a new node, the path disappears. Sometimes it comes back, sometimes not, especially when I add new nodes and edges to the graph. As I mentioned earlier, each node has the following properties: id, name, x, y, connectedToIdsList:[], gcost:Infinity, fcost:0, heuristic:0, parentId:null.

https://i.stack.imgur.com/nqNEB.png

https://i.stack.imgur.com/FnrEx.png

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).name];
            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
        }

        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
};

javascript reactjs data-structures graph a-star

Answer 1

Answer №1

There are a few issues in your code that need to be addressed:

The line return originLocationId; should not be included. If the source and target are equal, you should set the path accordingly and ensure that the final return statement of this function executes, as it is intended to return the div element.
When the target node is found within the loop, not only should the path be constructed, but the loop should also be terminated. To accomplish this, add a break statement inside the loop.
The line
```
currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
```
is incorrect. Modifying the value of currentNode.gcost based on its outgoing edge to the neighbor node is undesirable. Instead, assign the sum of these values to a temporary variable, such as gcost.
The comparison involving neighbourNode.gcost will not work when the neighbor node does not yet possess a gcost attribute. Based on your code, it seems like there is no default value assigned to guarantee that this condition evaluates to true. Therefore, consider using a default value, for example,
```
(neighbourNode.gcost ?? Infinity)
```
.
The line
```
path = path.reverse().join("->");
```
would ideally be executed under all circumstances, including situations where no solution exists (i.e., the path is an empty string) or when the source and target nodes are identical.

Here is a revised version of your code, slightly modified to function correctly as a runnable snippet:

function render() {
    const {
        destinationLocationId,
        locations,
        originLocationId
    } = this.props;
    let path = [];
    
    if (destinationLocationId !== null && originLocationId !== null) {
        path = [originLocationId]; 
        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; 
                    }
                    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;
                            neighbourNode.gcost = gcost; 
                            neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
                            neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
                            addNeighbourNodeToOpenList(neighbourNode, openList);
                        }
                    }
                }
            }
        }
    }
    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;
}

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}));

Answer 2

There are a few issues in your code that need to be addressed:

The line return originLocationId; should not be included. If the source and target are equal, you should set the path accordingly and ensure that the final return statement of this function executes, as it is intended to return the div element.
When the target node is found within the loop, not only should the path be constructed, but the loop should also be terminated. To accomplish this, add a break statement inside the loop.
The line
```
currentNode.gcost = currentNode.gcost + manhattanDistance(currentNode, neighbourNode);
```
is incorrect. Modifying the value of currentNode.gcost based on its outgoing edge to the neighbor node is undesirable. Instead, assign the sum of these values to a temporary variable, such as gcost.
The comparison involving neighbourNode.gcost will not work when the neighbor node does not yet possess a gcost attribute. Based on your code, it seems like there is no default value assigned to guarantee that this condition evaluates to true. Therefore, consider using a default value, for example,
```
(neighbourNode.gcost ?? Infinity)
```
.
The line
```
path = path.reverse().join("->");
```
would ideally be executed under all circumstances, including situations where no solution exists (i.e., the path is an empty string) or when the source and target nodes are identical.

Here is a revised version of your code, slightly modified to function correctly as a runnable snippet:

function render() {
    const {
        destinationLocationId,
        locations,
        originLocationId
    } = this.props;
    let path = [];
    
    if (destinationLocationId !== null && originLocationId !== null) {
        path = [originLocationId]; 
        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; 
                    }
                    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;
                            neighbourNode.gcost = gcost; 
                            neighbourNode.heuristic = manhattanDistance(neighbourNode, destinationNode);
                            neighbourNode.fcost = neighbourNode.gcost + neighbourNode.heuristic;
                            addNeighbourNodeToOpenList(neighbourNode, openList);
                        }
                    }
                }
            }
        }
    }
    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;
}

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}));

The misleading A*(A-star) algorithm inaccurately produces faulty routes and ultimately collapses

Answer №1

Similar questions

Is it possible for a user to modify the JavaScript code on a website?

One issue encountered in the AngularJS library is that the default value does not function properly in the select element when the value and

subscribing to multiple observables, such as an observable being nested within another observable related to HTTP requests

Automatically switch slides and pause the carousel after completing a loop using Bootstrap 5 Carousel

Ensure that the alert for an Ajax JSON record count remains active when the count is

Acquiring mapping information through JSON data retrieval

Is it possible to utilize the output of a function nested within a method in a different method?

Monitor a user's activity and restrict the use of multiple windows or tabs using a combination of PHP and

React Native - state hook refreshes and causes the component to re-render, yet no changes are visible

Exploring the optimal placement and techniques for testing an ESC keydown event within a modal component

An issue encountered with getServerSideProps in NextJS 12 is causing a HttpError stating that cookies are not iterable, leading

How can I create distinct component IDs effectively with the Catberry Framework?

Example of fetching Pubnub history using AngularJS

Ways to handle errors when using navigator.clipboard.writeText

Executing Client-Side Function Upon Data Retrieval in a Node.js Application

Exploring the Wonderful World of Styled Components

Implementing CSS keyframes when a specified PHP condition is satisfied

What is the procedure for verifying the type of an element using chai?

React and Redux: Error Alert - A change in state was detected during dispatch operations

Exploring the functionality of closing Material UI Drawer on escape key in a React 16 app with RTL support