This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

How to do Bounding Boxes on assembly?

How to do Bounding Boxes on assembly?
by on (#131592)
Hi! I'm new on this NES Development stuff. I have already learned a lot of things and i'm on a part that i need to do background and sprite collision, but, i don't know how to do it and neither the code. I read somewhere that you need to do Bounding Boxes. I know what is this, but i do not know the code, somebody please tell me! I would be very happy :D .
Re: How to do Bouncing Boxes on assembly?
by on (#131594)
I think it's "bounding" not "bouncing". Have you implemented bounding boxes in another language?
Re: How to do Bouncing Boxes on assembly?
by on (#131595)
tepples wrote:
I think it's "bounding" not "bouncing". Have you implemented bounding boxes in another language?


I didn't have checked it when I wrote it, thanks for pointing it out, i will fix it. :D

Anyway, no, i didn't do it before in any language, i am starting to get into video game development.
Re: How to do Bounding Boxes on assembly?
by on (#131596)
The short way to describe it is using greater-than and less-than checks. Which is done by a CMP instruction followed by BCC or BCS. Some assemblers give those instructions alternate names, BLT and BGT respectively, to make it easier to remember.

So your 2 objects, you have X,Y coordinates which represent the upper-left pixel. You'd compare the X coordinates of both objects, continue if obj1 X is greater than obj2 X. Take obj2 X, and add a number to it, this is the horizontal size of the box in pixels. If obj1 X is less than the new obj2 X, it's in the X coordinate of the box. Then follow the same process for the Y coordinate.

I could dig out a code example, if it would help.

edit: note that example is a little simplified, in that the size of obj1 is just one pixel, and only obj2 has a box. Making a box for obj1 is a similar process of comparing, adding the box size, comparing again.
Re: How to do Bounding Boxes on assembly?
by on (#131597)
Memblers wrote:
I could dig out a code example, if it would help.


I think that it would help, because i can't think of a way to do that on assembler (because i am a newbie)
Re: How to do Bounding Boxes on assembly?
by on (#131599)
Every object must have a position and dimensions. With that information you should be able to calculate the four edges (top, bottom, left and right) of an object.

Coordinates usually indicate the top left corner of pictures, and in that case you already know the top and left edges (they're the Y and X coordinates, respectively). To calculate bottom and left all you have to do is Y + Height and X + Width, respectively. An object's coordinates don't have to be at its top left corner though, I for example like coordinates to be the middle bottom of my sprites, so I can quickly use them for collisions with the ground, but that's my choice. Just keep in mind that this affects how you calculate the edges of the bounding boxes.

Once you have the 4 edges it's just a matter of comparing them to exclude collisions. For example, if the right edge of object A is less than the left edge of object B, they can't possibly be colliding because object B is entirely to the right of object A. If after 4 comparisons you haven't excluded the collision, you can know for sure that the objects are colliding.
Re: How to do Bounding Boxes on assembly?
by on (#131607)
Hopefully this code makes some sense. They're surely not the best examples..

In both examples, $200-$2FF is a copy of sprite memory. First one is from Munchie Attack, sprite at $204 is the player and sprites at $240 and up are the food objects. The second one is from Roadkill (not released, a rip-off of the David Crane's game Freeway). It compares an 8x8 player to individual 8x8 sprites instead of actual objects. In both of these, the values added and subtracted are pretty specific to the object sizes in the games. So it might not seem intuitive, at least it didn't to me when I was writing it, it took a little experimentation.

In both cases, a successful hit detect means the code makes to the end of the routine.

Code:
hit_detection:
        ldx #0
@hitloop:
        lda $241,x
        sta tiletype
        bne :+
        jmp @itsblank
:
        lda $243,x
        sec
        sbc #8
        cmp $207
        bcc :+
        jmp @itsblank
:
        clc
        adc #24
        cmp $207
        bcs :+
        jmp @itsblank
:

        lda $240,x
        sec
        sbc #15
        cmp $204
        bcc :+
        jmp @itsblank
:
        clc
        adc #30
        cmp $204
        bcs :+
        jmp @itsblank
:

        lda #0
        sta $241,x
        sta $245,x
        sta $249,x
        sta $24D,x


Code:
;----------------------------------------------------------
;                    Detect Hits
;----------------------------------------------------------
hit_detect:             ; detect vertical hits first

        ldy #0
        ldx #$0C

@check_next_v:
        lda $201,x              ; check to see if sprite tile is 0
        beq @skip_one           ; if it is, do not check

        lda $200,x
        sec
        sbc #8
        sta temp

        lda $208                ; load Y value of player
        cmp temp
        bcc @skip_one
        lda $200,x
        clc
        adc #8
        sta temp
        lda $208
        cmp temp
        bcc @hit1

@skip_one:

        txa
        clc
        adc #24
        tax

        cpx #$84
        bcc @check_next_v

        rts


@hit1:                       ; a V hit as occured, check H position

@check_next_h:
        lda $201,x
        beq @skip_2

        lda $203,x
        sec
        sbc #8
        sta temp

        lda $20B
        cmp temp
        bcc @skip_2
        lda $203,x
        clc
        adc #8
        sta temp
        lda $20B
        cmp temp
        bcc @do_hit1


@skip_2:
        inx
        inx
        inx
        inx
        bne @check_next_v

        rts

@do_hit1:
   lda #196
        sta $208
        lda #18
   sta p1wait
        rts

Re: How to do Bounding Boxes on assembly?
by on (#131612)
This is my generic collision test routine I used in DABG and Sliding Blaster that return whether or not a collision occured in carry (for ca65, but easily adaptable to other things):

Code:
.macro swapa mema, memb
  lda mema
  pha
  lda memb
  sta mema
  pla
  sta memb
.endmacro

.proc ChkTouchGeneric
  jsr TryCollide
  swapa TouchLeftA,   TouchLeftB
  swapa TouchTopA,    TouchTopB
  swapa TouchWidthA,  TouchWidthB
  swapa TouchHeightA, TouchHeightB
  jsr TryCollide
  clc ; no collision
  rts
TryCollide:
  lda TouchLeftB
  clc
  adc TouchWidthB
  sta TouchRight
  lda TouchTopB
  clc
  adc TouchHeightB
  sta TouchBottom

  lda TouchLeftA
  cmp TouchLeftB
  bcc No

  lda TouchLeftA
  cmp TouchRight
  bcs No

  lda TouchTopA
  cmp TouchTopB
  bcc No

  lda TouchTopA
  cmp TouchBottom
  bcs No
  pla ; pop the return address from either JSR off the stack
  pla
  sec ; collision detected
No:
  rts
.endproc
Re: How to do Bounding Boxes on assembly?
by on (#131617)
So i think i get it, but i will test later, because i need to do Background collision,
So, with background objects like the the blocks in Super Mario Bros., how did they made to define which object you can pass through and which one not?
Re: How to do Bounding Boxes on assembly?
by on (#131619)
Sample the background map at the four corners of the object and do bounding box on each sample that returns solid. Then you can calculate wall response.
Re: How to do Bounding Boxes on assembly?
by on (#131620)
I don't know about SMB's background collision, but this might get you on the right track:

When it's a regular grid, you no longer need to think about individual bounding boxes. Think of how many tiles are on a screen; you don't want to be testing 100 bounding boxes! If it's a grid of 16x16 pixel blocks, you can find the grid coordinates of an X/Y pixel location by dividing by 16.

So, you have a screen that is 16 blocks wide, 15 blocks tall. If you used 1 byte per block, you'd need 240 bytes for the screen. Looking up a collision value would be something like this in C:
Code:
grid_coord = (x >> 4) | (y & 0xF0); // note: (y & 0xF0) == (y >> 4) << 4
return collide[grid_coord];

When you move your character, you can test a couple of pixel locations along the edge of the character to check for collision with the world.

I'll leave you to figure out how this would translate to assembly. If you want to get more complicated, you could test your player character's bounding box against the grid. You can also store collision data more compactly (you may only need 1 bit per tile, so this screen could be 30 bytes if you have cycles to spare unpacking bits).
Re: How to do Bounding Boxes on assembly?
by on (#131621)
So, every single game did it different? Games with overhead perspective has a different way to do it differently than sidescrollers? if so i think i gave a bad example there, i´m doing a game with overhead perspective.
Re: How to do Bounding Boxes on assembly?
by on (#131622)
Checking collision with the background is pretty much the same between platformers and overhead view games, just what you actually do in response to a collision to prevent the player from going through would be different. In a platformer when you hit an object from below you would want to stop the player's jump, and from above you might want to adjust the player's Y position to make sure they're standing on whatever they landed on, but an overhead view game in all directions and when moving horizontally in a platformer you would want to adjust the player's position so they're as close as they can get without overlapping with the tile (or simply not move).
Re: How to do Bounding Boxes on assembly?
by on (#131649)
I always subtract x2 from x1, compare the result with w2, add w1 and check if the result is positive. Then I do the same for the y-axis.
Re: How to do Bounding Boxes on assembly?
by on (#131657)
psycopathicteen wrote:
I always subtract x2 from x1, compare the result with w2, add w1 and check if the result is positive. Then I do the same for the y-axis.


Care to explain a little further?



Sik, IIRC, had one that I hadn't seen before; for object to object collision detection (he used it on 68k code because the ISA gave it a speed up over traditional compare list). But, I don't remember what it was at the moment :B
Re: How to do Bounding Boxes on assembly?
by on (#131662)
If it helps, here's my bounding box collision with the player for the game I'm working on.

You load the temp variables x0,y0,x1,y1 with the bounding box to test against the player, and this function returns 0/1 in A (and also Z flag), without modifying any registers/variables except A/flags.

Code:
; clobbers A, flags
player_overlap:
   lda player_x1
   cmp x0
   bcc @no_overlap
   lda player_y1
   cmp y0
   bcc @no_overlap
   lda x1
   cmp player_x0
   bcc @no_overlap
   lda y1
   cmp player_y0
   bcc @no_overlap
@overlap:
   lda #1
   rts
@no_overlap:
   lda #0
   rts


The boxes include the row/column at x1/y1, this is intentional so that x1=255 can cover right to the edge of the screen. So, an 8x16 box test might look like:

Code:
   lda thing_x
   sta x0
   clc
   adc #7
   sta x1
   lda thing_y
   sta y0
   clc
   adc #15
   sta y1
   jsr player_overlap
   beq @no_hit


It is the following conditions, any of which results in no overlap:
  • player_x1 < x0
  • player_y1 < y0
  • x1 < player_x0
  • y1 < player_y0