As you can see from the images, I’m going to have battles with hundreds of objects. Now of course, I cannot use the physics library as it has way too much overhead. And because I use a terrain, I can basically reduce all the calculations to 2D by just adjusting the y-value from the terrain height value.
What I really want to know are ideas of how to efficiently calculate collisions for up to, say, 2k objects.
I have two ideas:
Create some kind of occupancy grid with a resolution of 50cmx50cm (or just another smallest possible entity size) and let the objects update its position in the grid. This will definitely be fast, but I can only store in every cell the height to which it is occupied. This would cause problems if a soldier is standing on top of a wall because this means that a cell is occupied by essentially two and not one object. This would be problematic with projectiles and their impact location. So this is where my 2D relaxation blows it…
Create a sufficiently sized (dynamic?) grid with each cell holding a list of objects and objects subscribe and unscribe when they move between those cells. Than I could go with standard 3D collision. But will this be ok with THAT amount of objects?
I would really like some comments on that or new ideas!
Just check the distances between your objects, no need to go about and check fro triangles etc. this basically boils it down, if you can before check for groups or similar then you should be able to pretty quickly check for collisions. Collision with the terrain using collideWith() (to determine the y-location of the unit) should be sufficiently fast to use with a few thousand units.
How about using two 2d layers (or howmuch you need)
then you can do all 2d calcualtions, and define where transition between y leves is possible (stairs, ladder, ect)
This way you could do it all in 2dgrids.
Now another question is, do you need only a collision detection or also a solving?
(Like knoing two objects overlap is enough, or do you need to solve the collision with physicall forces?
If you only need to know the overlappings, you could specifically check for that.
2K ghost bojects should work quite ok. Before movment you can then test will it work ? if move object else walk around or similar)
Advanced method:
Use only pseudophysical calcualtions for projektiles and bullets, do the rest with a A* algorithm, that alters the costs for already occupied fields to infinity, that way you wont have two units overlap in the first place, and can save all detection and solving.
You need to make sure however that objects cannot stuck (like vehicles that cannot turn without moving forward r backward)
thanks both of you for your suggestions. The point is that I want to have as few calculations as possible (obviously). So I will revert to 2D wherever I can (read: as good as always). No quaternions, no matrices. Just good 'ol Vector2f and cos/sin. Add to those 2k soldiers their corresponding “ghost-object reaction area”, another 1000 mid-air arrows and AI, all this running on my MacBook and you’ll realize my suffering
Of course, I don’t go down to the triangle level. I use a circle and a height (so basically a cylinder) for every soldier to do the calculations. But I really like the multiple 2d grids. Since I have at most 3 levels (terrain, and two wall layers in a castle) this computation will be fast. Why didn’t I think of this?
Well I would really also like solving the collisions. Imagine that a horse runs into a man: I want the soldier to slightly be pushed to the side so that the horse can pass. In every update the soldier knows his last position in the grid and will adjust his occupancy if his physical position is not corresponding with his grid position. The question is: How fine must the 2D grid resolution be to have a natural-looking “physics-space”. If you consider a solider to have a circle diameter of 50cm, maybe a grid size of 25cmx25cm is not fine enough. Well this needs to be checked by trial and error…
As for the projectiles: Yes, there will be no real physics and they won’t appear in the occupancy grid. I will actually only adjust the height in every frame and using something like Bresenham and, according to projectile speed and position, to check if I hit something along the line using the grid till the next frame.
So, I used the bullet implementation and cranked up the numbers to 500 soldiers and my CPU got hot as shit and sometimes slowed down a litte. I think there was no native bullet lib for all the OSs, right? Nonetheless, it would still in a way exhibit the same consumption of CPU time. The same scene, but using my 2D approximation, runs as smooth as butter with no heavy load on the CPU. And both implementations behave practically the same.
From where I’m standing I basically don’t have any other choice than to do 2D plus level grids. But thanks for the effort.
Concerning projectiles: I know of the Bresenham inside the Terrain class but I played with the thought of having wind influencing the flight path so this would be not possible in this manner…
I don’t quite see the connection, maybe we don’t understand each other… I was just talking about doing ray checks for the location of the objects, not full collision or anything. Everything else would have to be added. I did this with thousands of units and it works fine.
Erm, well obviously we do… You want to determine the objects location on the terrain by sending a ray down and doing collideWith(). Why not just use heightmap.getScaledHeight(x,y) like I do now? Seems faster to me… Thanks for your patience
In my bullet implementation I used HeightfieldCollisionShape for the terrain and CylinderCollisionShapes for the soldiers…
Yeh, collideWith() is not physics. But you could do the same with bullet, you don’t have to use the “falling boxes” physics part, you can just use it for collision checks with physicsSpace.rayTest() and .sweepTest()
Yes, I know that collideWith() is just maths. Ok, then we are clear The point was that the whole time I assumed you to take the pro-bullet stance. Took some time to realize that we actually had the same opinion
You might even get quite far with using bullet just like this, basically using the geometry collision also creates temporary data, so the collision shapes should not weigh in too much. Physics computations for so many units obviously will not yield great performance but the collision code of bullet is definitely more efficient when its not just about the terrain.
Well dont get it false, bullet (at least native) is extremly optimized if you need to do much raycasting, since it uses the broadphase first, no need to use the rest of bullet .
(The jbullet version however uses a far inferior algorithm for the rays (basically bruteforce) with exponential costs. (assuming each unit does one ray per update)
