BFS search function

Question

By profiling my application, I found that the bottleneck of my application is the function below. In particular it will be executed by a lot of entities (monsters) in a game, that will go onto a smartphone.

The graph is the model for this type of grid: (the final one is 25x45)

Also, each cell has an array of 4 pointers: if the cell IsNorthPassable, it has a pointer to the Up cell, if not, null.

If I should be more precise on the other classes involved, please let me know.

private List<Cell> FindPath(Cell A, Cell B)
{
    var parent = new Dictionary<Cell, Cell>();

    List<Cell> queue = new List<Cell>();
    List<Cell> visited = new List<Cell>();

    queue.Add(A);
    parent.Add(A, null);

    while (queue.Count != 0)
    {
        Cell c = queue[0];
        queue.RemoveAt(0);

        visited.Add(c);

        if (c == B)
            break;

        foreach (Cell near in c.Links)
        {
            if (near != null)
            {
                if (!visited.Contains(near))
                {
                    parent.Add(near, c);
                    visited.Add(near);
                    queue.Add(near);
                }
            }
        }
    }

    List<Cell> path = new List<Cell>();

    if (parent.ContainsKey(B))
    {
        Cell backTrack = B;
        do
        {
            path.Add(backTrack);
            backTrack = parent[backTrack];
        }
        while (backTrack != null);
        path.Reverse();
    }

    return path;
}

Answer 1

I suggest you add a simple heuristic (Manhattan will do) and transform it into a A* algorithm this will reduce the number of nodes you need to explore.

queue.RemoveAt(0);

This can take \$O(n)\$ time, not something you typically want inside a loop. Instead use a data structure that allows \$O(1)\$ (or \$O(log n)\$) popFront.

You can also attempt to reduce the number of times the algorithm needs to run. For example, by caching the results and using those cached paths to calculate the new paths.

If multiple monsters have the same target you can instead flood-fill from that target. When you hit a monster you can add the path from that monster to the target.

Answer 2

Beside's @ratchet freak's suggestion to use a more suitable data structure for queue (e.g. a Queue<Cell>), you can change visited.Contains(near) from an \$O(n)\$ operation to an \$O(1)\$ operation by making visited a HashSet<Cell>.

Once you've changed it to a HashSet<Cell>, the Add method returns a bool indicating whether the item was added to the set, so you could change this

if (!visited.Contains(near))
{
    parent.Add(near, c);
    visited.Add(near);
    queue.Add(near);
}

to the slightly cleaner

if (visited.Add(near))
{
    parent.Add(near, c);
    queue.Add(near);
}

Answer 3

Looking at the code I don't see anything strange.

Regarding the optimization of the search in terms of speed I would suggest to use the Iterative Deepening algorithm with a heuristic function (the slope of the line that connects point A and point B can be used to build a good heuristic function).

For more info/help I would suggest asking in Stack Overflow though, as I don't know if this is the right site for it.

Answer 4

I have spent a lot of time optimizing path-finding code. The most important thing is to only run the path-finder as often as you need to:

• If all your monsters begin or end at the same place, you can run BFS once over the entire graph, and cache the results. Then finding the direction a monster needs to move is always O(1).
• For the majority of games, an approximation to the shortest path is acceptable. HPA* is a fantastic algorithm for this which is easy to program and understand. See this post for other options.

As for your specific implementation:

• As already mentioned, make sure you are using the correct data structures, a Queue for the queue and a Set for the visited nodes.
• It's fairly simple to transform this into A*, which should have better performance. You will need to replace your queue with a priority queue. I have written one for C# that has been highly-optimized for path-finding. You can find it here.
  Also, make sure you use the correct tie-breaking criteria.

Answer 5

not really much for making this more efficient as it is for making it a little prettier, try not to nest more than you have to.

    foreach (Cell near in c.Links)
    {
        if (near != null)
        {
            if (!visited.Contains(near))
            {
                parent.Add(near, c);
                visited.Add(near);
                queue.Add(near);
            }
        }
    }

you should merge the two if statements inside this for loop like this

foreach (Cell near in c.Links)
{
    if ((near != null) && (!visited.Contains(near)))
    {
        parent.Add(near, c);
        visited.Add(near);
        queue.Add(near);
    }
}