4
\$\begingroup\$

Currently I have a very general purpose A* algorithm, which I've submitted as open sourced at https://github.com/kd7uiy/AStar . I've been trying to speed it up for the last month or so, and while I'm making steady progress, I'm struggling to see anything major that I can do to speed things up at this time. I'm using this for Unity, although I believe it is general purpose C# code. For reference, I've included the profiler output below for a difficult path, that is about 50 nodes away with some complexity involved.

enter image description here

I'm fairly certain that I can improve the speed by pre-computing some of the distances inside of my tiles and providing "neighbor" inputs as a result to reduce the iteration count somewhat, but I would like to provide an optimal solution for just the library portion if possible.

FYI, my map is a non-uniform asymmetric map. It attempts to model the effect of wind on a sailing boat in determining the speed. That reduces considerably the algorithms which I can use, but a general purpose A* still seems to work reasonably well.

I won't include all of my code here, but here's the main pathfinding class. The rest can be seen in the git repository that I have above.

using Priority_Queue;
using System;
using System.Collections.Generic;

public class AStarPathfinder<T> where T : class, IAstarNode<T>
{

    private FastPriorityQueue<DataSet<T>> orderedTestList;
    private static AStarPathfinder<T> _instance;
    private List<T> visited;
    private DataSet<T>[] fullDataTraveled=null;

    private IComparer<DataSet<T>> Comparer;

    /// <summary>
    /// Get an instance of the pathfinder. The tile should be passed as a function
    /// </summary>
    public static AStarPathfinder<T> Instance
    {
        get{
            if (_instance== null)
            {
                _instance = new AStarPathfinder<T>();
            }
            return _instance;
        }
    }

    private AStarPathfinder()
    {
        orderedTestList = new FastPriorityQueue<DataSet<T>>(16);
        visited = new List<T>();
        Comparer = Comparer<DataSet<T>>.Default;
    }

    /// <summary>
    /// Finds the distance to a given tile, given A* processing
    /// </summary>
    /// <param name="cur">The start tile</param>
    /// <param name="dest">The end tile</param>
    /// <returns></returns>
    public int DistanceTo(T cur, T dest, float tweakParam)
    {
        return PopulatePath(cur, dest, tweakParam).distTraveled;
    }

    /// <summary>
    /// Find a path from the current tile to the destination. Assumes there is a path to the destination
    /// </summary>
    /// <param name="cur">The start tile</param>
    /// <param name="dest">The end tile</param>
    /// <returns></returns>
    public List<T> FindPath(T cur, T dest,float tweakParam)
    {
        DataSet<T> curTest = PopulatePath(cur, dest, tweakParam);
        List<T> ret = new List<T>();
        while (curTest.prev != null)
        {
            ret.Insert(0, curTest.current);
            curTest = fullDataTraveled[curTest.prev.AStarIndex()];
        }
        return ret;
    }


    int[] heuristics=new int[0];
    int[] blankHeuristics;
    DataSet<T>[] blankTraveled;
    private DataSet<T> PopulatePath(T cur, T dest, float tweakParam)
    {
        orderedTestList.Clear();
        visited.Clear();
        if (heuristics.Length != cur.MaxAStarIndex())
        {
            fullDataTraveled = new DataSet<T>[cur.MaxAStarIndex()];
            blankTraveled = new DataSet<T>[cur.MaxAStarIndex()];
        } else
        {
            Array.Copy(blankTraveled, fullDataTraveled, cur.MaxAStarIndex());
        }

            Tuple<T, int>[] set;
        if (heuristics.Length != cur.MaxAStarIndex())
        {
            heuristics = new int[cur.MaxAStarIndex()];
            blankHeuristics = new int[cur.MaxAStarIndex()];
        } else
        {
            Array.Copy(blankHeuristics, heuristics, cur.MaxAStarIndex());
        }
        DataSet<T> curTest = new DataSet<T>(cur, null, 0, 0);
        fullDataTraveled[cur.AStarIndex()]= curTest;

        while (curTest.current != dest)
        {
            visited.Add(curTest.current);
            set = curTest.current.GetNeighborsAstarDistance(tweakParam);
            foreach (Tuple<T,int> neighbor in set)
            {
                int distanceTo = curTest.distTraveled + neighbor.Second;
                int heuristic = 0;
                if (heuristics[neighbor.First.AStarIndex()]>0)
                {
                    heuristic = heuristics[neighbor.First.AStarIndex()];
                }
                else
                {
                    heuristic = neighbor.First.GetAstarHeuristic(dest, tweakParam);
                    heuristics[neighbor.First.AStarIndex()]= heuristic;
                }

                DataSet<T> ds = new DataSet<T>(neighbor.First, curTest.current, distanceTo, distanceTo + heuristic);
                if (fullDataTraveled[neighbor.First.AStarIndex()]!=null)
                {
                    //A quicker path was found to the tile
                    if (Comparer.Compare(ds, fullDataTraveled[neighbor.First.AStarIndex()]) < 0)
                    {
                        orderedTestList.Remove(fullDataTraveled[neighbor.First.AStarIndex()]);
                        fullDataTraveled[neighbor.First.AStarIndex()] = ds;
                        Enqueue(ds);
                    }
                }
                else
                {
                    fullDataTraveled[neighbor.First.AStarIndex()] = ds;
                    Enqueue(ds);
                }

            }
            try
            {
                curTest = orderedTestList.Dequeue();
            }
            catch (InvalidOperationException)
            {
                curTest = fullDataTraveled[dest.AStarIndex()];
                break;
            }
        }

        return curTest;
    }

    private void Enqueue(DataSet<T> ds)
    {
        if (orderedTestList.Count==orderedTestList.MaxSize)
        {
            orderedTestList.Resize(orderedTestList.MaxSize * 2);
        }
        orderedTestList.Enqueue(ds, ds.Priority);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Welcome to Code Review and great first post - you should get some good answers! \$\endgroup\$ – ferada Sep 8 '16 at 16:49
  • \$\begingroup\$ I hope so:-) I've had this site on my mind for a while as a potential resource, this seemed like a good problem to let the brilliant minds here work;-) \$\endgroup\$ – PearsonArtPhoto Sep 8 '16 at 18:00
  • \$\begingroup\$ What is a "non-uniform asymmetric map" in this context? As far as I remember, A* operates on graphs. Could you elaborate? \$\endgroup\$ – I'll add comments tomorrow Sep 8 '16 at 19:42
  • \$\begingroup\$ The "distance" between tiles depends on the direction, and there isn't an easy pattern to it. If you are moving with the wind, then you go faster, against the wind and you go slower. \$\endgroup\$ – PearsonArtPhoto Sep 8 '16 at 20:10
1
\$\begingroup\$

FindPath

You can improve the performance of this method by using a LinkedList instead of a List because you are inserting itemns before the first one and for the list it's an O(n) operation. LinkedList.AddFirst can do it as O(1).^

Or alternatively you can also add it to the list at the end and then Reverse the list.


I cannot say more then this. A lot of methods the you call inside the loops are not in the source code you've provided.

\$\endgroup\$
  • \$\begingroup\$ the GetAstarHeuristic is not even in your repository... where did you implement it? You should provide the entire code. \$\endgroup\$ – t3chb0t Sep 9 '16 at 18:32
  • \$\begingroup\$ I'm less worried about the specific implementation of my A* algorithm, which includes things like the GetAstarHeuristic, and more concerned about the core code, which is in the repository. \$\endgroup\$ – PearsonArtPhoto Sep 9 '16 at 18:58
  • \$\begingroup\$ Thanks, I'll have to give that a shot! Small improvement, but still, I'll take it! \$\endgroup\$ – PearsonArtPhoto Sep 9 '16 at 18:59
  • \$\begingroup\$ @PearsonArtPhoto one more thing, I believe you can improve the performance of the FastPriorityQueue class too. Instead of moving the nodes around the array on each enqueue with CascadeUp, add the nodes as they are and track the priority aka sorting in the OrderedDictionary the insertions there are O(1). \$\endgroup\$ – t3chb0t Sep 10 '16 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.