Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » C++ 2D collision detection

This thread is locked; no one can reply to it. rss feed Print
C++ 2D collision detection
cableguy
Member #14,197
April 2012

Hello everyone,

For starters I'll introduce myself. I'm a 47YO PC Technician and I recently picked up a few C++ books and started making 2D games as a hobby. I'm currently trying to make my 1st physics based game, but it has been over 20 years since I practiced my maths and physics "skills" and needless to say I'm quite rusty and I could use some help.

I'm currently working on a 2D vehicle sidescroller that's quite similar to the game "Happy Wheels". So far I've implemented gravity, acceleration, friction, etc. and a basic collision detection for non-diagonal rectangular objects.

Problem I'm having is figuring out how to implement collision detection for diagonal objects (slopes), I want the vehicle to efficiently "climb" the slope and modify its rotation accordingly. Any tips on how I could do that would be greatly appreciated!

David Sopala
Member #5,056
September 2004

Slopes are just triangles in disguise. Use triangle - rectangle collision. I am assuming a side scroll since I have no idea what happy wheels looks like. Use right triangles and the you can find that hypotenuse take the point on the line of the hypotenuse nearest the center of the rectangle(?vehicle?) and correct against that.

As for the rotation right triangle properties a1 + a2 + a3 = 180 degrees. You know the height and the width of said triangle.

Keep in mind allegro uses 256 degree rotation for it's functions(not sure on a5 though).

I am writing this off the top of my head, it should be semi-correct.

   a2     hyp = sqrt(w^2 + h^2);
   /|     sin(a1) = h / hyp;    rotation = (h / hyp * 23040) / 360;  //this will be ready to use 90*256 = 23040.
  / |     sin(a2) = w / hyp;
 /  |  h  
/___|     
a1        
  w

useful links:

http://www.helixsoft.nl/articles/circle/sincos.htm

gnolam
Member #2,030
March 2002
avatar

There's no reason whatsoever to use any trigonometric functions here. That much is certain. :P

cableguy said:

I want the vehicle to efficiently "climb" the slope and modify its rotation accordingly. Any tips on how I could do that would be greatly appreciated!

More details, please. Are you using a vector or bitmap world? Heightmapped or completely free? How is the vehicle represented in terms of collidable objects?

--
Move to the Democratic People's Republic of Vivendi Universal (formerly known as Sweden) - officially democracy- and privacy-free since 2008-06-18!

cableguy
Member #14,197
April 2012

@David, Thanks a bunch for the tips. That link's brilliant, I'll start reading through it as soon as possible.

@Gnolam, "More details, please. Are you using a vector or bitmap world? Heightmapped or completely free? How is the vehicle represented in terms of collidable objects?"

Completely free and all objects are in fact bitmaps(Even the slope), each object is governed by vectors tho. The vehicle is basically a red rectangle right now (platform1.bmp), and depending on the vehicle's velocity I check for collisions. For example if Vehicle.XVelocity>0, I check the left side of each terrain object for collisions.

I managed to calculate the slope by using the following algorithm

m = (y2-y1)/(x2-x1)

I then used the y = mx + b equation to find the slope's angle in degrees and converted it into radians which I then used to rotate the object. I then set the vehicle's direction according to its rotation and it climbs that slope just fine :). BUT, without acceleration - the vehicle starts to sink through the slope... And I'm not sure how to stop that from happening.

l j
Member #10,584
January 2009
avatar

I think you need some sort of collision response.
Basically push the vehicle back out of the slope if it collided.

I'm not good at collision detection so I'm afraid I can't help you a lot.

Box2D is a nice physics engine and it's open source, so you can look at their code, but it's rather advanced.

cableguy
Member #14,197
April 2012

Thanks for your reply Taron. I'll definitely have a look at Box2D (although it's probably WAAAAY too advanced for me) As I said in my previous reply, all of the objects are bitmaps (I've attached the slope bitmap so you guys can see what I'm working with).

I already found the slope and the angle of the bitmap, but I'm not sure what algorithm to use in order to let the vehicle know to apply the collision detection function only when it touches the slope itself (right now collision detection is applied whenever the vehicle touches the bitmap's bounding box)

I thought about creating a pixel perfect collision test using bit-masking, but I have no idea where to start + I'm worried it might lag the game.

David Sopala
Member #5,056
September 2004

I assumed he wanted the car or whatever to rotate based on the angle it was climbing, maybe I was wrong.

Dizzy Egg
Member #10,824
March 2009
avatar

cableguy said:

BUT, without acceleration - the vehicle starts to sink through the slope... And I'm not sure how to stop that from happening.

You need to keep checking those collisions even if the car velocity is 0.00 I guess....

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

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

If your car is on a slope, give it a pointer to, or a copy of the triangle it is on, or check the triangle/rectangle collision each frame. Adjust the height of the car to match the height of the slope as it travels up or down it.

To get an angle from P1 to P2, use theta = atan2(p2.y - p1.y , p2.x - p1.x);

Arthur Kalliokoski
Second in Command
February 2005
avatar

If your car is on a slope, give it a pointer to, or a copy of the triangle it is on, or check the triangle/rectangle collision each frame. Adjust the height of the car to match the height of the slope as it travels up or down it.

What happens when the car crosses a valley or peak? I'd say to have the front wheel follow the slope under the front wheel, and likewise for the back wheel.

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

Gnamra
Member #12,503
January 2011
avatar

I have a related question which I don't think is worth starting a new topic about.

This is my first attempt at collision detection and I'm considering using the bounding box / rectangle collision detection, what I want to know is if you have multiple boxes, do you have to check with all of them if you're colliding?

That seems really inefficient..

Stas B.
Member #9,615
March 2008

@cableguy: From personal experience, I can tell you that handling collisions with a bitmap is a lot more trouble than it's worth. Your objects will sink into the bitmap and you will need to figure out how to push them out. You will need to figure out how to convert pixel data into a normal vector for collision response and a tangent vector for motion. Your terrain will not consist of a single slope in the general case, but of arbitrary shapes. It's very hard to achieve smooth and natural motion along a bitmap terrain. You'll be better off if you write a simple polygon level editor and use that to construct your levels.

As for making a Happy-Wheels-style game, a simple way to do it would be to use a constraint-based Verlet system for the physics and implement some simple circle-triangle collision handling. It will allow you to create not only the vehicles themselves, but also ragdoll passengers like in Happy Wheels and all sorts of other crazy things with great ease. Try googling for Advanced Character Physics by Thomas Jakobsen. A Verlet system with constrains should be around 100 lines of code and may be easier to implement than to learn how to use a third-party physics API.

cableguy
Member #14,197
April 2012

Thank you all for your replies!

After a few hours of bashing my head against the keyboard, I decided to abandon all hope of implementing proper collision detection using bitmaps ;D... At least for now. Need to do a lot more reading.

@stas, thanks for the Jakobsen reference. His guide is going to make a good read.

@Gnamra, Depending on your algorithm you might want to break the collision checks into sectors. Or maybe just implement a few extra if statements to check individual bounding boxes.

@edgar, thanks for the atan formula!

@arthur, I was thinking about that possibility too but wasn't sure how to implement it.

Go to: