1
\$\begingroup\$

I have a problem more closely described on a picture below. The idea is that I have my agent in point A and I want to get to the point B. The problem is, that agents rotation towards point B is alpha degrees. I want to get to the point B in n steps (path segments) such that at each step, I rotate towards point B by uniform degrees. That should be (if I am not mistaken) \$2\times\frac{alpha}{n}\$ degrees at each step.

Update: as correctly pointed out, it should be \$2\times\frac{alpha}{n - 1}\$ degrees at each step.

enter image description here

I want to know how big of a steps (path segments) I need to make so they all have same size and will get me to the point B.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Is this for problems that you know will have solutions like you've shown? For instance, if your illustration has has the tightest possible turn & the destination is half way between pts A & B, then you'd need a different route entirely to get there. If the solution needs to find a turning radius constrained route that's doable, but a lot more complex than finding the segment size of a known path. \$\endgroup\$ Commented Jan 6, 2024 at 17:41
  • \$\begingroup\$ @Pikalek Scenarios that I have should have solution. Destination doesnt dynamically change. I start at point A and should end in point B. Turning radius should be uniform (same for each segment) which should be \$2\times\frac{alpha}{n}\$ degrees. \$\endgroup\$ Commented Jan 6, 2024 at 19:53
  • \$\begingroup\$ @Peter, are you sure about your formula for the angle? 2 times alpha divided by n? It seems to me that if alpha is 90, and n i 2 then it woul yield a turn angle of 90, which wouldn't get you to point b in two segments. \$\endgroup\$ Commented Jan 7, 2024 at 11:36

2 Answers 2

Reset to default
0
\$\begingroup\$

A simple way to solve this is just to assume all segments have length 1 for a first pass, so they contribute a distance parallel to AB equal to the cosine of their angle (using our friend the unit circle). We can then add up this contribution across the n segments to get the total distance along AB when the arc curls back to cross the line. It might overshoot or undershoot B, but that's OK. We can take the distance AB and divide it by the total distance we tabulated to get a scaling factor that will make it match exactly. That quotient is then the segment size to use.

float GetSegmentSize(Vector2 A, Vector2 B, float startAngle, int segmentCount) {

    // Fencepost: an arc with n segments has n-1 turning joints.
    float angleIncrement = 2 * startAngle / (segmentCount - 1);

    float totalLength = 0;
    for (int i = 0; i < segmentCount; i++) {
        float segmentAngle = startAngle - i * angleIncrement;
        totalLength += Mathf.Cos(segmentAngle);
    }

    return Vector2.Distance(A, B) / totalLength;
}

Since we're adding up several small values into a larger total, this is subject to some loss of precision in floating point math, but you can upgrade to double precision if needed for the intermediate steps, and that should be enough precision for most game purposes.

You can also use symmetry to halve the calculation, since the segments before and after the halfway point add the same distance contribution - we don't need to calculate their cosines twice:

// For odd n, there's a segment perfectly parallel to AB in the middle.
float totalLength = (n & 1) == 0 ? 0 : 1;
int halfway = n >> 1;
for (int i = 0; i < halfway; i++) {
    float segmentAngle = startAngle - i * angleIncrement;
    totalLength += 2 * Mathf.Cos(segmentAngle);
}
\$\endgroup\$
0
\$\begingroup\$

If you consider a circle that runs through both A and B, constructed so that the circle tangent at A is equal to the initial path-segment (or the direction of the A agent):

diagram

Then you can solve for the radius r as you have a triangle where you know one angle, 90 - alpha, and one side (distance a to b) / 2.

When r is calculated, you can calculate where point c is located. With c and a and b you know how many degrees there is between the vectors c to a and c to b, divide that angle with n and you get the angle step you need to move every step to get from a to b.

Take the vector from c to a, rotate it by the angle step, the distance between that endpoint and a is the segment length you are looking for.

visualization

In the above example I am changing n, and the coordinate of b and the direction of the first segment.

I think there is some special case where c is on the other size of vector between a and b but that should be trivial to cater for.

I got pointed in the right direction by the people over at math.stackexchange (https://math.stackexchange.com/questions/4840292/given-two-points-and-a-an-angle-find-the-radius-of-the-circle-that-intersects-b)

Update:

As correctly pointed out by @DMGregory, the above method plots secants evenly distributed along the arc of the circle that runs through points a and b such that the direction vector (of angle alpha) is the tangent to the circle, this means that the angle of the first segment is not alpha, but some smaller angle.

The first segment of the path needs to lie on the direction vector to correctly answer the question. I think this can be achieved by instead of just evenly distribute the arc n times extend the line of the first pie-slice (in red) of the until it intersects the direction vector ad point p, and then construct the subsequent segments by simply rotating that segment by 2 * alpha / (n - 1).

updated diagram

This way the path will always start with a segment that lies on the direction vector from a, which is what I call the line at angle alpha from the line a to b.

updated animation

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Note that in your construction, the angle alpha describes the angle between line AB and the tangent to the circle, but the segments formed in the end are secant lines, not tangent lines. So the angle between line AB and the first segment will be shallower than the angle to the tangent. Compare this to the question, where the angle to the secant line is the one called alpha. Do you have any scheme for adjusting the secant alpha in the question to get the tangent alpha needed to form your circle construction? \$\endgroup\$ Commented Jan 7, 2024 at 17:06
  • \$\begingroup\$ @DMGregory, no I do not. I sort of assumed that what he actually had at the start was not the initial segment, but point A and the direction the agent at point A is facing. But that might be a bad assumption. I agree that my solution is off by the difference between the tangent line and the secant line. \$\endgroup\$ Commented Jan 7, 2024 at 17:53
  • \$\begingroup\$ Now that I think about it, this approach will probably work with the correct scant line if I just extend out to the intersection with the tangent line. \$\endgroup\$ Commented Jan 8, 2024 at 12:31
  • 1
    \$\begingroup\$ Thank you both @DMGregory and bornander for your answers. At first, I had something similar what bornander come up with in mind. But answer of DMGregory seems to be more straight forward for implementation, so I will mark that as correct answer. Also, it is correct that angle alpha is between AB line and secant line. \$\endgroup\$ Commented Jan 8, 2024 at 13:06
  • \$\begingroup\$ @bornander Could you elaborate on how that extension would work? I am now playing with the idea to not have segments of the same size, but instead to have first k segments rotated by beta angle, and the rest by some gamma that would be just enough to enclose the arc. Your answer seems to be perfect for getting segments sizes in this specified scenario, but I am a bit stuck with first line not beign tangent, but secant. \$\endgroup\$ Commented Jan 9, 2024 at 21:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.