lower_bound is the optimal way of searching, but the heap functions are the optimal way of arranging the structure so that you don't have to search. So yeah, they're pretty much two approaches to the same problem. If you abstract your algorithm out a bit instead of having it all in one function, you should be able to easily switch between the two implementations and see which is faster. You might even find that it's quicker to use one implementation in some situations and the other in different ones.

I would if I had the time, but 4E4 is looming! Maybe later I'll play some more with that - I'd hoped that for A* as an algorithm maybe this was a cut'n'dried thing. I've heard binary heaps mentioned in a few sources now I've looked it up more, but it seems fast enough already so maybe I'll leave it until it becomes a problem. Implementing a proper queuing system for path-finding is probably going to make more difference to the fbs stability than fine-tuning the speed of finding each path.

Quote: Original post by d000hg
I got lower_bound working fine now, one last question is whether this is used in conjuntion with the heap functions?

Oh no that was just an example of using custom predicates with any standard library algorithm that takes'em, i choose to show it with those two as they had more relevance [wink]. I think Kylotan pretty much answered your other question.

I maintain both a vector and a map for the open list and a map for the closed list.
I heapify the vector using make_heap/push_heap so I can quickly find the lowest element, and the maps allows me to quickly check if a given node is already on the open or closed lists.

There are ton of responses to this post but very few mention new algarithims. well its good to optimize the inner workings of A* the best you can for large maps strait A* will never be enough no matter how fast your sorts and checks are.

I'm working on an rts game with large maps and just wrote a pathfinding system for it. The trick to navigating large maps is to break your problem down into chunks. You dived your map in to sections of some sort and precalculate what sections connect to what sections. Where chunks connect you have a portal so what you end up with is a list of portals. And you solve a path by first performing A* on these portals (opening portals by connections) then you solve the intermediate paths you do a convential tile map A* from one portal to the next
The details of this is pretty complicated, how your define you chunks dictates how you precede. The easiest way is the quad tree you make a quad tree of your map any leaf in your tree thats contains no obstructions or is completely block in every tile doesn't need to have any children. I've implimented this and it works if your don't need to do to alot of pathfinding, but if you have tons of objects pathfinding its still to slow.

The way I'm doing it now thats very quick and worth the work is I divide the map in to square block of an equal size and define portals along the edges of the blocks (starting a new portal when ever the egde is broken by an obstruction)you precalculate which portals connect to which portals inside the same block. You solve through the portals and solve between the portals. The soliving between the portals is very very quick because your working with a block of a small fixed size, you can keep a 2d arrary of open nodes and another of closed nodes which an the best possible access time ever of O(1). Plus if your blocks are small enough you probably won't get any benifit of having a sorted priority queue just use a first in first out queue and it will be faster. The other big plus is if your block is empty (also precalculatable) you can avoid A* through this block altogether and just go strait through. The real tricky part to this algarthim is that a portal isn't a single point it is a line that stretches a length, and determining where to pass through this line is the complicated a part. You guessitmate in some way by assuming the closes point to the destination or the point thats most in a strait line to the destination, or rather then using the final destination for these guesses use the next portal. Depending on your needs this may be enough. For me it was not and what I had to do is solve for every potentional pass through point in the portal and this can all be done at the same time but its more then I can explain in this post. If any one is seriously interested in this I might be inspired to write a tutorial on it.

Yeah, I'm using a similar approach... but I've strayed from the grid and use 3d waypoints (or nodes) instead. :) These are either "gridded and linked" at loading/runtime or handplaced in an editor...

Oh, and also each unit in my rts is a node of its own, so if it can see it's target, no pathfinding is done at all..

and then I use some basic collision detection to move/wait units if an obstruction is found...

If it still hasn't moved after some time, it will send a new pathfinding request etc.

My first implementation of A* took over 30 minutes to get a solution. Granted, I was searching 10s of thousands of nodes, but it was still slow. After doing some optimizing, it can now solve a path through a 200,000 node world in about 1/30 of a second (and that was with a map that basically made my heuristic function useless). I'm not sure how good that is, but it's been more than fast enough for the FPS I'm working on and it certainly beat the pants off what my basic implementation of the algorithm came up with :) My suggestions for a general case:

1. Don't use a heap, use a list. The benefits of fast adding/removing outweigh being able to search faster. In addition, there are three really good ways to speed up the cost of searching a list.

2. Don't use STL. You can get a much faster search by making each node/tile have a next and prev pointer. That is, if you have a node you can remove it directly which is O(1). In addition, if you want to insert into a known place, you can insert O(1) as well.

3. Use a char or int for flags. Rather than searching to see if a node is in the open or closed list, flag it on the node itself. Also flag whether a node is valid or blocked.

4. Make a memory manager and allocate nodes in chunks. Doing an alloc for each node is slow when searching through 1000s and 1000s of nodes.

5. Breakup your open and closed lists into many smaller lists and index them using a hash. It is generally much faster to hash and then search a list of 100 items than it is to search a list of 1000 items. Usually you can make a hash table of nodes pretty easily. For 2d paths, you can simply hash based on x and y coordinates, like in a bitmap.

6. Rather than searching for the best node in the entire openlist each loop or sorting the open list make a quicklist. The quicklist works like this: when looking for the best node, check the quicklist. If the list is empty, repopulate it with the 10 or 15 best nodes. Otherwise, return from the front of the list. Anything in the quicklist is also considered to be in the openlist. It should NOT exist separately in the open list. Since you can check the state of a node using its flag (as mentioned above), you don't need to search the quick list to see if something is in the open list. Also, whenever adding to the openlist, always check to see if you can add to the cheaplist. It's ok to let the cheap list size exceed its base size of 10 or 15.

Hope this helps.

Now that I think about it, my actual game had yet another optimization. There is a preset maximum number of nodes that can be in any given level in my game. I also know that any path can be solved within one game tick (i.e., no priority queue needed). Because of this, I preallocated ALL nodes for my A* engine. This not only removed any memory allocation, but it also removed the need for an A* memory manager :) In order to allow for multiple paths to reuse this array, it returns a pointer to a path structure that just contains the final list of waypoints it generated.