Hi! I'm working on a little A* pathfinding algoritme, and it works fine, but i want to make it faster so i've implemented a binary heap. The heap works fire exept for one thing: Resorting. I've followed this tutorial: http://www.policyalmanac.org/games/binaryHeaps.htm Now it says this: As is described in the main article, occasionally you will find that the F score of an existing open list item can change. When that happens, you don’t need to take the item out of the list and start all over. Simply start in its current location, and compare it to its parent using its new (lower) F score. If its F score is low enough to warrant a swap with that parent, then you need to do so (or you will have an invalid heap, and everything will break down). In general, you use the same code described in the “Adding an Item to the Heap” section of this article, with the following additional consideration: ... This can't be right... can it?! If I would change the first ellement in the heap, it just stays there, 'cause it doesn't have any parent nodes... But when i update the heap like that, and then I want the lowest item, I will get the item that was lowest recently, but is now maybe way bigger then the smallest in the list... Any thoughts please? (PLEASE :p I really need some help..., 'cause this is just confusing). Thx in advance... Dauntless (I know this nick is taken by someone else, but still, i'm used to using 'Dauntless' as my nickname ;) Crappy 'DauntlessCrowd' :@ ) //EDIT I was thinking... Maybe this just never happens in A*... Maybe the highest F will NEVER be replaced, because its already the highest, and if another path to that node is shorter, that other tile would be in place 1, and the current tile would be 2 or 3 or whatever... Can anyone confirm that? Any A* wizzes here ?? [Edited by - DauntlessCrowd on July 29, 2005 7:28:57 PM]

I don't know anything about A* but for a normal heap you'd have to check against both the parent and your children to make sure that the heap property is preserved. If not you'd either have to move the item up or down, possibly even multiple steps, in the tree to compensate. And that's probably not enough either..

Personally I'd implement the heap check and reinsert the item completely if it fails.

Quote:Original post by doynax
I don't know anything about A* but for a normal heap you'd have to check against both the parent and your children to make sure that the heap property is preserved. If not you'd either have to move the item up or down, possibly even multiple steps, in the tree to compensate. And that's probably not enough either..

I have a feeling that I'd be a lot easier just to remove and reinsert the item instead..

Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...

Quote:Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...

You're right of course, I just wasn't thinking. You'd have to rebuild the entire thing.

I suppose that it could work if the condition is rare enough, otherwise you'll have to choose a different datastructure.

Quote:Original post by doynax

Quote:Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...

You're right, I just wasn't thinking. You'd have to rebuild the entire thing.

Jup, and that would just be stupid... But thx for the input, all thoughts are welcome :)

Quote:Original post by DauntlessCrowd

Quote:Original post by doynax

Quote:Original post by DauntlessCrowd
Then again, if the element i changed is in the middle of the heap, and i remove it, my heap would be totaly screwed up...

You're right, I just wasn't thinking. You'd have to rebuild the entire thing.

Jup, and that would just be stupid... But thx for the input, all thoughts are welcome :)

Another option would be to keep the node around but flag it as removed and only rebuild the heap when the amount of dead meat exceeds some magical limit, i.e. the garbage collection approach.

In general it should be possible to replace the heap with a balanced binary tree, unless you only need to keep track of the top matches or something. Keep in mind that the space overhead and constant factors will be a lot higher though.

That would still be more time consuming... And what about adding a new node when its parent is deleted?

I was thinking... Maybe this just never happens in A*... Maybe the highest F will NEVER be replaced, because its already the highest, and if another path to that node is shorter, that other tile would be in place 1, and the current tile would be 2 or 3 or whatever...

Can anyone confirm that? Any A* wizzes here ??

The point in A* is using the tile with the lowest F. So i've put all the F's in a binary heap so that i can easily find the lowest F. (And it also works, no problems there! :) ). Its just that it DOES happen that an F changes, so I would have to update my heap...

But I think i'm right with the fact that its just impossible... But if someone could please confirm that? :)

//edit
Uhm, did you delete your post or something?

//Another edit:
The thing in A* is: It would only be changed to a lower F. Changes of an F to a higher F dont occur. So I think it would also be stupid to check the children of the current node... (That's atleast with my small knowledge of the binary heap).

Quote:Original post by DauntlessCrowd
Uhm, did you delete your post or something?

I reread your original post and realized that you were just taking the top node as an example.

Quote:Original post by DauntlessCrowd
The thing in A* is: It would only be changed to a lower F. Changes of an F to a higher F dont occur. So I think it would also be stupid to check the children of the current node... (That's atleast with my small knowledge of the binary heap).

It doesn't matter. If the value of any node in the heap (not just the one at the top) can change then you still have to rebuild the entire thing.

You should try it out on paper... The explenation from the tutorial actually works... You still end up with a valid heap after the change... Exept afcourse when you want to change the first node.