Ralph wrote:TrueLight wrote:Also, if you need Exist() in the first please, a Binary Heap is not what you need
Binary Heap is to sort, and find the lowest value
If you want to avoid double entries, I suggest using AIList, or create an other kind of list
Binary Heap is _not_ your friend (Exist() is always O(n)). If you use it for any AyStar alike routine, I suggest looking at the AyStar library
Hehe
I have not sat down and worked out the numbers, but using an Exist() to prevent duplicate entries on your open list 'feels' like it should be quicker, as those duplicates will soon add up. If you fetch the node that exists you can also take the opportunity to update the g cost and parent node if it turns out to be shorter. I typically found my open list to contain at maximum ~500 nodes, so its not really in the territory that looping over the list a few times is going to break the bank.
I would test both behaviours, but it seems the latest build has broken my pathfinder...
How a Binary Heap works is totally unrelated to what you expect it to do
Exist() is a O(n) for Binary Heap, as it is a Priority Queue, and can only tell you very quick what the lowest value is, nothing else. Most other actions are O(n). If you want fast Exist() action, you need other tree (RedBlack?). However, for A* this is not important.
There is no need to check if a value is in your Open-list, and update any f-value if needed. What you do, is just put duplicated nodes in the tree, no problem what so ever. As here the Closed-list comes in. As soon as you pop an item from the Open-list, you check if it is in the Closed-list. If so, ignore the item, and find the next one. This way there is no need to use any Exist() on the Open-list (just on the Closed-list, which should NOT be a Binary Heap). That is how A* is intended to work. For example, at any time in your Open-list those values can exist:
Code: Select all
Value Tile
1 2356
2 2356
6 2356
9 2357
As you can see, '2356' is 3 times in the list. No problem, his value '1' is pop'd first, and the other two are ignored when ever they are used. Yes, the Open-list will be bigger than you are used to, but it is the most efficient approach. Also, because of how the A* algorithm works, it ALWAYS finds the shortest route to any tile, so don't worry about it being added many times; as soon it is pop'd from the Open-list, you can be very sure that the path to that tile is most efficient via that way. But now I am explaining how A* works ...
Anyway, I think I now told more about how A* works than I intended, and also how one should handle an Open-list and Closed-list. I strongly suggest to read some real documentation about A* implementation, and you will see
(not 'you' as one person, but 'you' in general) To summarize it once more: using Exist() on Open-list: not needed. Using Exist() of Binary Heap: bad idea! Use other tree-type if you require this action.
The only thing necessary for the triumph of evil is for good men to do nothing.
