- All Implemented Interfaces:
- Serializable
public class PlannedAStar
extends AStarSearch
(SLOW) Modified version of AStarSearch that does some pre-planning and uses that to speed up pathfinding later on.
Pre-planning is in the form of full distance calculations using DijkstraMap, with each centered on an infrequent
landmark somewhere on a walkable tile on the map. This affects the A* heuristic and allows it to establish a better
lower bound for distance. Landmark placement is non-random; 1 out of 85 walkable tiles will be made into a landmark,
and they will be considered in Hilbert Curve order (which helps prevent nearby areas from being chosen twice).
Idea can be credited independently to Joshua Day, who mentioned this long before I understood it, and Amit Patel,
http://www.redblobgames.com/pathfinding/heuristics/differential.html
NOTE: Due to implementation problems that seem to also be present in AStarSearch, this class does not offer any speed
improvements or any other benefits. It may be fixed in future versions, but for now you should strongly prefer
DijkstraMap for pathfinding.
- See Also:
a much faster pathfinding algorithm with more features.
Created by Tommy Ettinger on 5/5/2016.
,
Serialized Form