# Box2D Forums

 It is currently Sun May 26, 2013 12:09 am

 All times are UTC - 8 hours [ DST ]

 Page 1 of 1 [ 7 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Optimizing Body.createFixture()Posted: Tue Apr 17, 2012 4:33 pm

Joined: Tue Jul 05, 2011 8:43 pm
Posts: 6
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()
+------ 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.)
Code:
Contour[] contours = solver.findAllContours(); //get all the contours for the chunk.
Body bodyRef = world.createChunkBody(); //create a body to attach fixtures to.

//for each contour...
for (int i = 0; i < contours.length; i++) {
IntPoint[] path = contours[i].path; //each contour contains a path, which is a list of points

//for each element of the path..
for (int j = 0; j < path.length; j++) {
if (path.length < 4) ; //short path check here.
IPoint p0 = path[j]; //grab first point
IPoint p1 = path[(j+1)%path.length]; //grab second point, wrapping over if needed

//figure out the fixture and other properties to use for the body
FixtureDef fixDef = getWorldFixtureDef();

// ***** Where the shape is created. Ideally, this would be replaced with edge shapes, but they're unavailable. *****

PolygonShape poly = new PolygonShape(); //create a shape
shape.setAsEdge(new Vec2(p0.x, p0.y), new Vec2(p1.x, p1.y)); //set up the shape

fixDef.shape = poly; //attach shape to polydef

// ***** This is where my bottleneck lies. This operation takes forever. *****
bodyRef.createFixture(fixDef);
}
}

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.

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Tue Apr 17, 2012 4:48 pm

Joined: Tue Jul 05, 2011 8:43 pm
Posts: 6
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?

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Wed Apr 18, 2012 1:33 am

Joined: Tue Jun 24, 2008 8:25 pm
Posts: 1518
Location: Tokyo
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.

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Wed Apr 18, 2012 6:33 am

Joined: Tue Jul 05, 2011 8:43 pm
Posts: 6
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.

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Mon Apr 23, 2012 7:59 pm

Joined: Mon Jun 08, 2009 12:21 pm
Posts: 353
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()
+------ 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.

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Mon Apr 30, 2012 9:34 pm

Joined: Tue Jul 05, 2011 8:43 pm
Posts: 6
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.

Top

 Post subject: Re: Optimizing Body.createFixture()Posted: Sun May 06, 2012 6:11 pm

Joined: Mon Jun 08, 2009 12:21 pm
Posts: 353
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.

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 7 posts ]

 All times are UTC - 8 hours [ DST ]

#### Who is online

Users browsing this forum: No registered users and 2 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

 Search for: