2
\$\begingroup\$

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.

\$\endgroup\$
2
  • 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\$
    – Patrick Hughes
    Commented Mar 16, 2012 at 1:15
  • \$\begingroup\$ Nothing to do with space partitioning as far as I know. :) \$\endgroup\$
    – user14170
    Commented Mar 16, 2012 at 15:19

1 Answer 1

Reset to default
1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .