This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.
I have an old post on A* algorithm which I created as an engine component for another graph structure in another project. In this post, I will talk about a different implementation on A* with a more scalable and complete graph structure.
Graph Structure
For the basic graph structure that is being used by this version of A* algorithm, please reference the other post.
A* Data Strctures
Some crucial aspects of this algorithm are the node record structure and the priority queue class that I use. The node record is what we put into the open/closed list (priority queues) and sorted according to their cost.
For the priority queue, instead of using the C++ std one, I decided to create my own class so that we can have more control over the extensibility and provide extra interfaces if needed. However, the underlying structure is almost identical to the std::priority_queue since I’m using a std::vector as the container with heap operations (push_heap, pop_heap, etc.) to maintain the heap structure.
A* Search
The actual A* algorithm is pretty standard. The only point to note is that I am assuming that admissible heuristic is being used in our algorithm. Therefore, we can guarantee that if we are expanding the sink node, then we must’ve found the optimal path leading to it! Here is a simple explanation while the full proof can be found in “A Formal Basis for the Heuristic Determination of Minimum Cost Paths” by Nilsson et al.
Cheng-Hao "Nick" Chu 祝成豪 