Article
hpa

Hierarchical Path-Finding A* Demo on a Counterstrike Map (Video)

Alex J. Champandard on February 4, 2009

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.

Note: If you’re an AiGameDev.com Member, you will be able to get access to this demo and the code (plus a few bug fixes and improvements to the area generation) at the end of the week. If you’ve not signed up yet you can join here for another day and a half!

The video goes through the following phases:

  1. 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.)

  2. Connections between the areas are identified and used to setup a high-level graph that can be searched.

  3. 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.

  4. The set of connections being searched are displayed in orange, and the active connections are displayed in yellow while the algorithm is running.

  5. 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.

Discussion 7 Comments

jadnohra on February 5th, 2009

You are right Nathan, the '2' got lost along the way / during renaming. The original name was map_cs2d_de_dust2_sub2 :):)

memoni on February 5th, 2009

It looks like taxicab convex has other names too, like orthogonal convex hull, rectilinear convex hull or x-y convex hull.

jadnohra on February 5th, 2009

[QUOTE]That’s pretty clever. Solves quite nicely the path smoothing problem the original HPA* with square blocks had.[/QUOTE] This video uses a pretty simplistic way of choosing the 'border' nodes, very similar if not the same as the 'original HPA*'. The area clustering algorithm plays a determining role as well and this is the reason why this looks better than the 'original HPA*'. A smarter algorithm could be used to control which border nodes can be safely discarded while allowing mostly smooth paths. On the extreme, ALL the border nodes could be included in the hierarchical graph, but ... performance ...

memoni on February 5th, 2009

Jad, I think you could use a modified version of funnel string pulling to deal with the border edges. That is, consider the series of nodes between two clusters as straight lines, then use the funnel algorithm, and finally find match the edge intersection points to the nodes at the edges of the clusters. A couple of iterations with naive a naive algorithm which moves the edge nodes might do the trick too. Or you could smooth out the path when you are following it with a little lookahead (pretty much like that original CS bot).

jadnohra on February 5th, 2009

memoni, thanks for the tip, I am not familiar with the funnel algorithm I will look it up, but what I instinctively wrote is an algorithm that finds lines of connected border nodes (maybe that's similar to the Funnel Algo with my 'lines' being called strings?), then for each line, choosing each nth node in it as a border node, or if the line is short taking its middle ... I did not go much in detail there, this is the 1st working version so we concentrated on having something working, along with the needed area analysis to automatically build the area graph, improvements will definitely follow as needed, so keep the ideas coming :)

jadnohra on May 14th, 2009

I just added string-pulling to the samples, we finally got the the point where we needed for the upcoming demos. It works well ... memoni you were obviously right, me noob had no idea :) now i know ... level-up. as for 'funnel' string-pulling, what exactly is that? my google searches for that are failing miserably.

memoni on May 15th, 2009

Here's a couple of quick links from google: [url]http://www.geometrylab.de/ShortestPathLP/index.html[/url] graphics.ucmerced.edu/publications/2005_IJCAI_Kallmann.pdf This one also has good illustration how it works (you should listen to the audio too, it helps a lot to understand it): [url]www.navpower.com/gdc2006_miles_david_pathplanning.ppt[/url] Detour also includes string pulling using very similar algorithm.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!