Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
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. – Patrick Hughes Mar 16 '12 at 1:15
Nothing to do with space partitioning as far as I know. :) – user14170 Mar 16 '12 at 15:19
Thank you for the replies. It's just as I thought :) – Tangeleno Mar 16 '12 at 17:50
up vote 1 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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