Box2D Forums

This is a continuation of my previous question, asking about edge shapes, located here: http://box2d.org/forum/viewtopic.php?f=9&t=7254
However, I'm going to summarize it for clarity's sake.

I'm working on a tile based game, and I'm using Box2D for the physics implementation. The most recent version of my code splits areas of the world into chunks and traces out the edges of solid tiles using a Marching Squares algorithm. My algorithm then returns a set of paths around the chunk, which I feed into box2d. Right now, I'm using a series of two vertex edge shapes, as recommended by toucansam. These perform quite admirably, and as long as I unload old chunks, I experience basically no drop in framerate during gameplay. However, when I load new chunks, the shapes must be recreated, and this takes a long time, causing noticeable lag spikes when the player crosses a load boundary. I've narrowed this down to the Body.createFixture() function. I don't mean to draw blame away from my own code, but the createFixture() function takes 9 times longer than the MarchingSquares algorithm to execute a full trace, so that's where I'm starting.

Going deeper into the profiler results, the most intensive parts of the code are:
+ Body.createFixture()
+-- Fixture.createProxy()
+---- BroadPhase.createProxy()
+------ DynamicTree.createProxy()
+-------- DynamicTree.computeHeight()
+---------- DynamicTree.computeHeight()
+------------ (This recursion continues for some time, ending on the same function, with the percentage of function time taken not dwindling significantly until about half-way down.)


I'm using the following code (with some modifications for clarity of the example) to convert the MS path to physics data. The important part of the code is marked near the bottom. (The first few lines are just iterator stuff.)


So I have the following questions: Is there some way I can optimize creating the fixtures? Am I using createFixtures() wrong? It feels to me like this isn't really the right way to be doing things. I feel like there should be some way to create all the shapes, then build all the fixtures at once.

I had another thought: is there a way to lock the world, so that all the fixtures are added at the same time? Would such a thing actually help?

I doubt it because this is a tree, so each added node has to go on a branch which implies that there must be other fixtures previously added for it to have somewhere to go. Perhaps you could stream them in more gradually as the player approaches, that seems to be the way it's done in games with no 'loading screens'.

I wonder if you could make a separate Box2D world for each sector and just warp the player and animate objects into the neighboring sectors' world when they cross the boundary. Then you could even use a separate thread to set it up.

I had a feeling that that was what it was going to be. I'm just going to have to be more gradual with things. I already limit the game to one chunk physics update per tick, so in the short term I can just turn the delay up.

The separate worlds idea is an interesting one, but the world only separated into chunks for convenience and management's sake. The chunks still represent parts of the world right next to each other, and I'm pretty sure if I made separate worlds for each one, that would kill physical interaction across chunk boundaries.

I suppose the main reason I brought this up was so I could see if I was doing anything wrong with this code. It sure *seems* wrong. But I guess that's just me.

Note: I did try setting up the body with bodyDef.active = false, and then calling body.setActive(true) after attaching all the fixtures, but that didn't help much.

I'm not sure what version of the engine you're using, but the latest ones (2.1.2.2 and trunk) both don't have that call hierarchy. You should see

+ Body.createFixture()
+-- Fixture.createProxy()
+---- BroadPhase.createProxy()
+------ DynamicTree.createProxy()
+-------- DynamicTree.allocateNode()
+-------- DynamicTree.insertLeaf()

Even though I did a lot of work in the dynamic tree to optimize these operations, it still uses a java object array instead of a c++ struct array, so this will probably never be as efficient as box2d (due to caching). However, feel free to implement your own broadphase. I think java might do better with a plane-sweep approach, where a new optimal tree is built each step. But that relies on efficient sorting using cache-friendly data, and that's not super predictable with java either.

If you're updating your engine, please use the 2.1.2.2 version

Alright. I haven't updated in a while, mainly because I haven't had a reason to, but I suppose this is a good one. I believe I'm at 2.1.2.

About implementing a broadphase: (Firstly, the broadphase is what filters out bodies when they aren't anywhere near each other to skip intensive calculations, right?) I'm not really sure I could implement an entire broadphase, although I could give it a shot. One thing I am interested in is perhaps "helping" the broadphase. As noted, my game is split into chunks, and my code actively keeps track of which objects are in which chunks, which is needed to load and unload the chunks, among other things. Is there a way I could feed this information into the broadphase to help it run faster? No object is ever going to bigger than a chunk, or even half the size of a chunk, so in theory, objects that are more than a chunk away don't need to be tested, right? Or is the existing broadphase fast enough that this information wouldn't actually noticeably speed things up?

For reference, chunks are 32 meters across, and placed on a regular grid of the same size. Most objects are less than 2 or 3 meters tall and across, with future plans for objects upward of 8 to 16 meters in dimension, although these objects would be special and fairly rare (basically boss creatures).

EDIT: Also, I should note that the function tree I listed is only the most intensive functions in the tree. Other branches had negligible execution times, so I did not list them. I can get the whole tree if necessary.

I would test with the new version first to see if you're still getting those lag spike. If so, it's 'possible' that making a segmented broadphase could slightly speed things up (removes approx log(n) iterations for proxy insertion, where n is your chunks, so about 1-2 iterations). But this would come with a host of unknown issues, especially if you have accidental object crossover. Plus, you still have to have everything in memory.

So in my opinion, I would suggest balancing the dynamic loading with opportune points to have a quick 'loading' screen. This gives you the best performance for your levels, while hiding your loading pauses with a common game element that people will be used to (and if the loading screen is super fast anyways, they might come to the assumption that your game is fast).

But again, I would check with the new release first.