Basic pathfinding with obstacle avoidance in a continuous 2D space

Question

I'm writing a simulation in which a creature object should be able to move towards some other arbitrary object in the environment, sliding around obstacles rather than doing any intelligent pathfinding. I'm not trying to have it plan a path -- just to move in one general direction, and bounce around obstacles.

It's a 2D environment (overhead view), and every object has a bounding rectangle for collision detection. There is no grid, and I am not looking for A* solution.

I haven't been able to find any tutorials on this kind of "dumb" collision-based pathfinding, so I might not be describing this using the most common terms.

Any recommendations on how to implement this (or links to tutorials)?

Answer 1

Expanding on what Guillaume said about obstacle avoidance, a technique that would work well for you is anti-gravity movement. You treat local obstacles as point sources of antigravity, the destination as gravity, and your computer controlled character will slip (like soap!) around the obstacles to get to the destination.

Answer 2

you can combine two steering algorithm :

seek : you apply a steering force in the direction which is the difference between the current velocity and the desired velocity towards the target

Obstacle Avoidance : you anticipates the vehicle's future using a box whose length is a constant time multiplied by the current velocity of the vehicle. Any obstacle that intersects this box is a potential collision threat. The nearest such threat is chosen for avoidance. To avoid an obstacle, a lateral steering force is applied opposite to the obstacle's center. In addition, a braking (deceleration) force is applied. These forces vary with urgency (the distance from the tip of the box to the point of potential collision). Steering varies linearly, braking varies quadratically.

You can find more on the website "Steering Behaviors For Autonomous Characters"

regards

Guillaume

PS : this assume you're using a point/velocity/acceleration method for the object's movement.

Answer 3

Maybe you could use Pledge's algorithm