Thinking clearly about collision detection

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems.

Moderator: Moderators

tepples
Posts: 22049
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Thinking clearly about collision detection

Post by tepples » Mon Jan 14, 2013 8:31 am

In a lot of NES games, it was fairly easy to get things to glitch through the walls due to poor collision detection and response between sprites and the background. The programmers may have been rushed or just inexperienced. So I decided to sit down and think about what collision detection actually is so that I can add a bit of mathematical rigor to make it more predictable. The goal is to determine whether something is overlapping one or more solid cells, and then push it out of all walls that it's overlapping.

With this clear goal in mind, I devised an algorithm to discover the contour of the walls in an object's neighborhood and act on it. Does anyone want to see a tech demo of this method on the NES, so that you have something to cheat off of when coding terrain collision in your own games? Or did I overcomplicate things?

User avatar
tokumaru
Posts: 11858
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Thinking clearly about collision detection

Post by tokumaru » Mon Jan 14, 2013 9:25 am

I'd say this is one of the topics that cause most confusion to newbies once they get past the very beginning and start coding programs that actually resemble games, so any new material on this is welcome. If you have some visual aids to provide, that would be nice too. EDIT: I hadn't checked the link yet! You have a whole page on this! =)

Celius
Posts: 2157
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Re: Thinking clearly about collision detection

Post by Celius » Mon Jan 14, 2013 10:59 am

Collision detection is very hard to wrap your mind around in the beginning, so the more you can simplify it, the better. I haven't read the article to comprehend it in great detail, but it seems to be pretty short and sweet. If not done correctly, collision code can be littered with messy comparisons and off-by-one errors. I know when I started, I had lots of problems with being off by one. If an object is 16x16 pixels in size, the corners are actually at 0,0 and 15,15; not 0,0 and 16,16. If you code this wrong, the object will not fit between 2 16x16 pixel solid objects :).

User avatar
mikejmoffitt
Posts: 1352
Joined: Sun May 27, 2012 8:43 pm

Re: Thinking clearly about collision detection

Post by mikejmoffitt » Mon Jan 14, 2013 12:24 pm

A simple box-based collision detection I sometimes use between two boxes: It's written out in C-style syntax but it should be somewhat adaptable:

Code: Select all


bool boxCol(int x1, int x2, int y1, int y2, int x3, int x4, int y3, int y4)
{
	return !(x2 < x3 || x1 > x4 || y2 < y3 || y1 > y4 );
}

x1 and x2 are the left and right boundaries of box 1, and y1 and y2 are the top and bottom boundaries of box 1.
x3 and x4 are the left and right boundaries of box 1, and y3 and y4 are the top and bottom boundaries of box 2.
It checks if x1 is more to the left than x4, and a similar comparison for the other boundaries.

Basically, if any facing boundary is beyond the other, it means it is not a collision.

User avatar
MottZilla
Posts: 2832
Joined: Wed Dec 06, 2006 8:18 pm

Re: Thinking clearly about collision detection

Post by MottZilla » Mon Jan 14, 2013 12:30 pm

That's how you do collision between two objects, but collision between a tile map and an object is the subject here I think.

User avatar
mikejmoffitt
Posts: 1352
Joined: Sun May 27, 2012 8:43 pm

Re: Thinking clearly about collision detection

Post by mikejmoffitt » Mon Jan 14, 2013 1:23 pm

MottZilla wrote:That's how you do collision between two objects, but collision between a tile map and an object is the subject here I think.
True, but you can consider the tile to be a box.

tepples
Posts: 22049
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Thinking clearly about collision detection

Post by tepples » Mon Jan 14, 2013 1:47 pm

In the case of tiles, it's not only collision detection but also collision response: what happens when you know two things are overlapping. Here, we know that an object overlaps multiple boxes at once, and we want to know where to move the object so that it stops overlapping them.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Re: Thinking clearly about collision detection

Post by blargg » Mon Jan 14, 2013 1:48 pm

There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical. You need a system which can quickly determine a collision with a tile and determine where the colliding object should end up, given the original coordinates of the object and the coordinates it would be at had there been no collision.

User avatar
tokumaru
Posts: 11858
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Thinking clearly about collision detection

Post by tokumaru » Mon Jan 14, 2013 2:36 pm

blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.
Also, when you have slopes, not all tiles are boxes.

User avatar
Bregalad
Posts: 7951
Joined: Fri Nov 12, 2004 2:49 pm
Location: Chexbres, VD, Switzerland

Re: Thinking clearly about collision detection

Post by Bregalad » Mon Jan 14, 2013 2:48 pm

I remember that, back when I was a complete newb in NESdev, I had the following reflexion :

There is 256x240 pixels on the screen, so this makes 61440 pixels. For collision detection you'd need at least 61440 bits = 7.7 kB but there is only 2 kB of RAM in the NES. How can games then do collision detection ?

Well now I know the answer but back then it was really not obvious.

Simple object <-> object collision or object <-> BG collision is not too complex to do as long as you only move one pixel at a time (or simulate a faster move by moving one pixel at a time internally).
However I really wonder how games with REALLY complex collision such as Super Castlevania IV did it. It had multiple background layers in Level 4, and mode 7 a little everywhere with scaling and rotation of object. Also rotating wheels in level A and moving platforms in level B. Of course if has slopes too. Do a proper collision for this should have been a total nightmare.
(PS : And it is also the first game of the series where they got it perfectly right).

tepples
Posts: 22049
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Thinking clearly about collision detection

Post by tepples » Mon Jan 14, 2013 2:51 pm

Rotating levels aren't any harder provided the object and camera positions are stored in "world space", relative to the origin of the map.

Sik
Posts: 1589
Joined: Thu Aug 12, 2010 3:43 am

Re: Thinking clearly about collision detection

Post by Sik » Tue Jan 15, 2013 8:38 am

tokumaru wrote:
blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.
Also, when you have slopes, not all tiles are boxes.
Technically, in practice they still are handled as such, but the collision response is different.

Denine
Posts: 398
Joined: Wed Feb 17, 2010 5:42 pm

Re: Thinking clearly about collision detection

Post by Denine » Tue Jan 15, 2013 10:09 am

While we are at topic of background colissions.
What adventages have mario bros style collisions? I mean, that player is pushed outside of the box if player is inside of the box.
Fantastic Dizzy do the same thing, but pushes player upwards, so the game can use a fake slope tiles without extra coding for it.

In inversion I have a detection point just below the player's foot to detect a tile below. If it's a solid one, then I ignore "player is falling" code.

Which one is better way to use? Pushing player out of box or stopping player from entering the box?
The first one proves to be more glitchy(?)

tepples
Posts: 22049
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: Thinking clearly about collision detection

Post by tepples » Tue Jan 15, 2013 10:36 am

Image
MarioWiki.com


This glitch is caused by the collision detection routine not seeing that the lower left corner of Mario is within air when Mario comes out of the crouch. My algorithm, sampling at each corner, would give a contour of B ▀█ which means "push to the left, then push down".

And even if an object were suddenly entirely embedded in solid tiles, one of the suggestions given on the page for how to handle contour F ██ is to remember the last tile that the object was in and then push toward that tile, which is ultimately the same as "stopping player from entering the box".

Celius
Posts: 2157
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

Re: Thinking clearly about collision detection

Post by Celius » Tue Jan 15, 2013 11:12 am

Sik wrote:
tokumaru wrote:
blargg wrote:There could be hundreds of tiles on screen, so checking each tile's bounding box is impractical.
Also, when you have slopes, not all tiles are boxes.
Technically, in practice they still are handled as such, but the collision response is different.
I agree. Maps, as far as collision is concerned, should ultimately be broken down into boxes/tiles. Each box would have a collision "type". In the instance of a slope, rather than displacing an object to be entirely outside of the box, you could factor in the coordinates within the block to do a partial displacement. A 45 degree slope would be very easy to handle, as point of collision happens when x = y within the tile (depending on the direction of the slope).
Bregalad wrote:Simple object <-> object collision or object <-> BG collision is not too complex to do as long as you only move one pixel at a time (or simulate a faster move by moving one pixel at a time internally).
I have actually set a size/speed limit in my game as a work around. Objects which can collide with one another must not be smaller than the number of pixels they will move per frame (actually, half of that, I believe). Typically, I don't have objects smaller than 8x8 pixels, and I don't have anything moving close to 8 pixels per frame (or even 4, for that matter). This will ensure that objects do not pass through each other and miss collision. This way I don't have to waste time checking for collision multiple times in the same frame, or implement some goofy logic to check for missed collisions.

Post Reply