Dijkstra's Algorithm - Infinite loop

Question

While running Dijkstra's Algorithm to assign a direction to every tile and when an object land on the tile, follow the direction to a goal. I encountered an infinite loop (or I think it is). The following is my code:

while (openList.Count > 0)
    {
        Debug.Log("Running alg");
        failsafe++;
        if (failsafe > 1000) { break; }

        Tile currentTile = openList[0];
        openList.Remove(currentTile);
        closedList.Add(currentTile);

        List<Tile> neighbours = GetNeighbours(currentTile.localX, currentTile.localY, grid);

        foreach (var neighbour in neighbours)
        {
            if (!closedList.Contains(neighbour))
            {
                neighbour.parentX = currentTile.localX;
                neighbour.parentY = currentTile.localY;
                openList.Add(neighbour);
            }
        }
    }

Under these conditions, the failsafe triggered and broke the loop. The grid is a 11x11 grid and as such by my understanding should have never reached 1000 cycles.

When the failsafe triggers, it explored 9 tiles away from the goal and the rest are unexplored.

What am I doing wrong here?

Answer 1

Aw, what the heck. I'm pretty sure this question belongs on Stack Overflow but my inner algorithm geek won't let this go without showing a classic breadth-first search implementation...

void FindShortestHopcountPaths(Tilemap map, Tile start)
{
    foreach(Tile tile in map.GetTiles())
       tile.visited = false;

    start.parent = start;
    start.visited = true;
    start.hopCount = 0;

    var queue = new Queue<Tile>();
    queue.Enqueue(start);

    while(queue.Count > 0)
    {
         var parent = queue.Dequeue();
         foreach(Tile child in parent.Neighbours)
         {
             if(child.visited)
                 continue;

             child.visited = true;
             child.parent = parent;
             child.hopCount = parent.hopCount + 1;

             queue.Enqueue(child);
         }
    }   
}

By the way, if you like geeking out over algorithms like this, there's a fantastic free course online where I learned pretty much everything I know. :)

Answer 2

Your current algorithm is not dijkstra. Instead it's breadth first floodfill with a buggy loop elimination. Dijkstra implies that you sort the open list according tot he cost of the tile.

Fixing the loop check requires something like:

if (!closedList.Exists(n => (n.localX == currentTile.localX &&
                             n.localY == currentTile.localY)))
{
    if (!openList.Exists(n => (n.localX == currentTile.localX &&
                                 n.localY == currentTile.localY)))
    {//also check the open list
        neighbour.parentX = currentTile.localX;
        neighbour.parentY = currentTile.localY;
        openList.Add(neighbour);
    } 
}

Adding the sorting requires that you keep a cost field in each Tile that is defaulted to the max value;

foreach (var neighbour in neighbours)
{
    if (!closedList.Exists(n => (n.localX == currentTile.localX &&
                                 n.localY == currentTile.localY)))
    {
        if (!openList.Exists(n => (n.localX == currentTile.localX &&
                                     n.localY == currentTile.localY)))
        {//new value
            neighbour.cost = currentTile.cost + currentTile.traverselCost;
            neighbour.parentX = currentTile.localX;
            neighbour.parentY = currentTile.localY;
            openList.Add(neighbour);
        } 
        else
        {
            auto newCost = currentTile.cost + currentTile.traverselCost;
            if(newCost < neighbour.cost){
                neighbour.cost = newCost;
                neighbour.parentX = currentTile.localX;
                neighbour.parentY = currentTile.localY;
            }
        }
    }
}
openList.sort((x, y) =>{return x.cost.CompareTo(y.cost);} );