help with collision detection

[picccca]

Ok, I'm stuck. I can not for anything get my collision detection to work. I have read so many posts on the subject, so I have a clue as to what must be done, but I just can't get it to work.

What I have so far is a background and a moving sprite. This is how I made the background.

I have the background nametable like so:

Code: Select all

background:
      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;;row 1
      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;;

      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;;row 2
      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;;

.
.
.

      .db $1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1  ;;row 29
      .db $1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1,$1  ;; THE FLOOR

      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;;row 30
      .db $0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0,$0  ;

And then it is copied to PPU RAM $2000 like so:

Code: Select all

LoadBackground:
      LDA $2002
      LDA #$20
      STA $2006
      LDA #$00
      STA $2006

      LDA #$00
      STA pointerLo
      LDA #HIGH(background)
      STA pointerHi
      
      LDX #$00
      LDY #$00
BGOutsideLoop:
BGInsideLoop:
      LDA [pointerLo], Y
      STA $2007

      INY
      CPY #$00
      BNE BGInsideLoop
      
      INC pointerHi
      
      INX
      CPX #$04
      BNE BGOutsideLoop

I also have some collision data harcoded to start with:

Code: Select all

CollisionData:
      .db %00000000, %00000000, %00000000, %00000000 ;row1(air)
      .db %00000000, %00000000, %00000000, %00000000 ;row 2(air)
.
.
.
      .db %11111111, %11111111, %11111111, %11111111 ;row29(floor)
      .db %00000000, %00000000, %00000000, %00000000 ; row30(air)

Zeros are air and ones are solids.

Then I have CollisionData copied to RAM like this:

Code: Select all

LoadColData:
      LDA coltab
      STA pointerLo
      LDX #$00
LoadColDataLoop:
      LDA CollisionData, x
      STA pointerLo, x
      INX
      CPX #$78
      BNE LoadColDataLoop

The variable coltab is declared like this:

Code: Select all

coltab  .rs $78 ;  120 bytes, 1 bit per background tile (0 air, 1 solid)

Now for the gravity, I want to look up in the CollisionData table if the tile underneth the sprite is solid or not. I have gotten this far:

Code: Select all

      LDX MarioX        ; Sprite X-pos.
      LDY MarioY        ; Sprite Y-pos.

      ;Calculating Y-tile number
      TYA
      LSR A
      LSR A
      LSR A  ; divide by 8
      INC A
      INC A  ; add 2 rows, to get under the sprite

      ;Calculating X-tile number
      TXA
      LSR A
      LSR A
      LSR A   ; divide by 8

So far I think is correct, but what comes after that. First I had some idea to calculate what adress the tile below the sprite is at, like this:
$2000 + (32*SpriteY) + 32 + SpriteX
But it seams like I then would need to calculate som 16bit numbers or something.

So the question is basically what do I do next.

[Bregalad]

What you need to do for doing sprite -> BG collision, is to compute a set of points arround the sprite (typically the 4 corners), and have a routine that compute their equivalent position on the background map (typically it is just shifting a value right, dropping the low bits - depending on which meta-tile size you use for collision, and how many bits you use to position your sprite).

If all points are "false" collision then your sprite is free to move, but if any point becomes "true", you can't have it moving.

Of course you can improve it at a later stage to support for more stuff (this method of 4 points won't work well for very large sprites, for instance, as some part of solid BG could "slip" between the point), but this should at least get you started.

[picccca]

What you need to do for doing sprite -> BG collision, is to compute a set of points arround the sprite (typically the 4 corners), and have a routine that compute their equivalent position on the background map (typically it is just shifting a value right, dropping the low bits - depending on which meta-tile size you use for collision, and how many bits you use to position your sprite).

I have already managed to calculated the corners of the character simply by adding some pixels:
- Upper right corner X = sprite_X + 16pixels
- Upper right corner Y = sprite_Y
and so on.

I don't really know what meta-tile size is or which size I use for the collision. Maybe this is the true source of the problem, I don't know.

I use two bytes to store the sprites position, one for X-position and one for Y-position.

If all points are "false" collision then your sprite is free to move, but if any point becomes "true", you can't have it moving.

Ok, I think I get this point. I need to check if the corners overlap the solid tiles of the background.

Of course you can improve it at a later stage to support for more stuff (this method of 4 points won't work well for very large sprites, for instance, as some part of solid BG could "slip" between the point), but this should at least get you started.

I implemented gravity, then obviously the main character went trough the floor as collision with the floor isn't implemented. But after this is done I think it is quite easy to test collision with other things also.

But can you please explain "meta-tile size".

[tepples]

Notice that all objects in Super Mario Bros. are 16x16 pixels, made of a 2x2 block of 8x8 pixel tiles. These blocks are metatiles. Have a look through the nesdev.com glossary.

[tokumaru]

I don't really know what meta-tile size is or which size I use for the collision.

Metatiles are groups of tiles that you use to build the levels. NES games typically use a metatile size of 2x2 tiles, because that's the area covered by each entry in the attribute table, but 4x4 is also very common. This is actually a form of compression, since a whole screen can be defined in just 240 bytes if you are using 2x2 metatiles, while 1024 are needed if you are just using raw name/attribute table data.

You don't need metatiles to implement collision detection though, that's optional. If the large size of raw screens is not a problem for you, there's no need to overcomplicate things. You just have to keep in mind that the blocks that form your level are 8x8 pixels (the size of a NES tile).

Now, collision detection with the background works like this: You first move the character/object in the direction he's supposed to go, then you check if this movement caused it to enter any blocks it shouldn't have, if so, you eject it back.

If the character moved right, you need to calculate its top-right and bottom-right points, then translate those to coordinates inside your collision map, and finally scan all the blocks from the top one to the bottom one. If any of those is solid, you eject the character to the left.

Note that if the character moved right, there is no need to check its left side, because there is no possible way for it to collide in that direction, so don't do any unnecessary calculations. The same thing is true when moving up or down.

Also, test for collisions in each axis separately. Move horizontally, check for horizontal collisions and eject horizontally; then move vertically, check for vertical collisions and eject vertically. If you don't, your character might end up going through corners and other nasty stuff.

[picccca]

Metatiles are groups of tiles that you use to build the levels. NES games typically use a metatile size of 2x2 tiles, because that's the area covered by each entry in the attribute table, but 4x4 is also very common. This is actually a form of compression, since a whole screen can be defined in just 240 bytes if you are using 2x2 metatiles, while 1024 are needed if you are just using raw name/attribute table data.

Let's see if I get this, so if I use 2x2 metatile size. The background data will only consist of 16x15 bytes instead of 32bytes per row and 30 rows. Then the part of the code that copies this background data to the PPU RAM need to add the rest of the tiles.

Now, collision detection with the background works like this: You first move the character/object in the direction he's supposed to go, then you check if this movement caused it to enter any blocks it shouldn't have, if so, you eject it back.

Is this done before NMI interrupt, I guess it is. I actually have all my code within the NMI ruotine now, I don't think that's the way to do it. Should I do almost everything before VBlank (NMI) starts?

If the character moved right, you need to calculate its top-right and bottom-right points, then translate those to coordinates inside your collision map, and finally scan all the blocks from the top one to the bottom one. If any of those is solid, you eject the character to the left.

The problem that I have been having is translating the coordinates of the sprite into the collision map. But if I have 2x2 metatile size I think it's easier. Just to confirm, is the idea to calculate a byte offset and add that offset to the adress of the first byte in the collision map, then check if this byte represent solid tile? if so is it not possible without using 2x2 metatile size, becouse of the byte offset calculated being greater then what a 8bit register can hold? Maybe I just see the easy way of doing this.

However, I need to clean up my code first, move stuff away from the NMI routine, then I will try to implement the 2x2 metatile size, and then the collision dettection.

BTW, Thanks for the help so far.

[tokumaru]

Let's see if I get this, so if I use 2x2 metatile size. The background data will only consist of 16x15 bytes instead of 32bytes per row and 30 rows. Then the part of the code that copies this background data to the PPU RAM need to add the rest of the tiles.

That's correct. Copying the data to PPU RAM becomes more indirect, because you'll need to load a byte from the map and use that byte as an index to read the tiles from the metatile definitions, which you'll then write to VRAM.

Is this done before NMI interrupt, I guess it is. I actually have all my code within the NMI ruotine now, I don't think that's the way to do it. Should I do almost everything before VBlank (NMI) starts?

Yes, you should do all the game logic beforehand and make sure that only actual PPU updates are performed during VBlank. You can still have everything in the NMI, but do the PPU updates first (to make sure they happen during VBlank), and then process the game logic for the next frame.

Having the game logic outside of the NMI and graphical updates in the NMI will result in a more robust program structure though, so if you are up to it, I recommend it.

Just to confirm, is the idea to calculate a byte offset and add that offset to the adress of the first byte in the collision map, then check if this byte represent solid tile?

Yeah, but since you are using bits to represent the solidity of each tile, just checking bytes won't do, you'll have to use masks in order to check the individual bits.

if so is it not possible without using 2x2 metatile size, becouse of the byte offset calculated being greater then what a 8bit register can hold?

You can access arrays with more than 256 entries if you use pointers, but that's not really necessary in your case because you are using bits for the solidity, so you really only have (32 * 30) / 8 = 120 bytes for the collision data.

You just have to find the formula to convert the sprite coordinates to collision map coordinates. The sprite coordinates are measured in pixels, while the collision coordinates are measured in 8x8-pixel tiles (unless you decide to use metatiles, but since this is not the case yet I'll stick to the tiles), so you discard the lower 3 bits of the coordinates (just shift the numbers right 3 times). These 3 bits indicate where in the tile your point of interest is, but that info is meaningless because you are not doing pixel collision, just tile collision.

So now you have 2 5-bit values. The Y value indicates the row (0 to 31), and if you pay attention to your collision data you'll see that there are 4 bytes per row, so you multiply the Y coordinate by 4 (shift it left twice) to locate the start of the row you want. Now X. There are 4 bytes in a row, and each byte has 8 bits. Use the top 2 bits (a value between 0 and 3) of the 5-bit X coordinate to find which byte, and the lower 3 (a value between 0 and 7) to find the bit.

So, to find the byte you use: (Y / 8) * 4 + (X / 64)

And to find the bit you use: (X / 8) AND 7

I'm sure you know how to read the byte, but maybe I need to elaborate on the bit. you will probably need a table like this:

Code: Select all

BitMasks:
	.db %10000000
	.db %01000000
	.db %00100000
	.db %00010000
	.db %00001000
	.db %00000100
	.db %00000010
	.db %00000001

So, once you have calculated the index of the bit you need, you use that index to load a value from this table. Then you can AND it with the byte read from the collision map, and if the result is 0, the tile is air, otherwise it's solid.

[MetalSlime]

trust everything that tokumaru says, but I'll add my 2 cents.

Let's see if I get this, so if I use 2x2 metatile size. The background data will only consist of 16x15 bytes instead of 32bytes per row and 30 rows. Then the part of the code that copies this background data to the PPU RAM need to add the rest of the tiles.

Yes. 2x2 metatiles (16x16 pixels) are Mario block size. 4x4 (32x32 pixels) is also common.

Is this done before NMI interrupt, I guess it is. I actually have all my code within the NMI ruotine now, I don't think that's the way to do it. Should I do almost everything before VBlank (NMI) starts?

It's good practice to do all game logic outside of NMI and save NMI for graphics updates. See Disch's NMI guide to learn how to set this up.

If the character moved right, you need to calculate its top-right and bottom-right points, then translate those to coordinates inside your collision map, and finally scan all the blocks from the top one to the bottom one. If any of those is solid, you eject the character to the left.

The problem that I have been having is translating the coordinates of the sprite into the collision map. But if I have 2x2 metatile size I think it's easier. Just to confirm, is the idea to calculate a byte offset and add that offset to the adress of the first byte in the collision map, then check if this byte represent solid tile? if so is it not possible without using 2x2 metatile size, becouse of the byte offset calculated being greater then what a 8bit register can hold? Maybe I just see the easy way of doing this.

However, I need to clean up my code first, move stuff away from the NMI routine, then I will try to implement the 2x2 metatile size, and then the collision dettection.

BTW, Thanks for the help so far.

I wrote a post about sprite->bg collision detection on my nesdev blog back when I was dealing with the same problem. My post is specific to my game (which uses 16x16 metatiles), but you might pick something up from it: sprite collision

My approach was to check for a collision first and then not move if there was a collision, rather than move first and eject upon collision. Tokumaru is more knowledgable than I am in nesdev, so his method is likely better than mine, but give my post a read and see if it helps.

[tokumaru]

My approach was to check for a collision first and then not move if there was a collision, rather than move first and eject upon collision. Tokumaru is more knowledgable than I am in nesdev, so his method is likely better than mine, but give my post a read and see if it helps.

The reason I think the approach I described is better is because it requires less computation. For example, when you move horizontally, most of the time the movement is allowed, and very few times there will be walls to stop you, so it seems like a good idea to assume the movement is allowed.

Another problem is that when a movement is not allowed, you can't just "not move", you still have to move as close to the solid obstacle as possible. For example, say that the character is moving at a speed of 4 pixels per frame and there is a wall 3 pixels ahead. If you detect that the point 4 pixels ahead is inside a wall and just don't move at all, your character will stop even though it's still 3 pixels away from the wall. So you still must move it those 3 pixels so that it touches the wall.

Either way should work though, so do whatever you think is easier. I just happen to think that assuming that movements are always possible (and correcting the few cases when they are not) is slightly easier on the CPU, but aside from that I don't think there are many differences between both approaches.

[cartlemmy]

Another problem is that when a movement is not allowed, you can't just "not move", you still have to move as close to the solid obstacle as possible. For example, say that the character is moving at a speed of 4 pixels per frame and there is a wall 3 pixels ahead. If you detect that the point 4 pixels ahead is inside a wall and just don't move at all, your character will stop even though it's still 3 pixels away from the wall. So you still must move it those 3 pixels so that it touches the wall..

I think this is a really good point, when you have a finite time step (in this case 1/60th of a second) it is better to "move back in time", than to "look forward in time".

I've been implementing collision detection over the last week, and I feel your pain. This stuff is hard Especially when you try to do slopes as well.

[tokumaru]

This stuff is hard Especially when you try to do slopes as well.

Yeah, things get much more complex when you throw slopes in. We've had a pretty interesting conversation about slopes a while back, if anyone is interested.

[picccca]

I finally got collision detection working now, thanks alot. I see now that I was in fact not far from the solution, but I wouldn't have made it without the help given to me here.

I will now try to use metatiles 2x2 for the background. Let's see how far I will come on that.

Yeah, things get much more complex when you throw slopes in.

As this is my first program for the NES, I think I will not make the collisions much more complex.

[cartlemmy]

Yeah, things get much more complex when you throw slopes in.

As this is my first program for the NES, I think I will not make the collisions much more complex.

Hehe, sorry I wasn't meaning that you should do slopes. I just said that because that is what I am doing