clintbellanger/flare-engine — pull request #692 by RyanDansie (2013-05-29 23:16:53+00:00)
Title: Pathfinding optimisation

AStarNode list containers are replaced with more efficient container classes. The new classes don't require iterating every node to determine if the node exists or to find the shortest. Access to nodes are O(n) and adding/removing operations are O(log n). The processing time for the pathfinding algorithm seems to be about 25% of its original processing time.

Also includes caching of pathfinding results. Paths are not recalculated on every frame when it is unecessary. Some randomisation is used to prevent all entity paths being calculated in the same frame.

Also includes a short cooldown period when the target is unreachable to prevent cases like https://github.com/clintbellanger/flare-engine/issues/247.