Optimisations to A*star Search Algorithm on 2D Array with Walls

Question

I'm trying to implement the A*star Search Algorithm and I was successful with it, however it sometimes does not produce the optimal shortest path, I was wondering if I could optimise the algorithm to produce a better shortest path? (I mean the shortest path isn't actually the shortest path)

At the moment I am keeping track of the Parent Node for each neighbour to find the shortest path, I think this is where the problem lies and so when I add the FinishNode last to the VisitedNodesInOrder array, I can access the parent that got us to that cell the fastest, and I keep going back until I reach the startNode in which case the parent is null.

It doesn't work as intended when there are walls, because it doesn't see the walls until it reaches them and so it takes a non-optimal path, so when I am tracing back from the FinishNode, it follows the non-optimal path.

Is this suppose to work like this? Or is there a way for the Algorithm to consider the walls before trying to take the non-optimal path?

The grid is made up of a 2D Array of Node Object, which has a row, col and NodeType Property.

The neighbour of each Node consists of the 4 cells next to it (left, right, top, bottom)

const aStar = (grid, startNode, finishNode) => {
    const n = grid.length;
    const m = grid[0].length;

    const endRow = finishNode.row;
    const endCol = finishNode.col;


    const visitedNodesInOrder = [];

    const pq = new PriorityQueue((a, b) => a.distance < b.distance);

    startNode.parent = null;

    //Store in an object {node: {row, col, parent}, distance: x}
    //Distance refers to distance to FinishNode

    pq.push({node: startNode, distance: Math.abs(endRow - startNode.row) + Math.abs(endCol - startNode.col)});

    while(!pq.isEmpty()){
        const {node} = pq.pop();

        const row = node.row;
        const col = node.col;
        const parent = node.parent;

        if(grid[row][col].nodeType == NodeType.VISITED_NODE){
            continue;
        }

        if (grid[row][col].nodeType === NodeType.FINISH_NODE) {
            visitedNodesInOrder.push({row, col, parent});
            break;
        }

        if (grid[row][col].nodeType === NodeType.WALL_NODE) {
            continue;
        }

        if (row < n - 1) {
            pq.push({node: {row: row + 1, col, parent: {row, col}}, distance: Math.abs(endRow - row + 1) + Math.abs(endCol - col)});
        }

        if (row > 0) {
            pq.push({node: {row: row - 1, col, parent: {row, col}}, distance: Math.abs(endRow - row - 1) + Math.abs(endCol - col)});
        }

        if (col < m - 1) {
            pq.push({node: {row: row, col: col + 1, parent: {row, col}}, distance: Math.abs(endRow - row) + Math.abs(endCol - col + 1)});
        }

        if (col > 0) {
            pq.push({node: {row: row, col: col - 1, parent: {row, col}}, distance: Math.abs(endRow - row) + Math.abs(endCol - col - 1)});
        }

        if (grid[row][col].nodeType === NodeType.EMPTY_NODE) {
            visitedNodesInOrder.push({row, col, parent: parent});
            grid[row][col].nodeType = NodeType.VISITED_NODE;
        }

    }

    return visitedNodesInOrder
};

The Blue in the picture represents visitedNodes, The black being the walls and the yellow path is the "shortest" path.

do you have some data, where the algo doesn't give the optimal result? — Nina Scholz, Oct 29 '19 at 09:24
Updated the post, I accidentally pasted old code. The main problem was with the walls, and also added a picture because I'm not sure if i can really show the data since the 2D Array is quite large? — , Oct 29 '19 at 09:35
The A* algorithm *does not* give you the shortest path, it is only (a pretty good) approximation. If you want the optimal shortest path, use Dijkstra's algorithm (for weighted edges), or Breadth-First Search (for unweighted edges, faster than Dijkstra). — Emily, Oct 29 '19 at 18:26
@Emily A* gives you shortest path if the heuristics used is reflecting real movement behavior ... — Spektre, Oct 29 '19 at 20:55
@WaqasAbbasi If the result is not shortest path then you either have a bug in code or used wrong heuristics (costs per movement) if it helps here is mine (for comparison) [How to speed up A* algorithm at large spatial scales?](https://stackoverflow.com/a/23779490/2521214) — Spektre, Oct 29 '19 at 20:58
@Spektre Thank you, I will check it out. I think the problem is not that there is a bug, the problem is that the A* Algorithm does not see the walls, so until it actually reaches a wall It thinks that it's taking the optimal path. If I remove the walls, it takes the shortest path. Do you think there's a way for me to implement the algorithm in a way that takes the walls into account? — , Oct 30 '19 at 09:09
@WaqasAbbasi if your code would not see the walls then it would go through them. This is more likely a bug in the assigning of costs. You should chose the smaller cost on already visited cells. I suspect you are blindly overwriting without checking first but too lazy to go through your code. But from a quick look you are creating the path at the same time as filling the grid that is wrong for raster maps. You need to first fill until hit the target cell and then reconstruct the path ... see [Backtracking in A star](https://stackoverflow.com/a/28317199/2521214) — Spektre, Oct 30 '19 at 09:16
@Spektre The code sees the wall. However the cost for A* search does not take the location of the walls into account when making the next move. So if there is a wall infront of a node, the algorithm won't consider that wall Until it's right next to it, in which case it has to go around it. I will look into the link, I think what you are suggesting is right about filling first and reconstructing the path afterwards and that might solve this issue — , Oct 30 '19 at 09:27
@WaqasAbbasi yep then this is not raster A* ... more like weird port of graph Dijkstra's/A* which does not work well for raster. You should use your map (empty space ... no need to add any other array) and fill it with costs instead prior the reconstruction of path. What you're doing is more like right/left hand maze rule which is far from optimal — Spektre, Oct 30 '19 at 09:42
A* works fine, but the algorithm you've implemented here is not A*, and not enough like A* that I could tell you what to fix except to say "go back and implement A* instead". You don't even keep track of the shortest discovered path length to each node, which is pretty fundamental to the whole thing. — Matt Timmermans, Oct 31 '19 at 12:06
@MattTimmermans Thank you for the feedback, I will try to do more research and try to re-implement it. I did initially try to implement it the way you suggested but for some reason couldn't get it to work, but I will try again. — , Oct 31 '19 at 13:06

Optimisations to A*star Search Algorithm on 2D Array with Walls

0 Answers0