+Karl G Posted November 18, 2020 Share Posted November 18, 2020 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? 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/ Share on other sites More sharing options...
RevEng Posted November 18, 2020 Share Posted November 18, 2020 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. 3 1 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4679808 Share on other sites More sharing options...
Pat Brady Posted November 18, 2020 Share Posted November 18, 2020 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. 3 1 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4679941 Share on other sites More sharing options...
+Karl G Posted November 18, 2020 Author Share Posted November 18, 2020 Thanks! I plan on posting whatever routine I come up with, which I intend to use with Cosmic Cabbie. 3 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680047 Share on other sites More sharing options...
+Karl G Posted November 19, 2020 Author Share Posted November 19, 2020 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 5 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680610 Share on other sites More sharing options...
RevEng Posted November 19, 2020 Share Posted November 19, 2020 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) 3 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680668 Share on other sites More sharing options...
+Karl G Posted November 19, 2020 Author Share Posted November 19, 2020 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 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680693 Share on other sites More sharing options...
RevEng Posted November 19, 2020 Share Posted November 19, 2020 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 5 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680787 Share on other sites More sharing options...
Pat Brady Posted November 19, 2020 Share Posted November 19, 2020 (edited) 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 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680790 Share on other sites More sharing options...
+Muddyfunster Posted November 20, 2020 Share Posted November 20, 2020 @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! Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680879 Share on other sites More sharing options...
RevEng Posted November 20, 2020 Share Posted November 20, 2020 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. 1 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4680951 Share on other sites More sharing options...
Pat Brady Posted November 20, 2020 Share Posted November 20, 2020 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 3 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681140 Share on other sites More sharing options...
RevEng Posted November 20, 2020 Share Posted November 20, 2020 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. 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681310 Share on other sites More sharing options...
+Karl G Posted November 20, 2020 Author Share Posted November 20, 2020 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! 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681333 Share on other sites More sharing options...
Pat Brady Posted November 20, 2020 Share Posted November 20, 2020 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. 4 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681441 Share on other sites More sharing options...
TwentySixHundred Posted November 21, 2020 Share Posted November 21, 2020 Indeed! Another thanks for sharing and the community working together ? 4 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681834 Share on other sites More sharing options...
Pat Brady Posted November 21, 2020 Share Posted November 21, 2020 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. 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4681836 Share on other sites More sharing options...
SlidellMan Posted November 22, 2020 Share Posted November 22, 2020 Pat, did you write demos some time in the past? Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4682711 Share on other sites More sharing options...
Pat Brady Posted November 22, 2020 Share Posted November 22, 2020 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. 2 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4682745 Share on other sites More sharing options...
Pat Brady Posted November 25, 2020 Share Posted November 25, 2020 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 3 Quote Link to comment https://forums.atariage.com/topic/313689-collisions-with-irregular-tiles/#findComment-4684455 Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.