A* and Binary Heap

[TrueBrain]

Update of Convoy:

Recent developments ( especially the different behaviour of IsBuildable ) did make the pathfinding of the previous Convoys pretty useless ( as is: not able to find a route ). I tried integrating the BinHeap of the library, as it was better coded than my version ( that is, being a much more pure Container class), but unfortunately, the performance was a lot worse than in my previous Convoy version. Main reason: the Exists function, which does compare a complete node. Suggestion to the devs: add an id to the Insert parameter list.
So for now, I still use my own BinHeap.

Lots of things have improved since the previous version, and I realise lots of things still have to be done.

Nice job I will run it on the tournament server soon

About the Binary Heap: the Exist() function is identical to yours ... so why don't you just insert the index? Via the index you can find back your node by your own... I mean, easy as pie Adding something like an other 'id' field to the list, only makes it less of a Binary Heap, and makes it break/slow for other routines This is the most pure implementation you can get (as it doesn't assume anything about the outside world )

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

Either way, please let me know how you estimated the 'performance' of your own routine against the one in SVN.

[Ralph]

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...

[TrueBrain]

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.

[kuifware]

Doesn't shortest path/Dijkstra/A* need to support priority changes in your priority queue?

[Yexo]

Doesn't shortest path/Dijkstra/A* need to support priority changes in your priority queue?

It doesn't need that. You can just put the same tile multiple times in the priority queue with different values, as the one with the lowest value will be picked first. When the tile is fetched again (with a higher value) it'll be ignored. That's the use of the closed list.

[Zutty]

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.

Agreed. Because of the way Squirrel/the compiler can optimise the main pathfinder loop, its will be quicker to do it this way. By querying OPEN before you insert a node your just wasting time on a comparison that it would have to do anyway.

In my experience its best not to try to second guess your programming language or environment, as it is nearly always faster to do it the "stock" way rather than your own way! More importantly though by doing it the proper A* way you preserve the integrity algorithm, which enables the use of structures like a binary heap. The only query you should ever make to OPEN is to pop the top node.

...because of how the A* algorithm works, it ALWAYS finds the shortest route to any tile

Not strictly true. A* is always guaranteed to find a path (if one exists), but whether or not it is optimal depends on your heuristic. I suppose you could say its optimal to the heuristic, but the meaningfulness of a heuristic function is hard to define. What makes a function "good"??!!!. Something like

Code: Select all

f(x) = g(x)*0 + h(x)

would be very fast and generally create lines that hug the terrain, but could easily create bizarre loops and kinks!

[Yexo]

...because of how the A* algorithm works, it ALWAYS finds the shortest route to any tile

Not strictly true. A* is always guaranteed to find a path (if one exists), but whether or not it is optimal depends on your heuristic. I suppose you could say its optimal to the heuristic, but the meaningfulness of a heuristic function is hard to define. What makes a function "good"??!!!. Something like

Code: Select all

f(x) = g(x)*0 + h(x)

would be very fast and generally create lines that hug the terrain, but could easily create bizarre loops and kinks!

That statement by TrueLight *IS* true, under one provision: the estimate function may *NEVER* return a higher value then the cost function over each route. If that holds, A* will return the optimal path. So f(x) = g(x) + h(x). The closes h(x) comes to the real value, the better the performance, if h(x) is higher then the real value, it's no longer guaranteed that the optimal path is found.

[TrueBrain]

And I hope you don't mind I assume your h(x) is valid ...

Mind that it finds the optimal route which your g(x) defines. What this 'optimal' is you can debate about, but if your h(x) doesn't over estimate, A* finds the most optimal solution within the limits of your g(x), ALWAYS and EVER.