next »

[Ping]

Hello all,

I've just recently become interested in game design (as a hobby) and have gone along a tutorial or two from DevHub. I love the code style used there; it's very OO-centric, a good thing for a coder in the Java/C++ mindset like myself.

However, I've kinda run out of tutorials on that site; I'm eagerly awaiting the next tutorial, but for now would like help with Collision Detection at least.

I hope to do the seemingly-recommended thing and start with Tetris, but need to know how to do collision detection.

I know how to blit surfaces, handle events, animate sprites, etc. However, I simply don't know how to do collision detection.

If anyone could point me in the right direction (other than LazyFoo's tutorials; such abysmal coding and explanations) I would be one happy newbie!

[idiotmeat]

I would check out gamedev.net.  There's a few resources there that explain collision detection.
On a side note, LazyFoo's tutorial should get the job done if you're looking for box-box type collisions.

[Ivan]

Not to be a dick about it, but try googling it.

http://www.google.com/search?hl=en&safe=off&q=collision+detection+tutorial&btnG=Search

[Gravious]

Not to be a dick about it, but try googling it.

http://www.google.com/search?hl=en&safe=off&q=collision+detection+tutorial&btnG=Search

That is pretty dickish 

I'd like to think he thought of that already, just wanted the benefit of the tiggers wisdom 

saying that though, I'd have probably said the same  :D except, i found this site pretty good: http://cone3d.gamedev.net/cgi-bin/index.pl?page=tutorials/gfxsdl/index

[Ping]

Not to be a jerk about it, but try googling it.

http://www.google.com/search?hl=en&safe=off&q=collision+detection+tutorial&btnG=Search

That is pretty jerkish 

I'd like to think he thought of that already, just wanted the benefit of the tiggers wisdom 

saying that though, I'd have probably said the same  :D except, i found this site pretty good: http://cone3d.gamedev.net/cgi-bin/index.pl?page=tutorials/gfxsdl/index

I did indeed Google for it, found both Cone3D and gamedev.net, but I thought cone3d applied to some proprietary engine, and had not yet found most of gamedevs content.

But yeah, the primary reason was that the TIGers seem quite knowledgeable in this field, and a few of you have expressed previous knowledge of SDL.

That said, thanks for the links, folks. Good to know there are helpful people on these here internet tubes.

[Saint]

Hmm, SDL is a media library and as such it doesn't contain any specific collision detection code...

... That is, unless you want to do pixel collisions, which I generally recommend against since it hogs a lot of your cycles without giving you much usable information. But anyway.

Collision detection in it simplest form is a matter of having a bounding volume for every object - spheres or cubes in 3D, circles or rectangles in 2D. Now, for every frame you check if any objects overlap and what the smallest axis of separation would be. For spheres/circles this is done by seeing if the distances between the centers are less than the combined radii and the separation axis is the ray going through both of the centers. For boxes, you simply check one dimension at a time and pick the axis where the boxes overlap the least. When you have this information, it is simple to push one or both objects away from each other on the axis of separation.

Tell me if you need me to explain this further, It's kind of late here so I might have glossed over things 

There might be some resources at http://www.ultimategameprogramming.com , but I'm not sure.

The ultimate resource on collision detection is a book by Christer Ericson called "Real-Time Collision Detection"; http://books.google.com/books?id=WGpL6Sk9qNAC&printsec=frontcover&sig=zLqv6AE9Po7Uv1deM7Rcfb8vhKI
... Although if you're just starting out, it can be a little too much.

Oh, and I wrote my bachelor's thesis on Rigid Body dynamics some years ago, it's not very good but it might be a little easier to take in; http://ekermo.se/kodo/thesis_ae05.pdf

[Ping]

I must be some level of retarded. My code is working -- but backwards.

Using my entity class and the provided resources, I've put together the following code:

Code:

bool CEntity::OnCollide(CEntity &Other)
{
	//define bounding box for other
	float OtherLeft = Other.X;
	float OtherRight = Other.X + Other.Width;
	float OtherTop = Other.Y;
	float OtherBottom = Other.Y + Other.Height;

	//define bounding box for self
	float ThisLeft = X;
	float ThisRight = X + Width;
	float ThisTop = Y;
	float ThisBottom = Y + Height;
	
	//test for collision
	if (ThisBottom < OtherTop) return true;
	if (ThisTop > OtherBottom) return true;
	
	if (ThisRight < OtherLeft) return true;
	if (ThisLeft > OtherRight) return true;

	return false;
}

However, my function is returning false on a collision, and true on no collision!

I beg for the assistance of a knowledgeable tiger!

[Saint]

I must be some level of retarded. My code is working -- but backwards.

Using my entity class and the provided resources, I've put together the following code:

Code:

bool CEntity::OnCollide(CEntity &Other)
{
	//define bounding box for other
	float OtherLeft = Other.X;
	float OtherRight = Other.X + Other.Width;
	float OtherTop = Other.Y;
	float OtherBottom = Other.Y + Other.Height;

	//define bounding box for self
	float ThisLeft = X;
	float ThisRight = X + Width;
	float ThisTop = Y;
	float ThisBottom = Y + Height;
	
	//test for collision
	if (ThisBottom < OtherTop) return true;
	if (ThisTop > OtherBottom) return true;
	
	if (ThisRight < OtherLeft) return true;
	if (ThisLeft > OtherRight) return true;

	return false;
}

However, my function is returning false on a collision, and true on no collision!

I beg for the assistance of a knowledgeable tiger!

What you are using is what is called the separating axis algorithm in it's simplest form. In short, if two convex bodies don't penetrate, there is an axis that you can project both bodies on and see this.

The thing you are doing wrong, though, is that - as you said - you are doing it backwards. Consider the first if-clause, if the bottom of this entity is lower than the top of the other, we have not proven that the bodies intersect - this entity could still be to the right, left, or lower than the other entity.

However, had the opposite been true - the bottom of this entity is higher than the top of the other - we would have proven that the entities do not intersect - as this entity is clearly above the other one, there's no way they can intersect.

Do this check for all axes and if you can't prove the objects don't intersect, ie, you haven't found the separating axis, then they intersect.

So the code would be...

Code:

bool CEntity::OnCollide(CEntity &Other)
{
	//define bounding box for other
	float OtherLeft = Other.X;
	float OtherRight = Other.X + Other.Width;
	float OtherTop = Other.Y;
	float OtherBottom = Other.Y + Other.Height;

	//define bounding box for self
	float ThisLeft = X;
	float ThisRight = X + Width;
	float ThisTop = Y;
	float ThisBottom = Y + Height;
	
	//test for collision
	if (ThisBottom > OtherTop) return false;
	if (ThisTop < OtherBottom) return false;
	
	if (ThisRight < OtherLeft) return false;
	if (ThisLeft > OtherRight) return false;

	return true;
}

[Ping]

Wow, I really must have some level of retardation. The critical thinking portion of my brain has shut down.

Thanks for the help and the explanation!

[Saint]

Ah, no worries, we all have our bad days

Glad it worked out.

[skrew]

If your interested, another good learning resource for SDL is at http://sol.gfxile.net/gp/index.html

[Corpus]

This thread has made me realise how terrifyingly bloated my collision code is. For serial.

[Alec]

For serial.

Honest to blog.

[Zaphos]

I hope to do the seemingly-recommended thing and start with Tetris, but need to know how to do collision detection.

In a case like this, where things are sort of laid out in a grid, you can do collision detection just by checking a 2D array of booleans, where the value of array[x,y] is true if there's something in that space, and false otherwise.

This is also good for platforming games, where you often want to check a character for collision against a non-moving background (handling the typically much smaller number of moving elements separately); you can figure out which tiles your character is over, and check the array to see if any of those tiles are occupied.

[Ping]

Awesome. Thanks Zaphos.

Though, since this thread, I've learned a few things with the help of tigIRCers:

• C++ is bad for game newbies.
• PyGame melts faces.
• For most purposes, tile-based grids work dandy.

So, I'm learning Python and PyGame (and loving both.)

Still working on that whole "implementation" of the tile-based engine. I'm slowly grasping some of the basic concepts of a simple engine.

My current main problem is my codemonkey mentality: client say, codemonkey do. Codemonkey not sit and plan design, codemonkey implement client design.

Having run through a few tutorials (each having me write their own engines, somewhat confusing at times) I'm starting to get it, and hopefully can finish up a decent engine for future use soon.

After that? Some project involving sombreros.

[Derek]

Good luck!  You seem very determined to learn, which is great!

You might find these pygame tutorials useful:

http://www.scriptedfun.com/category/screencasts/

I haven't looked at them myself, but they look promising (source included).

[Ping]

Thanks, Derek!

I must admit, I've run through most of that tutorial already, but had an issue with my code that I couldn't sort out....so I moved to a different tut on tile-based engines...

[Bad Sector]

Or to simplify and generalize the code above, here is a function i wrote and carry with my stuff  (games and not) since many years ago (first written in Pascal):

Code:

int rect_over_rect(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{
        return !(bx1 > ax2 || bx2 < ax1 || by1 > ay2 || by2 < ay1);
}

It just checks if a rectangle is "over" another rectangle and can be used for collision detection for entity-vs-entity and entity-vs-tilemap (by finding the tilemaps around the entity and bringing them to "world space" - that is usually multiplying their x,y values with the tile's size and subtracting scrolling values, if your game scrolls).

Also i think you'll be better if you stay away from OOPisms for your first games. OOP helps to maintain and reuse the code, but your first games won't be code you really want to reuse :-). Writing in a procedural manner is usually easier, unless what you want to do really fits in the OOP style (like making a Swing-like GUI library -- i wouldn't imagine how horrifying Swing would be if it was written in C).