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)

Clusters, entrances and connections

Low quality path using HPA* (cost: 70.464)

High quality path using HPA* (cost: 25.349)

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

 

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:

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 8x8 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