Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Collision Detection with a rotating square.

Credits go to Edgar Reynaldo for helping out!
This thread is locked; no one can reply to it. rss feed Print
 1   2 
Collision Detection with a rotating square.
Darren Hoehna
Member #15,297
September 2013

Hey there Allegro goers,

I have a square bitmap that I am able to move around the screen. The left and right keys rotate the bitmap, the up key is to move the bitmap in the direction the bitmap is facing, and the down key is used to move the bitmap in the opposite direction the bitmap is facing.

Now that I have the movement down I am on to collision detection. I learned from http://wiki.allegro.cc/index.php?title=Allegro_5_Tutorial/Bitmaps about border detection, but that was with a square that did not rotate.

My question is how do I go about seeing if the square has collided with the display?

My first, and only, thought was to keep track of the four corners of the square and see if any of them are overlapping the display but I don't know how to keep track of the points through the rotation.

I also just don't know where to start with solving this problem.

Thanks,

Darren.

Trent Gamblin
Member #261
April 2000
avatar

The easiest way to do this is to use transforms right from the start, if you're not already. When you draw the square you'd do something like:

al_rotate_transform(&t, angle);
al_use_transform(&t);
al_draw_filled_rectangle(x1, y1, x2, y2, color);

Hold onto the transform, t. When you do collision detection, you'd use the transform again:

float x = x1;
float y = y1;
al_transform_coordinates(&t, &x, &y);
if (x < 0 || x >= SCREEN_WIDTH || y < 0 || y >= SCREEN_HEIGHT) {
   /* collided */
}
/* check another point... */
x = x2;
y = y1;
/* and so on for all 4 points */

al_transform_coordinates will apply the same transform to the point x, y as was applied to the square, so you'll get the position after the rotation.

Darren Hoehna
Member #15,297
September 2013

I never knew there was such a thing. I'll give it a try and reply back. Thanks. :)

Neil Roy
Member #2,229
April 2002
avatar

You could also use circular collision detection. It's actually easier to use that a box, though perhaps not as accurate if you have a square object, it works quite well.

It's really easy. In this case SPRITE is just a struct containing the x, y co-ordinates on screen of the center of the sprite, and the radius (r) of the circle from that center to check.

bool collision(SPRITE *sprite1, SPRITE *sprite2)
{
   double dist_x = (double)sprite1->x - (double)sprite2->x;
   double dist_y = (double)sprite1->y - (double)sprite2->y;

   // The distance of the vector between the two
   double dist = sqrt((dist_x * dist_x) + (dist_y * dist_y));

   // is the distance less than or equal to the absolute sum of the two radiuses?
   // returns true is it is (collision) false if they're too far apart.
   return dist <= abs(sprite1->r + sprite2->r);
}

Edit: Sorry just realized you asked about a collision with the DISPLAY, this is with two sprites. You could still use the same idea, test the radius and see if it is less than the left edge, greater than the right edge etc.

---
“I love you too.” - last words of Wanda Roy

AmnesiA
Member #15,195
June 2013
avatar

I did not know about al_transform_coordinates either, that is freakin awesome.

=======================
Website
My first game!

jmasterx
Member #11,410
October 2009

If you are interested in OBB (Oriented Bounding Box) collision, one way to do it that's not too complex is Separate Axis Theorem.

http://www.jkh.me/files/tutorials/Separating%20Axis%20Theorem%20for%20Oriented%20Bounding%20Boxes.pdf

It's beyond your needs for this, but it might be interesting for future projects.

Darren Hoehna
Member #15,297
September 2013

Umm, I have tried and tried but I don't understand how to start using transformations.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Transforms aren't too difficult to understand if you know what they are doing.

First, start with an identity transform. This is a transform that will not alter any coordinates passed to it.

Second, apply in order each transformation that you need.

al_translate_transform(&t , -camx , -camy);
al_scale_transform(&t , (double)SCREEN_WIDTH/BUFFER_WIDTH , (double)SCREEN_HEIGHT/BUFFER_HEIGHT);

These two transforms apply a translation (movement) and a scale (stretching).

Now you need to use the transform :

Now everything you draw will be shifted by (-camx , -camy) pixels and scaled from buffer size to screen size.

If you want to transform coordinates manually, use al_transform_coordinates.

float x = player.x;
float y = player.y;
al_transform_coordinates(&t , &x , &y);

Now x and y hold the screen coordinates of the player after applying the camera transformation.

Darren Hoehna
Member #15,297
September 2013

Well, good news is I got it working. Bad news is that it's not working correctly. Here are the transformations I have now to rotate the square.

al_translate_transform(&ShipTransformation, -Ships_X_Position, -Ships_Y_Position);
al_rotate_transform(&ShipTransformation, -CHANGE_IN_ANGLE);
al_translate_transform(&ShipTransformation, Ships_X_Position, Ships_Y_Position);
al_transform_coordinates(&ShipTransformation, &UpperLeft.X, &UpperLeft.Y);
al_transform_coordinates(&ShipTransformation, &UpperRight.X, &UpperRight.Y);
al_transform_coordinates(&ShipTransformation, &LowerLeft.X, &LowerLeft.Y);
al_transform_coordinates(&ShipTransformation, &LowerRight.X, &LowerRight.Y);

And it works. I then call al_draw-filled rectangle and pass in the x and y coordinates of the upper left, and lower right corners.

The problem is that as the square rotates the corners soon meet up on the same vertical or horizontal line. I don't know how to explain it. So I'll draw it.

-----
| |
| |
-----

--------
| |
--------

----------

--------
| |
--------

-----
| |
| |
-----

---
| |
| |
| |
---

|
|
|
|
|

The problem is with the al_draw_rectangle because it is defined on only two points. Is there another drawing I can use that I can use all four points?

Werwolf696
Member #15,203
June 2013
avatar

I'm working on a similar task, I got my bounding box (rectange) to display correctly as follows:

#SelectExpand
1al_identity_transform(&trans); 2al_translate_transform(&trans, -Origin.x, -Origin.y); 3al_rotate_transform(&trans, RotationAngle); 4al_translate_transform(&trans, Origin.x, Origin.y); 5al_use_transform(&trans); 6al_draw_rectangle(BoundingBox.x, BoundingBox.y, BoundingBox.x + BoundingBox.w, BoundingBox.y + BoundingBox.h, al_map_rgba_f(0.6, 0, 0.6, 0.6), 1.0); 7al_use_transform(&identity);

Without seeing your draw call, I can only assume you are not using it correctly by adding the width to the x coordinate to get "x2" and the height to y to get "y2".

Can you post your rectangle draw line of code?

Darren Hoehna
Member #15,297
September 2013

I can post my code. Also, thank you for helping me.
I have structures that holds two floats, one for a X-coordinate and one for a Y-coordinate.

With this code I can see the square change shape

CHANGE_IN_ANGLE = 0.034906585 (rad)
al_translate_transform(&ShipTransformation, -Ships_X_Position, -Ships_Y_Position);
al_rotate_transform(&ShipTransformation, -CHANGE_IN_ANGLE);
al_translate_transform(&ShipTransformation, Ships_X_Position, Ships_Y_Position);
al_transform_coordinates(&ShipTransformation, &UpperLeft.X, &UpperLeft.Y);
al_transform_coordinates(&ShipTransformation, &UpperRight.X, &UpperRight.Y);
al_transform_coordinates(&ShipTransformation, &LowerLeft.X, &LowerLeft.Y);
al_transform_coordinates(&ShipTransformation, &LowerRight.X, &LowerRight.Y);

al_draw_filled_rectangle(UpperLeft.X, UpperLeft.Y, LowerRight.X, LowerRight.Y, al_map_rgb(255, 128, 64));
al_identity_transform(&ShipTransformation);
al_use_transform(&ShipTransformation);

But if you omit the al_transform_coordinates then the square rotates and move like the square is rotating but the square does not visually rotate.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

@Darren - you're not using transformations quite right. Instead of manually transforming coordinates and then drawing a rectangle over them, let allegro use the transform to draw the rectangle from the original coordinates. ;)

CHANGE_IN_ANGLE = 0.034906585 (rad)
al_identity_transform&(&ShipTransformation);
al_translate_transform(&ShipTransformation, -Ships_X_Position, -Ships_Y_Position);
al_rotate_transform(&ShipTransformation, -CHANGE_IN_ANGLE);
al_translate_transform(&ShipTransformation, Ships_X_Position, Ships_Y_Position);
al_use_transform(&ShipTransformation);
al_draw_filled_rectangle(UpperLeft.X, UpperLeft.Y, LowerRight.X, LowerRight.Y, al_map_rgb(255, 128, 64));
al_identity_transform(&ShipTransformation);
al_use_transform(&ShipTransformation);

Don't use these because they modify the contents of UpperLeft.X and UpperLeft.Y and so on

al_transform_coordinates(&ShipTransformation, &UpperLeft.X, &UpperLeft.Y);
al_transform_coordinates(&ShipTransformation, &UpperRight.X, &UpperRight.Y);
al_transform_coordinates(&ShipTransformation, &LowerLeft.X, &LowerLeft.Y);
al_transform_coordinates(&ShipTransformation, &LowerRight.X, &LowerRight.Y);

I think this will work, try it. I got a paper I got to write.

AmnesiA
Member #15,195
June 2013
avatar

This might be an incredibly stupid question but how does al_rotate_transform know how big the rectangle is? Obviously a bigger rectangle means larger change in coordinates based on an angle

=======================
Website
My first game!

J-Gamer
Member #12,491
January 2011
avatar

AmnesiA said:

This might be an incredibly stupid question but how does al_rotate_transform know how big the rectangle is? Obviously a bigger rectangle means larger change in coordinates based on an angle

Actually, al_rotate_transform just multiplies the current transformation matrix with a rotation matrix. If you use al_use_transform, OpenGL/DirectX will multiply all coordinates it draws to with that matrix, thus performing the rotation.
It doesn't matter what you draw ;)

" There are plenty of wonderful ideas in The Bible, but God isn't one of them." - Derezo
"If your body was a business, thought would be like micro-management and emotions would be like macro-management. If you primarily live your life with emotions, then you are prone to error on the details. If you over-think things all the time you tend to lose scope of priorities." - Mark Oates

Darren Hoehna
Member #15,297
September 2013

That does work. Almost. The square is rotated and the square acts like it has been rotated when I move the square forward. The only problem is that the display draws the square with only one rotation and when I let go of the left or right key the square returns to normal, but the rotation is kept.

But I am using what you gave me and it should work.

Any ideas? I can give you the code so you can see what I am doing.

Also good luck on your paper.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Darren Hoehna
Member #15,297
September 2013

Glad you got it done. My school starts on the 26th. I have started a new project so I can play with translations. I'll post what I have in a few days.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Darren Hoehna
Member #15,297
September 2013

Thanks for the bump. Here is what I have. I am only including the code for moving the square up and rotating it to the left.

#SelectExpand
1#include <allegro5/allegro.h> 2 3float ULX = 320; 4float ULY = 320; 5float LRX = 340; 6float LRY = 340; 7 8double FPS = 60.0; 9ALLEGRO_TIMER *Timer = al_create_timer(1.0/FPS); 10ALLEGRO_EVENT_QUEUE *EventQueue = al_create_event_queue(); 11bool Stop = false; 12al_start_timer(Timer); 13bool Redraw = false; 14bool Keys[] = {false, false, false, false}; 15float Ships_X_Position = 330; 16float Ships_Y_Position = 330; 17 18al_clear_to_color(al_map_rgb(0, 0, 0)); 19al_draw_filled_rectangle(ULX, ULY, LRX, LRY, al_map_rgb(204, 153, 64)); 20al_flip_display(); 21 22float ChangeInAngle = 0.034906585; 23while(!Stop) 24{ 25 ALLEGRO_EVENT Event; 26 al_wait_for_event(EventQueue, &Event); 27 if(Event.type == ALLEGRO_EVENT_TIMER) 28 { 29 al_identity_transform(&ShipTransformation); 30 if(Keys[0]) 31 { 32 al_translate_transform(&ShipTransformation, 0, -5); 33 Ships_Y_Position -= 5; 34 } 35 if(Keys[2]) 36 { 37 al_translate_transform(&ShipTransformation, -Ships_X_Position, -Ships_Y_Position); 38 al_rotate_transform(&ShipTransformation, ChangeInAngle); 39 al_translate_transform(&ShipTransformation, Ships_X_Position, Ships_Y_Position); 40 } 41 Redraw = true; 42} 43 else if(Event.type == ALLEGRO_EVENT_KEY_DOWN) 44 { 45 switch(Event.keyboard.keycode) 46 { 47 case ALLEGRO_KEY_UP: 48 Keys[0] = true; 49 break; 50 case ALLEGRO_KEY_LEFT: 51 Keys[2] = true; 52 break; 53 } 54 } 55 else if (Event.type == ALLEGRO_EVENT_KEY_UP) 56 { 57 switch(Event.keyboard.keycode) 58 { 59 case ALLEGRO_KEY_UP: 60 Keys[0] = false; 61 break; 62 case ALLEGRO_KEY_LEFT: 63 Keys[2] = false; 64 break; 65 } 66 } 67 if(Redraw && al_is_event_queue_empty(EventQueue)) 68 { 69 70 //al_transform_coordinates(&ShipTransformation, &ULX, &ULY); 71 //al_transform_coordinates(&ShipTransformation, &LRX, &LRY); 72 al_use_transform(&ShipTransformation); 73 al_draw_filled_rectangle(ULX, ULY, LRX, LRY, al_map_rgb(204, 153, 64)); 74 al_identity_transform(&ShipTransformation); 75 al_use_transform(&ShipTransformation); 76 al_flip_display(); 77 al_clear_to_color(al_map_rgb(0, 0, 0)); 78 Redraw = false; 79 } 80 } 81}

Now...this works. Kind of. If I comment out the al_transform_coordinates then, when I hole the up key, the square will move five pixles up and stay there. If I have al_transform_coordinates un-commented, then the square continuously moves up because the coordinates are being changed as well.

The square rotates correctly, but the square morphs because the ULX, ULY, LRX, and LRY are changing. My only solution to this is to make a method that draws a square where I can define all four points and not two points.

So my question is, how do I successfully rotate a square and have the square keeps it's shape?

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Okay, you need to keep track of the angle too, you can't just display one angle and expect it to keep rotating, and yes your ship should move up 5 pix per frame but you're setting the view to 0,5 that's not really what you wanna do. And you need to update your ULX... variables. But better than that make a ship or player or object struct and store all the info in there. Have it store the rectangle of the ship and its angle.

Read, and try compiling this source code and running it. It should give you a basic example of transforms and movement :

#SelectExpand
1 2#include <allegro5/allegro.h> 3#include <allegro5/allegro_primitives.h> 4 5#include <cstdlib> 6#include <cmath> 7 8const float SCREEN_WIDTH = 800; 9const float SCREEN_HEIGHT = 600; 10 11int TIMER_BPS = 60; 12float TIMER_FREQ = 1.0f/(float)TIMER_BPS; 13 14float camera_xpos = 0.0f; 15float camera_ypos = 0.0f; 16 17const float SHIP_WIDTH = 50.0f; 18const float SHIP_HEIGHT = 100.0f; 19const float SHIP_SPEED = 120.0f/60.0f;// 120 pixels every 60 seconds 20 21 22enum KEYS { 23 KEY_MOVE_FORWARD = 0, 24 KEY_MOVE_BACKWARD = 1, 25 KEY_TURN_LEFT = 2, 26 KEY_TURN_RIGHT = 3 27}; 28 29// These match the KEYS enum 30const int NUMKEYS = 4; 31int keycodes[NUMKEYS] = {ALLEGRO_KEY_UP , ALLEGRO_KEY_DOWN , ALLEGRO_KEY_LEFT , ALLEGRO_KEY_RIGHT}; 32 33int keys[NUMKEYS] = {0,0,0,0};// track key ups and downs 34 35 36 37typedef struct SHIP { 38 float x,y,w,h,rx,by,angle; 39}; 40 41SHIP s; 42void init_ship(SHIP* s) { 43s->x = s->y = s->w = s->h = s->rx = s->by = s->angle = 0.0f; 44} 45 46void update_ship_corner(SHIP* s) { 47 s->rx = s->x + s->w; 48 s->by = s->y + s->h; 49} 50 51void set_ship_rectangle(SHIP* s , int x , int y , int w , int h) { 52 s->x = x; 53 s->y = y; 54 s->w = w; 55 s->h = h; 56 update_ship_corner(s); 57} 58 59void set_ship_pos(SHIP* s , int x , int y) { 60 s->x = x; 61 s->y = y; 62 update_ship_corner(s); 63} 64 65void translate_ship(SHIP* s , float xshift , float yshift) { 66 set_ship_pos(s , s->x + xshift , s->y + yshift); 67} 68 69void set_angle(SHIP* s , float angle) { 70 s->angle = angle; 71} 72 73void shift_angle(SHIP* s , float angle_delta) { 74 set_angle(s , s->angle + angle_delta); 75} 76 77void move_ship_forward(SHIP* s) { 78 translate_ship(s , SHIP_SPEED*cos(s->angle) , SHIP_SPEED*sin(s->angle)); 79} 80 81void move_ship_backward(SHIP* s) { 82 translate_ship(s , -SHIP_SPEED*cos(s->angle) , -SHIP_SPEED*sin(s->angle)); 83} 84 85 86void set_transform_for_ship(ALLEGRO_TRANSFORM* t , SHIP* s) { 87 al_identity_transform(t); 88 // center on ship 89 al_translate_transform(t , -(s->x + s->w/2.0f) , -(s->y + s->h/2.0f)); 90 // rotate 91 al_rotate_transform(t , s->angle); 92 // move ship back where it was 93 al_translate_transform(t , +(s->x + s->w/2.0f) , +(s->y + s->h/2.0f)); 94} 95 96void draw_ship(SHIP* s) { 97 ALLEGRO_TRANSFORM transform, old; 98 set_transform_for_ship(&transform , s); 99 // follow our camera 100 al_translate_transform(&transform , -camera_xpos , -camera_ypos); 101 al_use_transform(&transform); 102 al_draw_filled_rectangle(s->x , s->y , s->rx , s->by , al_map_rgb(255,127,0)); 103 // theoretically, reset transformation matrix for allegro here,too lazy though 104} 105 106int main(int argc , char** argv) { 107 108 if (!al_init()) {exit(1);} 109 if (!al_install_keyboard()) {exit(2);} 110 if (!al_init_primitives_addon()) {exit(2);} 111 112 al_set_new_display_flags(ALLEGRO_OPENGL | ALLEGRO_WINDOWED); 113 ALLEGRO_DISPLAY* disp = al_create_display(SCREEN_WIDTH , SCREEN_HEIGHT); 114 115 if (!disp) {exit (3);} 116 117 ALLEGRO_EVENT_QUEUE* events = al_create_event_queue(); 118 if (!events) {exit(4);} 119 120 ALLEGRO_TIMER* timer = al_create_timer(TIMER_FREQ); 121 if (!timer) {exit(5);} 122 123 al_register_event_source(events , al_get_keyboard_event_source()); 124 al_register_event_source(events , al_get_display_event_source(disp)); 125 al_register_event_source(events , al_get_timer_event_source(timer)); 126 127 SHIP ship; 128 init_ship(&ship); 129 set_ship_rectangle(&ship , 100 , SCREEN_HEIGHT/2 - SHIP_HEIGHT/2 , SHIP_WIDTH , SHIP_HEIGHT); 130 131 bool quit = false; 132 bool redraw = true; 133 134 al_start_timer(timer); 135 136 while (!quit) { 137 if (redraw) { 138 redraw = false; 139 al_clear_to_color(al_map_rgb(0,0,0)); 140 draw_ship(&ship); 141 al_flip_display(); 142 } 143 do { 144 ALLEGRO_EVENT e; 145 al_wait_for_event(events , &e); 146 if (e.type == ALLEGRO_EVENT_TIMER) { 147 redraw = true; 148 if (keys[KEY_TURN_LEFT]) { 149 shift_angle(&ship , TIMER_FREQ*(-M_PI/3.0f)); 150 } 151 if (keys[KEY_TURN_RIGHT]) { 152 shift_angle(&ship , TIMER_FREQ*(M_PI/3.0f)); 153 } 154 if (keys[KEY_MOVE_FORWARD]) { 155 move_ship_forward(&ship); 156 } 157 if (keys[KEY_MOVE_BACKWARD]) { 158 move_ship_backward(&ship); 159 } 160 } 161 else if (e.type == ALLEGRO_EVENT_KEY_DOWN) { 162 if (e.keyboard.keycode == ALLEGRO_KEY_ESCAPE) {quit = true;} 163 for (int k = 0 ; k < NUMKEYS ; ++k) { 164 if (e.keyboard.keycode == keycodes[k]) { 165 keys[k] = 1; 166 } 167 } 168 } 169 else if (e.type == ALLEGRO_EVENT_KEY_UP) { 170 for (int k = 0 ; k < NUMKEYS ; ++k) { 171 if (e.keyboard.keycode == keycodes[k]) { 172 keys[k] = 0; 173 } 174 } 175 } 176 else if (e.type == ALLEGRO_EVENT_DISPLAY_CLOSE) { 177 quit = true; 178 } 179 } while (!al_is_event_queue_empty(events) && !quit); 180 } 181 182 183 /** Leak a bunch of memory here because I haven't called any of the al_destroy routines and cleaned up after myself */ 184 185 return 0; 186}

And if you learn anything from this code, it should be to use functions and compartmentalize your code.

Edit - the movement isn't quite right for some reason I haven't figured out yet

Darren Hoehna
Member #15,297
September 2013

It works. I'll look it over and learn from it. I know that I should use functions. I do that at my job. But I wanted to first get the rotation correct then I was going to worry about functions and the such.

EDIT:

I'm going through you code and I have some questions.

I understand what by are used for, but what do they stand for?
for init_ship(), why do you have SHIP x; before the method?

Dizzy Egg
Member #10,824
March 2009
avatar

Do you mean why does he have SHIP s; before calling init? He's declaring an instance of the structure; s is an instance of SHIP...you need it to pass to init..

struct SHIP; //the structure

SHIP s;  //s is a SHIP

initShip(s); //send ship to function

----------------------------------------------------
Please check out my songs:
https://soundcloud.com/dont-rob-the-machina

LennyLen
Member #5,313
December 2004
avatar

Dizzy Egg said:

Do you mean why does he have SHIP s; before calling init? He's declaring an instance of the structure; s is an instance of SHIP...you need it to pass to init..

Except that in the main function a SHIP called ship is declared and passed to the initShip() function.

That line is not required at all. I'm guessing it was part of an earlier revision and was not removed.

Dizzy Egg
Member #10,824
March 2009
avatar

Yeah, what Lenny said.

----------------------------------------------------
Please check out my songs:
https://soundcloud.com/dont-rob-the-machina

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

LennyLen said:

That line is not required at all. I'm guessing it was part of an earlier revision and was not removed.

Yes, you are correct. ;)

Anybody know why the movement follows integer or rounded angles, but the orientation looks perfect all the time? Ie. why doesn't it go the direction it is facing? I don't get it. Anybody try the code?

 1   2 


Go to: