Broadphase / Tile Based Game

[bmueller]

Hi,

I am coding a tile based game. The levels are about 512x512 fields - but may also be bigger (>= 256.000 objects). The tiles consist of a floor plane and may contain objects lying on the floor - e.g. diamonds to pick up or walls,...
Tiles don't collide with each other - only the player interacts with the world.
For the game only the tiles in the neighborhood of the actor are relevant for the game. It should be enough to calculate only 6x6 squares around the player.
Due to limination on the destination platform (mobile device) initialising the complete world could exceed the available memory on the plattform.

So I am currently thinking about only adding the relevant parts of the world before calculating the next simulation step. This means that in the worst case I have to exchange 11 tiles (if the player moved diagonal)...

Code: Select all

               R R R R R R       P = Player
. . . . . .    R . . . . . A     A = Added Tiles
. . . . . .    R . . . . . A     R = Removed Tiles
. . . . . .    R . . P . . A
. . P . . . => R . . . . . A
. . .\. . .    R . . . . . A
. . . . . .     A A A A A A

Is this possible?
Which would be the best broad phase to implement this?
So the broad phase algorithm itself should just do nothing - except that it should be very fast to add and remove objects.
Or ist it possible to run without a broad phase?
Is it possible to reuse the collision shapes from the tiles removed to avoid allocation/freeing of memory?

[Erwin Coumans]

Is this possible?
Which would be the best broad phase to implement this?
Or ist it possible to run without a broad phase?

Yes, it is best to use btDbvtBroadphase for this, you cannot run without a broadphase.

Is it possible to reuse the collision shapes from the tiles removed to avoid allocation/freeing of memory?

Yes, you can re-use collision shapes.

Thanks,
Erwin

[bmueller]

I made some benchmarks using all 3 broad phases.

Simple seems to be the best in my case: It is slow in calculation (about 3 times slower) but much faster in modifying the world (1/4) (removing / adding objects).

Times are in ms.

Code: Select all

Simple:
step:           cur=   1.02600 avg=   1.10527 min=   0.95400 max=  10.21800
modify physics: cur=   0.77200 avg=   0.83346 min=   0.69700 max=   2.53600

Dbvt:
step:           cur=   0.40800 avg=   0.41779 min=   0.33200 max=   6.37400
modify physics: cur=   2.79300 avg=   3.11932 min=   2.57200 max=   4.74700

axisSweep:
step:           cur=   0.34300 avg=   0.34162 min=   0.04200 max=   6.81500
modify physics: cur=   3.34400 avg=   3.69864 min=   1.72200 max=   6.23100