Jump to content
  • Advertisement
Sign in to follow this  
SymLinked

Pathfinding grid and memory consumption.

This topic is 3410 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

Hi guys, I've implemented A* pathfinding in our prototype and it's working nicely, however the memory consumption is huge. I know it has to do with how I create the "grid" (the list containing all the nodes) and I would appreciate if someone has a better option here. What I'm doing is creating a list of size (NodesPerSide * NodesPerSide). This does lead to wasted space since not all of the nodes are used (~20% are used, the rest is unused.. we don't have many open areas to traverse) but it's fast and simple to find the closest node to a certain position in the 3d world.
index = start.x + (start.y * mCellsY);
If I were to start deleting unused nodes, this algorithm would fail. Manually searching the whole grid would work, but that sounds like it could be really really slow. Maybe seperating the level into several of these grids and doing the manual search would work? Going to try that but meanwhile any comments are very much appreciated!

Share this post


Link to post
Share on other sites
Advertisement
A couple of questions:

1. What's the environment like? Is a grid the most natural representation for the search space, or are you superimposing the grid over arbitrary geometry?

2. Are the majority of the grid cells unreachable? (That's what I gather from your post, but I just wanted to make sure.)

Share this post


Link to post
Share on other sites
Also if it's grid based, you can build it using a quadtree instead. Not all the places in the map require that much precision.

See an example of what I mean:


You will not only save memory, but also computation speed (Less nodes)

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
1. What's the environment like? Is a grid the most natural representation for the search space, or are you superimposing the grid over arbitrary geometry?


To be honest, I made it a grid because that's what I felt comfortable with and what most papers on the net went into detail about. The big deal for me here was the simplicity in searching a square grid.

Quote:
Original post by jyk
2. Are the majority of the grid cells unreachable? (That's what I gather from your post, but I just wanted to make sure.)


That's right. The level is made up of tunnels mostly, with a larger room here and there.

Quote:
Original post by Daivuk
Also if it's grid based, you can build it using a quadtree instead. Not all the places in the map require that much precision.
(Video)


That's beautiful. Thanks for the motivation!

Share this post


Link to post
Share on other sites
Based on what you've described, I don't see any reason to use a full grid for this. Using a full grid certainly simplifies things somewhat, but it wouldn't be too involved to implement a more memory-friendly version, I don't think.

Although I'm sure a quadtree (as suggested by Daivuk) would work, you might be able to get away with something even simpler.

The first step would be to store only the used (reachable) nodes, and make the links between them explicit rather than implicit.

You would then of course need a way to quickly find the node associated with a given coordinate. If there are few enough nodes overall, you might be able to get away with a linear search. Otherwise, you could hash into the node array using the input coordinate, or perhaps sort the nodes by coordinate (using a lexicographical comparison), and then do a binary search to find the node associated with the input point. (I haven't thought either of these approaches through carefully, so there may be flaws with either or both of them.)

[Edit: You could also match coordinates to nodes using a map (std::map in C++). This would be somewhat similar to the second option described above (the binary search), but would be more straightforward to implement.]

Share this post


Link to post
Share on other sites
You could make your grid nodes a little smarter, such that they kept pointers to up, down, left, right. Then a NULL neighbor shouldn't be considered since he doesn't exist.

Share this post


Link to post
Share on other sites
Quote:
You could make your grid nodes a little smarter, such that they kept pointers to up, down, left, right. Then a NULL neighbor shouldn't be considered since he doesn't exist.
Just to clarify my own post, that's actually what I meant by making the links between nodes explicit rather than implicit. (The links could be pointers as you suggest, or even just the indices of other nodes in the array.)

Share this post


Link to post
Share on other sites
Is this data structure you refer to the "map" or graph that you are searching? If so then all you really need is a bitmap; you're just storing an occupancy grid and the 'neighbors' are implied. You can pack 8 cells into each byte. Compare this to data structures that keep a bunch of pointers around: each pointer takes 32 (or 64) bits!!

If the data structure you refer to is your OPEN list (which is really a priority queue, not a list), then consider dynamically allocating space. Obviously dynamically allocating space at runtime can be slow if you're really naive about it, but if you begin with a reasonable guess at the typical maximum size of your queue and then use a size-doubling strategy I think you'd be fine.

If the data structure you refer to is the CLOSED list (which is really better implemented as a hash than a list), then this too can just be implemented as a bitmap.

Share this post


Link to post
Share on other sites
It's the graph, a bunch of nodes each with its own list of neighbours.

I'm trying to save some time now by trying external libs, and the Boost Graph Library looks interesting. Will it do all this for me? I've been looking trough their docs, but it isn't said anywhere how their allocation works in regards to "removed" nodes. In another lib I tried, the node was merely marked as such but still existed in memory, which is the opposite of what I want.

Share this post


Link to post
Share on other sites
Quote:
Original post by SymLinked
It's the graph, a bunch of nodes each with its own list of neighbours.


Then just let the graph be implied by an occupancy grid. Don't explicitly store neighbors anywhere. The neighbors are just whatever cells in the occupancy grid that you can get to in one move that are not occupied. You could even wrap this stuff in accessor functions so that it "looks" like a graph; e.g., consider a "getNeighbors" function that, given an index into the occupancy grid, returns the indexes of all adjacent cells that are not occupied. You can wrap this up in whatever OO-prettiness you want in the language of your choice; e.g., you could have an abstract "GraphNode" class of which "OccupancyGridGraphNode" is an implementation. Under the hood, "OccupancyGridGraphNode" could be implemented as indexes into an occupancy grid, but A* doesn't have to know.

Quote:
but it isn't said anywhere how their allocation works in regards to "removed" nodes.


Wait... instead of maintaining a CLOSED list, you want to somehow remove those nodes from memory? I get it. But you still need some representation of your map somewhere in memory at all times, so rather than copying that and then deleting that copy as you go, why not just work with the original representation?

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!