Path Finding
This section shows how to run A* on the hexasphere.
Creating a Weight Function
To guide the path finding algorithm, we need a weight function to express the cost of visiting a tile. A* prioritizes exploration of cheaper tiles.
The following weight function prioritizes tiles of lower height, avoiding mountains.
You can use a constant weight function to get the shortest path. In this case, make sure to use a distance-based heuristic to speedup the algorithm.
// C++ example code not available yet.
Creating a Heuristic Function
The heuristic function guides the search, helping the algorithm to find a good path faster. It tells an estimation of the cost from a tile to the target tile.
Note: If the heuristic function overestimates the cost of a tile relatively to another tile, the algorithm can return non-optimal paths.
Important: the cost of the algorithm can quickly explode if you use a constant heuristic or don't use a heuristic function on a large hexasphere.
1. Constant Heuristic Function
In the following code, we use a constant heuristic function, which is the same as not using one. Doing so guarantees the path found is optimal, but the algorithm will explore a lot of tiles, as it doesn't know in which direction is should progress.
// C++ example code not available yet.
2. Distance-Based Heuristic Function
The following Heuristic Function uses the distance between the two tiles. It will make the algorithm first try the tiles that are closer to the target tile instead of exploring all tiles blindly.
// C++ example code not available yet.
3. Heuristic Function Performance Comparison
Performance for asynchronous A* for path finding on a Hexasphere of type { Divisions=50, Tiles=25002 }, avoiding high tiles:
- Constant-Based: Found a path in
0.58612swith10085iterations. - Distance-Based: Found a path in
0.00085swith263iterations.
Important: test your heuristic for best performance. A* running time can be found in the logs.
Running A*
Now that we have a weight and an heuristic function, we can run A*. A* returns the Tile IDs of each tile in the path in order.
// C++ example code not available yet.
Result
Painting the tiles returned by A*, we get the result shown below, we can see the path avoiding mountains, as expected. Note that as height is 0 for several tiles, the algorithm can visit tiles for free and makes some small suboptimal turns which are still optimal weight-wise. It can be solved by adding a constant to the weight function, for example height + 1.
