Performance with large numbers of static bodies

Oct 22, 2008 at 7:23 PM
Edited Oct 22, 2008 at 7:24 PM
First off, thanks for a great physics engine - it was easy to integrate with and has been working really well.

I have a situation where I have a large number of bodies that are static. As that number increases, the cpu usage of the physics simulator goes up - even if no non-static bodies have been added to the simulator.

I'm guessing (but not sure - I haven't yet delved too deep into the farseer code) that the issue is that, even though the bodies are static, the engine still needs to do pairwise comparisons to decide not to collide. Even though those checks are quick, for a very large number of bodies, the total cost of the n-squared comparisons is quite expensive.

I tried setting all of the bodies to have the same, non-zero collision group number, but that didn't change the cpu usage. Same with collision categories.

It seems that performance in this type of senario - where you have a large number of static bodies, or large numbers of bodies in separate collision groups - could be dramatically improved by collision categories being collection-based. You would then only need to do any operations at all between objects in collections that collide with one another.

In an extreme case (which happens to be close to my actual case) of 10,000 bodies that cannot collide with one another, a collection-based system would do no work at all, instead of doing the 100 million pairwise comparisions needed to determine that none of the objects needs to be checked for collision.

Or maybe I'm just missing something?
Coordinator
Oct 22, 2008 at 8:29 PM

"First off, thanks for a great physics engine - it was easy to integrate with and has been working really well."

Thanks to you too for using it.

"the engine still needs to do pairwise comparisons to decide not to collide"

Well, there are some small calculations on static and even disabled bodies that needs to be done, before any other checking can be done. This is properbly what is causing the slowdown.

There are no pairwise comparisons on static, disabled and geometries that are in the same collision group (or category). They are all eleminated in the broad phase collision detector.

The small calculations I was talking about before are only being done in the SelectiveSweep and SweepAndPrune broad phase colliders. BruteForce collider does it brute force (hence the name) and does not need any premade calculations.

"You would then only need to do any operations at all between objects in collections that collide with one another"

The BruteForce collider checks every geometry against every other geometry. This gives you the O(n^2) complexity but a detector such as SAP (Sweep And Prune) can do it much faster over multiple fames by using frame coherence and other tricks. You can get it down to n in complexity if I remember correctly.

If you have some geometries that collide with nothing else but them self, then you could create a new PhysicsSimulator and add those to it. The advantage is that you can make efficient use of a multithreading this way with only a small overhead in memory.

And indeed, partitioning the geometries into seperate lists would make a logical boundary between geometries, but tho the BruteForce collider traverses all the geometries and check one against the next, it just continues to the next geometry if they are not colliding.

You best bet would be to limit the number of geometries live at once. Unless you have 10.000 geometries on a single screen all the time, there are some tricks you can do.

You best bet would be to limit the number of geometries to test against. If you are interested in ways of doing this, you can download the WIP (work in progress) documentation here: http://www.codeplex.com/FarseerPhysics/SourceControl/DownloadSourceCode.aspx?changeSetId=42143
or wait until Farseer Physics 2.0 comes out.

Oct 22, 2008 at 9:17 PM
Thanks for the detailed reply!

"Well, there are some small calculations on static and even disabled bodies that needs to be done, before any other checking can be done. This is properbly what is causing the slowdown."

Yes, that is exactly it. Although I may have not been completely clear, I was referring to the pairwise checks in broad phase collision (which are still O(n^2) even with the smart broad phase colliders).

Even though the checks are relatively trivial, 100 million of them is still a lot - on my (pretty darn fast) computer, I can't keep a coherent simulation with 10,000 static bodies.

If collision categories were represented as lists rather than flags, the number of pairwise broad-phase checks could be drastically reduced in cases where there are large number of static bodies or bodies in collision categories that cannot collide with one another.

To make things more concrete, I'm running into this issue with a driving game I'm working on. I have a large auto-generated cityscape with lots of buildings and AI and computer-controlled cars driving around. The buildings are, obviously, all static. Even when I have very few cars (or none at all) in the system, it grinds to a halt with lots of buildings.

Another, related aspect is that the game has high-level geometric structure that could inform physics collision detection, but that I cannot currently feed into the system. For example, my city is divided into districts and blocks. I know what block a car is in, I know what buildings are in that block, and I know that a car can only collide with buildings in the block that it is in.

While I definitely plan on implementing a system that restricts physics to operating on only a part of my entire city area, I'd like the "live" area to be as large as possible.

I'm starting to thing that my best bet is to just implement my own custom broad phase collider. Given the specifics of my game, I'm guessing that even a brute force broad phase collider that is informed by my game (ie: only pairwise checks cars with cars/buildings in the current block) would work great.
Coordinator
Oct 22, 2008 at 9:29 PM
I will take a look at it and see if there are anything we can do to speed it up.

Sounds like a nice simlation you have there. Would be great to see a picture or demo of it when you are done.
Thanks for the suggestion on collision categories.
Oct 22, 2008 at 10:18 PM
"I'm starting to thing that my best bet is to just implement my own custom broad phase collider"

Just wanted to let you know that I went ahead and did this, and it works great. I added a new collider to Farseer that is a slightly modifed version of the BruteForceCollider. I made the Update() method virtual, and changed DoCollision() to take a pair of Geoms.

You then create a subclass of the new collider in your own code, override Update(), and intelligently pass DoCollision() pairs of Geoms you know need to be checked based on higher level game state.

Now my simulation runs great - even with huge numbers of static buildings.

I can send you the modified collider code if you like. It would be cool if the same thing could be done for the SelectiveSweep collider, but it looks to be more complex due to the internal data structures.

Coordinator
Oct 23, 2008 at 8:06 AM
Could you try to count the number of geoms checked both in broad and narrow phase colliers? Just count the number of comparisons in the broad phase and count the number of arbiters created. (they are used in the narrow phase)

You can then try to compare it to the normal broad phase colliders.

I would like to have a look at your implementation, it's always fun to see what others are doing with the project.
Oct 23, 2008 at 8:25 PM
Edited Oct 23, 2008 at 8:28 PM
You can see a screenshot of my current work in progress here:

http://mikescodeblog.blogspot.com/2008/10/more-automatic-city-generation.html

As you can see, lots of static bodies...
Coordinator
Oct 23, 2008 at 9:13 PM
Nice one ladron. And thanks for the note about Farseer Physics. Really appreciate it.

And yep, seems like a lot of static bodies. Is there any particular usage for this project?
Oct 24, 2008 at 1:53 AM
Just a hobby project I'm playing with.
Coordinator
Oct 24, 2008 at 11:32 AM
Very extensive hobby project. Have you considered making it opensource?

Could be useful for someone.
Oct 24, 2008 at 5:16 PM
Extensive indeed.  Looks cool too!  Do you expect the NPC traffic to be occasionally run into buildings, or are they all ace drivers?  If you don't expect any accidents from them on their own, you could probably add and remove buildings from the simulation so that only buildings near to the player or other key points (like accidents?) are calculated in the simulation.
Oct 24, 2008 at 6:19 PM
The AI driving works pretty well - they don't run into buildings unless you smash into them with your own car, so that would probably work. Because I can now limit collision detection to buildings in the block the car is currently in, though, it is pretty fast even with physics active throughout the entire city.