How to find where to cast a ray to avoid collision in Bullet?

Question

Say we have an object at point A. It wants to find out if it can move to point B. It has limited velocity so it can only move step by step. It casts a ray at direction it is moving to. Ray collides with an object and we detect it. How to get a way to pass our ray safely (avoiding collision)?

btw, is there a way to make such thing work in case of object cast, will it be as/nearly fast as with simple ray cast?

Is there a way to find optimal in some vay path?

Answer 1

What you're asking about is actually a pathfinding question; more specifically, it's the "any-angle pathfinding problem."

If you can limit the edges of obstacles to a grid, then a popular solution is to just use A* on that grid, then apply path-smoothing. However, there is a (rather recent) algorithm that is both simpler to implement/understand and gives better results than path-smoothing. It's called Theta*.

There is a nice article explaining Theta* (from which I stole the above image) here

---

If you can't restrict your obstacles to a grid, you'll have to generate a navigation mesh for your map:

There are many ways of doing this, of varying complexity; see for example here, here, or here. A quick google search also turns up plenty of libraries available to do this for you, such as this one or this one.

Answer 2

One approach could be to use a rope, or several ropes, where a rope is made of a few points connected linearly. You can initialize the points in random places in space, but the first point is the initial position of A, and the last point is the final position of A.

Initially, the rope will be a very bad route. In order to optimize, move the points along an energy gradient. In your case the energy function is very simple, i.e. the total length of the rope.

This is not a new idea but is used in computer vision to detect boundaries of objects, although the energy functions are much more complicated. Yet, have look at "snakes" to give you an idea how to move each point given its two neighbors: http://en.wikipedia.org/wiki/Snake_(computer_vision)

In your case, however, simply deriving a direction for each point from the force exerted by its neighbors will be just fine.

Your problem is a constrained problem where you consider collision. I would really go with @paddy's idea here to use a convex hull, or even just a sphere for each object. In the latter case, don't move a point into a place where its distance to B is less than the radius of A plus the radius of B plus a fudge factor considering that you don't have an infinite number of points.

A valid solution requires that the longest distance between any neighbors is smaller than a threshold, otherwise, the connecting line between two points will intersect with the obstacle.