How to do Bounding Boxes on assembly?

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

AleksMTE
Posts: 5
Joined: Sat Jul 26, 2014 5:22 pm

How to do Bounding Boxes on assembly?

Post by AleksMTE »

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 .
Last edited by AleksMTE on Sat Jul 26, 2014 6:14 pm, edited 1 time in total.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Re: How to do Bouncing Boxes on assembly?

Post by tepples »

I think it's "bounding" not "bouncing". Have you implemented bounding boxes in another language?
AleksMTE
Posts: 5
Joined: Sat Jul 26, 2014 5:22 pm

Re: How to do Bouncing Boxes on assembly?

Post by AleksMTE »

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

Re: How to do Bounding Boxes on assembly?

Post by Memblers »

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.
AleksMTE
Posts: 5
Joined: Sat Jul 26, 2014 5:22 pm

Re: How to do Bounding Boxes on assembly?

Post by AleksMTE »

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)
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: How to do Bounding Boxes on assembly?

Post by tokumaru »

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

Re: How to do Bounding Boxes on assembly?

Post by Memblers »

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

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

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

User avatar
NovaSquirrel
Posts: 483
Joined: Fri Feb 27, 2009 2:35 pm
Location: Fort Wayne, Indiana
Contact:

Re: How to do Bounding Boxes on assembly?

Post by NovaSquirrel »

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

.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
AleksMTE
Posts: 5
Joined: Sat Jul 26, 2014 5:22 pm

Re: How to do Bounding Boxes on assembly?

Post by AleksMTE »

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

Re: How to do Bounding Boxes on assembly?

Post by tepples »

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.
User avatar
rainwarrior
Posts: 8732
Joined: Sun Jan 22, 2012 12:03 pm
Location: Canada
Contact:

Re: How to do Bounding Boxes on assembly?

Post by rainwarrior »

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

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).
AleksMTE
Posts: 5
Joined: Sat Jul 26, 2014 5:22 pm

Re: How to do Bounding Boxes on assembly?

Post by AleksMTE »

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.
User avatar
NovaSquirrel
Posts: 483
Joined: Fri Feb 27, 2009 2:35 pm
Location: Fort Wayne, Indiana
Contact:

Re: How to do Bounding Boxes on assembly?

Post by NovaSquirrel »

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).
psycopathicteen
Posts: 3140
Joined: Wed May 19, 2010 6:12 pm

Re: How to do Bounding Boxes on assembly?

Post by psycopathicteen »

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.
tomaitheous
Posts: 592
Joined: Thu Aug 28, 2008 1:17 am
Contact:

Re: How to do Bounding Boxes on assembly?

Post by tomaitheous »

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
__________________________
http://pcedev.wordpress.com
Post Reply