In my XNA game I'm implementing A* as part of enemy behavior, using my own generic PriorityQueue class. However, the implementation is way too time consuming - to the point where less than a second in game time takes ~5 seconds of real time. What exactly is so time consuming, and how to change that?
Priority is expressed as an int instead of a float because when I tried doing it with a float the game wouldn't even start.
I suspect that the number of operations is the problem. At the end of the last frame, the number of evaluated nodes (for finding a path from (100, 100) to (0,0) without obstecles) was ~800 or 305, after I've changed the size of the grid square size from 1 to 5. This improved the framerate drop, but still, it was nowhere near smooth.
Most articles and stack exchange questions on the subject suggest implementing a tie breaker, I've tried multiplying my h() score by 1.1, 1.01 and 1.0001 and none changed anything about the result. There's probably something there that I misunderstood.
Another probable option is that my PriorityQueue is not efficient enough. Admittedly, I don't know how to make it more efficient and would like suggestions.
Enemy members and Chase method:
#region data
private IFocusable Target { get; set; }
private Map WorldMap { get; set; }
#endregion
#region methods
protected void Chase(GameTime gameTime)
{
PriorityQueue<Vector2> openSet = new PriorityQueue<Vector2>();
List<Vector2> closedSet = new List<Vector2>();
Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>();
Dictionary <Vector2, int> gScores = new Dictionary<Vector2, int>();
openSet.Enqueue(Heuristic(Position, Target.Position), Tools.RoundDown(Position));
gScores.Add(Position, 0);
while(openSet.Count != 0)
{
Vector2 current = openSet.Dequeue();
if (current == Tools.RoundDown(Target.Position))
{
Position = ReconstructPath(cameFrom, current);
break;
}
closedSet.Add(current);
List<Vector2> neighbours = WorldMap.GetNeighbours(current, Speed);
foreach (Vector2 neighbour in neighbours)
{
if (closedSet.Contains(neighbour))
continue;
int tenativeGScore = gScores[current] + (int)Vector2.Distance(current, neighbour);
if (openSet.Contains(neighbour) == -1 || tenativeGScore < gScores[neighbour])
{
cameFrom[neighbour] = current;
gScores[neighbour] = tenativeGScore;
int fScore = tenativeGScore + Heuristic(neighbour, Target.Position);
openSet.Enqueue(fScore, neighbour);
}
}
}
}
private Vector2 ReconstructPath(Dictionary<Vector2, Vector2> cameFrom, Vector2 currentNode)
{
if (cameFrom[currentNode] == Position)
return currentNode;
else
return ReconstructPath(cameFrom, cameFrom[currentNode]);
}
//Heuristic: distance between neighbour and target, rounded down.
private int Heuristic(Vector2 current, Vector2 goal)
{
return (int)Vector2.Distance(current, Tools.RoundDown(goal));
}
#endregion
}
PriorityQueue:
public class PriorityQueue<T> where T : IEquatable<T>
{
#region data
private List<Tuple<int, T>> Items { get; set; }
public int Count {get{return Items.Count;}}
private bool Sorted { get; set; }
#endregion
#region c'tor
public PriorityQueue()
{
this.Items = new List<Tuple<int,T>>();
this.Sorted = true;
}
#endregion
#region methods
private int SortingMethod(Tuple<int, T> x, Tuple<int, T> y)
{
if (x == null || y == null)
throw new ArgumentNullException();
return x.Item1 - y.Item1;
}
public void Enqueue(Tuple<int, T> item)
{
int index = Contains(item.Item2);
if (index == -1)
{
Items.Add(item);
Sorted = false;
}
else
Items[index] = item;
}
public void Enqueue(int key, T value)
{
Enqueue(new Tuple<int,T>(key, value));
}
public T Dequeue()
{
if(!Sorted)
{
Items.Sort(SortingMethod);
Sorted = true;
}
Tuple<int, T> item = Items[0];
Items.RemoveAt(0);
return item.Item2;
}
public int Contains(T value)
{
for (int i = 0; i < Items.Count; i++ )
if (Items[i].Equals(value))
return i;
return -1;
}
#endregion
}
The relevant members of Map (a class that represents a map of squares the enemy navigates on. I didn't come around to implementing a mechanic where the enemy avoids blocked squares.):
#region data
private int SquareSize { get; set; }
private List<Vector2> BlockedSquares { get; set; }
private Rectangle Bounds { get; set; }
#endregion
public List<Vector2> GetNeighbours(Vector2 vector, int speed)
{
Vector2[] directions = new Vector2[8];
List<Vector2> neighbours = new List<Vector2>();
directions[0] = Tools.RoundDown(Vector2.UnitX);//right
directions[1] = Tools.RoundDown(Vector2.UnitX);//left
directions[2] = Tools.RoundDown(Vector2.UnitY);//down
directions[3] = Tools.RoundDown(Vector2.UnitY);//up
directions[4] = Tools.RoundDown(Vector2.UnitX + Vector2.UnitY);//down right
directions[5] = Tools.RoundDown(-Vector2.UnitX + Vector2.UnitY);//down left
directions[6] = Tools.RoundDown(Vector2.UnitX - Vector2.UnitY);//up right
directions[7] = Tools.RoundDown(-Vector2.UnitX - Vector2.UnitY);//up left
for (int i = (int)vector.X - speed; i <= (int)vector.X + speed; i += SquareSize)
{
for(int j = (int)vector.Y - speed; j <= (int)vector.Y + speed; j += SquareSize)
{
Vector2 point = new Vector2(i, j);
if (point == vector)
continue;
else if (Vector2.Distance(vector, point) <= speed)
neighbours.Add(point);
}
}
return neighbours;
}
public Vector2 InSquare(Vector2 vector)
{
int x = (int)vector.X, y = (int)vector.Y;
x -= x % SquareSize;
y -= y % SquareSize;
return new Vector2(x, y);
}
Hopefully this answer won't help just me, but also many programmers that will struggle with similar questions in the future.
Thanks in advance.
The reason for slowdown was using inefficient containment checks. Data types with fast containment checks, like binary search trees, HashSets, etc.
In the case of closedSet, I used a List instead of a HashSet:
List<Vector2> closedSet = new List<Vector2>();
Will be changed to:
HashSet<Vector2> closedSet = new HashSet<Vector2>();
Nothing else needs to be changed about closedSet since both types have Add and Contains functions.
For gScores, the problem is that I use ContainsKey instead of the more efficient TryGetValue. Based on this answer.
if (openSet.Contains(neighbour) == -1 || tenativeGScore < gScores[neighbour])
Needs to be changed to:
float gScore;//Current gScores[neighbour] value, if there's any.
if(gScores.TryGetValue(neighbour, out gScore) || tenativeGScore < gScore)