Collisions with Irregular Tiles

[+Karl G]

This is 7800Basic-related, but some of it probably applies generally to 7800 development. Anyway, I get how I can check to see what tile is underneath different points of a sprite to check for a collision, but it gets more complicated when the tile underneath isn't all solid. I was thinking I would solve this by having a table to map tiles to different types (e.g. all empty, all solid, right side solid, diagonal right, etc, etc), but it looks like I would need a lot of different handlers to handle all of the (often literal) corner cases.

 

I'm wondering if there's a more generalized approach I could use, which makes me wonder how graphics are stored in ROM. I'm wondering how feasible it would be to calculate if a certain point within a tile is the background/transparent color (no collision) or another color (collision). Has anyone taken this approach rto collision-detection?

[RevEng]

I don't think it's a particularly common approach, but it's certainly possible. The graphic bytes are stored in reverse-y order in the graphics block, with each line of any particular character's data separated by 256 bytes. So layout would be something like...

 

page 0 of gfx block: [last line of char 0] [last line of char 1] [...] [last line of char 255]

page 1 of gfx block: [2nd last line of char 0][2nd last line of char 1][...]2nd last line of char]

...

 

Decoding the bits from the graphics bytes themselves depends on the mode you're using. 320A:0=background. 160A:00=background (look at bit pairs). The rest get complicated, and you'll need to check out the guide for those.

 

If you're using double-wide and you need to incorporate both consecutive graphics bytes.

 

This kind of stuff is way under the hood with 7800basic, and you'd need to code most of it in assembly language to be reasonably compact.

[+Pat Brady]

Excellent idea!

 

You will need to align the data, both vertically (by selecting the correct page for the object's vertical position, as described by RevEng) and horizontally (by bit-shifting data).

 

Like RevEng said, the B-D modes are more complicated, but mostly not too bad. Here are the pixel numbers for each bit position:

 

160A: 33221100

160B: 1100xxxx

320A: 76543210

320B: 32103210

320C: 3210xxxx

320D: 32103210

 

In case it's not clear, pixel 0 refers to the right side, which is counter-intuitive to me but consistent with the Software Guide.

 

In all cases, 0 in the bit (320A, 320C, 320D) or pair of bits (160A, 160B, 320B) for whichever pixel means that pixel is background or transparent. In 160B and 320C, the bits marked x select a palette and are irrelevant to checking whether a pixel is background or transparent.

 

I am confident about 160A, 320A, 320B, and 320C, less so about 160B and 320D.

 

To check whether a certain pixel is background, mask off all the other bits. For example, to check whether pixel 2 is background in 160A, bitwise-AND the byte with %00110000. Iff the result is 0, then that pixel is background. But for collision detection, you need to compare multiple objects.

 

Comparing in 320A is straightforward, just bitwise-AND the objects' data. Iff the result is non-zero then they collide. In 320C, you can bitwise-AND the data, then bitwise-AND with $F0.

 

For other modes, you probably need a 256-entry table to map each possible graphics byte for one object to a mask for the other object. For example, in 160A, %10001101 means pixel 2 is background and the others are not, so the mask would be %11001111. Then bitwise-AND that mask with the corresponding data byte for the other object, and iff the result is non-zero then they collide.

 

Please let us know how this goes.

[+Karl G]

Thanks! I plan on posting whatever routine I come up with, which I intend to use with Cosmic Cabbie. 

[+Karl G]

Here's a function I wrote that seems to work for 160A. No bit-shifting needed because I only care if the result is 0 or non-zero. I give the character number, and the x and y offset within the current tile.

 

    function EmptyPixel ; character, x, y
    asm
    lda #WZONEHEIGHT
    sec
    sbc temp3 ; y position
    sbc #1
    sta temp4
    lda sCHARBASE
    clc
    adc temp4
    sta CSPtrHi
    lda #0
    sta CSPtrLo
    lda temp2 ; x position
    cmp #4
    bcc ____skip_increment_character ; doublewide
    sbc #4  ; carry already set
    sta temp2 ; x postition of second character
    inc temp1 ; character number
____skip_increment_character
    ldy temp1 ; character number
    lda (CSPtr),y
    ldx temp2
    and color_mask,x
    sta temp4
end
    return temp4
; End EmptyPixel

    data color_mask
    %11000000
    %00110000
    %00001100
    %00000011
end

 

[RevEng]

Your CSPtrHi calculation can be reduced to this...

    lda temp3 ; y position
    eor #WZONEHEIGHT-1 ; A=15-y *or* A=7-y  depending on WZONEHEIGHT
    clc
    adc sCHARBASE
    sta CSPtrHi

...offered with complete humility. Your assembly skills are solid, but most of us have room to learn from each other.

 

I'm not sure how you're prepping the y cooridinate prior to calling the function, but you can just use a raw Y sprite coordinate without prep by just doing an "and #WZONEHEIGHT-1" after the "lda temp3". (assuming the character Y=0 is the same as the sprite Y=0)

 

[+Karl G]

36 minutes ago, RevEng said:

Your CSPtrHi calculation can be reduced to this...

    lda temp3 ; y position
    eor #WZONEHEIGHT-1 ; A=15-y *or* A=7-y  depending on WZONEHEIGHT
    clc
    adc sCHARBASE
    sta CSPtrHi

...offered with complete humility. Your assembly skills are solid, but most of us have room to learn from each other.

 

I'm not sure how you're prepping the y cooridinate prior to calling the function, but you can just use a raw Y sprite coordinate without prep by just doing an "and #WZONEHEIGHT-1" after the "lda temp3". (assuming the character Y=0 is the same as the sprite Y=0)

 

Ahh, that is quite helpful. I was sharing it to help anyone who needed it, but also to get suggestions for improvements like this. I'll be running it 4 times every other frame (opposite of the frames where I do movement/physics), so optimization is a good thing.

 

I was indeed doing an AND to get the remainder this way, but adding that to the function would save code so I don't have to calculate it all 4 times before calling the function. Thanks!

 

Oh, and for completeness in case anyone needs this code, here was how I declared the CSPtr variables:

 

    dim CSPtrLo = r
    dim CSPtrHi = s
    dim CSPtr = CSPtrLo

 

[RevEng]

One more squeeze. Untested, but I believe I haven't broken anything...

   function EmptyPixel ; character, x, y
    asm
    ldy temp1 ; character number
    lda temp3 ; y position
    eor #WZONEHEIGHT-1 ; A=15-y *or* A=7-y  depending on WZONEHEIGHT
    clc
    adc sCHARBASE ; carry stays clear, unless we overflow
    sta CSPtrHi
    lda #0
    sta CSPtrLo
    lax temp2 ; x position
    sbc #3 ; -4 (carry is clear)
    bcc ____skip_increment_character ; doublewide
    tax
    iny ; character number
____skip_increment_character
    lda (CSPtr),y
    and color_mask,x
    sta temp4

end
    return temp4
; End EmptyPixel

    data color_mask
    %11000000
    %00110000
    %00001100
    %00000011
end

 

 

[+Pat Brady]

More micro-optimizations: it's possible I'm missing something, but it seems to me you can move

    lda #0
    sta CSPtrLo

into global initialization code (or omit it altogether if you initialize all memory to 0).

 

And replace

    lda (CSPtr),y

with

    lda CSPtrLo,y

and get rid of CSPtr.

 

EDIT: on second thought, it seems like you need

    lda (CSPtrLo),y

/EDIT

 

EDIT 2: This gets into how 7800basic allocates dims, which I am not familiar with. Regardless, I think you only need 2 bytes to store the address, and the low byte is always 0.

 

In the bigger picture, I think it would be more efficient to check multiple pixels at once. I'll try to work up a routine for that.

 

Edited November 20, 2020 by Pat Brady

[+Muddyfunster]

@Karl G This is a really neat idea thanks for sharing it.

 

I don't understand enough of the assembly to contextualise this in my head yet  

 

Not sure if it would be possible to take this technique and use something similar, for detecting collisions between two irregular sprites, rather than the sprite and the irregular background?

 

Currently I use multiple hitboxes for irregular sprites and I'd expect that's quite slow and a bit inefficient. Sometimes it's a bit of a brute force rather than a finesse approach for me.

 

Coming from the 2600 where we have hardware collision, I don't know a better way than multiple hitboxes right now (or lots of if then statements).

 

Every day is a school day around here, always something new to learn which is great!

 

 

[RevEng]

A pixel perfect check between two sprites, both on arbitrary x and x coordinates, both likely multiple bytes wide, is going to be pretty involved. For sure more involved than a few boxcollisions.

 

[+Pat Brady]

Okay, this caught my interest and I spent a while on it tonight.

 

I worked up a routine that does per-pixel comparison between two objects. I attached it in case anyone is interested. It works on one 1-byte character and one 1-byte sprite, but could probably be modified to work on a 2-byte character, or on 2 sprites. It is totally untested, and I'm not sure it's worth spending any more time on.

 

To use with a sprite that crosses zones, call it twice. To use with wider sprites, call it twice again.

 

Worst-case performance, by my calculation, is about 200 cycles per non-DMA-hole line, 20 cycles per DMA-hole line, plus about 100 cycles of per-call overhead. So if you have 16-line zones, and you call it 4 times (2 zones and 2 bytes wide, with half the lines in DMA holes), it takes about 7500 cycles. That is a big big chunk of SALLY time. I don't know whether it's useful. Adding wide-sprite support within a single call would help. Maybe I'll look into that later. It's still going to be expensive.

 

I reckon calling EmptyPixel with brute force on all those pixels would take somewhere around 10000 cycles in the worst case (40 cycles per call, 16*8=128 calls per object, 2 objects). And that doesn't include the calling loop.

 

But in many cases, you have knowledge about your sprites and how they move. In particular, you might know that a sprite only moved 1 or 2 pixels since the last check, and you might know which pixels along its leading edge are solid. If you exploit that knowledge, you may only need to call EmptyPixel a few times, and you could do pixel-perfect collision detection in maybe 1000 cycles for an arbitrary 16-line sprite. Maybe much less if one of your objects is small and non-animated, like a projectile. This is probably a lot better for most games than any generalized routine.

collision.s

[RevEng]

Excellent work! ?

 

To illustrate the relative cost between bounding box check (ie. boxcollision) and pixel perfect collision detection, a boxcollision check when both objects do overlap (which is worst case) is about 130 cycles. This includes the if...then logic, the parameter setup for the call to the boxcollision subroutine, and a variable-setting in the if...then as a consequence of the detection.

 

Perfection is costly.

[+Karl G]

Impressive indeed. Overkill for my needs, though. also, I didn't think about checking for collisions based on the movement since the last check - I'll have to think about how I could use this to get better results.

 

Anyway, thanks for the information and improvements!

[+Pat Brady]

3 hours ago, RevEng said:

Perfection is costly.

 

Indeed, although I think real games can achieve perfection more affordably than this fully general routine. (And looking back over the code, it can definitely be made faster.)

 

2 hours ago, Karl G said:

Impressive indeed. Overkill for my needs, though. also, I didn't think about checking for collisions based on the movement since the last check - I'll have to think about how I could use this to get better results.

 

Anyway, thanks for the information and improvements!

 

Overkill for your needs, and also for everyone else's. When I started I knew it would be expensive, but I didn't know it would be that expensive.

 

Another thought: many objects are solid, and for most that do have gaps, the gaps don't matter for collision detection. So we could store (or calculate) the boundaries per line, then check collisions on those. I think this would be general but much faster than comparing pixels. I'll take a stab at that tonight.

[+TwentySixHundred]

Indeed! Another thanks for sharing and the community working together ?

[+Pat Brady]

OK, the code I posted earlier had some massive inefficiencies. I think I can get it down to below 3000 cycles for a 16-pixel-tall, 2-byte-wide sprite, regardless of alignment. That's still expensive but possibly usable in some games. I'm ironing out the kinks, but probably finished for the night.

[SlidellMan]

Pat, did you write demos some time in the past?

[+Pat Brady]

25 minutes ago, SlidellMan said:

Pat, did you write demos some time in the past?

 

No.

 

Update: The code I posted recalculated the vertical offset every line and used a very slow shift loop. Better to just decrement addresses and use a lookup table. I have a version that is under 3000 cycles, but think I can get it faster still.

 

[+Pat Brady]

Here is a routine that works on 2 objects of the same size, either both 1 byte or both 2 bytes. It's mostly useful for checking 2 sprites (as opposed to playfield; it does not care what DMA mode is used to draw either object). This turns out to be less processing work, because it only needs to compare 1 sprite to 1 other sprite, whereas checking a sprite against an indirect-mode playfield usually requires comparing the sprite to 2 playfield characters per line, plus logic at the zone crossing.

 

I calculate this takes about 1500 cycles worst case for objects 8 pixels wide and 16 pixels tall.

 

Still totally untested. My next task is to write up a small demo. But I wanted to go ahead and share the code.

collisioncheckeachpixelsprites.s