Ideal way to reduce a 2D tile level into fewer p2.Bodies?

[danneu]

I've been working on a naive multiplayer CTF game with a p2.js simulation on the client and server.

- Live demo: http://p2-space-arena.herokuapp.com/ (may take 10 seconds for the server to boot)



It's created from this level data where each "X" is a 32x32 p2.Body that contains a p2.Box shape:

 

.............XXXXXXXXX.............
........XXXXX.........XXXXX........
.......X....X.........X....X.......
......X.....X...XXX...X.....X......
.....X...........X...........X.....
.....X.......................X.....
.....X....X......X......X....X.....
.....X....XXX....X....XXX....X.....
.....X....X.............X....X.....
......X.......XX...XX.......X......
......X.........X.X.........X......
.......X.........X.........X.......
..XXXXXXXX.......X.......XXXXXXXX..
.X>>>>>>>>.......X.......<<<<<<<<X.
X>..............X.X..............<X
X>.............X...X.............<X
X>.....X.....XXX...XXX.....X.....<X
X>.....XXXXXX...X.X...XXXXXX.....<X
X>.....X.........X.........X.....<X
X>.....X.........X.........X.....<X
.X.........X..r..X..b..X.........X.
..X..............X..............X..
...X.......X.....X.....X.......X...
....XXXXXXXXX...XXX...XXXXXXXXX....
.............XXX...XXX.............

It works and performs well enough, so I pushed my naive implementation farther by doubling the resolution of the map (16x16 tiles this time) and supporting sloped tiles.





Here's the map.txt data for this iteration: https://gist.github.com/danneu/81cf7c0d22e1f02ab00e4baacf8bcc98

However, the performance is atrocious. That's ~512 p2.Body's each with its own p2.Box or p2.Polygon (slopes).

The profiler says that most of my CPU time is spent in p2's default broadphase's .getCollisionPairs(). Even though the broadphase only produces 4-10 pairs, it's just too many bodies to sift through every frame.

The obvious approach from here is to merge adjacent tiles into single p2.Body entities. For example, instead of having a row of twenty 16x16 p2.Bodies, I could have a single 320x16 p2.Body. This would drastically reduce the amount of work the broadphase has to do.

But to what end do I try to reduce the number of p2.Bodies in the world? To follow this to the end of the spectrum, I could encode the level with a few p2.Polygons, but they'd be large and complex. Is there a rule of thumb?

[dimumurray]

Since the walls are going to be static its extremely wasteful to make each tile its own body. I'd recommend that you create a single body comprised of multiple chain shapes ( a body can be comprised of multiple shapes) for your walls. A chain shape is just a series of line segments as seen below: 

The problem here is how do you find said line segments. What I've done in past projects is to create an monochrome version of the map (see below) and run it thru potrace. Potrace is an API that can extract polygonal or edge shapes from a bitmap. The version of potrace I've used in past projects was for actionscript but I was able to find a javascript port.

Potrace produces a series of polygons that you can then use to create chain shapes for your collision wall body. 

[danneu]

Thanks for the great feedback and demonstration. I appreciate the time you took to create the black and white mask.

I gave potrace a shot on it with GeoJSON output and it looks good. I'll try to integrate it now.

[danneu]

I got it working using p2's `body.fromPolygon(vertices)` to create the concave bodies.

Unfortunately the performance is much worse than my original naive map with the 32x32 blocks. Looking at the profiler, it drastically increased the cost of the narrowphase:

 

 

For some reason I also have issues clipping through the walls.

Here's the sloppy git diff of my change: https://github.com/danneu/p2-space-arena/commit/91be74230232dc4a876fb48a9ab796909d98faa2

Perhaps p2 works best with the collision map broken down into a few dozen bodies/polygons so that the broadphase can spare the entire geometry blob from landing in the narrowphase every frame. I wonder if island splitting can even happen if the whole world is dominated by a single body.

One direction I've been working on here and there is a map editor built on Fabric.js since it comes out of the box with click/drag/transform controls:

Seems like it might be the easiest way to break apart the level into smaller bodies -- getting a human to do it!

[Fatalist]

Does not p2 use any spatial structure? I don't get why it needs to do so many collision checks for static objects...

Have you set static = true for your walls?

[danneu]

3 minutes ago, Fatalist said:

Does not p2 use any spatial structure? I don't get why it needs to do so many collision checks for static objects...

Have you set static = true for your walls?

 

Yeah, they're definitely Body.STATIC (the default since mass defaults to 0).

[dimumurray]

Just realized that you're working with p2.js and not Box2d. My example is based on work I've done using Box2D's chain shapes. Have you tried using Box2D? There are multiple Javascript ports (the most popular being this one.) You can integrate Box2D yourself or use the plugin available for Phaser (but the plugin will set you back $40).

[AutoSequence]

 

I saw your post on Github regarding this issue. Don't use concave shapes. Try to use a set of boxes (long boxes where possible, and small boxes for a single tile that doesn't have any neighbours for instance). Usually the p2 creator (schteppe) would reply quick to questions on Github, but I think he is on vacation at the moment. 

On 31-7-2016 at 10:21 PM, dimumurray said:

Just realized that you're working with p2.js and not Box2d. My example is based on work I've done using Box2D's chain shapes. Have you tried using Box2D? There are multiple Javascript ports (the most popular being this one.) You can integrate Box2D yourself or use the plugin available for Phaser (but the plugin will set you back $40).

I think if he would (properly) use kripken's box2d, it would definitely give his game a performance boost indeed. I think it is however a bit of ''pain in the ass'' to properly make it work (not sure about the phaser plugin, haven't used it). I believe Tagpro is using the same port.

I think p2 is the easiest and best 2D physics engine at the moment if you want to create something simple. I'm currently using it for a 2D turn based game, where I have a little bit of luck since that isn't actually realtime and can ''fast-forward'' some simulations on the server. However, yours is realtime and I don't know whether p2 (in my opinion the best physics engine that is written in Javascript) is good for that. I'd imagine you want to run multiple game instances on a single server, so you would run multiple game worlds, maps and other structures into a single machine that needs to calculate the physics in realtime. However, there might be some tweaks or properties you can do that would actually make it work smoothly.

[danneu]

5 hours ago, AutoSequence said:

 

I saw your post on Github regarding this issue. Don't use concave shapes. Try to use a set of boxes (long boxes where possible, and small boxes for a single tile that doesn't have any neighbours for instance). Usually the p2 creator (schteppe) would reply quick to questions on Github, but I think he is on vacation at the moment. 

I think if he would (properly) use kripken's box2d, it would definitely give his game a performance boost indeed. I think it is however a bit of ''pain in the ass'' to properly make it work (not sure about the phaser plugin, haven't used it). I believe Tagpro is using the same port.

I think p2 is the easiest and best 2D physics engine at the moment if you want to create something simple. I'm currently using it for a 2D turn based game, where I have a little bit of luck since that isn't actually realtime and can ''fast-forward'' some simulations on the server. However, yours is realtime and I don't know whether p2 (in my opinion the best physics engine that is written in Javascript) is good for that. I'd imagine you want to run multiple game instances on a single server, so you would run multiple game worlds, maps and other structures into a single machine that needs to calculate the physics in realtime. However, there might be some tweaks or properties you can do that would actually make it work smoothly.

 

Thanks. My current objective is to encode levels with just the vertices of the convex objects that comprise them so that I can break levels down myself. This way I should be able to get the most out of p2 by hand-crafting optimal walls.

My target level size will be no larger than TagPro's. I've stress-tested this and it seems to hold up as long as I minimize the number of wall bodies (via consolidation).

p2 is obviously much nicer to use than Box2d and I'm glad I started with p2 as my first physics engine. I have plenty of other obstacles just trying to build a multiplayer game. Ideally p2 would be good enough, but I'll eventually experiment with Box2d soon if it is more performant.

I'm in no rush, though. The Box2d port is pretty much undocumented and has no source code to read which is a bit chilling.

[AutoSequence]

4 hours ago, danneu said:

 

Thanks. My current objective is to encode levels with just the vertices of the convex objects that comprise them so that I can break levels down myself. This way I should be able to get the most out of p2 by hand-crafting optimal walls.

My target level size will be no larger than TagPro's. I've stress-tested this and it seems to hold up as long as I minimize the number of wall bodies (via consolidation).

p2 is obviously much nicer to use than Box2d and I'm glad I started with p2 as my first physics engine. I have plenty of other obstacles just trying to build a multiplayer game. Ideally p2 would be good enough, but I'll eventually experiment with Box2d soon if it is more performant.

I'm in no rush, though. The Box2d port is pretty much undocumented and has no source code to read which is a bit chilling.

Indeed, pretty much all the box2d ports seem poor in terms of documentation and even memory leaks. (Except the phaser plugin perhaps, but I'd imagine that wouldnt work on the server unless you use phaser there too which seems a little bit overkill)

Hopefully Schteppe will reply on your post and i'll make sure to send you a PM once I have a solution myself too.  

[symof]

Have you tried using tilemaps? I found it increased the efficiency by alot in my maze game, as I was using p2.body sprites for the walls then changed to tilemaps. But as far as I know it won't work with slopes.

http://phaser.io/examples/v2/tilemaps/create-from-array

http://phaser.io/examples/v2/tilemaps/csv-map-with-p2

It can hold really big maps with no performance issues that I can tell.

 

Your other choice would be Arcade physics as that is much more efficient on mobile.

 

 

[symof]

You could also do slopes like this.

https://jsfiddle.net/ms2vjzsk/

[danneu]

@symof Thanks.

I implemented axis-aligned tilemap collision in my previous iteration, but decided that I want slopes. From what I've read, Phaser's arcade physics has the same limitation.

I was thinking of just adding slope support to my hand-rolled collision system. For example, ImpactJS' source code has a simple implementation of a collision map with sloped tiles.

I ultimately went with p2, half of me feeling like a kid in a candy store ("I want gravity wells and constraints!") and the other half tired of reading/writing my own math. 

My physics needs certainly don't demand a full constraint solving simulator like p2, though I also don't want to re-implement the parts of p2 that I do use, like beginContact, endContact, collisionMasks, contactMaterials, etc.