c++ - 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.