Solved

Posted on 2009-12-22

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

4 Comments

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

You can also adjust the a* algorithm a little. For example, change the factor or the Heuristic.

this.Heuristic.Calculate(d

The better your Heuristic is, the quicker you find you path. You need to look into the problem and see if the Heuristic is always leading you to the correct path or not.

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.

By clicking you are agreeing to Experts Exchange's Terms of Use.

Title | # Comments | Views | Activity |
---|---|---|---|

deploying a service to production environment | 13 | 64 | |

C# winform large initialized array.... where to keep it?? | 4 | 32 | |

Debug Windows Service program in C# | 4 | 24 | |

Problem to event | 3 | 25 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**10** Experts available now in Live!