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.