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;
}