Investigate improvements to the actual algorithm #8

jgulotta · 2012-12-18T01:31:49Z

There has been some research on improving the general A* algorithm. We should see if any of these optimizations may be (optionally) applied.

Extensions and Applications of the A* Algorithm - presents a method of dynamically improving a given heuristic so that no node is visited more than once.
Optimizing the A* Algorithm - presents a couple high-level improvements: replace closed list with a boolean flag, conditional use of a priority queue, and early expansion of nodes
Fast Pathfinding via Symmetry Breaking - may apply only to rectangular grid path finding, but can significantly reduce the search space

See also: http://theory.stanford.edu/~amitp/GameProgramming/

Partially address LearnProgramming#8 HeapSet now remembers all states whether they are on the heap or not and has accordingly been renamed to CachingHeapSet. States will only be put on the heap, updated, or reinserted if they a) were not there before or b) are not closed and of higher priority than what's already on the heap. States are optionally closed when they are popped off the heap. Memory use and allocations went down from eliminating the extra set. 3x3 case --- Before: total heap usage: 27,547 allocs, 27,547 frees, 2,123,227 bytes allocated After: total heap usage: 26,681 allocs, 26,681 frees, 2,087,203 bytes allocated

jgulotta mentioned this issue Dec 23, 2012

Allow heapset to manage closed state #17

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Investigate improvements to the actual algorithm #8

Investigate improvements to the actual algorithm #8

jgulotta commented Dec 18, 2012

Investigate improvements to the actual algorithm #8

Investigate improvements to the actual algorithm #8

Comments

jgulotta commented Dec 18, 2012