Math/coding problem

theotherguy

Newbie
Joined
Jul 5, 2003
Messages
5,107
Reaction score
1
So in coding my game, I've come across a problem which I've been trying to solve through code, but because of special cases, has left me with some nasty bugs.

Basically I am trying to implement a laser weapon into my game. The game is a simple top-down shooter reminiscent of asteroids. I have gotten the laser to be able to be aimed and fired, and have been able to determine whether the laser intersects an asteroid by representing the asteroid as a circle and the laser as a line, and then using Java's geometry functions to figure out whether or not the laser and the asteroid intersect.

Well, this works just fine, except for the fact that the laser always passes through the asteroid, which can work, but is unrealistic. So basically I am trying to determine the point of intersection between the line and the circle, and then setting the endpoint of the laser as this point. This will cause the laser to appear to have struck the asteroid, and will allow me to place a neat "melting" particle effect on it.

Here is how I have tried to implement it:

I am basically moving a test point along the line until I discover it intersects the circle.

If the laser and the asteroid are intersecting, then create a new point at the origin of the laser.

Move the X coordinate of this point every cycle according to the slope's X value and move the Y coordinate of the point every cycle according to the slope's Y value until the point intersects the circle. Then, set the endpoint of the laser as this point.

This works just fine in most cases, except when I fire nearly tangent to the circle. When this happens, the number of steps that the point I am checking causes the point to leave the bounds of the circle, and continue into infinity, causing my computer to slow to a crawl, even when I put a reasonable limit on the distance the point can go. I realized that unless I make the distances that the point travels infinitely small, it could potentially miss the circle in almost every case which brings the line nearly tangent to the circle.

I have thought of two mathematical solutions to my problem, but I can't figure out how to emulate them in code.

Solution 1: Create an equation for the circle representing the asteroid, and an equation representing the line. Find the points where these are equal, and pick the one closest to the player. (Probably the easiest, but I'm not sure how to implement it in code)

Solution 2: Set up a differential calculus equation in which the variables are the changes in x and y experienced by the test point. Find the first exact point of intersection this way. (impossible to implement)

Any ideas?
 
I don't know a lot about how these things work but... couldn't you just find the distance between the player and the asteroid and only make the laser that long? Of course it would need some tweaking, like subtracting the radius of the circle from the laser length, but that would only be exactly correct if the laser hit the exact center of the circle.
 
You could just use the analytical solution of a circle intersected by a ray:

X',Y' is the unit vectors for your ray, Ox and Oy are the origin coordinates of your asteroid, and r is the radius of the asteroid. I assume that the ray passes through the origin.
For circle: (X-Ox)^2+(Y-Oy)^2 = r^2
For ray: X/X'=Y/Y'

Now just substitute one into the other.

(It should be correct this time)

(Y*X'/Y'-Ox)^2+(Y-Oy)^2 = r^2
Y^2*(X'/Y')^2 - 2*Y*Ox*X'/Y' + Ox^2 +Y^2 + Oy^2 - 2*Y*Oy = r^2
Y^2((X'/Y')^2+1) + Y(-2*Ox*X'/Y' - 2*Oy) - Ox^2 + Oy^2 - r^2 = 0

This is of the form aY^2+bY+c = 0
a = ((X'/Y')^2+1)
b = (-2*Ox*X'/Y' - 2*Oy)
c = Ox^2 + Oy^2 - r^2

Y = (-b+/-sqrt(b^2-4ac))/2a
X = Y'/X' * Y


You will get between 0 and 2 solutions. 0 means you missed, 1 means it's tangential, and 2 is a good hit (you would pick the solution depending on the sign of Y'. X' = 0 will require a special case, maybe Y' = 0 as well...

Oh yeah, and don't forget to get rid of solutions behind the direction of the gun. This equation would also show hits if you fired 180 degrees away from the asteroid.
 
You could just use the analytical solution of a circle intersected by a ray:

X' and Y' are the unit vectors for your ray, Ox and Oy are the origin coordinates of your asteroid, and r is the radius of the asteroid. I assume that the ray passes through the origin.
For circle: (X-Ox)^2+(Y-Oy)^2 = r^2
For ray: X/X'=Y/Y'

Now just substitute one into the other.

(X'/Y'-Ox)^2+(Y-Oy)^2 = r^2

Y = +/- sqrt(r^2 - (X'/Y'-Ox)^2) + Oy
X = (X'/Y')Y


You will notice that there are 0 to 2 solutions to this problem. It is pretty easy to cull the intersection that you want.

Awesome, that is exactly what I needed. I'll be testing this out shortly. Thanks.
 
I made a little mistake in the first solution. I think it should work now though.
 
You could just use the analytical solution of a circle intersected by a ray:

X',Y' is the unit vectors for your ray, Ox and Oy are the origin coordinates of your asteroid, and r is the radius of the asteroid. I assume that the ray passes through the origin.
For circle: (X-Ox)^2+(Y-Oy)^2 = r^2
For ray: X/X'=Y/Y'

Now just substitute one into the other.

(It should be correct this time)

(Y*X'/Y'-Ox)^2+(Y-Oy)^2 = r^2
Y^2*(X'/Y')^2 - 2*Y*Ox*X'/Y' + Ox^2 +Y^2 + Oy^2 - 2*Y*Oy = r^2
Y^2((X'/Y')^2+1) + Y(-2*Ox*X'/Y' - 2*Oy) - Ox^2 + Oy^2 - r^2 = 0

This is of the form aY^2+bY+c = 0
a = ((X'/Y')^2+1)
b = (-2*Ox*X'/Y' - 2*Oy)
c = Ox^2 + Oy^2 - r^2

Y = (-b+/-sqrt(b^2-4ac))/2a
X = Y'/X' * Y


You will get between 0 and 2 solutions. 0 means you missed, 1 means it's tangential, and 2 is a good hit (you would pick the solution depending on the sign of Y'. X' = 0 will require a special case, maybe Y' = 0 as well...

Oh yeah, and don't forget to get rid of solutions behind the direction of the gun. This equation would also show hits if you fired 180 degrees away from the asteroid.

My gosh.
 
I can't wait until I understand math problems that well for my game programming. :frown:
 
There really is nothing there that you wouldn't learn in high school algebra. I think that the number of variables might make it look more complex than it is.
 
Well yeah, probably, but I mean the whole task of looking at a problem and finding out a proper mathematical solution to it and having it work as intended I think is an artform. I don't know how much my theory of that holds true though to other people.
 
Well yeah, probably, but I mean the whole task of looking at a problem and finding out a proper mathematical solution to it and having it work as intended I think is an artform. I don't know how much my theory of that holds true though to other people.

I've always had a problem with using math in my programing. the most difficult part is that you start from nothing and have to figure out what type of math equation will give you the intended result. It's not like you have a multiple choice. It doesn't help if you aren't good at math like me.

the good part is that once you figure on a mathematical equation that solves a particular problem, you can use it - or a derivative - again in the future.

I've always been able to do a rough guess of most problems in my head, but I use little tricks and stuff, but you can't do that in a program.


fortunately, most math you need for basic programing is very simple. the complex stuff lies in things like creating 3D game engines, which you and I probably won't ever be doing.

You can always take more math courses in addition to programing courses. That's what I've been doing.
 
A lot of the time understanding how the underlying program actually works lets you use lots of little math tricks to manipulate the actual data bits instead of piling on lots of redundant code. We got a lot of emphasis on that in engineering programming because we were writing tiny C programs for microcontrollers where memory and speed were limited. I have found it to be less than practical for doing anything with a computer though.
 
exactly. I had worked around some math problems by tons and tons of redundant and unnecessary code in the past.

just an example of a redundant program - a very simple problem like where you want to do something 10 times, you could type the whole routine 10 times using 100 or even 1000 lines of code, or you can use a simple math equation and type the routine only once. so it really pays to use math to keep the program running very fast and to use less memory.
 
I made a little mistake in the first solution. I think it should work now though.

Okay, trying to implement this in code. You said that you assumed the ray to be at the origin, so does this mean I should be taking Ox and Oy (the coordinates of the asteroid) as relative to the origin of the ray?
 
This is not something I would have ever been able to do. I would have done it differently some how. how about just having the asteroid detect whether it's hit or not

If an asteroid detects a hit, then make the ray invisible right on the spot, and destroy it. since the beam only has 1 shot on screen, then you know the beam hit it. there is nothing else that could have hit it.


Or something you probably won't dig, but it's an option:

If you click the asteroid, it shoots where you click.



just use bullet type instead of beam. much more simple.
 
I would do per pixel collision myself on something like this, if there aren't 3d models involved.

EDIT: I wasn't being serious Vegeta, you dumbass.
 
This is not something I would have ever been able to do. I would have done it differently some how. how about just having the asteroid detect whether it's hit or not

If an asteroid detects a hit, then make the ray invisible right on the spot, and destroy it. since the beam only has 1 shot on screen, then you know the beam hit it. there is nothing else that could have hit it.


Or something you probably won't dig, but it's an option:

If you click the asteroid, it shoots where you click.



just use bullet type instead of beam. much more simple.

Unfortunately that won't work, because beams have different energies, and you can buy more powerful beams to destroy asteroids faster.

Setting it as the clicking point won't work either, because you can click beyond the asteroid and the laser will still hit it, making the endpoint of the laser far beyond the asteroid.

I've attempted Dan's solution in code, and have utterly failed. The beam either fires completely opposite the direction I desire, or it fires downward and several degrees off. I think it has something to do with resetting my points to the origin.

Here is my code thus far:

public vector intersectionPoint(Line line,Circle circle)
{

/* PROPS TO DAN OF HL2.net
X',Y' is the unit vectors for your ray, Ox and Oy are the origin coordinates of your asteroid, and r is the radius of the asteroid. I assume that the ray passes through the origin.
For circle: (X-Ox)^2+(Y-Oy)^2 = r^2
For ray: X/X'=Y/Y'

Now just substitute one into the other.

(It should be correct this time)

(Y*X'/Y'-Ox)^2+(Y-Oy)^2 = r^2
Y^2*(X'/Y')^2 - 2*Y*Ox*X'/Y' + Ox^2 +Y^2 + Oy^2 - 2*Y*Oy = r^2
Y^2((X'/Y')^2+1) + Y(-2*Ox*X'/Y' - 2*Oy) - Ox^2 + Oy^2 - r^2 = 0

This is of the form aY^2+bY+c = 0
a = ((X'/Y')^2+1)
b = (-2*Ox*X'/Y' - 2*Oy)
c = Ox^2 + Oy^2 - r^2

Y = (-b+/-sqrt(b^2-4ac))/2a
X = Y'/X' * Y

You will get between 0 and 2 solutions. 0 means you missed, 1 means it's tangential, and 2 is a good hit (you would pick the solution depending on the sign of Y'. X' = 0 will require a special case, maybe Y' = 0 as well...

Oh yeah, and don't forget to get rid of solutions behind the direction of the gun. This equation would also show hits if you fired 180 degrees away from the asteroid.
*/


double a;
double b;
double c;

float Ox;
float Oy;

double x1;
double x2;
double y1; //Option 1
double y2; //Option 2

float lineStartx;
float lineStarty;

float lineEndx;
float lineEndy;


Vector2f intersect1;
Vector2f intersect2;

//RESETS STARTING AND ENDING POINTS OF THE LINE TO THE ORIGIN
lineStartx=0;
lineStarty=0;
lineEndx=line.getStart().getX()-line.getEnd().getX();
lineEndy=line.getStart().getY()-line.getEnd().getY();

//RESETS CIRCLE COORDINATES RELATIVE TO LINE
Ox=circle.getX()-line.getStart().getX();
Oy=circle.getY()-line.getStart().getY();

a=(Math.pow(lineEndx/lineEndy,2)+1);
b=(-2*Ox*lineEndx/lineEndy-2*Oy);
c=Math.pow(Ox,2)+Math.pow(Oy,2)-Math.pow(circle.getRadius(),2);

y1=(-1*b+Math.sqrt(Math.pow(b,2)-4*a*c))/(2*a);
y2=(-1*b-Math.sqrt(Math.pow(b,2)-4*a*c))/(2*a);

x1=lineEndy/lineEndx*y1;
x2=lineEndy/lineEndx*y1;

//PUTS THE X's and Y's BACK TO THE WORLD COORDINATES
x1+=line.getStart().getX();
x2+=line.getStart().getX();
y1+=line.getStart().getY();
y2+=line.getStart().getY();

//Puts these into vectors
intersect1=new Vector2f((float)x1,(float)y1);
intersect2=new Vector2f((float)x2,(float)y2);

//Finds closest point to the laser
if(line.getStart().distance(intersect1)<line.getStart().distance(intersect2))
{
return new vector((double)intersect1.getX(),(double)intersect1.getY());
}
else return new vector((double)intersect2.getX(),(double)intersect2.getY());




}

EDIT: I think a simpler way to do this is find the closest point on the line to the center of the circle. That way, I can have a convincing effect at a much lower cost by simply picking the point on the line which is closest to the center of the circle. It would put the end of the laser somewhere inside of the asteroid, which would be perfectly fine.

EDIT2:
WAIT! I found the error!

x1=lineEndy/lineEndx*y1;
x2=lineEndy/lineEndx*y1;

should be
x1=lineEndy/lineEndx*y1;
x2=lineEndy/lineEndx*y2;

EDIT3: That didn't fix it :(
 
I really don't understand why you can't find the distance between the two targets and generate a beam that long.

[sqrt(x^2 + y^2)] - r

where x and y are the coordinates for the asteroid, r is the radius of the circle. Of course it would look a little weird if you struck near the circle's outer rim and maybe this isn't acceptable.
 
I really don't understand why you can't find the distance between the two targets and generate a beam that long.

[sqrt(x^2 + y^2)] - r

where x and y are the coordinates for the asteroid, r is the radius of the circle. Of course it would look a little weird if you struck near the circle's outer rim and maybe this isn't acceptable.

That wouldn't work unless the laser was pointing directly towards the center of the circle.
 
You said you were already able to detect the hit, the problem being the laser kept going off until infinity. If you can detect the hit, just throw the laser in the angle it was fired from and calculate the distance between the two points to create the length of the laser.

Maybe I'm just not seeing something here.
 
You guys are making this way too complicated...

1) Find the angle the point that the top of the circle makes with respect to the where the laser is on the ground. (use Math.atan2() with x,y displacement of this point)

2) Find the angle the point that the bottom of the circle makes with respect to the where the laser is on the ground. (use Math.atan2() with x,y displacement of this point)

3) Find the angle that the laser is pointing. (you probably do this already)

4) If the laser angle is between the first 2 angles, then you have a hit... easy.
 
You guys are making this way too complicated...

1) Find the angle the point that the top of the circle makes with respect to the where the laser is on the ground. (use Math.atan2() with x,y displacement of this point)

2) Find the angle the point that the bottom of the circle makes with respect to the where the laser is on the ground. (use Math.atan2() with x,y displacement of this point)

3) Find the angle that the laser is pointing. (you probably do this already)

4) If the laser angle is between the first 2 angles, then you have a hit... easy.

I know whether or not it is intersecting already. What I am trying to find is the exact point at which it intersects.
 
You said you were already able to detect the hit, the problem being the laser kept going off until infinity. If you can detect the hit, just throw the laser in the angle it was fired from and calculate the distance between the two points to create the length of the laser.

Maybe I'm just not seeing something here.

The problem is, I don't know the point at which the laser and the circle intersect. Dan has already solved this for me, but I've implemented it in the code incorrectly and its causing weird bugs.

On second thought, these bugs might be caused by the fact that the laser can intersect with multiple asteroids simultaneously currently. So to properly do this, I will have to figure out which asteroid it intersects first, and then calculate where it intersects.
 
I almost didn't post this, because I know you created this thread because you only need the answer to this problem.

posting anyway because I typed it for nothing.

What I would do is leave that feature out temporarily, and work on something that you know how to do, but just haven't yet. seriously. start with the easy stuff and the tedious stuff, and while you are doing that, you have plenty of time to think of a solution. all the while your game is progressing fine without the lazer.

Every game has features that never made it into the game. you can even see traces of stuff in the code. I'm not saying forget the idea, I'm saying that I would come back to it.
 
Pesh's solution seems the simplest. You seem to be misunderstanding him. You don't need to know the exact point of intersection. You just take the distance between the center of the circle and the ship's firing point. You don't even need to worry about the laser not being the right length, can't you just make the asteroid be in front of the laser, covering it? That way even though the laser is slightly longer than it needs to be, it will still be covered up by the asteroid. It should work at any angle.

laserat1.gif


Unless of course making the laser behind the circle isn't possible.
 
Pesh's solution seems the simplest. You seem to be misunderstanding him. You don't need to know the exact point of intersection. You just take the distance between the center of the circle and the ship's firing point. You don't even need to worry about the laser not being the right length, can't you just make the asteroid be in front of the laser, covering it? That way even though the laser is slightly longer than it needs to be, it will still be covered up by the asteroid. It should work at any angle.

Unless of course making the laser behind the circle isn't possible.

Oh, I see, that's what you meant. That would probably work just fine actually.
 
In retrospect, Dan's solution is far more accurate and you'll probably need to find the exact coordinate in order to pull off good looking particle effects, especially if the asteroids are rotating and moving simultaneously, or if the asteroids have varying shapes, or if the laser lasts longer than an instant.

As for picking which asteroid to find the distance from (if in any case there was an asteroid behind the intended target), I guess just find the coordinates of all the intersected asteroids and pick the one with the shortest distance from the origin (player).
 
I've got a different solution. This one just uses simple trig. You want to know the exact intersect point so that you can use an epic melting effect, right?

You know the distance between the spaceship (the starting point of the laser) and the asteroid's origin. Call this line D.

You know the angle of the laser. Call the laser line L.

You know the angle between the L and D. Call this angle a.

Work out the length of a line perpendicular to L that intersects the asteroid's origin, and call it line P. You now have a right angled triangle P = sin(a)*D

Now you also have a second right angled triangle in the asteroid circle, one vertex of which it the asteroid's origin, one vertex of which lies on the bondary of the asteroid circle where the laser crosses it (and is your intersect point) and the other is the right angle formed where P intersects L.

The line between the asteroid's origin and the intersect point is the asteroid's radius, r (the hypotenuse of the afromentioned right angled triangle).

The remaining side of the right angled triangle, called I, equals root(r^2 - P^2).

L - I = the distance of your laser line. You already know the angle of the laser, so that's all you need to know.

So basically:

P = sin(a)*D
I = root(r^2 - P^2)
Length of laser = L - I

I hope this works.

EDIT: This works on paper. I'm not sure how you'd implement it in a game environment, what with co-ordinates and angle systems to take into account. I would do it on Gamemaker, but it's being a bitch and keeps expressing sine numbers in radians.

EDIT EDIT: Great, I've done a diagram in paint, and now the bloody attach button won't work.
 
I've got a different solution. This one just uses simple trig. You want to know the exact intersect point so that you can use an epic melting effect, right?

You know the distance between the spaceship (the starting point of the laser) and the asteroid's origin. Call this line D.

You know the angle of the laser. Call the laser line L.

You know the angle between the L and D. Call this angle a.


Work out the length of a line perpendicular to L that intersects the asteroid's origin, and call it line P. You now have a right angled triangle
P = sin(a)*D

Now you also have a second right angled triangle in the asteroid circle, one vertex of which it the asteroid's origin, one vertex of which lies on the bondary of the asteroid circle where the laser crosses it (and is your intersect point) and the other is the right angle formed where P intersects L.

The line between the asteroid's origin and the intersect point is the asteroid's radius, r (the hypotenuse of the afromentioned right angled triangle).

The remaining side of the right angled triangle, called I, equals root(r^2 - P^2).

L - I = the distance of your laser line. You already know the angle of the laser, so that's all you need to know.

So basically:

P = sin(a)*D
I = root(r^2 - P^2)
Length of laser = L - I

I hope this works.

EDIT: This works on paper. I'm not sure how you'd implement it in a game environment, what with co-ordinates and angle systems to take into account. I would do it on Gamemaker, but it's being a bitch and keeps expressing sine numbers in radians.

EDIT EDIT: Great, I've done a diagram in paint, and now the bloody attach button won't work.

It all works I think, but you left out a lot of calculations. The only starting info you have is the ship coordinate, the asteroid coordinate, and the laser direction.
 
It all works I think, but you left out a lot of calculations. The only starting info you have is the ship coordinate, the asteroid coordinate, and the laser direction.

I'm asuming you already know the asteroid's radius too.

D = root((spaceship.x-asteroid.x)^2+(spaceship.y-asteroid.y)^2)

angle of D = sin^-1((spaceship.y-asteroid.y)/D)
^^This will only give a result between 90 and 0, so you'd have to use some code to add an appropriate number of 90s.

For angle a, there's some code I wrote ages ago to work out the difference between two angles, but I can't find it right now.

Are there any other calculations I missed?

EDIT:

{
if(direction1 < direction2)
{direction1 -= direction2}
else
{direction1 = direction2-direction1}

if(direction1 < 0)direction1 += 360
if(direction1 > 180)direction1 = 360-direction1

return direction1
}
 
its funny you should bring this up because im actually writing a small 2d engine in java . if you intend on doing more than shooting lasers i suggest looking up the "separation axis theorem", its an algorithm that determines if two convex polygons intersect and if so it provides you the smallest vector that will separate them .
 
Okay, here's a solution that works (I tested it in Mathematica). I think it's basically the same as the algebraic solution on the first page, except it uses vectors. I found it using dot products, the law of cosines, and the quadratic equation. I could bore you with all the details of the solution, but I don't think many of you would care.

So here it is:

astroid_problem-1.png


S is the position of the source of the laser (ship), A is the center of the astroid, and I is the (unkown) point of intersection between the laser and the astroid. Keep in mind these are all 2D vectors (although I think this solution works for 3D spheres as well). On top of that, we have the displacement of the laser L = I - S, the displacement of the ship from the astroid D = A - S, and the scalar radius of the astroid r. The L with the little hat on (^) is the normalized vector representing the direction the ship's laser is firing. The angle between L and D, theta, is only used for the derivation.

You should know A, S, L-hat, and r. From that you can get D, and substitute it into the formula to get I, the point of intersection. Keep in mind that because of the +/- in the formula you will get two solutions. The - one will be on the close side of the circle, the + on the far side (I'm guessing you only want the - one).

There's another thing... you can check to see if you got a hit or miss by checking the sign of the quantity inside the square-root. If that quantity is less than 0, it's a miss. If it equals 0, it hit the tangent of the circle. If it's greater than 0, it's a hit. This method for checking hit or miss should be much better than the one you're using now.

Hope that helps.

Edit:

Sorry, I'm assuming you know a lot about vectors here... if you don't, take a look at this: http://chortle.ccsu.edu/VectorLessons/vectorIndex.html

All you really need to know though is that 2D vectors are two numbers, e.g. A = <Ax, Ay>, where A is the vector, Ax is the number for its x-component, and Ay is the number for its y-component. The dot-product of two 2D vectors A.B is equal to Ax*Bx + Ay*By, the length of a 2D vector A is sqrt( Ax^2 + Ay^2 ), and a normalized vector is that vector divided by it's length: <Ax/sqrt(Ax^2 + Ay^2), Ay/sqrt(Ax^2 + Ay^2)>.

Edit 2:

Terribly sorry, one of my L's forget its hat in the last picture! Should be fixed now.
 
Okay, here's a solution that works (I tested it in Mathematica). I think it's basically the same as the algebraic solution on the first page, except it uses vectors. I found it using dot products, the law of cosines, and the quadratic equation. I could bore you with all the details of the solution, but I don't think many of you would care.

Excellent. Since Java already has standard vector operations pre-programmed, implementing this solution should prove quite easy. I'll try it today.
 
It does? D:

Yep, in the Vector class. I'm using another library right now which has other vector operations, and I'm using a class called Vector2f which has these operations on a vector with floats as its subunits.

Okay, here's a solution that works (I tested it in Mathematica). I think it's basically the same as the algebraic solution on the first page, except it uses vectors. I found it using dot products, the law of cosines, and the quadratic equation. I could bore you with all the details of the solution, but I don't think many of you would care.


EDIT: Question, how do I find L and Lhat without knowing I? Should I derive Lhat by normalizing the current laser, before I make it shorter?
 
EDIT: Question, how do I find L and Lhat without knowing I? Should I derive Lhat by normalizing the current laser, before I make it shorter?

I'm curious to know this myself.
 
Law of sines, I'm guessing.

a/sin A = b/sin B = c/sin C
 
Back
Top