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.
