Collision Detection Strategy

[aceofpack]

Hi all,

 

I'm making a mobile game and looking for the most efficient way of going about coding the following. Any comments would be most welcome

 

1. A solid background image

Is this just a sprite of an optimized bitmap? Or is there a special method for bg images that keeps them as efficient as possible.

 

2. Generate a lot of balls (sprites) that bounce around the screen

(Currently created a group for the balls and MANUALLY checking for boundary collisions to avoid the overhead of any physics engine). Am I being too harsh here? Will ARCADE physics do a better job of it, efficiency wise?

 

3. I need to check collisions with the touch/click co-ordinates at a given moment with all these balls, even if they overlap, a click will be detected regardless of layers.

 

 

My initial thoughts are to engage quad trees to elect candidates for running collision detection on. I have this function too, to detect clicks in a circle:

// Check if the input is within a circular radiuscheckCollision: function(ball, inputX, inputY) {var radius = ball.width/2var centerX = ball.x+radius;var centerY = ball.y+radius;if(Math.sqrt((inputX-centerX)*(inputX-centerX) + (inputY-centerY)*(inputY-centerY)) < radius) {return true;} else {return false;}},

I'm having trouble relating the sprites in a group to candidates that are retrieved from a quadtree, is the quadtree built into groups? Say if a candidate came back from the quadtree, and collision was true, how would I kill the sprite from the group?

 

Any pointers would be great! Thanks guys, Phaser is really great to work with.

[s-p-n]

You're on the right track. Arcade physics doesn't take shape into consideration- Arcade physics engine assumes all sprites are rectangles, and checks collisions that way. The way you're checking collisions is much better for your application. 

 

You don't need to know the group a sprite is in to kill that sprite. If you just want to kill any sprite in the quadtree that is clicked on, this would work:

// Assuming `quadTree`, `that`, `inputX`, and `inputY` are all defined in this scope...function killCollisions (sprite) {	if (that.checkCollision(sprite, inputX, inputY)) {		sprite.kill();	}}var candidates = quadTree.retrieve(...);candidates.forEach(killCollisions);

If you have objects in the quadTree that should not be killed, or that when clicked/touched for whatever reason should do something different (example, smaller circles give more points to the player), then you would put that logic in place of the line that says: `sprite.kill()`

 

To find the index of a sprite in a given group, use `group.getIndex(sprite)`. If the sprite is not in the group, the result will be -1. Otherwise, the result is the index of the sprite.
 

[aceofpack]

Awesome, big thanks for explaining this...

 

I had a thought that I'm looping through the sprite group anyway to move them, I would need to incorporate this somehow..

ballGrp.forEach(function(ball){	if(inputActive) { // True if there is input		// Here could live another check to see if this 'ball' is a candidate		// but if it's more expensive than the collision check itself...might not be worth it.		if(self.checkCollision(ball,self.game.input.x,self.game.input.y)) { //Collision			self.ballHit(ball);		}	}	self.moveBall(ball,maxPosX,maxPosY); // Movement});

The additional check I comment on in the above regarding the quadTree... I understand I will need to build and reset the tree every update frame and just haven't quite got it yet to make sure I'm actually implementing time savers rather than time makers! How would I achieve this without bloating it?

 

Thanks a lot.

[chg]

3. I need to check collisions with the touch/click co-ordinates at a given moment with all these balls, even if they overlap, a click will be detected regardless of layers.

My initial thoughts are to engage quad trees to elect candidates for running collision detection on.

For the situation you describe the cost of your quadtree will clearly be much greater than what it saves you. Quadtrees would be helpful though if the balls had to react in somewhat to touching/colliding with each other or with a group of other objects

 

I have this function too, to detect clicks in a circle:

// Check if the input is within a circular radiuscheckCollision: function(ball, inputX, inputY) {var radius = ball.width/2var centerX = ball.x+radius;var centerY = ball.y+radius;if(Math.sqrt((inputX-centerX)*(inputX-centerX) + (inputY-centerY)*(inputY-centerY)) < radius) {return true;} else {return false;}},

Any pointers would be great! Thanks guys, Phaser is really great to work with.

Your collision checkCollision() function has room for optimisation, I trust you realise this though I'll state the obvious just in case: you should of course move "inputX-centerX" and "inputY-centerY" into variables so squaring these values takes two less subtractions and compare against the radius squared (possibly precalculated if it doesn't change often) avoiding the somewhat costly squareroot.

If you wind up not using a quadtree or other partitioning system in front of it, there may also be some benefit to discarding inputs that are say less than the ball's coords and possibly inlining the code in the loop that tests all of the ball sprites (possibly chuck the full rect test in front, but then whether that wins might need to be benchmarked)

[aceofpack]

Again, thanks for the detailed help. So in my case, a quadTree would not be as useful. Would this still be true of 100 balls for example? I noticed it can reduce candidates for collision between 20-60% but the overhead just to work that out doesn't weigh up in my first go so wondered if it was my implementation.

 

I've implemented what you mentioned regarding the collision detection - I also moved the calculations of the radius and radius squared to properties of the ball which is calculated at create time since they can vary in their sizes, but only when creating them initially, not dynamically.

	checkCollision: function(ball, inputX, inputY) {		var centerX = ball.x + ball.radius;		var centerY = ball.y + ball.radius;		var inputXminusCenterX = inputX-centerX;		var inputYminusCenterY = inputY-centerY;		if(((inputXminusCenterX*inputXminusCenterX)+(inputYminusCenterY*inputYminusCenterY)) < ball.radiusSquared)			return true;				return false;			}

I tested this crudely on an iphone 4s in a safari browser, so a pretty unforgiving landscape.

 

At 100 balls, they all move around smoothly - but dragging finger across and colliding creates some noticeable stutter

At 50 balls, again smooth motion - dragging finger creates very minor stutter

At 40 balls, everything seems fine.

 

Do you typically see performance gains when packaged as an app?

[aceofpack]

 

 

If you wind up not using a quadtree or other partitioning system in front of it, there may also be some benefit to discarding inputs that are say less than the ball's coords and possibly inlining the code in the loop that tests all of the ball sprites (possibly chuck the full rect test in front, but then whether that wins might need to be benchmarked) 

 

I'll give this a go now too...

[chg]

You may need to throttle your touch event so you don't do multiple updates per frame

 

Again, thanks for the detailed help. So in my case, a quadTree would not be as useful. Would this still be true of 100 balls for example?

It's not the number of balls but the number of collision queries per ball (per update/rebuild of the quadtree). For a single collision test the quadtree should not win no matter how many balls you have.

[aceofpack]

Yeah it does seem to call it a lot, but because of the finger being held down is a valid input, I need to sample it at a decent enough rate so it seems responsive. So you can essentially hold your finger down and the balls can then run into that position.

 

At the mo I'm using this in the update:

	update: function() {				var inputActive = false;		if(this.game.input.activePointer.isDown)			inputActive = true;		this.checkBalls(inputActive);//Move and check for collisions	},

My knowledge of Phaser is still very young so if there is better ways to do this I'm all ears

 

 

The addition of the 'fail at the simplest checks first' principle improved it a fair bit. 100 balls now seems playable on iphone 4 safari browser albeit not the smoothest to start with. Iphone 5 has no problems. 

	checkCollision: function(ball, inputX, inputY) {		if(inputX < ball.x)			return false;		if(inputY < ball.y)			return false;		if(inputX > ball.x+ball.width)			return false		if(inputY > ball.y+ball.width)			return false;		var centerX = ball.x + ball.radius;		var centerY = ball.y + ball.radius;		var inputXminusCenterX = inputX-centerX;		var inputYminusCenterY = inputY-centerY;		if(((inputXminusCenterX*inputXminusCenterX)+(inputYminusCenterY*inputYminusCenterY)) < ball.radiusSquared)			return true;				return false;