quote:Original post by weasalmongler
What if you preprocess the level and group all nodes that can reach each other, any nodes that are unreachable are placed in another node list, or are simply tagged as part of a different group. Before performing the A* search, you check whether the target and start nodes are in the same group, if they are, voila, they will reach each other so you can begin the search, if not, exit immediately and you don''t even have to start the A* search.
- James
Sure this would solve one problem, but introduce a new overhead to all pathfinding calculations (which may or may not be significant depending on the specifics of the world and the implementation). There are some pre-culling operations you could use before using such a solution, such as, for any given grouping of nodes, have a centre point and a radius which envelopes all the nodes within the group. Then check if the target node falls within this circle (or sphere if you''re working in 3D). If it does then it still might not be connected, but if it doesn''t then it certainly is not connected and you can early-out with a failure.
I would also suggest that any grouping you used for the nodes be contained in such a manner as to allow fast retreival. Instead of using a list or a vector, for instance, you could a set, where the container simply stores a set of unique keys, the key could be the address of a node. This is a fast method (perhaps not the fastest, but orders of magnitude faster than a list retrieval) for finding out if a node is in a grouping.
Mike
