HPA*

I finally finished with the implementation of HPA*.

The pathfinder can be parameterized on cluster size, cluster-local path quality, coarse path quality and minimum distance between entrances to name a few. Below are a few examples. HPA* is ideal for use for many unit pathfinding queries, which I intend to have in AoT.

Clusters and entrances. Background is the movecost heatmap (blue: low move cost, red: high movecost)

output_overworld_navpathhpavis_true_false.png

Clusters, entrances and connections

output_overworld_navpathhpavis_true_true.png

Low quality path using HPA* (cost: 70.464)

output_overworld_navpath_q0_70.464.png

High quality path using HPA* (cost: 25.349)

output_overworld_navpath_q9_25.3496.png

High quality path using regular A* (cost: 23.765)

output_overworld_navpath_q10_23.7657.png

 

Dynamic path

The pathfinder works also with dynamic weights: when parts of the weights are updated, we only recalculate the cluster-local paths in the clusters that the weights are in, ie. minimizing A* calculations.

Here’s a busy visualization of a dynamic path:

output_visibility_unitpath_unit_dwarves_vis_normal(4).gif

The movecost map is visualized again as a heatmap. Green is the “unknown movecost”, and is the so-far invisible area. The map is split in 8×8 clusters. All entrances and connected paths are visualized with magenta. The fat white line is the evolving path calculation. It is clear that “highways” are formed naturally when we explore the movecost map, as several paths coalesce

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.