Fast (bounding box?) Collision detection

[Tigerskunk]

I thought I have a reasonably fast bounding box collision detection running in asm for my game (a shmup), but at the moment this seems to take too many cycles when there a some shots on the screen.

I have thought about some pre sorting, but I am not sure if this reasonable, we are talking about around 12 to 20 objects on screen here...

Any advice for this from the experienced coders here?

[zero]

Can you describe the game a little? For example, do the bullets travel in 8 directions or are they just going vertically/horizontally?

One trick is to use dual playfield mode, draw the shots on the front playfield and use sprite collision with bitplane checking which has no overhead. Also makes BOBs faster by not having to worry about restoring the background.

Can you post your code? Maybe we can optimize it.

[Tigerskunk]

Since images show more than a thousand words (at least that is a proverb in german ):

[ Show youtube player ]

It's a 4 bpl game. Architecture cannot be changed anymore at this point in development.

I am searching for some general ideas for speeding up the algorithm for this low object count (<20 objects) case here...

[NorthWay]

Hm. What is "too many cycles"? A comparison with ABS(dX) and ABS(dY) should be pretty fast unless you are getting into bullet-hell style. What are you checking - everything with everything, or spesifics?

[roondar]

There are several hardware based ways to speed up collision detection, but they all carry significant drawbacks (not in the least that they tend to be 100% pixel perfect, which is not usually what you actually want).

Generally, I'd split collision detection into two (or more) distinct phases: one for player vs objects, one for player bullets vs enemies. You might even split off the player vs scenery from the rest as well. The reason this can help is that it allows you to skip a bunch of checks.

A 'normal' bounding box collision detection algorithm (as well as the absolute distance method mentioned by NorthWay) would check every object vs every other object, but this can clearly be improved since not all collisions are relevant. Splitting the collision detection up in multiple different groups also lowers the object count per test and potentially allows you to check only one object vs all objects rather than the worst case of checking all vs all. These notions combined will speed up the checking compared to the standard algorithm by (potentially) quite a bit.

I'd go for a split something like:

1. player vs scenery*
2. player vs objects (one check for the player against all objects that it should collide with)*
3. bullets vs enemies (obviously only checking bullets vs enemies and not also bullets vs bullets)

This way only the bullets vs enemies group requires you to check a large number of objects, though even here many collisions are not checked for. Compared to the worst case scenario of all objects vs all objects (which would essentially run in O=n^2), the above is a massive improvement that leaves out a large number of pointless checks.

Edit: I noted I left out player bullets and enemy objects vs scenery. This might best be solved using a tilemap lookup IMHO.

All this said, collision detection does normally get slower with more objects to check quite rapidly.

*) If you can live with pixel perfect collisions, or don't mind creating a custom collision mask for the player, this can probably be done with the Blitter by doing a blit with channels A&C active (D disabled) and the minterm set for AND. When done, check the BZERO bit in DMACONR (bit 13) for the result. This can be quicker than doing bounding box checks if the number of objects is large enough.

Note that this method does require either a mask bitplane (i.e. one more bitplane that isn't shown but contains the mask you wish to collide against) or requires collisions to be checked vs specific bitplanes only (otherwise any pixel set will cause the mask to fire, including 'harmless background' pixels)

If the player is made up of Sprites, this can also be done through hardware but will either be fully pixel perfect or requires specific bitplanes to be set as collision 'sources'.

[mcgeezer]

With Bomb Jack i used a combination of bound boxing and thr blitter zero flag.

From recollection i check if there are any enemies within a 16pixel boundary of jack and then perform the blitter and check to see if there was an overlap.

Probably not very fast but it was accurate as i had fine pixel control over the masks.

Geezer

[Asman]

@Steril707
Can you post your collision routine ?
I use this to check collision with monsters (it's not optimized and I don't count cycles yet)

;-----------------------------------------------------------------------------
;in
;	a6 - player
HeroCheckCollisionWithMonster:

		tst.b	heroIsInvisible(a6)
		bne	.exit

		move.w	heroPosX(a6),d0		;d0 = left1
		move.w	d0,d1
		add.w	#4<<6,d0
		add.w	#14<<6,d1		;d1 = right1
		move.w	heroPosY(a6),d2		;d2 = top1
		move.w	d2,d3
		add.w	#4<<6,d2
		add.w	#28<<6,d3		;d3 = bot1

		lea	monstersStructs(a4),a1
		moveq	#MONSTERS_MAX_SIZE-1,d6

.loopmonsters	cmp.w	#ENEMYSTATE_LIVE,enemyState(a1)
		bne	.nextmonsters

		move.w	enemyPosX(a1),d4	;d4 = left2
		move.w	d4,d5
		add.w	#4<<6,d4
		add.w	#12<<6,d5		;d5 = right2


		cmp.w	d1,d4			;;if (right1 < left2) return(0);
		bhi	.nextmonsters

		cmp.w	d0,d5			;;if (left1 > right2) return(0);
		bcs	.nextmonsters

		move.w	enemyPosY(a1),d4	;d4 = top2
		add.w	#2<<6,d4
		move.w	d4,d5
		add.w	#14<<6,d5		;d5 = bot2

		cmp	d3,d4			;if (bottom1 < top2) return(0);
		bhi	.nextmonsters
		cmp	d2,d5			;if (top1 > bottom2) return(0);
		bcs	.nextmonsters

		;collision hit
		move.w	#HEROSTATE_DIE,heroState(a6)

		bra	.exit

.nextmonsters	add.l	#enemy_SIZEOF,a1
		dbf	d6,.loopmonsters

.exit		rts

If you can't post the asm routine (top secret), so perhaps you can post total cycles (68000) for whole collision rouitne, hero with enemies for example.

If you have questions or dubts - just ask.

[mcgeezer]

[QUOTE=Asman;1299242]@Steril707
Can you post your collision routine ?
I use this to check collision with monsters (it's not optimized and I don't count cycles yet)

Similar to mine, I do enemy to player tests though and not the other way around because different enemies have different bounds boxes.

This is my detection for one of the enemies in Rygar, it's not optimised as I can probably use the cmp2 instruction as I'm on 68020 - this works though.

; Input
;d2=X Position of Enemy
;d3=Y position of Enemy
;a3 = Coordinates pointer x1,x2,y1,y2
; Output
;d6=Return value (-1 is collision)


DRONE_TO_DISKARM_COLLISION	MACRO
		move.l	d4,-(a7)
		move.l	d5,-(a7)
		move.w	d2,d4					; Check a 32x32 boundary from x1/y1
		move.w	d3,d5
		add.w	#32,d4
		add.w	#32,d5

		moveq	#0,d6
.eny_coll_loop:	tst.w	(a3)
		bmi.s	.eny_coll_exit
		cmp.w	2(a3),d2
		bgt.s	.eny_coll_next
		cmp.w	(a3),d4
		blt.s	.eny_coll_next
		cmp.w	6(a3),d3
		bgt.s	.eny_coll_next
		cmp.w	4(a3),d5
		blt.s	.eny_coll_next
		moveq	#-1,d6
		bra.s	.eny_coll_exit
.eny_coll_next:	addq.w	#8,a3
		bra.s	.eny_coll_loop
.eny_coll_exit:	move.l	(a7)+,d5
		move.l	(a7)+,d4
		ENDM


DRONE_TO_RYGAR_COLLISION	MACRO
		move.l	d4,-(a7)
		move.l	d5,-(a7)

		move.w	d2,d4					; Check a 32x32 boundary from x1/y1
		move.w	d3,d5
		add.w	#32,d4
		add.w	#32,d5

		moveq	#0,d6
.ryg_coll_loop:	cmp.w	2(a3),d2				; Check X1 against Rygar X2
		bgt.s	.ryg_coll_next
		cmp.w	(a3),d4					; Check X2 against Rygar X1
		blt.s	.ryg_coll_next
		cmp.w	6(a3),d3				; Check Y1 against Rygar Y2
		bgt.s	.ryg_coll_next
		cmp.w	4(a3),d5				; Check Y2 against Rygar Y1
		blt.s	.ryg_coll_next
		moveq	#-1,d6
.ryg_coll_next:	nop
.ryg_coll_exit:	move.l	(a7)+,d5
		move.l	(a7)+,d4
		ENDM

[a/b]

Being bored a little, so here is optimized version. Probably not what you are really looking for, it's the same algorithm... And it's not tested, (C) possible bugs ahead .

HeroCheckCollisionWithMonster:

		tst.b	heroIsInvisible(a6)
		bne	.exit

		move.w	heroPosX(a6),d1
		add.w	#(14-4)<<6,d1		;d1 = right1
		move.w	#(14-4-(4-4)+12-4)<<6,d0 ; d0 = right1-left1+enemy_width

		move.w	heroPosY(a6),d3
		add.w	#(28-2)<<6,d3		;d3 = bot1
		move.w	#(28-2-(4-2)+14)<<6,d2 ; d2 = bot1-top1+enemy_height
		lea	monstersStructs+enemyState(a4),a1
		moveq	#MONSTERS_MAX_SIZE-1,d6

.loopmonsters
		cmp.w	#ENEMYSTATE_LIVE,(a1)
		bne.b	.nextmonsters

		move.w	enemyPosX-enemyState(a1),d4	;d4 = left2
		sub.w	d1,d4			;if (right1 < left2) return(0);
		bgt.b	.nextmonsters
		add.w	d0,d4
		blt.b	.nextmonsters

		move.w	enemyPosY-enemyState(a1),d4	;d4 = top2
		sub.w	d3,d4			;if (bottom1 < top2) return(0);
		bgt.b	.nextmonsters
		add.w	d2,d4
		blt.b	.nextmonsters

		;collision hit
		move.w	#HEROSTATE_DIE,heroState(a6)
		bra	.exit

.nextmonsters
		lea	enemy_SIZEOF(a1),a1
		dbf	d6,.loopmonsters

[Asman]

@a/b - Great work. Thanks and respect.

[Tigerskunk]

first off sorry for the late reply, had some family business to attend to yesterday...

Originally Posted by roondar

I'd go for a split something like:

1. player vs scenery*
2. player vs objects (one check for the player against all objects that it should collide with)*
3. bullets vs enemies (obviously only checking bullets vs enemies and not also bullets vs bullets)

Hmm, that I already have implemented in exactly that way.

For point one, player vs scenery I use a table that gets generated out of a level wide special collision table that I create in the TILED editor, plus subtracting the current hard scroll value (gets me a value of 0-31).
In the end, I check if the square where the player is currently has some background in it, or not. And if, then there are certain tiles that are more special that get checked against (half squares, etc).

This is rather fast, and errs on the side of the player if needed the way I create the level layout. I found out, that players hate pixel perfect collisions anyway.


It's point two, "player vs objects (one check for the player against all objects that it should collide with)" that makes my head ache the most at the moment.

If there are more than let's say 10 objects on screen, this gets rather slow. Seems the overhead generated for checking one object is a bit too high.

I wonder why, though, since I already leave the sequence immediately if enemy.x > player.x which should rule out most objects since the player ship should be at let's say 1/3 of the screen most of the time in a sideways scrolling shmup...

Is there any way to measure how much time a certain part of code needs? Any kind of "clock register" that I can check on? I know about using raster lines and the DMA Debugger in FS-UAE, but I'd like to have some more "hard data" for testing and comparing different setups and optimizations...

[roondar]

You can use the CIA timers to get a very accurate recording of how long something takes (do make sure you use a free one though, if you use a mod player and/or a keyboard reading routine some of them are probably in use). CIA timers are accurate to within about 10 CPU cycles (assuming a 68000@7Mhz).

Here is some example code (NOTE: if you want to return to the OS, it'll hang the keyboard unless you store the CIA state properly first )

	include hardware/cia.i ; from NDK (version 1.3 or higher)
ciabase				EQU	$bfe000

		lea.l	ciabase+1,a5			; CIA A
		move.b	ciacra(a5),d0
		and.b	#%11000000,d0			; Keep bits 6&7 as is
		or.b    #%00001000,d0			; Set for one-shot mode
		move.b	d0,ciacra(a5)
        	move.b	#%01111111,ciaicr(a5)	; Clear all CIA interrupts
		
		; Set up timer value (low byte first)
		move.b	#$ff,ciatalo(a5)
		move.b	#$ff,ciatahi(a5)

		; Timer is running now, do the test

		; Stop timer & fetch result
		bclr	#0,ciacra(a5)
		moveq	#0,d6
		moveq	#0,d7
		move.b	ciatalo(a5),d6
		move.b	ciatahi(a5),d7
		asl.w	#8,d7
		or.w	d7,d6 ; result in D6 (CPU cycles taken assuming 7MHz 68000 = ($ffff-d6)*10)

Note this uses the CIA-A timer A and clears all CIA-A interrupts, so make sure these are not in use by other stuff in your program or there will be trouble

Also note that the CIA setup at the start only needs to be done once, after that you can start the timer by writing the desired countdown value into ciatalo/ciatahi.

Edit: For reference, a PAL Amiga with a 7MHz 68000 has about 141000 cycles per frame.

---
Without looking at your code, I would say that 10 objects should be fairly CPU friendly to check, especially if you're just comparing one player object to 10 enemy objects one after the other, especially if you stop checking as soon as one axis is out of bounds.

[Tigerskunk]

@Roondar: Thanks, that code will come in very handy...

Yeah, I really wonder what's happening in there. And I feel the problem is more severe with bullets in comparison to normal enemy objects.

Probably needs a detailed debugging session to find out what's wrong with the code..

Thanks a lot in advance, will keep you guys up to date on this topic from my side...

[Asman]

@Steril707
Perhaps you know that but better repeat than forgot . To counting cycles you can use EASY68K which is free.

[zero]

What is your screen setup? Are you using sprites for the background, or dual playfield?

Another trick you can use is to only do collision detection every other frame, or on half the objects each frame, or just work through the list and stop when you reach a certain line on the screen, the continue where you left off next frame.

You would be surprised how well it works. Super Mario Brothers does it every other frame, for example.

Another trick is to use less than pixel perfect collision. In Pac Man it only registers collision when Pac Man and the ghost are in the same 8x8 block. It actually makes the game more exciting as you can get very close to the ghosts and still escape sometimes. For shooters it's not uncommon to have the hit box of the ship be smaller than the graphic of the ship.

[Tigerskunk]

Originally Posted by zero

What is your screen setup? Are you using sprites for the background, or dual playfield?

Sprites for background, or I'd not be able to use more than 7 colours for the foreground...

Originally Posted by zero

Another trick you can use is to only do collision detection every other frame, or on half the objects each frame, or just work through the list and stop when you reach a certain line on the screen, the continue where you left off next frame.

That's actually an amazing idea. Wonder why I didn't think about it yet?
Will probably do that for the enemy vs player collisions only, since I want player shots to be precise for "them feels"...

Originally Posted by zero

You would be surprised how well it works. Super Mario Brothers does it every other frame, for example.

Super interesting, didn't know that.. Really keeps CPU cycle count down, I'd guess.

Originally Posted by zero

Another trick is to use less than pixel perfect collision. In Pac Man it only registers collision when Pac Man and the ghost are in the same 8x8 block. It actually makes the game more exciting as you can get very close to the ghosts and still escape sometimes. For shooters it's not uncommon to have the hit box of the ship be smaller than the graphic of the ship.

Yep, i already do that. My game is pretty player friendly on collisions. You can even move into most background structures a few pixels in before a collision occurs.
That way I can punish the player with more shit flying around on screen and it's still not unfair... or at least I feel that way, need to wait what playtesters say...

[roondar]

By the way, I assumed you had access to the NDK for the address locations of the CIA registers. If not I can create a version that doesn't need the include file.

As for collisions every other frame, that sounds like a very interesting idea. But it'll only work if no object moves so fast as to 'cross through' any other object it needs to collide with between frames. Sadly I know this from personal experience as an Arkanoid clone I wrote in AMOS way back in 1996 or 1997 would only run correctly if I updated the ball by one pixel per frame. If I made the ball move faster, it would occasionally move 'through' the edges of bricks without interacting with them.

So, I'd agree it's mostly useful for player vs other stuff and less so for bullets vs enemies

[zero]

Originally Posted by Steril707

That's actually an amazing idea. Wonder why I didn't think about it yet?
Will probably do that for the enemy vs player collisions only, since I want player shots to be precise for "them feels"...

You might be able to do player shots every other frame too, depending on their size and speed and how much accuracy you want.

Say your shot is 8 pixels wide and moves 8 pixels per frame. You can extend the hit box to be 8+8 pixels wide with the area in front of the shot being the extra 8 pixels. To the player it looks like the shot hit the enemy from the front, for you you only need to test collision every other frame.

A lot of games do some variation of that because the shots travel really fast and if the hit box was only the size of the shot they would pass through smaller enemies some times.

Another option is to just make the enemy hit boxes less accurate but also make collision detection between the player's shots and enemies quite generous. Instead of using exact pixels, divide the screen into 8x8 blocks (or 16x16 blocks) and do collisions with a simple equality comparison. The hit boxes are giant and favour the player, but they are also super fast.

When everything is moving really fast players tend not to notice this lack of accuracy. That's how PacMan works, for example, and I'm sure I remember a few shoot-em-ups doing the same.

Also your equality test can be just one cmp instruction, by combining x and y coordinates into a single number.

[Chrille]

Here is another idea:

This Idea was for a bomberman clone project and every object has a maximum size of 16x16pixels. I used an array of pointers(a collision array). Each entry for a 16x16 pixel field. Every object (player, bomb or whatever) was written to this array. If an object has got a screen position like (X=150,Y=100 upper left corner) then I wrote this to this array[(150/16)+((100/16)*20{320/16})] . If there was already a pointer, I linked this object to the existing one (a single linked list). Every time a object moves you have to update this collision array (worst case delink object from list and link to a new list), but you have drastically less checks. I had only to check 4 entries (left upper corner to right lower corner, and okay you have to check more objects, if many objects are on the same field) of this array. I tested this algorithm with more than 320 objects at the same time and it was really fast

May be you can adjust this idea somehow to your shoot'em up game. May be you can use a 8x8 collision map (not with pointers, only indicate if there is a bullet or not) for the bullets and every enemy has to look up, if it is shot.

[zero]

Do you need a linked list? Why not just build a linear list every frame as you go through rendering objects?

Actually it might be faster to avoid the list entirely. If your collision map is only 40x32 (8x8 tiles on a 320x256 screen) just allocate 1.2k of RAM to it and have one byte per block. Write a 1 to any block with an object in it, and then you can test for collisions with all objects with a single check of one byte. No need to clear it, just write a 2 into it next frame and check for that.