Occasional sub-optimal paths returned

[Reousa]

Implementation returns sub-optimal paths in rare occasions.

Example: The path to the right side is sub-optimal.

This is due to the implementation skipping neighbor nodes in the closedSet without checking their comparative gCost to the currently opened cell's selected neighbor, resulting in a neighbor with a higher cost occasionally being selected.

Code illustration & proposed fix: Starting at line 44 in episode 4

                foreach (Node neighbour in grid.GetNeighbours(currentNode)) {
                    if (!neighbour.walkable || closedSet.Contains(neighbour)) {
                        continue;
                    }

                    int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                    if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {

Fix:

                foreach (Node neighbour in grid.GetNeighbours(currentNode)) {
                    if (!neighbour.walkable || (closedSet.Contains(neighbour) && newMovementCostToNeighbour >= neighbour.gCost)) {
                        continue;
                    }

                    int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
                    if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour)) {

[PeterBengtson]

Your fix uses the value of newMovementCostToNeighbour before it is declared. Is this code really correct?

[Reousa]

I declare it at the start of the foreach loop as I have a slightly differen implementation:

                    foreach (Cell neighbour in mapGrid.GetNeighbours(currentCell))
                    {
                        int newMovementCostToNeighbour = currentCell.gCost + GetDistance(currentCell, neighbour);

                        if (neighbour.cellTypeRaw == (byte)CellType.Unwalkable || (closedSet.Contains(neighbour) && newMovementCostToNeighbour >= neighbour.gCost))
                        {
                            continue;
                        }

                        if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
                        {
                            neighbour.gCost = newMovementCostToNeighbour;
                            neighbour.hCost = GetDistance(neighbour, targetCell);
                            neighbour.parent = currentCell;

                            if (!openSet.Contains(neighbour))
                                openSet.Add(neighbour);
                            else
                                openSet.UpdateItem(neighbour);
                        }
                    }

Though after debugging further & calculating by hand it turned out this wasn't the real issue (even though adding the check had fixed it, it came up elsewhere later), but rather another modification I made to the implementation.

For reference, there's no reason to use this check in Sebastian's implementation. This repo works perfectly fine as-is.

Appologies for not clarifying prior to closing. :)