Collision performance

Performance Tuning
#1

I’ve never previously worried about collision performance, however recently I’ve become picky about it.
If I have about 500 objects, all doing collision checks it is quit costly.

My frame rate may be alright on an A63 3000+ OC’d, however not everyone has an overclocked high end CPU.
This is where the trouble comes in.
Basically if the method returns (NONE, NONE), it detect no collision and nothing further is done.

Is my code in any way optimal as a collision routine?

public Compass[] directionOfCollision(Entity entity)
	{
		Compass[] direction = new Compass[] {Compass.NONE, Compass.NONE}; //Compass is an enum
		
		float
			entXMin = entity.bounds.x,
			entYMin = entity.bounds.y,
			entXMax = entity.bounds.x + entity.bounds.width,
			entYMax = entity.bounds.y - entity.bounds.height;
		float
			xMin = bounds.x,
			yMin = bounds.y,
			xMax = bounds.x + bounds.width,
			yMax = bounds.y - bounds.height;
		
		if(entXMin >= xMin)
			direction[0] = Compass.WEST;
		else if(entXMax <= xMax)
			direction[0] = Compass.EAST;
		
		if(entYMin <= yMin)
			direction[1] = Compass.NORTH;
		else if(entYMax >= yMax)
			direction[1] = Compass.SOUTH;
		
		return direction;
	}
#2

Have you run a profiler over you app? 500 isn’t really that many checks for a simple AABB->AABB test (although that new’d array isn’t going to help).

I wonder if you’re doing something daft like checking against every other object each time and duplicating the tests…?

#3

With Mustang builds the array should be built on the stack rather than the heap, so it wouldn’t make a difference AFAIK.

Basically you’re saying that I really can’t optimise this any further?

#4

You really, really, don’t want to be creating a new array every time you call the code!!

In fact a far more sensible way to do it would be to have 8 enums in your compass and return one as a simple return value (or null for no collision).

Cas :slight_smile:

#5

Sorry, I didn’t quite get the initial post, is that 500 objects checking against each other or against a single environment?

Kev

#6

Both, environment and each other.

#7

Thats a fair few calculations, some sort of spatial partioning appropriate for your game might be worth while at this point?

Kev

#8

Let’s say that we check for collisions between n entities. First, if you determine that Q doesn’t collide with P, then be sure not to waste time by determining that P doesn’t collide with Q. This will cut time in half. Total time taken will now be the base time of checking two entities against each other, times

½n(n-1).

Next, if you have n+m bodies dispersed on the map, such that n of them are in the left half while m are in he right one, you may associate all entities with which half of the map they are located in. When you perform collision detection, it will now take time

½n(n-1) + ½m(m-1)

instead of

½(m+n)(m+n-1) .

Of course there will be some inconvenience with updating the whereabouts of each entity whenever it moves, and also you may have to use mutually overlapping submaps in order to avoid trouble when entities overlap more than one area. You can further perform subdivisions of the map into cubes or squares such that large numbers of objects can be tracked this way, effectively converting the square of a sum into the sum of squares. Tracking requires extra time proportional to n. Feel free to comment critically, since I’m not the Master of Algorithms.

#9

I can’t see any optimality in that.

Why are you using two variables when one would do?
So you seem to have typical (a-1) * (a/2) problem. There are numerous things that could speed it up. Because it’s a commonly encountered problem there are various and not optimal solution on the net.
xxxxxxx
xxxxxx
xxxxx
xxxx
xxx
xx
x
12150 tests
Is what you want to do. So we can just guess if you are doing that.
Basically for colision you are using just code if((center - center2)^2 > ((size + size2)^2)) test for detailed colision.
Also you are returning for some reason two results It might be benefical to return just one.

You should download that little testing program that I used, and look at performance details. IIRC it did detection test between 10000 moving objects by closest point of aproach. Or was it 100000?

Of course you could do also something smarter and use quadtree. Or you could use Spanish moss algorithm.

It’s funny when you are seeing the message about some other post and you’d hastily click the “post”.

#10

Ouch.

Also, why even have this method? With the array creation, math and call overhead, it would be faster just to do a full bounds check with short circuiting on failures. Your doing half the tests and all the math for it anyway.

Or kill the array and return an int representing the directions.

#11

Are you sure. Mind explaining what you think is going on?

#12

Escape analysis.
Basically anything short lived is placed into cache rather than main memory.
This is why I don’t believe the cost of creating the enum array is anything larger than a basic cache allocation.

#13

Escape analysis or not it’s still extremely daft :slight_smile:

Cas :slight_smile:

#14

While there are plans to do this in Mustang, I didn’t think it had been added to a public build yet.

#15

Yes, but you are returning the array from the function. First, we don’t know you’re not passing the array around. Second, how can you be sure that the compiler will class it as short lived. It might give up when it leaves the function.

But I don’t know anything about how it would be implemented, so please correct me if I’m wrong.

#16

It’s only used once when it’s returned, that is right after it is returned. It ends right there. However the array’s scope is within the game loop.
It isn’t passed into any methods.

#17

I would rather expect escape analysis to work if you would allocate that array in ecompassing function and pass it to subroutine - where it would not escape. Checking your caller how value you return is used is outside scope of ‘trivial’ escape analysis, I’m afraid.

#18

It is possible when the called method is inlined as it then reverts to the simple case.

#19

In case of inlining, imaginary compiler can even detect that it is just a function with multiple return value disguised as array and just update 2 caller-allocated variables directly - no need to pretend it is an array.

Anyway, I’m going into Cas mode here - I’ll believe when I see this in action.

#20

I’m not holding my breath for this to appear in the next 12 months… but stranger things have happened at sea…

Cas :slight_smile: