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?
Answer
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:
No comments:
Post a Comment