search

JosephClay / beyond-beyaan

Automatically exported from code.google.com/p/beyond-beyaan
Other
0 stars 0 forks source link

Optimize the A* algorithm - Replace OpenNodes List with Binary Heap #5

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
In large galaxies, the pathfinding algorithm is slow.  Most of the components 
are optimized, but the bottleneck is finding the next best open node.  It 
searches through the entire list.  This can be significantly boosted if 
replaced with binary heap.

Original issue reported on code.google.com by zeraa...@gmail.com on 7 Apr 2011 at 5:15

GoogleCodeExporter commented 9 years ago 
This is done, and there was a huge performance increase!  The pathfinding 
algorithm may be final now, unless we find ways to optimize it even more.

Original comment by zeraa...@gmail.com on 13 Aug 2011 at 11:24

GoogleCodeExporter commented 9 years ago 
Ufff, having list as a container for OpenNodes is probably worst choice in A*, 
performance wise. In average case, complexity of finding node to expand is O(n).

Generally, when implementing path finding, keep this in mind:
DFS (depth first search) - stack of open nodes (list is OK too, same 
performance)
BFS (breadth first search) - queue of open nodes (or linked list, same as above)
A* - heap of open nodes as you've already figured

And one more thing. I see that you are using "fixed" as a status for completed 
tasks. By default, the Google Code offers status "done" for a truly completed 
tasks. "Fixed" by default means "implemented but not yet given green light". Of 
course status options are customizable so "fixed" may mean "done" in your 
project.

Original comment by subchann...@gmail.com on 4 Oct 2011 at 6:41

GoogleCodeExporter commented 9 years ago

Original comment by zeraa...@gmail.com on 4 Oct 2011 at 7:01