Collision detection in Assembly not working at all

Master (179)

27-06-2020, 06:17

Hi guys, this should be a simple code but is driving me crazy 2 days:

A simple routine to check if a point is inside a box, a building block of almost all games:

; ---------------------------------------------------------
; Checks if the point (x, y) is inside the box (x1, y1, x2, y2)
; 
; Destroys:
;   
; Inputs:
;   HL: point to be checked (H: x, L: y)
;   BC: upper left corner of box to be checked (B: x1, C: y1)
;   DE: down right corner of box to be checked (D: x2, E: y2)
; Output:
;   A = 0 : not collided
;   A = 1 : collided
CheckCollision:

;To compare stuff, simply do a CP, and if the zero flag is set,
;A and the argument were equal, else if the carry is set the argument was greater, and finally, if 
;neither is set, then A must be greater (CP does nothing to the registers, only the F (flag) register 
;is changed). 

; if (x >= x1)
    ld a, h
    cp b
    jp c, .false        	; c: a < parameter

; if (x <= x2)
    ld a, h
    cp d
    jp nc, .false           ; nc: a > parameter

; if (y >= y1)
    ld a, l
    cp c
    jp c, .false        	; c: a < parameter

; if (y <= y2)
    ld a, l
    cp e
    jp nc, .false           ; nc: a > parameter


;true:
    ld a, 1
    ret

.false:
    ld a, 0
    ret

I'm testing it isolated in another program, it gets false all the time:

	ld h, 30   ; point (30, 20)
	ld l, 20

	ld b, 15   ; box upper left (15, 10)
	ld c, 10

	ld d, 40   ; box bottom right (40, 30)
	ld e, 30
	call CheckCollision             ; 
    cp a
    jp nz, True
	jp False
	
	ret

False:
	ld	hl,FalseMsg
	call	Print
	ret
True:
	ld	hl,TrueMsg
	call	Print
	ret

TrueMsg:
	db "True",0
FalseMsg:
	db "False",0

Not having debug tools, trace, step, unit tests, it's very hard to be productive, you got stuck on something all the time.
Programmers of the 80's were real heroes.

Any idea?

By albs_br

Master (179)

27-06-2020, 06:27

MSX Pen here:

https://msxpen.com/codes/-MAo0qEi-VjjFcE04SwI

By robodrunk

Resident (50)

27-06-2020, 07:57

try

call CheckCollision
or a

By norakomi

Paragon (1084)

27-06-2020, 08:34

cp a is always zero, since you compare a with a

By pgimeno

Master (253)

27-06-2020, 12:54

Yes, the problem is obviously the 'cp a', but I see another one. This does not do what the comment says:

; if (x <= x2)
    ld a, h
    cp d
    jp nc, .false           ; nc: a > parameter

It actually checks if x < x2; if they are equal, it will be considered false (no collision). Similarly, the comment 'nc: a > parameter' is also wrong, 'nc' means 'a >= parameter'.

This may be the right or the wrong thing to do, depending on whether you consider the bottom and the right sides of the rectangle to be included as part of it. That is, for a point which is exactly on x=x2, should the routine return true (inside) or false (outside)?

If the right and the bottom borders are not considered part of the rectangle, your routine is fine, but the comments are wrong. They should say `if (x < x2)` and `if (y < y2)`.

If they are considered part of the rectangle, you can change it as follows:

; if (x2 >= x)
    ld a, d
    cp h
    jp c, .false           ; c: a < parameter
...

; if (y2 >= y)
    ld a, e
    cp l
    jp c, .false           ; c: a < parameter

By ARTRAG

Enlighted (6462)

27-06-2020, 12:57

Replace cp a by or a

By albs_br

Master (179)

27-06-2020, 17:44

norakomi wrote:

cp a is always zero, since you compare a with a

Oh f%$# !!!

That's it, I knew it might be something very stupid I was missing!

I think "cp 0" but wrote "cp a".
That's why I consider the sintax "cp a, 0" less prone to errors.

By albs_br

Master (179)

27-06-2020, 17:44

robodrunk wrote:

try

call CheckCollision
or a

Good point, "or a" is the same as "cp 0", but faster (4 x 7 T-states).
And speed is critical here, since is a routine that will be called many times per frame.

By albs_br

Master (179)

27-06-2020, 17:48

pgimeno wrote:

Yes, the problem is obviously the 'cp a', but I see another one. This does not do what the comment says:

; if (x <= x2)
    ld a, h
    cp d
    jp nc, .false           ; nc: a > parameter

It actually checks if x < x2; if they are equal, it will be considered false (no collision). Similarly, the comment 'nc: a > parameter' is also wrong, 'nc' means 'a >= parameter'.

If the right and the bottom borders are not considered part of the rectangle, your routine is fine, but the comments are wrong. They should say `if (x < x2)` and `if (y < y2)`.

If they are considered part of the rectangle, you can change it as follows:

; if (x2 >= x)
    ld a, d
    cp h
    jp c, .false           ; c: a < parameter
...

; if (y2 >= y)
    ld a, e
    cp l
    jp c, .false           ; c: a < parameter

Actually, I don't care about the difference between < and <= here, because I will check the equality before.
I mean, if x == x1, there is no point in check if x <= x2, and then I save some cpu cycles.

But your point is valid and I will change the comments.

Thanks for everyone.

By ARTRAG

Enlighted (6462)

27-06-2020, 20:49

maybe something here can be reused for your needs
https://github.com/artrag/Uridium-msx1/blob/master/collision...

By santiontanon

Paragon (1135)

28-06-2020, 07:21

If speed is important, then there's lots of things you can do to accelerate. For example, you only need "ld a, h" and "ld a, l" once, instead of twice, as a still contains the value of h and l the second time. Also, instead of "ld a,0", you might want to do "xor a" which is faster. Moreover, depending on how do you use the result, it will be faster outside of this routine to return the result in a flag ("z/nz" or "c/nc") rather than a = 0/1. This is trivial to do by replacing "ld a,1" by "or 1", and "ld a,0" by "xor a".

Currently you have do to this:
call CheckCollision
or a
jp nz, True

But if you return the result in z/nz, for example, you just need to do this (saving a comparison)
call CheckCollision
jp nz, True

I'm sure there are other ways to optimize further, but just a start