I am making a somewhat unusual character controller that requires me to do some strange math. Basically, I want to use the line drawn below in red to calculate a list of the points where the line intersects grid lines. Any hints as to what sort of approach I should use to accomplish this?
Well there are a lot of unknown left over. I assume that we talk about a 2d problem here, right?
You should notice that there are two different kinds of intersections with the grid:
- intersections with horizontal grid lines
- intersections with vertical grid lines
Those two has to be handled seperately. Lets further assume the line is defined by the starting point at the lower left and a direction vector. Also the grid passes through the origin and has a “stepsize” of “G”.
To find the x positions of the intersections with the vertical lines you start at the starting point and if the direction goes to the right you round the staring position up to the next higher grid position. If the direction goes to the left you find the next lower grid position. For this you just divide the x staring position by “G” and either Ceil or Floor the value. Multiply the result by G again and you get the x coordinate of an intersetion. To get the y position of an intersection we just use the slope of our line equation. Now just increase / decrease “x” by “G” to get the next vertical gridline. Continue as far as you need.
The same thing can be done for the horizontal grid lines. We just determine the y coordinate first and use the line equation to get the x coordinate. Finally you may want to sort all the points based on the distance from the starting point.
It’s a tedious process with several cases but nothing too complicated.
edit
If you have trouble understanding what i said, here’s a method that does what you want based on the assumptions i made above:
public static void FindGridIntersections(Vector2 aLineStart, Vector2 aDir, float aDistance, Vector2 aGridSize, ref List<Vector2> aResult)
{
aResult.Clear();
aDistance *= aDistance;
// vertical grid lines
float x = aLineStart.x / aGridSize.x;
if (aDir.x > 0.0001f)
{
Vector2 v = new Vector2((Mathf.Ceil(x) * aGridSize.x) - aLineStart.x, 0f);
v.y = (v.x / aDir.x) * aDir.y;
while (v.sqrMagnitude < aDistance)
{
aResult.Add(v);
v.x += aGridSize.x;
v.y = (v.x / aDir.x) * aDir.y;
}
}
else if (aDir.x < -0.0001f)
{
Vector2 v = new Vector2((Mathf.Floor(x) * aGridSize.x) - aLineStart.x, 0f);
v.y = (v.x / aDir.x) * aDir.y;
while (v.sqrMagnitude < aDistance)
{
aResult.Add(v);
v.x -= aGridSize.x;
v.y = (v.x / aDir.x) * aDir.y;
}
}
// horizontal grid lines
float y = aLineStart.y / aGridSize.y;
if (aDir.y > 0.0001f)
{
Vector2 v = new Vector2(0f,(Mathf.Ceil(y) * aGridSize.y) - aLineStart.y);
v.x = (v.y / aDir.y) * aDir.x;
while (v.sqrMagnitude < aDistance)
{
aResult.Add(v);
v.y += aGridSize.y;
v.x = (v.y / aDir.y) * aDir.x;
}
}
else if (aDir.y < -0.0001f)
{
Vector2 v = new Vector2(0f, (Mathf.Floor(y) * aGridSize.y) - aLineStart.y);
v.x = (v.y / aDir.y) * aDir.x;
while (v.sqrMagnitude < aDistance)
{
aResult.Add(v);
v.y -= aGridSize.y;
v.x = (v.y / aDir.y) * aDir.x;
}
}
aResult.Sort((a,b)=> a.sqrMagnitude.CompareTo(b.sqrMagnitude));
}
You have to pass a List of Vector2 which will be filled by the method. The points in the list are relative to the starting point. So to get the actual final point you have to add “aLineStart” to each point.
Here’s another implementation that uses a “Ray” as line definition. So the ray origin is the same as aLineStart and the ray direction is the same as aDir. Instead of returning Vector2s we just return the distance along the ray so we can simply use ray.GetPoint with that distance to get the actual point:
public static void FindGridIntersections(Ray aRay, float aDistance, Vector2 aGridSize, ref List<float> aResult)
{
aResult.Clear();
Vector2 pos = aRay.origin;
Vector2 dir = aRay.direction;
// vertical grid lines
float x = pos.x / aGridSize.x;
if (dir.x > 0.0001f)
{
x = (Mathf.Ceil(x) * aGridSize.x) - pos.x;
float v = x / dir.x;
while (v < aDistance)
{
aResult.Add(v);
x += aGridSize.x;
v = x / dir.x;
}
}
else if (dir.x < -0.0001f)
{
x = (Mathf.Floor(x) * aGridSize.x) - pos.x;
float v = x / dir.x;
while (v < aDistance)
{
aResult.Add(v);
x -= aGridSize.x;
v = x / dir.x;
}
}
// horizontal grid lines
float y = pos.y / aGridSize.y;
if (dir.y > 0.0001f)
{
y = (Mathf.Ceil(y) * aGridSize.y) - pos.y;
float v = y / dir.y;
while (v < aDistance)
{
aResult.Add(v);
y += aGridSize.y;
v = y / dir.y;
}
}
else if (dir.y < -0.0001f)
{
y = (Mathf.Floor(y) * aGridSize.y) - pos.y;
float v = y / dir.y;
while (v < aDistance)
{
aResult.Add(v);
y -= aGridSize.y;
v = y / dir.y;
}
}
aResult.Sort((a, b) => a.CompareTo(b));
}
Example:
List<float> points = new List<float>();
Ray ray = new Ray(pos, dir);
FindGridIntersections(ray, 10f, new Vector2(1f, 1f), ref points);
foreach(float dist in points)
{
Vector2 p = ray.GetPoint(dist);
// do something with p
}