Testbed is up to:
Loops: 1000, Seconds: 8.2598843, Loops per Second: 121.067071121081
Although it goes down to 12 LPS on 40x40.
My AStar class: The current version is the result of iterative tests - Yes, the List.Sort works, at worse, no worse than the HeapSorted. So I'm using the List.
My HeapSorted class is in the other thread.
public static class AStar { public struct AStarData : IAnytime<AStarNode, List<GraphNode>, Double> { public AStarData(Graph graph, Double maxRuntime = -1.0, Int32 maxSteps = -1) { this.graph = graph; this.runtime = 0.0; this.steps = 0; this.current = graph.Start; this.maxRuntime = maxRuntime; this.maxSteps = maxSteps; // open = new HeapSorted<AStarNode>(this.current, false); open = new List<AStarNode>(); closed = new HashSet<AStarNode>(); } private Graph graph; public Graph Graph { get { return graph; } } private List<AStarNode> open; public List<AStarNode> Open { get { return open; } } private HashSet<AStarNode> closed; public HashSet<AStarNode> Closed { get { return closed; } } private Double maxRuntime; public Double MaxRuntime { get { return maxRuntime; } set { maxRuntime = value; } } private Int32 maxSteps; public Int32 MaxSteps { get { return maxSteps; } set { maxSteps = value; } } private Double runtime; public Double Runtime { get { return runtime; } set { runtime = value; } } private Int32 steps; public Int32 Steps { get { return steps; } set { steps = value; } } private AStarNode current; public AStarNode Current { get { return current; } set { current = value; } } public List<GraphNode> Result { get { return current.Path(); } } public double Accuracy { get { return current.F; } } } /// <summary> /// Pathfinds on any mappable graph. /// </summary> /// <typeparam name="T">The type of data the graph contains.</typeparam> /// <param name="graph">An abstract Graph class.</param> /// <param name="start">The start data.</param> /// <param name="goal">The end data.</param> /// <param name="path">The output path.</param> /// <returns>Returns true if a path is found.</returns> public static Boolean Pathfind(Graph graph, dynamic start, dynamic goal, out List<GraphNode> path) { graph.SetStart(start); graph.SetGoal(goal); return Pathfind(graph, out path); } /// <summary> /// Pathfinds on any mappable graph. /// </summary> /// <typeparam name="T">The type of data the graph contains.</typeparam> /// <param name="graph">An abstract Graph class.</param> /// <param name="path">The output path.</param> /// <returns>Returns true if a path is found.</returns> public static Boolean Pathfind(Graph graph, out List<GraphNode> path) { AStar.AStarData data = new AStarData(graph); Boolean check = Pathfind(ref data); path = new List<GraphNode>(); if (!check) { if (data.Closed.Count > 0) { path = data.Current.Path(); } } else path = data.Current.Path(); return check; } public static Boolean Pathfind(ref AStar.AStarData data) { // Get the graph's Start node. AStarNode S = data.Graph.Start; // Add the Start node to the Open list. data.Open.Add(item: S); // Continue until we have no more Open nodes. bool check = false; data.Runtime = 0.0; data.Steps = 0; while (data.Open.Count > 0 && !check && (data.MaxRuntime == -1 || data.Runtime < data.MaxRuntime) && (data.MaxSteps == -1 || data.Steps < data.MaxSteps)) { check = PathFindInner(ref data); } if (!check && data.Open.Count == 0) { data.Closed.RemoveWhere(a => { return Object.Equals(a.Parent, null); }); if (data.Closed.Count > 0) { data.Current = data.Closed.OrderBy<AStarNode, Double>(a => { return a.H; }).ElementAt(0); } return false; } // If the While loop ends, we have no more Open nodes to check, so failure. return check; } private static bool PathFindInner(ref AStar.AStarData data) { Double startRuntime = NetExtensions.GeneralData.Stopwatch.Elapsed.TotalSeconds; // Sort from lowest F-value (Estimated distance to solution) // to highest F-value. data.Open.Sort((a, b) => { if (a.F < b.F) return -1; else if (a.F > b.F)return 1; else return 0; }); // SortedSet<AStarNode> test = new SortedSet<AStarNode>(data.Current); // Get the best node in the open list and remove it from // that list. do { // If there's nothing left in the open list, we've checked // everywhere and there's no solution. Exit, returning false. if (data.Open.Count == 0) { data.Closed.RemoveWhere(a => { return Object.Equals(a.Parent, null); }); if (data.Closed.Count > 0) { data.Current = data.Closed.OrderBy<AStarNode, Double>(a => { return a.H; }).ElementAt(0); } return false; } data.Current = data.Open[0]; data.Open.RemoveAt(0); // data.Current = data.Open.RemoveLowest(); } while (data.Closed.Contains(data.Current)); data.Closed.Add(data.Current); // If it's the destination, if (data.Current.Data == data.Graph.Goal.Data) { // Get the path to this node and return true. return true; } // Parse through all of the graph nodes linked to B. foreach (AStarNode C in data.Current.Links) { if (!data.Closed.Contains(C)) { // Make it's parent B, C.Parent = data.Current; // Calculate it's values C.Recalculate(); // and add it to the Open list. // Int32 n = data.Open.FindIndex(a => { return a.F >= C.F; }); data.Open.Add(C); /* if (n > -1) data.Open.Insert(n, C); else data.Open.Insert(0, C); */ } } data.Runtime += NetExtensions.GeneralData.Stopwatch.Elapsed.TotalSeconds - startRuntime; ++data.Steps; return false; } }
