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!

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

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)

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!

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

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.

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

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.

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.

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?