IDA* is a variant of an algorithm called Iterative Deepening Depth-First Search. Its memory usage is lower than A* because it doesn't make use of data structures to store the looked-up and explored nodes.
This is a long recipe that can be seen as an extensive two-step process: creating the main function, and creating an internal recursive one. Please take into consideration the comments in the code to understand the indentation and code flow more effectively:
GetPathIDAstar
:public List<Vertex> GetPathIDAstar(GameObject srcObj, GameObject dstObj, Heuristic h = null) { if (srcObj == null || dstObj == null) return new List<Vertex>(); if (ReferenceEquals(h, null)) h = EuclidDist; // next steps; }
List<Vertex> path = new List<Vertex>(); Vertex src = GetNearestVertex(srcObj.transform.position); Vertex dst = GetNearestVertex(dstObj.transform.position); Vertex goal = null; bool[] visited = new bool[vertices.Count]; for (int i = 0; i < visited.Length; i++) visited[i] = false; visited[src.id] = true;
float bound = h(src, dst); while (bound < Mathf.Infinity) { bound = RecursiveIDAstar(src, dst, bound, h, ref goal, ref visited); } if (ReferenceEquals(goal, null)) return path; return BuildPath(goal);
private float RecursiveIDAstar( Vertex v, Vertex dst, float bound, Heuristic h, ref Vertex goal, ref bool[] visited) { // next steps }
// base case if (ReferenceEquals(v, dst)) return Mathf.Infinity; Edge[] edges = GetEdges(v); if (edges.Length == 0) return Mathf.Infinity;
// recursive case float fn = Mathf.Infinity; foreach (Edge e in edges) { int eId = e.vertex.id; if (visited[eId]) continue; visited[eId] = true; e.vertex.prev = v; float f = h(v, dst); float b; if (f <= bound) { b = RecursiveIDAstar(e.vertex, dst, bound, h, ref goal, ref visited); fn = Mathf.Min(f, b); } else fn = Mathf.Min(fn, f); }
return fn;
As we can see, the algorithm is very similar to that of the recursive version of Depth-First Search, but uses the principle of making decisions on top of a heuristic from A*. The main function is responsible for starting the recursion and building the resulting path. The recursive function is the one responsible for traversing the graph, looking for the destination node.
This time we will need to implement a different a BuildPath
function, in case you have followed along with the previous path finding recipes. Otherwise, we will need to implement this method that we haven't defined yet:
private List<Vertex> BuildPath(Vertex v) { List<Vertex> path = new List<Vertex>(); while (!ReferenceEquals(v, null)) { path.Add(v); v = v.prev; } return path; }