In a previous post, I wrote about the terrain area generation algorithm that I implemented as part of the AiGameDev.com Sandbox. That code was based on the ideas of our resident expert William van der Sterren (his site). The areas, even those generated by a simple algorithm, are very useful for speeding up most types of terrain operations… including navigation. See our sample terrain analysis reports for more information about this.
Over the last month, Jad Nohra (programmer and contributor) has been adding hierarchical pathfinding to the codebase. This work is based on the HPA* algorithm which I covered previously on the blog. In the video below, you’ll see a 2D approximation of a popular Counterstrike map de-dust as a 64x64 grid, which has areas generated and searched hierarchically to find paths between two points.
The video goes through the following phases:
Areas are generated using the same algorithm as the previous post. This algorithm wasn’t explained publicly, but feel free to guess how it works! (It’s relatively simple.)
Connections between the areas are identified and used to setup a high-level graph that can be searched.
The user selects a set of points: source (white) and target (red, a bit hard to see) in the world and the HPA* pathfinder is engaged.
The set of connections being searched are displayed in orange, and the active connections are displayed in yellow while the algorithm is running.
Once the path is found, the final path on the low-level is displayed in white.
If you have any questions, feel free to post them! If you’d like to see the code at the end of the week, feel free to sign-up. :-) And big thanks once again to Jad Nohra for his hard work.
