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:
- Let's start by defining the main function called
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; } - Declare and compute the variables to use along with the algorithm:
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;
- Implement the algorithm's loop:
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); - Now it's time to build the recursive internal function:
private float RecursiveIDAstar( Vertex v, Vertex dst, float bound, Heuristic h, ref Vertex goal, ref bool[] visited) { // next steps } - Prepare everything to start the recursion:
// base case if (ReferenceEquals(v, dst)) return Mathf.Infinity; Edge[] edges = GetEdges(v); if (edges.Length == 0) return Mathf.Infinity; - Apply the recursion for each neighbor:
// 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 a value based on the recursion result:
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;
}