13
\$\begingroup\$

I've got a game situated in space, and I'd like to issue movement orders, which requires pathfinding. Now, it's my understanding that A* and such mostly apply to trees, and not empty space which does not have pathfinding nodes. I have some obstacles, which are currently expressed as fixed AABBs- that is, there is no unbounded "terrain" obstacle. In addition, I expect most obstacles to be reasonably approximable as cubes or spheres.

So I've been thinking of applying a much simpler pathfinding algorithm- that is, simply cast a ray from the current position to the target position, and then I can get a list of obstacles using spatial partitioning relatively quickly. What I'm not so sure about is how to determine the part where the ordered unit manoeuvres around the obstacles.

What I've been thinking so far is that I will simply use potential fields- that is, all units will feel a strong repulsive force away from each other and a moderate force towards the desired point. This also has the advantage that to issue group orders, I can simply order a mid-level force towards another entity. But this obviously won't achieve the optimal solution.

Will potential fields achieve a reasonable approximation given my parameters, or do I need another solution?

Improve this question
\$\endgroup\$

1 Answer 1

Reset to default
7
\$\begingroup\$

While potential fields may work, I imagine you'll have issues with sub-optimal paths and "local minimums" where your units will be trapped by surrounding obstructions. A* is suitable for 3D open space environments. It simply becomes an issue of generating a navigation mesh that fits your needs. You can even use structures like Octrees for navigational nodes. The smaller the maximum size of each octant, the smoother the path. Check out this article from Face to Face games (now defunct, added wayback link). A* combined with path optimization (like line of sight shortcuts) and steering behaviors and you'll be good to go! See the image below as an example of using an octree for path nodes:

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ How is this going to scale to larger maps? If I had a map that was twice as large in each dimension, I'd need eight times the number of nodes, which would be problematic. \$\endgroup\$
    – DeadMG
    Apr 10, 2012 at 0:14
  • \$\begingroup\$ Not necessarily. You can keep the node size large until your search gets near it. This allows you to keep the nodes you're not interested in rather large and few in number. \$\endgroup\$
    – House
    Apr 10, 2012 at 0:55
  • \$\begingroup\$ A nice property of empty space navigation meshes is journey cost equality; you may be able to use A*JPS \$\endgroup\$
    – Will
    Apr 10, 2012 at 8:11
  • \$\begingroup\$ @Will: I did a bit of Googling, but I didn't really understand the only pathfinding algorithm that came up. Care to post an answer on it? \$\endgroup\$
    – DeadMG
    Apr 14, 2012 at 21:49
  • \$\begingroup\$ @DeadMG this is definitive explanation: harablog.wordpress.com/2011/09/07/jump-point-search <br/> If you can implement A*, you can then retrofit JPS to it fairly straightforwardly. Do A* first, and add JPS as an optimisation. \$\endgroup\$
    – Will
    Apr 16, 2012 at 11:51

You must log in to answer this question.

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