search

GloryFish / lua-astar

A simple implementation of the A* (A Star) pathfinding algorithm for lua
http://gloryfish.org
Other
31 stars 4 forks source link

getBestOpenNode() is O(n) #1

Open GloryFish opened 13 years ago

GloryFish commented 13 years ago

Replace the linear table lookup in getBestOpenNode with a MinHeap pop.

Need to implement a min heap. Replace astar.on with the heap. Check to see if astar.o needs to be replaced.

berkona commented 11 years ago

Here's a python implementation using an array for the underlying data https://github.com/berkona/pymazegen/blob/master/priority_queue.py

You'd have to implement your own geometric expansion for arrays (python uses an oldSize * 9/8 + 1 algorithm), but overall it should be compatible with lua