BFS search function

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 FindPath(Cell A, Cell B)
{
    var parent = new Dictionary();

    List queue = new List();
    List visited = new List();

    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 path = new List();

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

    return path;
}

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.

StackExchange Code Review Q#91820, answer score: 7