Storing Nodes
I have started to put AI in my game using nodes which I guess are about the same as waypoints. I'll eventually use the nodes for A* searches but right now I've run into an issue with storing the nodes.
For use in the A* or any regular AI pathfinding what is a good way to store the nodes in your program? I was thinking that I might do it by having a list of structures containing the location of the node, a possible child node and possible sibling node as in a hierarchy.
I found two problems with this though. The first being, if the character is trying to go up the hierarchy, how will it find it's parents? Also, it seems that if there were branching in paths for the character, it might be slow for the computer to search through siblings.
Does this mean I should just store a list of connections from each node? This seems like it would be fastest for computation but the most memory consuming. I'm very new to this so I don't know how most people deal with this. What would you recommend?
Thanks a lot.
I would recommend a way point class with variables for it's position, and references to all other way points that it is connected to and a list of the distances/weights to each of those way points. This will likely store several weights twice, but that is somewhat necessary if you want to have the possibility that going to and coming back from a node might have different weights(like when one is uphill from the other).
When dealing with storing general graphs there are essentially two way to do it: An adjacency list, and an adjacency matrix. The above is an adjacency list. It works well when moving through graphs, and it is more memory efficient when the graphs are sparse. An adjacency matrix is most efficient with dense graphs where weights are referenced directly.
When dealing with storing general graphs there are essentially two way to do it: An adjacency list, and an adjacency matrix. The above is an adjacency list. It works well when moving through graphs, and it is more memory efficient when the graphs are sparse. An adjacency matrix is most efficient with dense graphs where weights are referenced directly.
Quote:Original post by Programmer101
I found two problems with this though. The first being, if the character is trying to go up the hierarchy, how will it find it's parents?
In the underlying graph, there is no 'up' or 'parents'. That comes about as a result of the A* search, which represents possible routes through the graph. Although many implementations of A* consider one position on a map to be one 'node' and use that both for the map representation and the search representation, it's important to understand that this is an implementation detail rather than how the algorithm actually works. It would be perfectly ok under some circumstances to have one of your waypoint nodes to appear several times in an A* search and to have a different parent in each situation. However most of the time you never need that, so you just overwrite previous instances if the previous instance was more expensive.
Quote:Also, it seems that if there were branching in paths for the character, it might be slow for the computer to search through siblings.
Does this mean I should just store a list of connections from each node?
Yes. Alrecenk has explained the benefits of adjacency lists and graphs, and in the pathfinding scenario you almost always want an adjacency list for your nodes. Generate those lists offline wherever possible.
Quote:This seems like it would be fastest for computation but the most memory consuming.
Hardly. Storing a pointer or an index to an adjacent waypoint is just a few bytes.
Quote:I'm very new to this so I don't know how most people deal with this. What would you recommend?
I would recommend that you look at how large a typical graphics texture is before you worry about trimming a few bytes off your AI. ;)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement