Background Collision Detection

Background Collision Detection
by Link on 2004-11-22 (#238)

This has totally thrown me off. I have no idea where to start.

Do I read the nametable thru $2006/7 and put that in accordance to where my sprite is (would I use some kind of formula or lookup table to find that?)?

All I'm asking now is for just a 1 screen name table collision detection. I would have no idea how to set that up when putting scrolling into account. So for now I'll jut start with reading a single nametable and detecting which tile the sprite is on and such. thx :-)

by Memblers on 2004-11-23 (#252)

I suppose you could read the data through $2006/$2007, but that'd need to be done during vblank, when time really valuable. (imagine then if you need to do collision checking for several projectiles against the background).

What I've always planned on doing is using the map data stored in the CPU's ROM/RAM for the collision detection. Preferably, it'd be much smaller than an uncompressed 1024 byte nametable.

Re: Background Collision Detection
by doynax on 2004-11-24 (#281)

Personally I'm allocating a 120-byte bitmap with each bit corresponding to a single tile in the name tables. This approach doesn't allow for any special tile types, only solid or not.

Another option is to use a system of 2x2 pseudo-tiles and use a whole byte for each of them. This will cost you 240-bytes instead but allows for a much more interesting collision system.

You could also access the map data directly in ROM, but that would make level compressions impossible.

None of these methods can handle permanent dynamic backgrounds by themselves, these are application specific and require all sorts of nasty hacks to save memory.

Bit detection
by Link on 2004-11-27 (#347)

Using a 120-byte array. How would you detect each of the bits. With a routine that checks the bits of a byte or something.

Re: Bit detection
by doynax on 2004-11-27 (#348)

Link wrote:
Using a 120-byte array. How would you detect each of the bits. With a routine that checks the bits of a byte or something.

Precisely. Here's some code to get to rolling (okay, I'm bored..).

Code:
;; this is the 120 byte array with a single bit per tile
;; 32 bits (4 bytes) columns x 30 rows
coltab = $300

;; lookup the bit in the collision array
;; input: (x, y) = coords
;; output: zero flag set on collision
checkbit:
;; calculate x byte index
txa
lsr
lsr
lsr
sta tmp

;; calculate y byte index
tya
asl
asl

;; get the final table pointer
adc tmp ;; no need to clear carry since y won't overflow
tay

;; lookup x bit pattern
txa
and #7
tax
lda bittab,x

;; check it
bit coltab,y
rts

;; a table of bit patterns
bittab .byte $01,$02,$04,$08,$10,$20,$40,$80

I know it could've been a lot faster with some more tables and one of those neat x-masking invalid opcodes. But it's supposed to be pedagogical, not an example of production code.

by Drag on 2004-11-28 (#352)

How does spelunker do it? Spelunker seems to have pixel-precise bg detection. You bump up and down with the ridges in the ground!

I don't know how useful this idea would be, but if all of your tiles are going to have 'flat' slopes (slope is constant throughout the tile), you could program a simple Y=mX+b type thing for 16x16 metatiles (correct term?).

by Memblers on 2004-11-28 (#353)

Drag wrote:
How does spelunker do it? Spelunker seems to have pixel-precise bg detection. You bump up and down with the ridges in the ground!

What I planned on doing was having a seperate table of the pixel offsets within each metatile (if it's not solid or empty). Then convert that position to screen pixels and see if it's in range of some parts of the sprite.

by tepples on 2004-11-28 (#354)

Sonic the Hedgehog 2 does sprite-BG collision the way Memblers described.
http://homepages.ihug.com.au/%7Enemesis ... #collision

by Link on 2004-12-02 (#409)

How would I match up the tiles with the sprite coordinates? For now my sprite is 16x16 as are my tiles (to match up with attributes).

Now I'm guessing that'd I'd want the sprite control routine to move the sprite 16 pixels at a time so that its proportional to the 16x16 tiles on the screen?

For the collision I'm going to use 234 bytes RAM to copy the Nametable in 16x16 metatiles. I guess I'd need some kind of formula to figure the byte of RAM is in accordance to what tile on the screen (y * 16 + x) and then have the sprites corrdinates range from x(0-15) and y(0-14).

I sorta want to move the sprite pixel by pixel right now, but if it'd be too hard for collision detection I can change it to moving in 16 pixel increments.

So would I use some kind of formula or lookup table to match them up if I wanted to do pixel by pixel sprite walking collision detection (not pixel by pixel collision detection, I want the sprite to walk pixel by pixel and the collision detction to be 16 by 16 pixels......understand what I mean?) ?

And one last thing, when I finally put my scrolling engine into this.....is it going to get a lot harder (I would prolly have to change the RAM usage around unless I used 1-screen mirroring huh?)?

Thanks for your help.

by doynax on 2004-12-02 (#411)

Link wrote:
How would I match up the tiles with the sprite coordinates? For now my sprite is 16x16 as are my tiles (to match up with attributes).

All you have to do is take the sprite's hotspot (probably at the feet) and divide it's coordinates by 16 when checking the collision array. There's really no need to restrict yourself to per-tile movement (which would look truly horrible in most games).

Link wrote:
And one last thing, when I finally put my scrolling engine into this.....is it going to get a lot harder (I would prolly have to change the RAM usage around unless I used 1-screen mirroring huh?)?

Why not treat the collision array as if it's using 1-screen mirroring regardless of what you're actually using?

Code:
;; the 16x15 (240) byte collision array
coltab = $300

;; input: x = sprite x-coord in pixels, y = sprite y-coord in pixels
;; output: a = collision byte
lookup:
;; divide x-coord by 16 to get the horizontal tile index
txa
lsr
lsr
lsr
lsr
sta tmp

;; divide y-coord by 16 to get it's tile index and multiply it by 16 again for the collision table lookup
;; (x >> 4) + (y >> 4) << 4 = (x >> 4) + (y & 0xf0)
tya
and #$f0

;; combine x and y coords into a byte offset
clc
adc tmp
tax

;; lookup the byte and return it
lda coltab,x
rts

Finally...
by Link on 2004-12-29 (#780)

I put off doing this for awhile, but now I've implemented it. Thanks, the code helped a lot. The next thing though is doing this in correspondence with my scrolling routine. That means I have to update the whole 240 bytes every time the game scrolls 8-pixels eithre way right? Is there a better way to do this?

Re: Finally...
by Guest on 2004-12-29 (#784)

Link wrote:
I put off doing this for awhile, but now I've implemented it. Thanks, the code helped a lot. The next thing though is doing this in correspondence with my scrolling routine. That means I have to update the whole 240 bytes every time the game scrolls 8-pixels eithre way right? Is there a better way to do this?

Fortunately, there's no need to do so.
Instead you can treat things like a circular buffer, just like you would do tilemap scrolling. Admittedly it's somewhat favorable to wrap directly to a new line instead of the beggining of the current one, like the video hardware would.

Lets say you've got a small 3x3 (meta-)tile screen in it's initial (unscrolled state):
0 1 2
3 4 5
6 7 8

Instead of the whole 16-byte buffer when scrolling to the buffer left by one tile we simply replace to column that's been scrolled out:
1 2 3
4 5 6
7 8 a

And to scroll down we repeat the procedure but offset the buffer by a whole line instead of a single tile.
4 5 6
7 8 9
a b c

To avoid growing this buffer to infinity you can simply clip the index to a single byte (which is the fastest way to do things anyway). On a normal screen with a status bar and an extra tile row for each axis (for scrolling) this should still fit in a single 256-byte page.

In your collision lookup code you only have to keep track of the current scrolling offset, calculated through scroll_x+scroll_y*16, and add it to the lookup address.

Here's an updated version of my previous code:
Code:
;; the 16x15 byte collision array, occupies a full 256-byte page for natural wrapping
coltab = $300

;; the collision scroll offset, increase this by 1 to scroll left and by 16 to scroll up. this is also used as a starting point when updating the table during
colscroll = $400

;; input: x = sprite x-coord in pixels, y = sprite y-coord in pixels
;; output: a = collision byte
lookup:
;; divide x-coord by 16 to get the horizontal tile index
txa
lsr
lsr
lsr
lsr
sta tmp

;; divide y-coord by 16 to get it's tile index and multiply it by 16 again for the collision table lookup
;; (x >> 4) + (y >> 4) << 4 = (x >> 4) + (y & 0xf0)
tya
and #$f0

;; combine x and y coords into a byte offset
clc
adc tmp

;; compensate for scrolling by adding the current offset
adc colscroll
tax

;; lookup the byte and return it
lda coltab,x
rts

Re: Finally...
by doynax on 2004-12-29 (#785)

The previous "Guest" post is mine. Just reinstalled the browser (go firefox), that should teach me not to trust auto login..
Now I can't even perform my traditional 103 edits to correct all the spelling and/or factual errors. Damn..

by RoboNes on 2004-12-30 (#787)

it works as long as clicked the always log on bit and don't delete the browsers cookies

by doynax on 2004-12-30 (#789)

RoboNes wrote:
it works as long as clicked the always log on bit and don't delete the browsers cookies

Uhm.. Yeah, it's just that reinstalling the browser tends to remove your cookies.

Thank You!
by Link on 2004-12-31 (#797)

You've really helped me a lot thanks All of this has really helped, I think I should be able to finish the beta version soon...