How to find where to cast a ray to avoid collision

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

How about a simple approach to begin with....

If this is just one object, you could compute the convex hull of all the vertices of the obstacle, plus the start and end points. You would then examine the two directions to get from A to B by traversing the hull clockwise and anti-clockwise. Choose the shortest path.

It's a little more complex because the shape you are moving is not just a point. You can't just blindly move its centre or it will collide. It gets more complicated still as it moves past a vertex, because you have to graze an edge of your object against the vertex of the obstacle.

But hopefully that gives you an idea to ponder over, that's not conceptually difficult to understand.

Answer 2

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 3

I have made this image to tell my idea for reaching the object to point B. Objects in the image :- The dark blue dot represents the object. The red lines are obstacles. The grey dot and line are the area which can be reached. The purple arrow is the direction of the point B. The grey line of the object is the field of visibility. Understanding the image :- The object will have a certain field of visibility. This is a 2d situation so i have assumed the field of visibility to be 180deg. (for human field of visibility refer http://en.wikipedia.org/wiki/Human_eye#Field_of_view ) The object will measure distance by using the idea of SONAR. With the help of SONAR the object can find out the area where it can reach. Using BACKTRACKING, the object can find out the way to the object. If there is no way to go, the object must change its field of visibility

Answer 4

One way to look at this is as a shadow casting problem. Make A the "light source" and then decide whether each point in the scene is in or out of shadow. Those not in shadow are accessible by rays from A. The other areas are not. If you find B is in shadow, then you need only locate the nearest point in the scene that is in light.

If you discretize this problem into "pixels," then the above approach has very well-known solutions in the huge computer graphics literature on shadow rendering. For example, you can use a Shadow Map to paint each pixel with a boolean flag that indicates whether it's in shadow or not. Finding the nearest lit pixel is just a simple search of growing concentric circles around B. Both of these operations can be made extremely fast by exploiting GPU hardware.

One other note: You can treat a general object path finding problem as a point path problem. The secret is to "grow" the obstacles by an appropriate amount using Minkowski Differences. See for example this work on robot path planning.

Answer 5

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.