In the past I've always worked on 3D games using proper physics engines and such. However I'm starting on my own game now, which will be a simple 2d game a bit like the old Missle Command. I want to do some simple line intersection tests in 2D, but I don't want to use a physics engine just for this simple ray casting as the game has no need for elaborate physics and collision response.

Here is a mockup image I drew of what I want to achieve.

• Red line is the ground that the game objects will sit on.
• Green shapes are the collision volumes for the sprites on the ground.
• Blue lines are what I want to calculate. I would like to be able to specify a 2D start point and a 2D direction vector for the line, then detect the first thing it hits, whether that be the red ground or one of the green shapes.

[attachment=28249:image.png]

So to achieve this I'm thinking I need to find some math for the following 3 scenarios.

• line-box collision check
• line-circle collision check
• line-ground collision check

I imagine scenario 1 and 2 should be pretty straight forward and would just be a matter of looping through the collision shapes and testing the line against each one. Then just returning the hit against the one that was the closest (i.e. the first hit). Does that sound right? Is there any links to this kind of math anywhere or even a basic math library somewhere that can do this?

Scenario 3 has me a little stuck, which is why I'm here. I was thinking that I could define a 1-dimensional array to store the height value of each pixel along the red line from left to right, i.e. left side of the red line in the image would be at index-0 in the array and the right side would be index-n. This would effectively give a 1-dimensional height map in a way. How could I test a line against this height map? Is there math for this sort of thing?

1.

">here

2. Even though there are numerous sources online Ill provide a solution just to refresh my maths.. by thinking about it.. so dont mind me:

you are given the line and the circle equation:

line: y = k * x + d
circle: (x - centerx)^2 + (y - centery)^2 = radius^2

2.1 First you need to determine the coefficients for these functions:
lets say your line vector looks like this: A [0,1] B[10, 10]
The "k" coefficient is the slope so...:

k := (B.y - A.y) / (B.x - A.x)

note care for special cases (vertical line = divide by zero error!)
Once you have k, you can now determine d by using the x and y value of either A or B, inputting them into the line function (because the line goes through both points) and adjusting it so that d is on the one side and the rest on the other:

A.y = k * A.x + dA.y - k * A.x = d

The circle is much easier since you have to do pretty much nothing.

2.2 There are now 3 cases for the line-circle intersection:
1 - the line doesnt intersect with the circle (passant)
2 - the line intersects with the circle exactly 1 time (the line is tangential to the circle; its a "tangent")
3 - the line intersects with the circle exactly 2 times (the line "pierces" through the circle; its a "secant")
What it boils down to is evaluating this:
line = circle (if they intersect, there is an (x,y) pair for which this holds true)
We know "y" from the line equation, so lets use it in the circle equation:

(x - centerx)^2 + (y - centery)^2 = radius^2
= (x - centerx)^2 + (k * x + d - centery)^2 = radius^2
to simplify the next step, lets define:
t := d - centery
= (x - centerx)^2 + (k * x + t)^2 = radius^2
= x^2 - 2*x*centerx + centerx^2 + k^2x^2 + 2*kx*t + t^2 = radius^2
= x^2 - 2*x*centerx + k^2x^2 + 2*k*x*t = radius^2 - t^2 - centerx^2
= (k^2 + 1)x^2 - 2*x*centerx + 2*k*x*t = radius^2 - t^2 - centerx^2

We know k, centerx, t, and radius, so what we have here is basically this ~

x^2 - x + x = some_constant

... a quadratic equations.
The number of solutions to a quadratic equations is the same as for our 3 cases:
0 solutions = no intersection (sqrt of negative number - we are not working with complex numbers here so its "no solution")
1 solution = tangent
2 solutions = secant

The last step is trivial: You have x, you just input it to either equation (i suggest the line equation, since its simpler) and get the y value. Then you have your (x,y) pair - which is the intersection position.

3 This is a bit more tricky. I dont have a proper solution but the first idea that came to my mind was a divide & conquer strategy:
You basically segment and approximate the curve (ground) with k line-segments. Then you do the line-line intersection check. You take the segment-line you intersected with, use its boundaries to repeat the whole process - segmenting and approximating the curve (ground) again and again and the more often you do it, the more accurate the result is going to be.

Edit: For problem 3, I have another divide & conquer strategy if there is nothing below "ground":
- divide your line into two segments. Check whether the center point is below or above ground (by determining the y positions of both line and ground at the center_x position)
-- if its below ground: take the segment that is "higher" in the air
-- if its above ground: take the segment that is "lower" in the air - closer to the ground
--- and repeat the whole process t amount of times
Result = center_x value if center_x was below ground at any iteration.
Again, the higher t is, the more accurate the approximation will be.

The ground surface - can you limit its shape to be a series of line segments ? (finer it is, the more seperate segments you have...)

I believe a game programming author (I once saw) used the term 'matchsticks' (segments laid head to tail) because that kind of set of data (a list of points) has some regularity you can use to optimize it (head point of one is tail point of adjacent segment).

That could allow something like a binary search based on the (head) points X poisition to minimize the detailed checking to a subset for intersection with the individual segments (Though you look to be doing intersection of entire trajectory 'ray' which lowers the potential savings a bit)

--

Also IF you have ALOT of memory and a largely static 'map', you might do an actual lin-pixel test for your ray intersection tests (indexed 'colors' to tell which object type (subset) to test in detail). Or even have the pixel 'colors' be the objects index ID.

for 3, assuming ground behaves like function f(x) = y:
- have x evenly spaced, so all ground-line-segments span the same width (cyan lines)

- make arrays minHeight[x] and maxHeight[x] for all ground-line-segments (store y1 and y2 for all segments in x-sorted arrays)

- also know min/max height of all ground. (gray lines)

- check if missile-line hits ground at all or if it leaves screen above maxGroundHeight.

- clip missile-line to min/max height of all ground. (yellow box)

- for remaining width of that missile-line's segment check all entries in min/max groundHeight arrays per line/box intersection if there is a hit.

- as a bonus do the comparison in reverse if missile-line goes from right to left and forward if from left to right, to find hit segment faster.