[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

C# AStar (A*) algorithm perfomance improvments

Posted on 2009-12-22
4
Medium Priority
?
1,388 Views
Last Modified: 2012-05-08
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
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;
        }

Open in new window

0
Comment
Question by:MikeDotNet555
  • 2
  • 2
4 Comments
 
LVL 9

Expert Comment

by:magicdlf
ID: 26110058
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?
0
 
LVL 3

Author Comment

by:MikeDotNet555
ID: 26110082
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
    }

Open in new window

0
 
LVL 9

Accepted Solution

by:
magicdlf earned 2000 total points
ID: 26110910
Sorry for the delay. I review the PQ and it looks also good. I think the a* implementation is correct. Do you know how many elements will be put into the PQ while you are executing your program?

You can also adjust the a* algorithm a little. For example, change the factor or the Heuristic.
this.Heuristic.Calculate(destx, desty, start.X, start.Y) * factor
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.
0
 
LVL 3

Author Comment

by:MikeDotNet555
ID: 26155018
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.
0

Featured Post

 [eBook] Windows Nano Server

Download this FREE eBook and learn all you need to get started with Windows Nano Server, including deployment options, remote management
and troubleshooting tips and tricks

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Today I had a very interesting conundrum that had to get solved quickly. Needless to say, it wasn't resolved quickly because when we needed it we were very rushed, but as soon as the conference call was over and I took a step back I saw the correct …
Real-time is more about the business, not the technology. In day-to-day life, to make real-time decisions like buying or investing, business needs the latest information(e.g. Gold Rate/Stock Rate). Unlike traditional days, you need not wait for a fe…
Integration Management Part 2
Exchange organizations may use the Journaling Agent of the Transport Service to archive messages going through Exchange. However, if the Transport Service is integrated with some email content management application (such as an anti-spam), the admin…
Suggested Courses
Course of the Month20 days, 4 hours left to enroll

872 members asked questions and received personalized solutions in the past 7 days.

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

Join & Ask a Question