Sign in to follow this  
Antonym

Pathfinding with Dynamic Environment

Recommended Posts

I am working on a spaceship game and am trying to accomplish several things. Make enemies able to find a path towards a certain target and/or position while navegating through a dynamic environment composed of: -Static terrain. -Huge asteroids that move slowly. -Small ones that move fast. -Other ships. The terrain is destructible and so are the asteroids. Make enemies able to dodge projectiles and approaching threats(Related to first?). Is there a method or combination of methods that could do this? Any info is much appreciated. Thanks.

Share this post


Link to post
Share on other sites
Do they need to move in 3D, or is it essentially a 2D problem, at least for the terrain?
I would start by using A* or similar to find a path through the terrain, and then avoid asteroids by simply turning to the side or up while following this path. It's probably not worth it to combine the methods, but rather just build two separate systems, one following a path towards a target, and one that overrides this behavior to avoid incoming projectiles.

Share this post


Link to post
Share on other sites
For dynamic scenes have a look at variants of A* including:

D*
Anytime D*

The different algorithms improve upon the basic A* algorithms to reuse previous information to make adjustments to the current plan based on the changes in the environment.

Basically, the general idea is to work backwards from the goal to the current location. Then, when the environment changes, put all the nodes that are affected into the open list and re-run the algorithm. This prevents having to start from scratch every time the scene changes.

- me

EDIT: more detail...

Share this post


Link to post
Share on other sites
You could stretch moving obstacles a bit in their direction of motion for the purposes of the path finding algorithm.

So if you have a rock (designated with an "o"):

o




traveling like this:

o ----->




Your pathfinder could pretend it was one long rock that looked like this:

=======





It'd still have inaccuracies, but it's probably cheaper than calculating a 4 dimensional route. Should perform passably for the occasional moving object, but if the scene is normally pretty cluttered with moving obstacles, this probably wouldn't work well.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this