I'm planning on implementing A* in my game for pathfinding, I understand the basics of how the algorithm works but I was wondering, other than finding the start and end nodes Are there any benefits to placing the navigation graph into a tree? It seems to me that it wouldn't really benefit any as each node has a list of connections to other nodes. But I recall reading an article about pathfinding a while back and it suggested using a space partition tree, I believe it suggested an AABB tree to be exact.

If A* wouldn't benefit would any of the algorithms benefit from such a thing?

And no, sadly I can't find the article again.

  • 1
    \$\begingroup\$ No benefit at all to path finding algorithms. Maybe to path following and obstacle avoidance while the actor is moving, but not to generating the path in the first place. Unless your world is stupendously large and intricately detailed, which is doubtful. \$\endgroup\$ Mar 16 '12 at 1:15
  • \$\begingroup\$ Nothing to do with space partitioning as far as I know. :) \$\endgroup\$
    – user14170
    Mar 16 '12 at 15:19

Space partitioning would be useless for A* in an established graph.

Spatial partitioning speeds collision checking, which is useful when constructing a graph that you navigate with A*. In a static environment, you should be pre-calculating the graph. In a dynamic environment, you will need to do some collision-checking on-the-fly to, at the very least, discover when edges have been broken by changes, and to find new paths.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.