Dynamic Weighted Abstraction

This demo shows a dynamic weighted abstraction. The underlying map is abstracted for pathfinding speed. The abstraction is updated dynamically as the map is changed. In the abstraction, terrain types are explicitly represented in the abstraction, making it possible to plan for any cost algebra without changing the abstraction. That is, each type of character can have different costs for different types of terrain traversal but use the same abstraction for planning.

For simplicity, you can plan with the following cost models:

• Human: Road < Ground < Water < Trees = Swamp
• Jesus: Road = Water < Ground < Trees = Swamp
• Sheep: Road = Ground < Trees < Water = Swamp
• Deer: Trees < Ground < Road < Water = Swamp

Instructions

1. Choose a terrain type and paintbrush size to draw on the map
2. Toggle whether the abstraction is drawn
3. Choose a cost model and a path to see resulting paths
4. The red path is the optimal path on the map. The purple path is the optimal path in the abstraction.
   (In practice the abstract path is refined into a smoother path on the map, but, for clarity of visualization, this step is not drawn.)

Code

The code for this demo can be found as an application in hog2. This implementation is grid-based, but it is not hard to adapt it for other underlying representations such as NavMeshes from Recast. (Which divides the world up using similar sectors.)

Related Videos

Selected Related Publications