koobas.hobune.stream
Find closest point to player input within 2D shape defined by lines/curves
I have a turn-based vehicle game. The camera is top-down. Movement is free (no grid) on a 2D plane, but vehicles can only move in a single turn according to certain rules. I want to allow the player to click and drag on a vehicle, and as he drags the mouse around, an indicator snaps to the closest legal position the vehicle could reach this move.
Essentially, I want to take the player's click on a 2D plane relative to an arbitrary shape, and if the click is not inside the shape, find the closest point to the click along the shape's edge.
I'm not even sure where to start, with regards to finding closest positions on the 2D plane.
In case it's relevant: vehicles can move straight, and then make a turn up to an angle and then move some more. So the basic shape is a line with a "pie" shape (arc) at the end. However, I want to eventually do gradual turning (not rotating in place) so I believe the 2D shape is basically an arbitrary one defined on the edges by straight lines and lengths of circle arcs.
I'd be happy to provide more specific information to the movement if requested; I tried to include only what I imagine is relevant.
Anything helping me along or pointing me in a direction is much appreciated.
TL;DR: Given a 2D plane, how do I find the point closest to a mouse click within an arbitrary 2D shape constructed of lines and circle arcs?
I've read this through three times, and I'm still puzzled. A drawing might be helpful.
It seems you are unable to make an object snap to a grid, does that sum it up? If so, length((float2)objectposition - (float2)floor(objectposition) - (float2)gridsize / 2) gives you the distance to the grid position floor(objectposition). I have really no idea if that helps..
So I was researching some stuff for "closest point to polygon," which is like this problem but in 3D, and for straight edges. I found [http://stackoverflow.com/questions/10983872/distance-from-a-point-to-a-polygon]this[1], which is for a 2D implementation of straight lines. Basically the suggestion is to iterate over all the lines and then run a closest point to finite line check for each of the edges. That seems sound, but I'm not sure how to do that for my circle arc segments.
[1]: http://stackoverflow.com/questions/10983872/distance-from-a-point-to-a-polygon
The correct way to do this is to test each line and arc individually for the closest point. The answer is the closest of all these points.
Here is a function for finding the closest point on a line:
public static Vector3 ClosestPointToLine(Vector3 _lineStartPoint, Vector3 _lineEndPoint, Vector3 _testPoint) {
Vector3 pointTowardStart = _testPoint - _lineStartPoint;
Vector3 startTowardEnd = (_lineEndPoint - _lineStartPoint).normalized;
float lengthOfLine = Vector3.Distance(_lineStartPoint, _lineEndPoint);
float dotProduct = Vector3.Dot(startTowardEnd, pointTowardStart);
if (dotProduct <= 0) {
return _lineStartPoint;
}
if (dotProduct >= lengthOfLine) {
return _lineEndPoint;
}
Vector3 thirdVector = startTowardEnd * dotProduct;
Vector3 closestPointOnLine = _lineStartPoint + thirdVector;
return closestPointOnLine;
}
And here is a function for finding the closest point on an arc:
public static Vector3 ClosestPointToArc(Vector3 _circleCenter, Vector3 _arcBegin, Vector3 _arcEnd, Vector3 _pointToTest) {
Vector3 endTowardBegin = _arcEnd - _arcBegin;
float radius = (_arcBegin - _circleCenter).magnitude;
Vector3 surfacePoint = _circleCenter - ((_circleCenter - _pointToTest).normalized * radius);
if (Vector3.Dot(Perpendicular(endTowardBegin), surfacePoint - _arcBegin) > 0) {
// The closest point on the circle is contained within the arc.
return surfacePoint;
} else {
// The closest point on the circle is outside the arc. One of the endpoints is closest.
float distanceToBegin = Vector3.Distance(_pointToTest, _arcBegin);
float distanceToEnd = Vector3.Distance(_pointToTest, _arcEnd);
if (distanceToBegin < distanceToEnd) {
return _arcBegin;
} else {
return _arcEnd;
}
}
}
These functions work in 3D, though my original question was for a 2D scenario.
For my specific implementation, I made an Interface named LineArc that can hold a Line or an Arc class. Each of these implements "ClosestPointOnMe" which takes a Vector3 (the point we're testing) and returns the closest point on the individual Line or Arc to the test point.
Now it's a simple matter to step through an array or List of LineArc objects and remember the Vector3 that is closest to our test point.
Hi,
First off, nice and elegant. $$anonymous$$y qustion is In the line Vector3.Dot(Perpendicular(endTowardBegin), surfacePoint - _arcBegin) > 0) How is the Perpendicular method on a single vector working? Is it your own method?
Ok so this looked fun. An interesting problem, but we can solve it if we break it down a little. A 'valid point' needs to follow 2 rules.
The point must be within a certain number of units away from the origin
The point must lie within a certain number of degrees from the cars forward vector.
Right, so lets get to it!
//first we need a vector from the origin to the mouse.
//image this as an arrow pointing to our mouse position from the origin!
Vector3 vecToMouse = mouseXY - origin;
//Lets do our first check, is this mouse outside
//of the valid distance from the origin?
if(vecToMouse.magnitude > distance)
{
//Yes it is. We need to clamp the value back.
//we normalize the vector. Now our vector looks like
//an arrow pointing towards the mouse position, but it is
//only 1 unit long. We multiply it by distance.
//Not it looks like a vector pointing at the mouse,
//but it only extends as far as our max distance
vecToMouse = vecToMouse.normalized*distance;
}
//Ok the easy part is out of the way! now we need to clamp
//the point inside our angle. The angle in your example is 90 degrees
//In other words, a valid point will lie within 45 degrees of
// the forward vector in one direction or another.
//Lets check, is the angle within 45 degrees in each direction?
// (angle / 2 = 45)
if (Vector3.Angle(forward, vecToMouse) > (angle / 2))
{
//No, its not. The point lies somewhere outside of this range. Uh oh.
//we need to rotate the point back towards the center.
//lets figure out how many degrees we need to 'correct' our vectors angle
//for it to lie right on the border of the valid range
float degreesToCorrectBy = Vector3.Angle(forward, vecToMouse) - (angle / 2);
//so, if our vecToMouse is 50 degrees away from our forward vector,
//we need to correct by 5 degrees-> 50 - 45 = 5
//but do we rotate 5 degrees to the left, or right? we could be on either side!
//luckily, the cross product is here to help.
//the sign of the Y component for the cross product will tell us what side we
//are on. if we are on the right side of forward, the sign will be negative,
//so we correct by -5 degrees..
//if we are on the left, it will be positive
//so we correct by 5 degrees..
degreesToCorrectBy *= Mathf.Sign(Vector3.Cross(vecToMouse, forward).y);
//Now to 'rotate' a vector...
//we can multiple a Quaternion that desribes the rotation we
//would like to achieve with our vector. the result will be
//our rotated vector.
vecToMouse = Quaternion.Euler(0, degreesToCorrectBy, 0) * vecToMouse;
}
//vecToMouse is now safely inside our range
Vector3 finalPoint = vecToMouse + origin;
There is a lot of concepts covered here, and I can't cover all of them in great detail. Just yell out if you have any questions regarding anything
Have Fun! I did :)
This answer solves specifically for arcs of circles of certain degrees and radius. The problem set actually requires more complicated shapes, however. You'll notice at the base of the arc, the vehicle begins turning into position before the "origin" point, so the solution needs to handle the parts of circles for that initial turn, as well as the starting line of the vehicle as well.
FYI in your example, for the lowest-right corner arc of about 225°, the answer gives a point radius distance along the edge from the origin, when it should find the closest point along the line - the point on that edge perpendicular to the mouse position I believe.
