0
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ print out the tiles it is exploring and see what happens. My guess is that the closedList.Contains call always returns false and will then loop forever. \$\endgroup\$ – ratchet freak Mar 22 '16 at 12:34
  • \$\begingroup\$ @ratchetfreak It appears that that is the case. Some tiles are explored once while others are explored up to 100 times. How would I check if the closed list contains the tile already if .contains return false? \$\endgroup\$ – DarkDestry Mar 22 '16 at 12:42
  • \$\begingroup\$ I assume the problem is in tiles ending up on your openlist multiple times rather than being on your closedlist. They only get added to your closed list after they have been on your open list, nothing is stopping tiles from being added to the open list multiple times \$\endgroup\$ – Niels Mar 22 '16 at 12:46
  • \$\begingroup\$ Normally you would change the equals method (or similar) of Tile so it only compares the localX and localY fields. \$\endgroup\$ – ratchet freak Mar 22 '16 at 12:46
  • 1
    \$\begingroup\$ This isn't Dijkstra's algorithm, this is (a buggy and low-performance) breadth-first search. This makes me unsure what kind of help you need. Do you want to make this a correct implementation of (depth- or) breadth-first search (enumerates all connected tiles), or a correct implementation of Dijkstra's algorithm (finds shortest paths to all connected tiles)? Either way, this is algorithms 101, which should be answered adequately on Stack Overflow - it doesn't look like your issues here are game-specific. \$\endgroup\$ – DMGregory Mar 22 '16 at 13:02
2
\$\begingroup\$

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. :)

\$\endgroup\$
0
\$\begingroup\$

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);} );
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.