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

Question

Say we have an object at point A. He wants to know if he can go to point B. He has a limited speed, so he can only move step by step. He throws a beam in the direction he is moving. Ray collides with an object, and we discover it. How to get a way to safely transmit our beam (avoiding a collision)?

btw, is there any way to make such a thing work in the case of an object, will it be / almost fast, as when using a simple beam?

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

Answer 1

What you are asking is actually a search related question; more specifically, this is a "problem with any angle of the search path."

If you can limit the edges of obstacles to a grid, then a popular solution is to simply use A * on that grid and then apply path smoothing. However, there is a (quite recent) algorithm that is easier to implement / understand and gives better results than smoothing the trajectory. It is called Theta * .

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

---

If you cannot limit your obstacles to a grid, you need to create a navigation grid for your map:

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

Answer 2

One approach may be to use a rope or several ropes, where the rope consists of several points connected linearly. You can initialize points at random places in space, but the first point is the starting position of A , and the last point is the ending position of A.

Initially, the rope will be a very bad route. To optimize, move the dots along the 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 the boundaries of objects, although the energy functions are much more complicated. However, take a look at the “snake” to give you an idea of ​​how to move each point, given its two neighbors: http://en.wikipedia.org/wiki/Snake_(computer_vision )

In your case, however, a simple indication of the direction for each point from the force exerted by its neighbors will be very good.

Your problem is a limited problem when you consider a collision. I would really go with the @paddy idea here to use a convex hull or even just a scope for each object. In the latter case, do not move the point to a place where its distance to B is less than the radius A plus radius B plus the fudge factor, given that you do not have an infinite number of points.

An acceptable solution requires that the largest distance between any neighbors be less than the threshold, otherwise the connecting line between the two points will intersect with the obstacle.

Answer 3

How about a simple approach to start with ...

If this is just one object, you can calculate the convex hull of all the vertices of the obstacle, as well as the start and end points. Then you explored two directions to get from A to B, going through the body clockwise and counterclockwise. Choose the shortest path.

This is a little more complicated because the shape you move is not just a point. You cannot just blindly move your center, otherwise it will collide. This gets even harder as it moves past the top because you have to graze the edge of your object against the top of the obstacle.

But hopefully this gives you an idea of ​​this, which is conceptually difficult to understand.

Answer 4

I made this image to talk about my idea of ​​reaching an object at point B. Objects in the image: - The object is a blue dot. Red lines are obstacles. The gray dot and line is the area that can be reached. The purple arrow is the direction of point B. The gray line of the object is the field of view. Understanding the image: - The object will have a certain scope. This is a 2d situation, so I suggested that the field of view should be 180deg. (for human visibility see http://en.wikipedia.org/wiki/Human_eye#Field_of_view ). The object will measure distance using the SONAR idea. With SONAR, an object can recognize the area in which it can fall. Using BACKTRACKING, the object can find out the path to the object. If there is no path, the object must change the field of view

Answer 5

One way to look at this is with custom shadows. Make A “light source,” and then decide whether each point in the scene is in or out of the shadow. Those who are not in the shade are accessible by rays from A In other areas, no. If you find B in the shadow, you only need to find the closest point in the scene that glows.

If you discretize this problem in “pixels”, then the above approach has very well-known solutions in the vast computer graphic literature on shadow rendering. For example, you can use the Shadow Map to draw each pixel using a boolean flag that indicates whether it will be in shadow or not. Finding the closest lit pixel is just a search for growing concentric circles around B Both of these operations can be performed very quickly using the GPU hardware.

One more note. You can view the problem of detecting shared objects as a point path problem. The secret is to “develop” obstacles by an appropriate amount, using Minkowski’s differences. See, for example, this robot route planning work .