Quote: Original post by Emergent

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?

Quote: Original post by SymLinked
I'm thinking we're on a different technical level here or we're simply talking about different stuff. :) I'm talking about the grid which occupies the whole area meant to be pathfinded trough. Each node has a neighbour list and a integer which determines the type (walkable, wall - etc). That's the list that's too large.

struct Node{    Vector3 position;    std::vector<Node*> neighbors;};

Quote: Original post by Palidine
Yeah, basically what they're suggesting is have a data-compilation stage in your pipeline. Walk your map and create a node graph

Quote: Original post by SymLinked
Each node has a neighbour list

For each element in Node's neighbor list   do stuffend

For each cell C of the four cells in my grid adjacent to Node // You do this by adding to your (x,y) coordinates.   If C is walkable // Check your occupancy grid for this       do stuff   endend

Quote: Original post by jyk
I think the OP is saying that linking to neighbors implicitly won't work because he doesn't want to store the grid in its entirety, but rather only the nodes of interest (i.e. those that are reachable).

Quote: Also, it doesn't sound like a bitfield will work, since the cells store more information than simply 'blocked or unblocked'.

Quote: I think I've started to "get" that this is what he's thinking. But,
1 - "Storing only the nodes of interest" isn't necessarily smaller, because it necessitates a more complicated data structure. There's also a lot of redundancy when you have explicit pointers to neighbors: If your graph is undirected (meaning: If I can walk from a to b, then I can always walk from b to a), then why do we need to store a pointer in each direction? That's 64 or 128 bits right there for something we knew a priori anyway.
2 - If I were a betting man, I'd put money on OP having the entire map in memory anyway. How else can he draw the level, for instance? If he has this, then also having another data structure is just redundant and inefficient.

Quote: Original post by Palidine
So you programatically explore your maps and essentially throw away all the nodes that are not walkable. Then at runtime you pathfind through this pruned node list rather than your grid.

What's the size of your grid? Novice mistake but are you possibly creating the node grid on the stack instead of the heap ( Node myNodes[width][height] instead of Node *myNodes = new Node[width * height]; )

Quote: Original post by jyk

Quote: 2 - If I were a betting man, I'd put money on OP having the entire map in memory anyway. How else can he draw the level, for instance? If he has this, then also having another data structure is just redundant and inefficient.

Well, he could (presumably) draw the level by iterating over the nodes in the reduced list and drawing each in turn. But you're right - since we don't really know much about the application, these are all just guesses, more or less :)

Quote: Original post by SymLinked

Quote: Original post by Palidine
So you programatically explore your maps and essentially throw away all the nodes that are not walkable. Then at runtime you pathfind through this pruned node list rather than your grid.

What's the size of your grid? Novice mistake but are you possibly creating the node grid on the stack instead of the heap ( Node myNodes[width][height] instead of Node *myNodes = new Node[width * height]; )

It's allocated on the heap. I used a build I found on the web and they store something like ~48 bytes per node. That's a lot of memory. All three examples I've looked at store their neighbours in a Vector per node, etc.

Quote: Original post by jyk

Quote: 2 - If I were a betting man, I'd put money on OP having the entire map in memory anyway. How else can he draw the level, for instance? If he has this, then also having another data structure is just redundant and inefficient.

Well, he could (presumably) draw the level by iterating over the nodes in the reduced list and drawing each in turn. But you're right - since we don't really know much about the application, these are all just guesses, more or less :)

I have the entire map in memory, yeah. But it's nothing you can use to pathfind, or else I would have used it. It's a seperate data structure of AABB's and its much less dense.

Anyhow, I'll get to work. If I do try the Boost libs I'll post back the results here. Thanks alot for the discussion guys!

Quote:
4 bytes for index.
8 bytes for position.
4 bytes for "extra information".
A std::vector for neighbours.
4 bytes for state.