MikeDotNet555
asked on
C# AStar (A*) algorithm perfomance improvments
Hi, I use an a* algorithm from someone else in my code, I use it alot but there is a big bottleneck in the method attached to it (single call of this method require about 15% CPU). I am looking for advices to improve it's performances.
Thanks
Thanks
private List<AStarNode> FindPathNoReduction(Point start, Point dest)
{
List<AStarNode> ptd = new List<AStarNode>();
start.Offset(-(this.Map.X), -(this.Map.Y));
dest.Offset(-(this.Map.X), -(this.Map.Y));
int destx = dest.X;
int desty = dest.Y;
int left = this.Map.Bounds.Left;
int top = this.Map.Bounds.Top;
int right = this.Map.Bounds.Right;
int bottom = this.Map.Bounds.Bottom;
int width = this.Map.Width;
int height = this.Map.Height;
UInt16[,] collisiondata = this.Map.CollisionData;
float factor = 1;
AStarNode[,] nodegrid = new AStarNode[this.Map.Width, this.Map.Height];
AStarNode endnode = new AStarNode(dest.X, dest.Y, false, false, null, 0, 0);
AStarNode startnode = new AStarNode(start.X, start.Y, false, true, null, 0, this.Heuristic.Calculate(destx, desty, start.X, start.Y) * factor);
PriorityQueueB<AStarNode> openQueue = new PriorityQueueB<AStarNode>(new AStarNodeComparer());
openQueue.Push(startnode);
float newg = 0;
int cx = 0;
int cy = 0;
AStarNode node;
int vxvy;
AStarNode cnode;
while (true)
{
if (openQueue.Count == 0)
break;
node = openQueue.Pop();
//CHeck to see if we have reached the destination
if (node.X == endnode.X && node.Y == endnode.Y)
{
//set score
this.Score = node.F;
//BUILD PATH USING REFRENCED PARENTS
ptd.Add(node);
node.X += this.Map.X;
node.Y += this.Map.Y;
if (node.Parent != null)
{
do
{
ptd.Add(node = node.Parent);
node.X += this.Map.X;
node.Y += this.Map.Y;
if (node.Parent == null)
break;
} while (true);
}
//return the final path
ptd.Reverse();
//Put the offset back in and move to path
return ptd;
}
else
{
// look for adjacent blocks that we attach to and add them to open
for (int vy = -1; vy < 2; vy++)
{
for (int vx = -1; vx < 2; vx++)
{
if (vx == 0 && vy == 0) continue; //continue if we are on the current node
cx = node.X + vx; cy = node.Y + vy;
vxvy = vx * vy;
//check for map edge
if (cy < 0 || cy > height - 1 || cx < 0 || cx > width - 1) continue;
//check for walkability and small diagonal gaps that cant be passed
if ((collisiondata[cx, cy] & 1) > 0) continue;
if (vxvy != 0 && ((collisiondata[node.X, cy] & 1) > 0)
&& ((collisiondata[cx, node.Y] & 1) > 0)) continue;
newg = node.G + SCORE[Math.Abs(vxvy)];
cnode = nodegrid[cx, cy];
if (cnode == null)
{
cnode = new AStarNode(cx, cy, false, false, node, newg, this.Heuristic.Calculate(destx, desty, cx, cy) * factor);
nodegrid[cx, cy] = cnode;
}
else
{
if (cnode.G > newg)
{
cnode.IsClosed = false;
cnode.G = newg;
cnode.Parent = node;
}
else continue;
}
if (!cnode.IsOpen)
{
cnode.IsOpen = true;
openQueue.Push(cnode);
}
}
}
node.IsOpen = false; node.IsClosed = true;
}
}
return ptd;
}
First I would like to say, your code is very clear and easy reading. I read through the method and it seems to me they are all necessary operations except one thing: How big your priorqueue will be? Do you implement it yourself?
ASKER
Hi, thanks for the answer. Code is not mine so I can't get any credits for clarity. Here is the implementation of PriorityQueue.
public class PriorityQueueB<T> : IPriorityQueue<T>
{
#region Variables Declaration
protected List<T> InnerList = new List<T>();
protected IComparer<T> mComparer;
#endregion
#region Contructors
public PriorityQueueB()
{
mComparer = Comparer<T>.Default;
}
public PriorityQueueB(IComparer<T> comparer)
{
mComparer = comparer;
}
public PriorityQueueB(IComparer<T> comparer, int capacity)
{
mComparer = comparer;
InnerList.Capacity = capacity;
}
#endregion
#region Methods
protected void SwitchElements(int i, int j)
{
T h = InnerList[i];
InnerList[i] = InnerList[j];
InnerList[j] = h;
}
protected virtual int OnCompare(int i, int j)
{
return mComparer.Compare(InnerList[i], InnerList[j]);
}
/// <summary>
/// Push an object onto the PQ
/// </summary>
/// <param name="O">The new object</param>
/// <returns>The index in the list where the object is _now_. This will change when objects are taken from or put onto the PQ.</returns>
public int Push(T item)
{
int p = InnerList.Count, p2;
InnerList.Add(item); // E[p] = O
do
{
if (p == 0)
break;
p2 = (p - 1) / 2;
if (OnCompare(p, p2) < 0)
{
SwitchElements(p, p2);
p = p2;
}
else
break;
} while (true);
return p;
}
/// <summary>
/// Get the smallest object and remove it.
/// </summary>
/// <returns>The smallest object</returns>
public T Pop()
{
T result = InnerList[0];
int p = 0, p1, p2, pn;
InnerList[0] = InnerList[InnerList.Count - 1];
InnerList.RemoveAt(InnerList.Count - 1);
do
{
pn = p;
p1 = 2 * p + 1;
p2 = 2 * p + 2;
if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
p = p1;
if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
p = p2;
if (p == pn)
break;
SwitchElements(p, pn);
} while (true);
return result;
}
/// <summary>
/// Notify the PQ that the object at position i has changed
/// and the PQ needs to restore order.
/// Since you dont have access to any indexes (except by using the
/// explicit IList.this) you should not call this function without knowing exactly
/// what you do.
/// </summary>
/// <param name="i">The index of the changed object.</param>
public void Update(int i)
{
int p = i, pn;
int p1, p2;
do // aufsteigen
{
if (p == 0)
break;
p2 = (p - 1) / 2;
if (OnCompare(p, p2) < 0)
{
SwitchElements(p, p2);
p = p2;
}
else
break;
} while (true);
if (p < i)
return;
do // absteigen
{
pn = p;
p1 = 2 * p + 1;
p2 = 2 * p + 2;
if (InnerList.Count > p1 && OnCompare(p, p1) > 0) // links kleiner
p = p1;
if (InnerList.Count > p2 && OnCompare(p, p2) > 0) // rechts noch kleiner
p = p2;
if (p == pn)
break;
SwitchElements(p, pn);
} while (true);
}
/// <summary>
/// Get the smallest object without removing it.
/// </summary>
/// <returns>The smallest object</returns>
public T Peek()
{
if (InnerList.Count > 0)
return InnerList[0];
return default(T);
}
public void Clear()
{
InnerList.Clear();
}
public int Count
{
get { return InnerList.Count; }
}
public void RemoveLocation(T item)
{
int index = -1;
for (int i = 0; i < InnerList.Count; i++)
{
if (mComparer.Compare(InnerList[i], item) == 0)
index = i;
}
if (index != -1)
InnerList.RemoveAt(index);
}
public T this[int index]
{
get { return InnerList[index]; }
set
{
InnerList[index] = value;
Update(index);
}
}
#endregion
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Well I finally noticed after doing some tests that the area I was searching a path for wasnt suited at all for a*. The area consisted of about 1000x1000 nodes that were all the same distance to eachother with some walkable/unwalkable nodes. After adding some logging to my a* method, I found it it would be visiting about 30 000 nodes! My solution have been to completly replace a* with my custom-made algorithm wich is alot faster. I dosen't always find a path but I need performances alot more than accuracy.
I will accept your answer because it could indeed help some others that are looking to improve a* performances, but my solution was to simply get rid of it.
Thank you.
I will accept your answer because it could indeed help some others that are looking to improve a* performances, but my solution was to simply get rid of it.
Thank you.