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

I posted a pathfinding algorithm in C# a while back

Here's the link

You can try and use it as a starting point, ie, you could modify the function that checks the next cell to see if it's valid to check for the obstacles, and you could feed it small intervals instead of the starting and end points, kinda like multiple mini-pahfinding routes.

(The text is in spanish, but you can download the application from the link at the top)

Answer 2

Maybe you could use Pledge's algorithm

Answer 3

Whenever your creature, travelling in vector direction v, collides with a wall whose direction is represented by vector w, the direction that you need to "slide" is given by the vector that is the projection of v onto w. This can be found using

  v . w
--------- w
 |w|*|w|

where . is the vector dot product and |w| is the magnitude of vector w ( = sqrt(w . w)). If w is a unit vector, this becomes simply

(v . w) w

Using the resulting vector as your creature's speed will mean your creature travels quickly when it just "grazes" the wall, and slowly when it hits the wall nearly dead-on. (This is how most first-person shooter games manage collisions for the human player.)

If instead you want your creature to always travel at full speed, you only need the sign of v . w -- you will always be travelling either in the direction the wall faces (w) or the opposite direction (-w).

The issue that you will have is when your creature hits the wall dead-on. In that case your projected vector will be (0, 0), and you need some other technique to decide which way (w or -w) to go. The usual approach here is A*, although this may be unnecessary if your environment possesses enough structure.

Answer 4

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 5

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.