Improving A* for memory: IDA*

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.

Getting ready

For this recipe, it is important to have some understanding of how recursion works.

How to do it…

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:

1. 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;
   }

2. Declare and compute the variables to use along with the algorithm:

   List<Vertex...