Planning movement without a graph across an infinite plane

Question

The object is placed in A and wants to go to B. I want to calculate there a motion vector that does not move within the distance D of the points that will be avoided in the array C.

So, if the displacement vector (BA), normalized and multiplied by the speed of the objects, leads it to D at any point in C, the vector will be rotated so that it does not.

It is in two dimensions. Also, if this operation has a name, make a comment or edit this question yourself, since I had no idea how to call it.

In addition, my first instinct was to divide the active region into nodes and run A *, but I want to try the mathematical approach on this, several experiments with flocking give me the impression that this can be done.

Refresh (from comments): This image is very close to the solution I want:

Assuming that we start at a point on the left, we begin to turn right towards the target (another point), we find a wall on the right so that we stop turning and move forward. The wall was gone, so we were allowed to start moving towards the goal again and so on. I know that this can cause the object to not get there at all, but I want to determine the behavior , not necessarily the solution , if you know what I mean.

Update2 : translating the active area into a set of nodes may be ineffective. A * and other heuristic graph traversal algorithms are great for small-dimensional problems. But the area that I want to resettle is infinite in size and has only a few obstacles scattered around it. The nodes themselves, or rather, potential positions, are infinitely small. Of course, this could be optimized using a quad tree, but I have a feeling that simple motion vectors that somehow rotate and interpolate can also solve this problem.

Answer 1

Also on the page you link to in your answer , the behavior of the steering as a whole is pretty well discussed.

In particular, look at its pages for containment and the path for good examples.

Steering behaviors for autonomous characters

Answer 2

I heard that this is called traffic planning , and path finding (as mentioned above)

There are many algorithms available, but from your description, a visibility chart may be a good start. You have a graph with points A, B and polygons around each point C (you can also do this with circles, calculating the tangent lines from each point, I suppose). You calculate edges as potential paths between points. Here's a slide show that explains it better.

Then at the top of the visible graph, apply a search algorithm such as A * (heuristic search) to find the most optimal path through the graph.

However, you should consider what you are looking for. The above approach will find the shortest path, approaching all angles as close as possible, but other algorithms may better match your idea of ​​optimality.

Answer 3

You can use potential fields . This avoids the "hugging edges" of obstacles.

But note that, like the A * algorithm, this requires that you quantize the state space and, therefore, could be computationally intensive enough depending on how much accuracy you need.

Answer 4

I found a fairly detailed description of the flocking procedure on this page .

Use the separation rule for all obstacles and alignment only in relation to the position of the target (since we do not have teammates) and (for the same reason) ignore the rule of cohesion.

I realized that this will give the desired effect.