This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Thinking clearly about collision detection

Thinking clearly about collision detection
by on (#106161)
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?
Re: Thinking clearly about collision detection
by on (#106163)
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! =)
Re: Thinking clearly about collision detection
by on (#106171)
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 :).
Re: Thinking clearly about collision detection
by on (#106176)
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:

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.
Re: Thinking clearly about collision detection
by on (#106180)
That's how you do collision between two objects, but collision between a tile map and an object is the subject here I think.
Re: Thinking clearly about collision detection
by on (#106184)
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.
Re: Thinking clearly about collision detection
by on (#106186)
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.
Re: Thinking clearly about collision detection
by on (#106187)
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.
Re: Thinking clearly about collision detection
by on (#106189)
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.
Re: Thinking clearly about collision detection
by on (#106192)
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).
Re: Thinking clearly about collision detection
by on (#106193)
Rotating levels aren't any harder provided the object and camera positions are stored in "world space", relative to the origin of the map.
Re: Thinking clearly about collision detection
by on (#106251)
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.
Re: Thinking clearly about collision detection
by on (#106254)
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(?)
Re: Thinking clearly about collision detection
by on (#106257)
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".
Re: Thinking clearly about collision detection
by on (#106260)
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.
Re: Thinking clearly about collision detection
by on (#106261)
tepples wrote:
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.

Ok, but individual 16x16 (pixel) boxes(such a coin block) can do the thing I have in mind, too
In this video the guy uses the fact that coin block box pushes the player to the left to bring mario closer to the right part of the screen.
Which shape(0-F) is the one that makes this trick possible? Guess it's....01?
Re: Thinking clearly about collision detection
by on (#106262)
Interesting article on MCKid's development with a section on sloped collision:
http://games.greggman.com/game/programming_m_c__kids/
Re: Thinking clearly about collision detection
by on (#106265)
Quote:
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).

Hehe, it sounds like it would be "collision alasing".
But the problem is that if you want for example an enemy to move 3 pixels in a direction, and that there is a collision, does it means the enemy can't move ? Of course not, because the enemy could possibly move 1 or 2 pixels in the same direction, and if this is possible, you definitely want it to do that.
Because of this, I think the simplest way is to do it one pixel at a time. Of course it's lazy and inefficient, but my game is not a shooter that will requires lots of fast moving bullets at the same time so I don't care.

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

Now that you mention it this is right, you only have to rotate the gravity, and the display. However I still think it is complex to do, and I still show much respect for programmers of SCV4 in this regard.
Re: Thinking clearly about collision detection
by on (#106269)
Super Ghouls 'n Ghosts also has a rotating level... Just the other day I was wondering how I would handle a situation like that.
Re: Thinking clearly about collision detection
by on (#106272)
tokumaru wrote:
Super Ghouls 'n Ghosts also has a rotating level... Just the other day I was wondering how I would handle a situation like that.

You mean handling collisions in a rotating level? I beat the game and I can only remember rotating in Level 4, but it immobilizes the player, so no collisions check are actually needed...
As for me-I would never be able to calculate collisions for rotating level...
Re: Thinking clearly about collision detection
by on (#106328)
Bregalad wrote:
Quote:
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).

Hehe, it sounds like it would be "collision alasing".
But the problem is that if you want for example an enemy to move 3 pixels in a direction, and that there is a collision, does it means the enemy can't move ? Of course not, because the enemy could possibly move 1 or 2 pixels in the same direction, and if this is possible, you definitely want it to do that.
Because of this, I think the simplest way is to do it one pixel at a time. Of course it's lazy and inefficient, but my game is not a shooter that will requires lots of fast moving bullets at the same time so I don't care.


Well, if we're talking object to BG collision, there is a displacement routine that checks how far the bounding box is sticking into the solid wall, and moves them in the opposite direction that many pixels. Depending on the scenario, it might certainly be easier to just not allow them in, in the first place. This can be done by moving them one pixel at a time, like you were saying.

And since my game is a platformer, with upwards of 8 enemies + projectiles on the screen at one time, it can be tricky to manage time, so moving one pixel at a time wouldn't work. But for a static screen game, it would definitely be easier. And there comes a point where if the engine doesn't require increased efficiency, it's ok to be lazy :).

Denine wrote:
tokumaru wrote:
Super Ghouls 'n Ghosts also has a rotating level... Just the other day I was wondering how I would handle a situation like that.

You mean handling collisions in a rotating level? I beat the game and I can only remember rotating in Level 4, but it immobilizes the player, so no collisions check are actually needed...
As for me-I would never be able to calculate collisions for rotating level...


It might actually be easier to see the objects as being rotated in relation to the level. Then again, I've never done collision detection for an object with a rotated bounding box. You might also use a square bounding box that just changes dimensions as the objects rotate, to more appropriately accommodate the object it houses.
Re: Thinking clearly about collision detection
by on (#106329)
Denine wrote:
You mean handling collisions in a rotating level? I beat the game and I can only remember rotating in Level 4, but it immobilizes the player, so no collisions check are actually needed...
As for me-I would never be able to calculate collisions for rotating level...

Pardon me but it sounds like this should have been a joke to code. The hero is immobilized during the rotation, and the rotation only do it 90° at once.

Look what a real rotating level looks like :
http://www.youtube.com/watch?v=EAkSpq0FZJE at 1:35
Then at 3:25 you have 2 layers.

and here too :
http://www.youtube.com/watch?v=jkKDPFUUDHU at 1:05

Now THIS should have been hard to code.
Re: Thinking clearly about collision detection
by on (#106332)
Bregalad wrote:

How is this different from what Super Ghouls 'n Ghosts does? Can you release that switch before the level snaps to a multiple of 90 degrees?

Quote:
Then at 3:25 you have 2 layers.

I don't see anything rotating at 3:25 besides the funky tunnel background.

Quote:

Doesn't seem so hard... there are no walls to collide with, the slope doesn't cause the player to slide down, and the movement is jerky as hell.

For a second I though you were going to point me to a level that worked at odd angles, filled with objects moving around and properly colliding with slopes and walls. That would've been impressive. I really don't see how this stuff in Super Castlevania 4 is way more advanced than what Super Ghouls 'n Ghosts has.
Re: Thinking clearly about collision detection
by on (#106334)
Quote:
How is this different from what Super Ghouls 'n Ghosts does? Can you release that switch before the level snaps to a multiple of 90 degrees?

Yes you can. And the collision detection is not only with walls, but also with spikes. It's true there is no enemies DURING the rotation, but come on. This is still very impressive.

Quote:
I don't see anything rotating at 3:25 besides the funky tunnel background.

Nothing rotating but pehaps if you wait until 3:30 then you will see 2 independents backgrounds, which should have been hard to code for collision detection. You can also die by being crushed between both backgrounds.
Re: Thinking clearly about collision detection
by on (#106335)
The rotating of the level in Super CV4 has very limited collision going on while the level actually rotates. There is the ground plane that you need to escape by whipping the hold. It gradually slopes and I believe eventually you'll slide off and die. Then it rotates once more where again you'll slide off the small platform and fall to your death if you don't whip the hold. There isn't a whole lot going on. I'm not sure how difficult it would be to program something to handle this. You may not need to involve the background map array at all, you could simulate these things were game objects that you don't actually see as sprites. The big swinging things in the later level are just some kind of game object platforms that behave in that swinging pattern probably.

So I'd agree that neither game does anything completely amazing with scaling while actually navigating a level. It's just a visual effect but in practice probably only the minimal amount of effort to compute whatever needs to be done. I think you'd need a coprocessor to calculate everything if the whole level was rotating without some sort of tricks. But then again those tricks are part of the fun of figuring out how to do such effects.

The two backgrounds at the 3:30 mark, the scrolling up part actually might be sprites. The SNES has enough sprites per line to do that. All the pieces moving up could be game objects that it tests collision with.
Re: Thinking clearly about collision detection
by on (#106356)
The part with two background layers was done in some of the castles in Super Mario World. What you need to do for levels like these is run collision against both layers, then make sure the push vectors returned by the algorithm don't point in opposite angles.
Re: Thinking clearly about collision detection
by on (#106365)
Bregalad wrote:
Yes you can.

I'm curious to see what that looks like... is there a video?

Quote:
2 independents backgrounds, which should have been hard to code for collision detection.

My initial though was to just check for collisions against both planes and react as normal. Crushing happens when one layer ejects you into the other.
Re: Thinking clearly about collision detection
by on (#106370)
tokumaru wrote:
How is this different from what Super Ghouls 'n Ghosts does? Can you release that switch before the level snaps to a multiple of 90 degrees?

At 2:17 the level starts rotating while the player is still on the floor, giving away that the game has at least to be able to handle such stuff.

tokumaru wrote:
My initial though was to just check for collisions against both planes and react as normal. Crushing happens when one layer ejects you into the other.

I believe this is exactly what happens in Sonic & Knuckles in Sky Sanctuary (except for the crushing part as maps can't crush you, only objects - that's why there are some invisible solid objects in some areas).
Re: Thinking clearly about collision detection
by on (#106386)
Sik wrote:
tokumaru wrote:
How is this different from what Super Ghouls 'n Ghosts does? Can you release that switch before the level snaps to a multiple of 90 degrees?

At 2:17 the level starts rotating while the player is still on the floor, giving away that the game has at least to be able to handle such stuff.


Another thing that must be tricky is factoring in gravitational effects. If you're standing on the platform as the level rotates, do you end up sliding off? Or do you stay on it until it is completely rotated 90 degrees?
Re: Thinking clearly about collision detection
by on (#106404)
Quote:
I'm curious to see what that looks like... is there a video?

I don't know but honnestly you should just play the game. It's one of the best on the console, and I'm not the only one who is in this opinion. And it's really quite easy, especially at the beginning, so you shouldn't have trouble passing the first 3 levels if you are a platformer veteran.
Re: Thinking clearly about collision detection
by on (#106442)
In my game,,collision detection is OK,,
For the operation of the vram will be difficult
But :

LDA #$20
STA $2006
LDA #$00
STA $2006
LDA #$90
STA $01
LDA #$e0
STA $00
LDY #$00
LDX #$04
loop: LDA ($00),Y
STA $2007
INY
BNE loop
INC $01
DEX
BNE loop

So:The location of the player will be mapped to the $90E0~$XXXX.
In the direction of the player.
For the next tileID judge .
if(tile ID>81){
not modify coordinates;
}else{
modify coordinates;
}
Re: Thinking clearly about collision detection
by on (#106444)
You can't simply "not move" when your objects can move faster than 1 pixel per frame, you want them to get as close as possible to the solid block(s). Another challenge in colliding with the background is knowing WHICH blocks to check.
Re: Thinking clearly about collision detection
by on (#106445)
Quote:
Another challenge in colliding with the background is knowing WHICH blocks to check.

In my game it was a piece of cake, as there is only scrolling or only collision but never both at the same time, so the collision is made with a static map, and also I aligned the bits in the X and Y coordinates so that they would match with the metatile #, this way no additional bit shifts has to be made.
In a previous version I had both X and Y coordinates in 8-bits but it sucked, it wasn't precise and I had problem with things wrapping around the screen. Now it is in 16-bit and it's much cleaner. High 8 bits is metatile #, low 8 bits are 1/256 of a metatile (16x16 metatiles), this means the pixel position is the middle 8 bits.

In the case of a scrolling game it wouldn't be much harder, exept you'd have to decompress and store in RAM 2 (single direction) or 4 (multi-directional) screens at the same time, and select the correct screen. At least that's the approach I'd use.
Re: Thinking clearly about collision detection
by on (#106464)
I actually ended up decompressing a "window" of the level into RAM (2 screens wide; the full screen that the player sees, and 1/2 screen off either direction. Scrolls only horizontally. Decompressed into 2x2 metatiles). So I ended up using 2 pages of RAM, every $10 bytes represented a column of metatiles. The way it was decompressed made it so you could use 9 bits of an object's coordinates in the entire level to calculate where it would be in the rolling window. I think the formula to get the byte of RAM that represents the tile at which an object's coordinates are located was ((ObjectX AND #$01F0)) + (ObjectY / 16) + $300 ($300 and $400 are the two pages used). Takes very little time to get that tile ID. Working through compression on the fly is a nightmare, so the 2 pages of RAM was worth it in my opinion.
Re: Thinking clearly about collision detection
by on (#106467)
Super Mario Bros. uses almost exactly the same sliding window method that you mentioned. But there is a tradeoff if you want to implement both backtracking and destructible environments without paying extra for an extra 8 KiB of PRG RAM.
Re: Thinking clearly about collision detection
by on (#106469)
I can think of a good way to get destructible environments without using that much RAM. Sparse map of 8x8 destroyed region cells, 8 bytes for the destroyed bit for an 8x8 region, and the map is sparse.
Re: Thinking clearly about collision detection
by on (#106470)
Or you could have have 16 or so blocks in the whole level that are destructible and remember those so they can be spaced and used in the level a few places.
Re: Thinking clearly about collision detection
by on (#106471)
3gengames wrote:
Or you could have have 16 or so blocks in the whole level that are destructible and remember those so they can be spaced and used in the level a few places.

16 is negligible, you can easily implement that many as regular game objects, no need for special treatment.

Dwedit's idea makes a lot of sense, specially considering that destructible blocks are commonly used to block passages, so it's natural that they be placed in large chunks of 64 blocks. I believe most people can spare a good number of 8-byte block in RAM, so you can block a lot of passages in one level! You can also limit backtracking halfway through the level with the level's layout, so you can reuse the RAM for more breakable blocks, if you really need that many breakable blocks.

This has nothing to do with collision though.
Re: Thinking clearly about collision detection
by on (#106474)
tepples wrote:
Super Mario Bros. uses almost exactly the same sliding window method that you mentioned. But there is a tradeoff if you want to implement both backtracking and destructible environments without paying extra for an extra 8 KiB of PRG RAM.


Just change out the 2kb RAM in your NES for 8kb, problem solved!

About Super CV4, when the level is rotating, it's not a complicated setup. There is the flat floor that begins rotating. It would be more complicated if the platforms that rotated were not flat. As I suggested with the swinging chandelier, the actual game may just have a hidden object you collide with rather than a tilemap.
Re: Thinking clearly about collision detection
by on (#106499)
Yeah but there is not only the flat floor (which is only flat before the rotation begins) but also a spike wall on the left and another wall on the right. The collision is kept accurate all during the rotation, and the level has been designed so that if you don't grab the thing that stays still, you die crushed on the spikes by gravity.

I think they did that by simply making the gravity rotating, this way it feels like the level is rotating. That's the approach I'd have at least.
Re: Thinking clearly about collision detection
by on (#106575)
tepples wrote:
Super Mario Bros. uses almost exactly the same sliding window method that you mentioned. But there is a tradeoff if you want to implement both backtracking and destructible environments without paying extra for an extra 8 KiB of PRG RAM.


I thought SMB used a method where the entire contents of the buffer were updated to match exactly what the player saw on screen. It was almost as if the bytes "scrolled" in RAM as the player moved throughout the level... Perhaps what I saw was for something else. Perhaps I'm imagining the whole thing... I'll have to check again.
Re: Thinking clearly about collision detection
by on (#106592)
Play SMB1 with a RAM editor pointed at 500, and watch what happens as you scroll or hit blocks. There are two maps, one at 500, and one at 5D0.
Background objects like bushes and clouds don't exist on those maps, they seem to only exist in the nametables.
Re: Thinking clearly about collision detection
by on (#106600)
I seem to remember that right after the table at $5D0, there's another 13-byte array which is the column where the map is actually decoded. Inert background objects, such as clouds and water and the 8-3 wall, aren't copied from the column to the sliding window because their metatile number exceeds the maximum metatile number for each of the four groups ($00-$3F, $40-$7F, $80-$BF, $C0-$FF).
Re: Thinking clearly about collision detection
by on (#106619)
I think the idea was to have those background objects separate from the main layout in the first place. This helps with the variety a bit.