A* search done in a hierarchical manner for pathfinding of computer agents
Oct 2006
Hierarchical A* Pathfinding
@ programming > artificial intelligence

Waymarkers are placed on the ground to serve as locations where the computer agents will move to, as they traverse through the game level. In this demo, the calculations of the paths are done using the standard A* search technique which uses heuristics to find the guaranteed shortest path to reach a certain destination. As an enhancement, the waymarkers are broken down into hierarchies so that the time and space complexities are significantly reduced.

In the video below, the robot is moving to a waymarker (represented by the flags) which the user has selected. It is doing this by moving from waymarker to waymarker, until the destination has been reached. Every time it reaches some intermediate waymarker, it will query from the pre-computed A* shortest path table to find out the next waymarker to go to, in order to reach the destination.

Video showing how a robot finds the shortest path from one waymarker to the next using a pre-computed A* search table

If the selected waymarker is in another room, the robot will find the shortest path in terms of rooms (e.g. shortest path from room A to B is through rooms C and then D etc). Then within each room, the robot will find the shortest path from door to door. This hierarchical search carries on until the robot ends up in the final selected waymarker.

Note: Scene setup done by Goh Cheng Teng.

Skeel Lee Skeel Lee
Facebook Google+ Twitter Tumblr
YouTube Vimeo Flickr Pinterest
Senior FX TD / R&D
Digital Domain 3.0 (Previously at Sony Pictures Imageworks, MPC, Industrial Light & Magic, Double Negative)
LinkedIn IMDb GitHub Stack Overflow
I am a Senior Technical Director with strong interests in both tech and art. My life evolves round VFX, photography, software engineering, tools programming and generally anything that looks / sounds cool.
I have done a variety of CG programming, including fluid sims, muscles, soft/rigid bodies, raytracing etc. These knowledge complement the visual works that I do as a TD in VFX.
I was interviewed by The Straits Times in May 2014 for my VFX work in X-Men: Days of Future Past.