# Pathfinding with Dynamic Environment

This topic is 3433 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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.

1. 1
2. 2
Rutin
16
3. 3
4. 4
5. 5

• 11
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633722
• Total Posts
3013538
×