Background Collision Detection

Are you new to 6502, NES, or even programming in general? Post any of your questions here. Remember - the only dumb question is the question that remains unasked.

Moderator: Moderators

Link

Background Collision Detection

Post by Link »

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 :-)
User avatar
Memblers
Site Admin
Posts: 4044
Joined: Mon Sep 20, 2004 6:04 am
Location: Indianapolis
Contact:

Post by Memblers »

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.
doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Re: Background Collision Detection

Post by doynax »

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.
Link

Bit detection

Post by Link »

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.
doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Re: Bit detection

Post by doynax »

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: Select all

;; 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.
Drag
Posts: 1615
Joined: Mon Sep 27, 2004 2:57 pm
Contact:

Post by Drag »

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

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?).
User avatar
Memblers
Site Admin
Posts: 4044
Joined: Mon Sep 20, 2004 6:04 am
Location: Indianapolis
Contact:

Post by Memblers »

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! :P
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.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples »

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

Post by Link »

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.
doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Post by doynax »

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: Select all

;; 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
Link

Finally...

Post by Link »

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?
Guest

Re: Finally...

Post by Guest »

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: Select all

;; 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
doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Re: Finally...

Post by doynax »

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..
RoboNes
Posts: 48
Joined: Mon Sep 20, 2004 6:47 am

Post by RoboNes »

it works as long as clicked the always log on bit and don't delete the browsers cookies
doynax
Posts: 162
Joined: Mon Nov 22, 2004 3:24 pm
Location: Sweden
Contact:

Post by doynax »

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.
Post Reply