Home  Forums  Reviews  Guides  Newsgroups  Register  Search 
Thread Tools 
jesper@alphacash.se 


 
Dietmar Kuehl
Guest
Posts: n/a

http://www.velocityreviews.com/forums/(EMail Removed) wrote:
> A while back I was trying my hand at some pathfinding for a small game > I was making. What kind of path are you seeking? From your use of a heap I assume you are looking for some kind of shortest path search in some form of a graph. However, for a shortest path you should not need a heap which supports changing of a node's priority. Well, for a vanilla formulation of Dijkstra's algorithm you do but this is not how to implement it unless your graph is rather dense: just stick the edge instead of the node into the priority queue and test whether your node was visited. The tricky part of changing a node's priority is that this means that you need to support some form of node based priority queue where you can store some handle to the node in the priority queue and use this later when needed. This is a distinct disadvantage compared to a much faster array based priority queue which does, however, not allow [easily and efficiently] dealing with node handles. I have implemented various priority queues in the past (in particular dheaps and Fibonacciheaps) and measured a factor of 10 between using an array based dheap instead of a node based heap (e.g. the Fibonacciheap and a node based variation of a dheap). Also, the optimal "d" for a dheap is typically not 2 but rather something like 5 (this depends on the application and the relative cost of moving vs. comparing elements, of course; using a general dheap allows for profiling different values of "d"). > Is this implementation valid? Dunno. It is too big for me to quickly glance at it and determine whether the code does what it should especially as there is no statement what the code should do in detail. > Is this implementation fast? Dunno. > The member TNode * Spread[LevelSize][LevelSize]; I put it in > there to make accessing the open and closed lists faster, What is this good for? Maybe you should provide some details on what kind of paths you are seeking. Typical graph search algorithms require O(n) (where n is the number of nodes) memory with a rather small constant (e.g. 1/8th of a byte for each node because all what is really needed is a bit to mark whether a node was visited; whether this extreme is really useful is a different question, though, because extracting a bit is possibly more expansive than wasting some memory). > doubles the memory requirement of the object is there > another way that is better memorywize without being slower? Do you have a memory constraint? Well, of course, you don't have infinite memory. The question is essentially whether 'sizeof(TNode*) * LevelSize * LevelSize' is a substantial fraction of your overall memory and whether you have alternatives for using it. In general you can normally trade memory for speed. Of course, the more compact your working set is, the faster your code will be on modern processors (because more of the data you need fits into a suitable cache). > TBinaryHeap, can it be replaced with an stl container? Is that > faster? Replacing your heap with a version not supporting changes of the priority will definitely make the heap *much* faster. However, it also requires a change of in the algorithm to traverse the graph. As I said, I hadn't a too close look at your code. However: > float > nf=c+UtilCost(x,y,data)*sqrt(((GoalXx)*(GoalXx))+((GoalYy)*(GoalYy))); Typically, only the relative costs really matter. Thus, you may not need to use 'sqrt()' at all. I haven't looked at your use of the cost in detail but often you don't really necessary. Also, you seem to be moving through some form of a plain. In this case you might be able to immediately remove branches if the detour taken becomes too large. Of course, this depends on the topology of your graph. Depending on your cost functions you might be able to come up easily with an upper limit of the distance from your start to your target (e.g. by using Breadth First Search before employing are more advanced search) and ignore everything which would yield a longer path. This essentially limits the number of elements in your heap and thus the number of elements you need to process.  <(EMail Removed)> <http://www.dietmarkuehl.de/> <http://www.eaisystems.com>  Efficient Artificial Intelligence 




Dietmar Kuehl 


 
jesper@alphacash.se
Guest
Posts: n/a

Thank you for taking your time.
I wrote this routine to find a path from point a to point b, for "monsters" in a mazelike gaming level. (Very much like Nethack if that is familiar) The Idea was to use the same algorithm for all pathfinding tasks in the game. It's some time since I touched the code but I intend to return to it soon. It's kind of like a love child . I built it so that the AI could explore diffrent "Gain" values from taking diffrent routes. In effect making a certain detour worth the longer trip. This is why I needed to be able to change priorty. Or so I thought when I did it. Spread[LevelSize][LevelSize] I put in there to simplify checking if a node is on the openlist or closedlist. I don't have to traverse collections to find if a node is present. I can't remember why I put the sqrt in there (in any case a lookup table would have been faster, go figure). I'll take it out and test the game and see if something breaks You mention a "static" heap being much faster. I would like to learn (in general terms) how this is done, it sounds very intriguing. (I can't spell, *sigh*) At the moment the bintree is the fastest I know how to do. 




jesper@alphacash.se 
Dietmar Kuehl
Guest
Posts: n/a

(EMail Removed) wrote:
> I wrote this routine to find a path from point a to point b, for > "monsters" in a mazelike gaming level. (Very much like Nethack if that > is familiar) I ascended this year already > The Idea was to use the same algorithm for all pathfinding tasks in the > game. My idea would be more ambitious: use the same algorithm for all pathfinding tasks (note the omission of the phrase "in the game"). Effectively, this is what the BGL (Boost Graph Library; see <http://www.boost.org/>) is all about. > I built it so that the AI could explore diffrent "Gain" values from > taking diffrent routes. > In effect making a certain detour worth the longer trip. OK. I will assume that your maze consists of corridors and rooms. This can easily be modelled by a graph: each position represents a node and two nodes are adjacent, i.e. connected by an edge, if it is possible to move from on position to the other in one step. Each edge then become a weight representing the cost to move along this edge (note, that to use Dijkstra's algorithm it is necessary that all costs are positive; if you have negative costs for edges your problem would become real hard). This model can possibly refined to e.g. replace all nodes along a corridor by just one edge (in which case special treatment becomes necessary if the source and/or the target are somewhere within a corridor; of course, the special case of moving along a corridor towards a known end of the corridor is not really that complex to handle...): for the immediate decision, it is entirely sufficient to determine the next step and the details of corridors somewhere down the road are likely to be irrelevant. If the paths stay stable this could even be extended to rooms which are somewhat more complex to handle: a room could be replaced by its entrances which are each connected to all other entrances with an edge weight with the shortest path. Of course, this could even be taken one step further: if the paths have the same costs for all monsters (or if the costs just differ by a factor), it would be possible to create a data structure presenting the next step towards an arbitrary target for each node in the graph. This is what "allpair shortest paths" algorithms determine. However, this algorithm has a higher complexity and it thus makes sense to create a compressed representation first. > This is why I needed to be able to change priorty. I'm not sure whether I have understood this objective... > Spread[LevelSize][LevelSize] I put in there to simplify checking if a > node is on the openlist or closedlist. Are these used to represent whether a node was visited? I'm unaware of the use of terms "openlist" and "closedlist" in this context. I'd just call this a label where each label could, of course, represent the appropriate direction to take. Efficient access to such a label is, of course, essential. > You mention a "static" heap being much faster. Did I...? Oh, you mean a priority queue where the priorities don't change. Yes, this is much faster because all you need to maintain is essentially an array of pointers which are just moved appropriately. The movements are identical to those you use in your implementation (which is just a dheap with d == 2; d is the number of children each node has). However, you don't maintain the position of the object within the heap, i.e. you have no efficient access to a specific element (and hence you cannot change its priority efficiently). The 'std:riority_queue' is a class template which is implemented that way also using d == 2. I made a collection of several heap data structures available in the past which included a dheap where d was a template parameter. This collection also includes the Fibonacciheap I mentioned which performs better when you need to reduce the priority. > At the moment the bintree is the fastest I know how to do. Arraybased dheaps are the fastest approach for dynamic maintenance of priorities if you don't need to change priorities. However, I found that d > 2 is typically better. Of course, the bigger your objects, the bigger the d which is optimal: when increasing d you trade the number of comparisons against the number of moves. When you need to change the priority, Fibonacciheaps are better because they will reduce the overall number of operations, at least when the heap is used reasonably often: the have amortized constant costs for changing the priority (if I remember correctly) e.g. when using them with Dijkstra's algorithm.  <(EMail Removed)> <http://www.dietmarkuehl.de/> <http://www.eaisystems.com>  Efficient Artificial Intelligence 




Dietmar Kuehl 


 
Thread Tools  


Powered by vBulletin®. Copyright ©2000  2014, vBulletin Solutions, Inc..
SEO by vBSEO ©2010, Crawlability, Inc. 