Actually, better than a balanced binary tree for this case would be a
priority queue.
Whilst you're correct that a priority queue is indeed what's wanted, note that it isn't "better" as such since a tree is a data structure whilst a priority queue is an abstract thing (effectively a requirements specification). Indeed, priority queues can be efficiently implemented
using binary trees!
You're right; I thought of that after I posted, but didn't end up making an edit. Thanks!
uumhmf , these hardcore termonology technicalities...
i've implemented dijksta (a* without different costing 'terrain tiles' (?right?)) once, and if i remember correctly one/I just pushed/popped the nodes on the open/closedlist , when done correctly this made the order perfect from the start, when backtracking with the smallest distance for every node.... (without the need to sort)
i'm still waking up, but what you guys are talking about, is that even more better ?
What you're describing sounds like a depth-first search, not Dijkstra's Algorithm. The key thing about Dijkstra is that it checks the closest nodes (to the origin) first; this requires sorting the open list. The difference between A* and Dijkstra is that A* also accounts for the (estimated) distance to the
destination as well as the distance travelled from the origin. This requires a
heuristic, a guess as to how far any given node will be from the destination; it's generally quite easy to come up with such a heuristic on a tile-based map (just get the manhattan or euclidean distance between the tile and the destination), but much harder with something like, say, a graph of nodes in a wireless network, which is why Dijkstra's algorithm might be used there instead.
A*'s quite nice, but it's an optimization; like all optimizations, it's generally better to implement a simpler solution (like a DFS, or Djikstra's) until you know that you actually need the greater speed. (Optimizations come at the cost of maintainability, which you want to preserve as much as possible.) If you didn't have a problem with your solution, there was probably no need for anything more sophisticated.
Developer
