Optimizing bounding box routine

[vdub_bobby]

I'm programming for the 2600 and I need a routine to find out if two sprites collided and I need to use bounding boxes (is that the correct term); I can't use the hardware collision detection registers.

 

So, here's my routine:

CheckBoundaries

;--Temp variables should be set up as follows:

;	Temp=X1, Temp+1=X2, Temp+2=X3, Temp+3=X4

;	will set carry if X1 or X2 are between X3 and X4 

;	or if X3 or X4 are between X1 and X2

;	will clear carry else.

lda Temp

cmp Temp+2

bmi Check2a

cmp Temp+3

bmi InsideBoundingBox

Check2a

lda Temp+1

cmp Temp+2

bmi Check3a

cmp Temp+3

bmi InsideBoundingBox

Check3a

lda Temp+2

cmp Temp

bmi Check4a

cmp Temp+1

bmi InsideBoundingBox

Check4a

lda Temp+3

cmp Temp

bmi NotInsideBoundingBox

cmp Temp+1

bpl NotInsideBoundingBox

InsideBoundingBox

sec

rts

NotInsideBoundingBox

clc

rts

Is there a better way?

[+batari]

It all depends. What do x1-x4 represent, are there two boxes checking against one another, are they always the same size, is one always bigger than the other or can they both be any size?

[vdub_bobby]

It all depends.  What do x1-x4 represent, are there two boxes checking against one another, are they always the same size, is one always bigger than the other or can they both be any size?

Two sprites, 1 & 2.

Left edge of bounding box for sprite 1 is x1

Right edge of bounding box for sprite 1 is x2

Left edge of bounding box for sprite 2 is x3

Right edge of bounding box for sprite 2 is x4

 

They are not always the same size; either can be bigger.

 

I set up the temp variables with the X coordinates and call this subroutine, then if I have a match, I set up the temp vars with the Y coordinates and call it again.

 

Thanks; any help is appreciated

[+batari]

OK,in that case, I think you can save a little bit but not too much. You're currently checking x1<=x3<=x2, x1<=x4<=x2, x3<=x1<=x4, and x3<=x2<=x4. The first two checks would suffice for all situations except box 1 being completely contained within box 2. But to handle this case, only one additional check is needed. I'm pretty sure that you can pick any three checks out of the four and this will do the job. Or can anyone see a reason why this wouldn't work?[/code]

[Thomas Jentzsch]

Instead of storing both edges, just store the right edge and the width (maybe as a constant).

 

Then you can do something like

  lda right2

 sec

 sbc right1

 adc #width1+1

 rts              ; c=1: right2 is inside

Repeat for right2-width2

[vdub_bobby]

Instead of storing both edges, just store the right edge and the width (maybe as a constant).

 

Then you can do something like

  lda right2

 sec

 sbc right1

 adc #width1+1

 rts              ; c=1: right2 is inside

Repeat for right2-width2

I kinda figured there was some simpler solution that involved subtracting one from the other (I kept thinking that something similar to the SkipDraw routine should do it), but my brain wouldn't think of it on a Friday afternoon. Thanks.

 

And thanks, Batari: I didn't realize that in the case where one is completely contained inside the other one, only three checks are needed, not four.

 

You guys are fabulous

[vdub_bobby]

Instead of storing both edges, just store the right edge and the width (maybe as a constant).

 

Then you can do something like

  lda right2

 sec

 sbc right1

 adc #width1+1

 rts              ; c=1: right2 is inside

Repeat for right2-width2

This works except for the case when both sprites have equal X positions or Y positions:

situation:

X1=X2



instr   carry   accum

lda X1             X1

sec       set	

sbc X2    set       0

adc W2  clear      W1

But if they are overlapping in the Y-axis that should register as a collision. Unless I'm screwing something up here.

[Thomas Jentzsch]

How about

  clc

 ...

 adc #width+2

?

[vdub_bobby]

How about

  clc

 ...

 adc #width+2

?

I dunno. Similarly, I tried messing around with adding 1 to right1 before the collision routine. But I was getting some weird results (in certain cases they collided before they should have and in certain cases they collided after they should have) and I don't know if they are resolvable. I'll keep staring at it

 

Actually....hmmmmm...

[vdub_bobby]

[...] I was getting some weird results (in certain cases they collided before they should have and in certain cases they collided after they should have) and I don't know if they are resolvable.  I'll keep staring at it

And here's a solution, of sorts...

	lda Left1

sec

sbc #1

sbc Left2

adc Width1

bcc CheckOtherSide

rts

CheckOtherSide

sec

sbc Width1

sbc Width2

bcs NoCollision

sec

rts

NoCollision

clc

rts

I'm pretty sure that works for all cases.

However, this has a few problems:

First of all, to make the widths inclusive, both of them need to be incremented by one. Second, that is 23 bytes...my cmp version is 24 bytes. The difference doesn't seem worth the trouble. Here's the cmp version.

	lda Left1

cmp Left2

bmi CheckOtherSide

cmp Right2

bmi Collision

CheckOtherSide

lda Left2

cmp Left1

bmi NoCollision

cmp Right1

bpl NoCollision

Collision

sec

rts

NoCollision

clc

rts

For all of the code above, the variables Left1 & Left2 are the left edges of the bounding box, Width1 & Width2 are the widths of the bounding boxes, and Right1 & Right2 are the right edges of the bounding boxes.

 

Any comments/ideas?

[Heaven/TQA]

ehm... am i little bit stupid or why is there no check against the y-dimension? i mean a sprite could be overlapping in x-direction but not in y?

[Heaven/TQA]

seems i overread the sentence "call the routine twice for x,y"...