• Advertisement
Sign in to follow this  

PathNodes: array or list

This topic is 1065 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I store my PathNodes in an array that lets me instantly get the PathNode at (x,y). If I used a list, I'd have to go through the list to match the coordinates and only then be able to tell if it's closed or open or not added yet. However the array uses up a lot of memory and this is a cache miss. Do people do it both ways? You could get both benefits by having an array of pointers that might be NULL that point to the PathNodes in the list to get instant access time.

Share this post


Link to post
Share on other sites
Advertisement

You are talking about pathfinding, right ? In this case you often need only to find a handful of nodes to start your pathfinding (eg A*). Once it has started you can traverse the graph by using a adjacent list, so once your pathfinding is running , you can access each node of interest in O(1).

 

For the general node structure I would sugguest a tree (quad/oct tree). Most trees suited for this task guarantee an access time of O(log n).

Edited by Ashaman73

Share this post


Link to post
Share on other sites

Assuming you are talking about A*, you will use more than one container for the pathfinding, you will need one to represent your scenario, one for the open list and one for the closed list.

 

The simplest solution is to use a grid to store your nodes and represent your scenario (assuming all your nodes have the same area size), where node of position x, y can be directly translated to the grid x, y index. A grid has two problems, the first one is that it will use a lot of memory, the second is that you will have a lot of nodes.

 

The best container to keep an open list a heap, since it will always recover the node you need in O(1), inserting an element in a heap is a O(log n) operation. Just keep in mind that you will need a modified heap, as you need to update the node cost (you can also update the values and call the heapify operation, if your implementation allows it).

 

For the closed list I like to use a list and a flag in the node, once I add it to the closed list I mark the flag and add it to the closed list. This approach is good because the only information you need for the closed list is if the node is in it. In the end of the pathfinding I go through all the elements of the list, reseting the flag.

Share this post


Link to post
Share on other sites

Just keep in mind that you will need a modified heap, as you need to update the node cost (you can also update the values and call the heapify operation, if your implementation allows it).


The problem with trying to update the node cost in the heap is that you need another structure to keep track of where things are in the heap, or you need to keep the costs in a separate structure... An easier solution is to allow a node to be inserted multiple times in the heap. When you take a node out of the heap, you check if it is in the closed list, and in that case you skip it.

Share this post


Link to post
Share on other sites

If you repeatedly do pathfindings over the same terrain  then keeping an array (with the inbuilt relation between nodes) can be less costly  -- particularly if you have to interpret/process  the actual (raw) terrain to generate the 'symbolic' map - simplified down to what the pathfinding needs to know -- eliminating re-doing THAT every pathfinding can be a significant saving    (interpretations like edge costs/impassibility  in different directions for slopes, content of the nodes for difficulty of movement, etc... )

 

Of course now you may need a array grid for the entire map (versus a subset around where the pathfinding is done if you rebuild that data each time)  

Share this post


Link to post
Share on other sites

I use a specialized priority Queue  for my Open list, and a dictionary for my visited nodes.  I know that another way to do it, for grid implementations, is to have a bitfield for the visited nodes.  Then it's trivially easy to clear all the bits.  And now that I wrote that, I think I'll looking into seeing how I'd do that for C# and see if I get any performance gains.  

 

EDIT:  It would be slightly trickier in my case, since i'm doing directional and minimum turn radius.

Edited by ferrous

Share this post


Link to post
Share on other sites

I have an interesting dilemna for the experts. It is about CPU use vs. cache misses. I have a max of 63x63 tiles on a map, each of which breaks down into 20x20 collider tiles and pathnodes. No unit can be smaller than a collider tile, and so it has only room for 4 unit ID's to be partly occupying it at the same time. It takes a ushort to store a unit ID but a bitfield might also be used because they only go up to 4098. 63x63x20x20x12 bit bitfield = 2,381,400 bytes = 2,325.58594 kB = 2.271 MB. Most of the A* pathnode checks will return no collision and require no precise collision check. However if we use a map tile size for the collider tile, and keep a list for any units in the tile, we fragment the memory but we also reduce memory use significantly. But we also have to check for collisions with all units on that map tile for each pathnode we check.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement