Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Line Collision / Shot Detection System

This thread is locked; no one can reply to it. rss feed Print
Line Collision / Shot Detection System
EricsonWillians
Member #15,027
April 2013

Greetings!

I'm developing a Top-View 2D Multiplayer Shooter in C and I'm having serious problems with the Shot Detection System.

I would really enjoy a major help concerning the whole problem that I've posted in the stackoverflow website:

http://stackoverflow.com/questions/15722996/c-and-allegro-how-to-detect-shots-in-a-top-view-2d-shooter

The answer they gave to me involving atan2() from the C standard math library is mysterious to me and I'm looking forward to expand my knowledge in Geometry and Mathematics to fully understand it.

Nevertheless, I can draw a line between the two players in this way:

#SelectExpand
1al_draw_line(defaultPlayer1.pos[0], defaultPlayer1.pos[1], defaultPlayer2.pos[0], defaultPlayer2.pos[1], al_map_rgb(0, 255, 0), 2);

It would be rather easy if I could detect when the first button of the mouse is pressed OVER the line (When the weapon is above the line between the two players). In this way I could detect the shot.

But the problem with this idea is: al_draw_line() does not return anything, I can't find a way to test if something interacts with the line drawn.

Anyway, you all are experts in the Allegro library and I am just a programmer beginning to deal with game concepts and the Allegro library. It would be really really helpful if you could point me an example of a solution to this top-view problem.

Thank you very much!

Arthur Kalliokoski
Second in Command
February 2005
avatar

I guess you mean that the image rotates as you move your mouse sideways? You've already passed the angle in radians to al_draw_rotated_bitmap(), so you get the difference between player2 y and player1 y (to make a vector) to pass as the first argument to atan2(), then do the differences in x to get the second argument. If the returned value (an angle in radians) is "close enough" to the angle you drew the sprite at, it collides. The "close enough" part is to account for the size of the enemy (after all, he's not an infinitely small point).

The distance between the players can be gotten by the good old Pythagorian theorom to see if it's within range or not. If you want to get fancy, you could associate this distance with the "good enough" value by various ways so the closer the enemy was, it'd be easier to hit him, just like you'd expect.

I wish I was articulate. :-/

The guy who answered you on stackoverflow is Matthew, the guy who runs this site.

They all watch too much MSNBC... they get ideas.

pkrcel
Member #14,001
February 2012

It would be rather easy if I could detect when the first button of the mouse is pressed OVER the line (When the weapon is above the line between the two players). > In this way I could detect the shot. But the problem with this idea is: al_draw_line() does not return anything, I can't find a way to test if something interacts with the line drawn.

You should definitely read-up on arc-tangents (and therefore the atan2 function) and the angles they gave you in return. You aren't expected to do anything with returns of a drawing functions after all (except for operation status check of course).

Basically Matthew suggested to calculate 2 angles:

- The angle your main character is facing when Mouse button 1 is pressed (you SHOULD already have it, as AK already pointed out, since you're already drawing a rotated bitmap of the player.

- The angle (range) between the player and the target(s)

Comparing the two should get you your "collision", and therefore your hit status.

Of course, as everybody already mentioned it, you HAVE to count in eventual obstacles, which involves checking the "line" you mention in your post from start to end.

And if an obiject is impenetrabel along this trajectory, you should stop checking and resolve the collision.

Try to sketch up a simple diagram on paper so you can visualize the trajectories and relative angles, I'm sure it would help you a lot.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

EricsonWillians
Member #15,027
April 2013

First of all, I thank you two for the excellent replies. I haven't completely understand it yet, but now I have stronger clues.

Yes, I have the angle when the left mouse button is pressed; as you've said, I draw the rotated bitmap already. I do so here:

#SelectExpand
1al_draw_rotated_bitmap(playerTux, defaultPlayer1.size / 2, defaultPlayer1.size / 2, 2defaultPlayer1.pos[0], defaultPlayer1.pos[1], mousePos / mouseSensitivity, 0);

For you to understand it more clearly, the angle in this case is a division of mousePos with a constant called mouseSensitivity (Giving the fact that it is a shooter game, I found a way to give to the user the option of choosing between 4 sensitivities.)

The rotation of the bitmap involves a curious solution that I've found:

#SelectExpand
1if (ev.type == ALLEGRO_EVENT_MOUSE_AXES) { 2 3// This says that the variable mousePos equals to the movement of the mouse 4// in the x axis, which is something necessary to change the angle of the image. 5 6 mousePos = ev.mouse.x; 7 8 9// I had several problems with the image stoping to rotate when the mouse 10// goes off the screen area. So this basically warps the mouse cursor to the 11// beginning of the screen when it goes off it, and vice-versa. To examine 12// how this works, put a comment in the "al_hide_mouse_cursor()" up there. 13 14 if (mousePos >= screenWidth - 1) { // If the mouse cursor goes off the screen (right), 15 al_set_mouse_xy(display, 1, 0); } // warp it to the beginning of the screen. 16 if (mousePos < 1) { // If the mouse cursor goes off the screen (left), 17 al_set_mouse_xy(display, screenWidth - 1, 0); } } // warp it to the end of the screen.

This "mouse cursor teleportation" solved perfectly an old problem of mine (Maybe there's a clever way to solve this, but if it is, I don't know it yet).

The "mouseSensitivity" is declared together with the mousePos in this way:

#SelectExpand
1float mousePos = 0.0; 2float mouseSensitivity = LOW_MOUSE_SENSITIVITY;

LOW_MOUSE_SENSITIVITY is a constant, defined together with these ones:

#SelectExpand
1#define PLAYER_ROTATION_FACTOR 81.2 2#define VERY_LOW_MOUSE_SENSITIVITY PLAYER_ROTATION_FACTOR * 2 3#define LOW_MOUSE_SENSITIVITY PLAYER_ROTATION_FACTOR 4#define MEDIUM_MOUSE_SENSITIVITY PLAYER_ROTATION_FACTOR / 2 5#define HIGH_MOUSE_SENSITIVITY PLAYER_ROTATION_FACTOR / 2 / 2

This "rotation factor" is a solution to a terrible problem. When I've put the mouse.x as an angle argument to draw the rotated bitmap; even with the pivot placed properly, the bitmap didn't rotate completely (360), and then, by testing endlessly, I found that when I divided the mousePos with this value (81.2), the turn was complete (And therefore, mathematically speaking, I could double it's value to get a slower turn, but a still complete turn). I don't know if this all is clear enough, but it's working perfectly.

The thing is, thanks to this odd division, the angle does not go from 0 to 360; instead, it goes from 0.000000 to 6.299999. If I print this angle multiplied by something closer to 28 I can get the 360, but it's irrelevant. Now I've come to my actual problem, and I'm trying to apply this atan2() like this:

#SelectExpand
1 double playerPosArray1X[2] = {defaultPlayer1.pos[0], defaultPlayer2.pos[0]}; 2 double playerPosArray1Y[2] = {defaultPlayer1.pos[1], defaultPlayer2.pos[1]}; 3 double angleCalculation = atan2(playerPosArray1Y, playerPosArray1X);

And then, inside the loop:

#SelectExpand
1printf("Angle Calculation: %f\n", angleCalculation);

But I receive the following error in terminal:

main.c: In function ‘main’:
main.c:84:2: error: incompatible type for argument 1 of ‘atan2’
In file included from /usr/include/math.h:71:0,
                 from main.c:22:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:61:1: note: expected ‘double’ but argument is of type ‘double *’
main.c:84:2: error: incompatible type for argument 2 of ‘atan2’
In file included from /usr/include/math.h:71:0,
                 from main.c:22:
/usr/include/x86_64-linux-gnu/bits/mathcalls.h:61:1: note: expected ‘double’ but argument is of type ‘double *’
make: *** [main] Error 1

So, I can't pass an array as an argument of atan2(), and I'm still quite lost. But I'll keep studying... After all, that's what game development is all about, right? Solving terrible problems in the most efficient way :).

Thank you very much again!

Arthur Kalliokoski
Second in Command
February 2005
avatar

The thing is, thanks to this odd division, the angle does not go from 0 to 360; instead, it goes from 0.000000 to 6.299999. If I print this angle multiplied by something closer to 28 I can get the 360

It's giving you the angle in radians, not degrees. If you multiply that by 180.0/M_PI (which is close to 28) then you get degrees. As I said before, you're passing radians to al_draw_bitmap(), but I guess you didn't know it.

Quote:

expected ‘double’ but argument is of type ‘double *’

So put an asterisk in front, to dereference the pointers.

double angleCalculation = atan2(*playerPosArray1Y, *playerPosArray1X);

They all watch too much MSNBC... they get ideas.

pkrcel
Member #14,001
February 2012

So put an asterisk in front, to dereference the pointers.

I wouldn't do that, he is passing dereferences Array Pointers (yeah blame me for this ;D ) to the atan2 function this way....while he SHOULD get the angle between the first two values, this is not formally correct, is it?

You should pass to atan2 only the vectors you want to calculate the angle in respect to the x-axis...in this case you should pass the DIFFERENCE between X and Y coords of the two objects.

Ericson, I encourage you once more to read up some math text about angles, tangents and the like...you basically have discovered the ratio between a circumference and his diameter..namely PI....but you should have known this beforehand (!)

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

atlasc1
Member #15,020
March 2013

I highly recommend that you brush up on your trigonometry and linear algebra, as these are heavily relied on in game development. Nonetheless, this is essentially what you want to do:

The problem is a variant of line-segment & circle collision detection. Let's say you have two players in the following configuration (top-down 2D view):
{"name":"607363","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7ae43296c4fc9ac3aff7b59ca982dc8.png","w":512,"h":512,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/e\/7\/e7ae43296c4fc9ac3aff7b59ca982dc8"}607363

Let's represent our players as circles (we want them to have some sort of area, it's much easier to shoot at a circle than it is to shoot at an infinitely small point). Player 1 is aiming toward player 2. Therefore, the player is rotated at some angle; let's call this angle <math>\theta</math>. We can also represent this angle's direction as a unit vector (that is a vector that strictly has a magnitude of 1). The unit vector (we'll call this <math>v</math>) is composed of an x component and a y component, which can be derived from the angle we have:

<math>x = \cos(\theta)</math>
<math>y = \sin(\theta)</math>

When player 1 shoots, the bullet will travel along this vector (direction).
{"name":"607364","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/8\/f8402053e091769c4088ac0a25db6cad.png","w":512,"h":512,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/8\/f8402053e091769c4088ac0a25db6cad"}607364

We want the bullet to travel some given distance, or range. This is easily accomplished by multiplying the x and y components of our unit vector by our desired range.

<math>range * v</math>
{"name":"607365","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fab385dcbe0a8772e400a77907dca1d6.png","w":512,"h":512,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/f\/a\/fab385dcbe0a8772e400a77907dca1d6"}607365

We have all of the information to represent the line-segment that is the bullet's trajectory. A line-segment is simply composed of two points. The first point is player 1's position, and the second point is player 1's position plus our scaled unit vector. Now this becomes a line-segment & circle collision check:
{"name":"607366","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/6\/166b8e0d9c5497dde1e9566d8b71eb22.png","w":512,"h":512,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/6\/166b8e0d9c5497dde1e9566d8b71eb22"}607366

james_lohr
Member #1,947
February 2002

It's worth mentioning that, when dealing with vectors, it's usually best not to resort to explicitly using trigonometric functions (e.g. sin,cos) unless you absolutely must. You will usually get a much cleaner and more performant solution if you stick to vectors.

It's actually extremely rare that you really need trig functions. For example, if you wanted to calculate whether the line between two players is within some angle of a players facing, you could achieve this using unit vectors and dot products. Instead of defining the tolerance (or field of view or spray or whatever you want to call it) in units of theta, you would need to define it in units of cos(theta). Which is fine - in actual fact it usually simplifies things a lot.

To illustrate what I mean, suppose you have two players: p1, p2.

Let D = (p2.position - p1.position)

Let v = D / |D| (unit vector from p1 -> p2)

Let u = p1.facing / |p1.facing| (unit vector of p1's facing)

Now, testing whether p2 falls within the field of view of p1 is the following simple test:

|u.v| > k

k is a value between -1 and 1. This is, in my opinion, much more meaningful than radians or degrees, but if you really must convert, then k = cos(theta).

Note how not once have I needed to use cos or sin explicitly, and I most certainly have not had to touch the filthy atan2!

Using atan2 is usually a sign that you've gone wrong somewhere or, at the very least, there is a much cleaner way of doing it.

pkrcel
Member #14,001
February 2012

Interesting James, but

k is a value between -1 and 1. This is, in my opinion, much more meaningful than radians or degrees, but if you really must convert, then k = cos(theta).

wouldn't that formally be u·v = cos(theta) and then you have to define a sort of kmin and kmax?

so that kmin < u·v < kmax defines you spray ?

(of course being this simmetric one can compare only the abs values but this is not really important)

And given that, why is it so wrong to rely on trigonometric functions for something simple as this?

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

james_lohr
Member #1,947
February 2002

Yeah, there was supposed to be an || around the u.v. Thanks for pointing this out pkrcel, I've now fixed it.

pkrcel said:

And given that, why is it so wrong to rely on trigonometric functions for something simple as this?

Sure, computing k from theta is no big deal, especially considering that it's likely to be a one-off calculation. However, I would still recommend sticking to k on principle, since it will reveal opportunities for simplifications when you start doing more complicated things later on. As soon as you start talking in angles, you will invariably end up going back and forth between the two domains and introducing all sorts of unnecessary complexity along the way.

My point was more about not approaching the problem from an "angles" perspective in the first place. For example, one might be tempted to start with an atan2 to calculate the angle between p1 and p2, and then work from there. This is usually a bad idea. Sure, it does the job, but it is not mathematically elegant.

That said, this was just an example and not that big a deal. It's when you start relying upon trigonometric functions in your core collision code that it can become a really big deal, both in terms of performance and in terms of introducing unnecessary complexity.

Don't get me wrong, I'm a massive fan of trig functions. I use them all over the place, particularly when slapping something together quickly. However, when I'm solving a difficult problem or writing code that matters (either because it has the potential to be complex, or because it needs to be fast) I will make a real effort to avoid trig functions.

pkrcel
Member #14,001
February 2012

it can become a really big deal, both in terms of performance and in terms of introducing unnecessary complexity

I ask out of curiosity, but...vector math is not that simple compared to computing angles, and having to normalize most vectors you should be doing a good number of divisions, are the trig functions implementation so slow in these regards?

Note: of course I reckon converting back and forth between cartesian and polar domains is definitely sub-obtimal.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

james_lohr
Member #1,947
February 2002

pkrcel said:

vector math is not that simple compared to computing angles

It probably depends on the problem. Certainly in 2D, I would argue that in the majority of cases, vector math is more simple.

For example, show me the derivation, using trigonometry, for determining which side of a line-segment a point is on. There is no reason even to enter the "polar domain", but I have seen people do it and get into a horrible tangle.

Quote:

and having to normalize most vectors you should be doing a good number of divisions, are the trig functions implementation so slow in these regards?

Quite often you'll find there are tricks to avoid sqrts and divisions. Generally they are more forthcoming than in the equivalent trigonometric solution.

Though I suppose performance is probably not the strongest justification, as one could use lookup tables for either solution.

pkrcel
Member #14,001
February 2012

vector math is not that simple compared to computing angles

It probably depends on the problem. Certainly in 2D, I would argue that in the majority of cases, vector math is more simple.

Well.....I think that in 3D(+) vector math is a huge boon since you're mostly going matrices(tensors+)...diffcult to visualize but in the end more procedural.
Anyway it's not really my trade....

Quote:

For example, show me the derivation, using trigonometry, for determining which side of a line-segment a point is on. There is no reason even to enter the "polar domain", but I have seen people do it and get into a horrible tangle.

I do not understand the question in the first place ( ??? ) ...you mean determine on which "half" of segment and arbitrary point is located? ...or you mean determine in which region of space the point lies in regards of the line?

Sorry for being dumb but I fail to see trigonometry in there but only coordinates check...

Quote:

Though I suppose performance is probably not the strongest justification, as one could use lookup tables for either solution.

I didn't hear something about that since my long gone days on late-age microcontrollers.... ;D

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Go to: