Infinite Collision Detection tutorial

by snout on 28-11-2010, 20:46
Topic: Development
Languages:

Infinite have published an article on collision detection in the code corner of their website. The article explains the collision detection routines as implemented in Universe: Unknown and is a good explanation, including source codes, that can get new MSX/Z80 developers to implement collision detection quite easily.

Relevant link: Infinite Collision Detection tutorial

Comments (8)

By ARTRAG

Enlighted (6322)

ARTRAG's picture

29-11-2010, 08:21

Good routine but it doesn't handle the EC bit.
Now, if one of the two sprites is partially under the left border and the other isn't, this routine can miss the collision.

By Hrothgar

Champion (479)

Hrothgar's picture

29-11-2010, 09:37

Missing hits with sprites that are half outside the screen isn't that horrible; it's quite an errm.. edge case.

I would be more concerned about false positives with EC and non-EC sprites having the 'same' position. Does that fail as well?

By ARTRAG

Enlighted (6322)

ARTRAG's picture

29-11-2010, 10:26

If one sprite is partially under the border (EC set) and another is aroud x=32 the routine gives a false collision.
You simply cannot use this code is you game needs the use of the EC bit

I guess that UU does not mange the EC bit

By ARTRAG

Enlighted (6322)

ARTRAG's picture

29-11-2010, 15:41

in case positions of objects were stored on 16 bit Edwin's code could become

;-----------------------------------------------------

.check16.
        xor  a            ; HL=x1,DE=x2,B=size2,C=size1
        sbc    hl,de
        jr    nc,.other16
        xor     a
        ex    de,hl
        sbc    hl,de            ; Carry is reset
   
        ld    d,a
        ld    e,b
        sbc    hl,de             ; compare with size 2
        ret

.other16:
        ld    d,a
        ld    e,c
        sbc    hl,de             ; compare with size 1         
        ret

it is the case of objects in a virtual map where only a window is displaied

By Edwin

Paragon (1182)

Edwin's picture

29-11-2010, 23:44

ARTRAG> Since I wouldn't switch to 16 bit calcs that quickly, I added a little update to demonstrate the way I would deal with it.

By ARTRAG

Enlighted (6322)

ARTRAG's picture

30-11-2010, 22:40

my contribution (from MOAM project): it works on SAT data stored in ram and with offsets and sizes passed on the stack

    psect   npcs

    global  _check_collision
				; check_collision
				;  (byte *sprite1,       DE - SAT pointer
				;	byte *sprite2,       BC - SAT pointer
				;	unsigned sprite1_size_hor,   	ix+4
				;	unsigned sprite1_size_vert,  	ix+6
				;	unsigned sprite2_size_hor,   	ix+8
				;	unsigned sprite2_size_vert);	ix+10
				;	sizes decode as follows:
				;		lobyte - first pixel set
				;		hibyte - number of pixels set
				;	it returns:
				; 		HL = 0 for no collision
				; 		HL = 1  collision from right
				; 		HL = -1 collision from left
_check_collision:
				push    ix
				ld  	ix,0
				add 	ix,sp	; use ix as poiter to parameters on the stack

				push 	bc		; store the two pointerst to the SAT
				push 	de

				; test y
				ld  	a,(de)	; a = vertical pos. sprite 1 (y1)   

				add a,32		; needed to deal with sprites partially under the top border
				add a,(ix+6)    ; y offeset within the sprite 1
				ld  e,a
				ld  d,0     	; de = vertical pos. sprite 1 + 32 (i.e. y1+yoffset1+32)

				ld  	a,(bc)	; a = vertical pos. sprite 2 (y2)

				add a,32		; needed to deal with sprites partially under the top border
				add a,(ix+10)   ; y offeset within the sprite 2
				ld  l,a
				ld  h,0     	; hl = vertical pos. sprite 2 + 32 (i.e. y2+yoffset2+32)

				ld  b,(ix+11)   ; b = number of pixels, sprite 2 (i.e. ysize2)
				ex  de,hl   	; swap de and hl
				or  a
				sbc hl,de
				
				jr  nc,1f   	; if hly1+yoffset1) ? ysize1 : ysize2;
				cp  b
				jr  nc,nocollosion  ; test on y failed

				; test x
				
				pop hl      	; pointer to SAT for sprite 1

				inc hl
				ld  e,(hl)
				inc hl
				inc hl
				ld  a,(hl)		; retrive the EC bit of sprite 1
				and 128
				rrca
				rrca
				xor 32
				add a,(ix+4)
				add a,e
				ld  e,a
				ld  a,0
				adc a,a
				ld  d,a     	; de = horizontal pos. sprite 1 + 32*EC

				pop hl			; pointer to SAT for sprite 2

				inc hl
				ld  c,(hl)
				inc hl
				inc hl
				ld  a,(hl)		; retrive the EC bit of sprite 2
				and 128
				rrca
				rrca
				xor 32
				add a,(ix+8)
				add a,c
				ld  l,a
				ld  a,0
				adc a,a
				ld  h,a     	; hl = horizontal pos. sprite 2 + 32*EC

				ld  b,(ix+9)    ; b = number of pixels, sprite 2
				ex  de,hl
				or  a
				sbc hl,de

				push af
				push af

				jr  nc,1f
				
				ld  b,(ix+5)    ; swap sprites
				add hl,de
				ex  de,hl
				or  a
				sbc hl,de
				
1:				ld  a,h
				or  a
				jr  nz,collision
				
				ld  a,l
				cp  b
				jp  nc,nocollision

collision:		
				pop af
				pop af

				ld  hl,-1		; return -1 if sprt1 is hit by sprt2 from left
				jp  nc,sprt1_hit_by_left

				ld  hl,1		; return 1 if sprt1 is hit by sprt2 from right

sprt1_hit_by_left:
exit:
				pop ix

				pop bc			; return address

				pop af			; remove sprite 1 and 2 sizes
				pop af
				pop af
				pop af

				push bc
				ret


nocollision:
				ld  hl,0

				pop af
				pop af

				jp  exit    ; return 0 if no collision

By ARTRAG

Enlighted (6322)

ARTRAG's picture

30-11-2010, 23:12

Small fix to the code above
my contribution (from MOAM project): it works on SAT data stored in ram and with offsets and sizes passed on the stack

    psect   npcs

    global  _check_collision
				; check_collision
				;  (byte *sprite1,       DE - SAT pointer
				;	byte *sprite2,       BC - SAT pointer
				;	unsigned sprite1_size_hor,   	ix+4
				;	unsigned sprite1_size_vert,  	ix+6
				;	unsigned sprite2_size_hor,   	ix+8
				;	unsigned sprite2_size_vert);	ix+10
				;	sizes decode as follows:
				;		lobyte - first pixel set
				;		hibyte - number of pixels set
				;	it returns:
				; 		HL = 0 for no collision
				; 		HL = 1  collision from right
				; 		HL = -1 collision from left
_check_collision:
				push    ix
				ld  	ix,0
				add 	ix,sp	; use ix as pointer to parameters on the stack

				push 	bc		; store the two pointers to the SAT
				push 	de

				; test y
				ld  	a,(de)	; a = vertical pos. sprite 1 (y1)   

				add a,32		; needed to deal with sprites partially under the top border
				add a,(ix+6)    ; y offset within the sprite 1
				ld  e,a
				ld  d,0     	; de = vertical pos. sprite 1 + 32 (i.e. y1+yoffset1+32)

				ld  	a,(bc)	; a = vertical pos. sprite 2 (y2)

				add a,32		; needed to deal with sprites partially under the top border
				add a,(ix+10)   ; y offset within the sprite 2
				ld  l,a
				ld  h,0     	; hl = vertical pos. sprite 2 + 32 (i.e. y2+yoffset2+32)

				ld  b,(ix+11)   ; b = number of pixels, sprite 2 (i.e. ysize2)
				ex  de,hl   	; swap de and hl
				or  a
				sbc hl,de
				
				jr  nc,1f   	; if hly1+yoffset1) ? ysize1 : ysize2;
				cp  b
				jr  nc,nocollision  ; test on y failed

				; test x
				
				pop hl      	; pointer to SAT for sprite 1

				inc hl
				ld  e,(hl)
				inc hl
				inc hl
				ld  a,(hl)		; retrieve the EC bit of sprite 1
				and 128
				rrca
				rrca
				xor 32
				add a,(ix+4)
				add a,e
				ld  e,a
				ld  a,0
				adc a,a
				ld  d,a     	; de = horizontal pos. sprite 1 + 32*EC

				pop hl			; pointer to SAT for sprite 2

				inc hl
				ld  c,(hl)
				inc hl
				inc hl
				ld  a,(hl)		; retrieve the EC bit of sprite 2
				and 128
				rrca
				rrca
				xor 32
				add a,(ix+8)
				add a,c
				ld  l,a
				ld  a,0
				adc a,a
				ld  h,a     	; hl = horizontal pos. sprite 2 + 32*EC

				ld  b,(ix+9)    ; b = number of pixels, sprite 2
				ex  de,hl
				or  a
				sbc hl,de

				push af
				push af

				jr  nc,1f
				
				ld  b,(ix+5)    ; swap sprites
				add hl,de
				ex  de,hl
				or  a
				sbc hl,de
				
1:				ld  a,h
				or  a
				jr  nz,collision
				
				ld  a,l
				cp  b
				jp  nc,nocollision

collision:		
				pop af
				pop af

				ld  hl,-1		; return -1 if sprt1 is hit by sprt2 from left
				jp  nc,sprt1_hit_by_left

				ld  hl,1		; return 1 if sprt1 is hit by sprt2 from right

sprt1_hit_by_left:
exit:
				pop ix

				pop bc			; return address

				pop af			; remove sprite 1 and 2 sizes
				pop af
				pop af
				pop af

				push bc
				ret


nocollision:    
				ld  hl,0

				pop af
				pop af

				jp  exit    ; return 0 if no collision

By ARTRAG

Enlighted (6322)

ARTRAG's picture

01-12-2010, 01:49

here there is the code above integrated in a small demo RON project (use space and cursors)
https://docs.google.com/leaf?id=0Bx4kWAc-fapqMWQ0NGM2N2EtN2U1My00MWI2LWIzZWYtYjk3MjM4MGJlODcw&hl=en&authkey=COTshr8O