Quadtree 2d terrain physics

Game Mechanics
#1

Hi there! I don’t know if this question belongs here or in Performance tunning… But I’ll leave it here.
I’m making some terrain using a Quadtree and I’d like to add collision to the terrain.
Although I know some ways of doing if (query the quadtree that is the terraing with an object AABB + collision check with interscetion on narrow phase), I would like to use a physics engine instead. I’m planing to use this terrain technique with libgdx and box2d (and leave it opensource).
The main issue I’m thinking will be the method to generate bodies effectively. I could sweep the tree and try to generate a poligon around the filled areas but that would be expensive (http://en.wikipedia.org/wiki/Convex_hull_algorithms).
A was reading through google and I found out that another technique was to relax the merging rules of the quad-tree and merge rectangles like crazy to reduce to the max the amount of rectangles. Than use the filled rectangles to generate static bodies. I have no idea how to do this. I’ll be thinking about this for the next days, but I wanted to share the question here to discuss this with you masters!
Thanks for reading up to here.
And here.

Something like this:

I5_WBPBQ6kE

I have this
http://lucasmontec.github.io/TerrainGeneration/

#2

You can always code a sort of “quadtree-to-mesh” adapter, and hand the dapter API to the physics engine. It won’t be super-efficient, but maybe good enough. This will conserve the memory efficiency of the quadtree while using more CPU.

The other way is to dump the tree and use a regular mesh for terrain. That will need more memory but less CPU.

It’s a tradeoff, like always. If you change the mesh from a regular mesh to something less regular you get something in between the tree and the mesh in terms of CPU and memory.

Personally I use to take the solution that gives me the least headaches. In this case I’d use a mesh for terrain unless I know in advance that the mesh will consume too much memory for the hardware where the program is meant to be run. Look up the KISS principle if in doubt.

#3

I’ve been thinking on a ton of ways of doing this. Most of them failed because the concept has flaws. I’ll explain some here.

The easiest way I thought was to generate a low-res quadtree by using the existing quadtree and traversing it limiting the deepness level. The check for each node just sees if the node is a leaf or if it is in the max desired level. Doing this I limit the number of regions of the quadtree.

private static void analizeTree(QuadtreeTerrain tree, int resLevel) {
		if (tree != null) {
			if (tree.isLeaf() || tree.getLevel() == resLevel) {
				// Analise each son
				analizeNode(tree);
			} else {
				// Go down the tree
				for (QuadtreeTerrain child : tree.getChildren())
					analizeTree(child, resLevel);
			}
		}
	}

Then I would use this low res tree to generate Box2D static squares. Directly.
I don’t know how many objects box2d can handle without it start beeing a problem. Terrain shouldn’t hold this many physics information though…
A way of simplifying even more would be to remove all boxes which have the border sourounded by other boxes. And then merge the rectangles the best I can.
Here is a picture of what I’m saying (something like this):

This generates (hypothetically) 24 static bounding boxes for this chunk of terrain. Is this too much?
Also, I have no idea how to merge those rectangles.
To find the edge ones I think I can use the rectangle area and form a grid of filled regions. Then look the adjacent regions to see if they are filled.

Another way of doing this entire thing I was thinking about making a grid the size of the lowest desired resolution and then iterating vertically forming rectangles the biggest horizontal size they can.

Yet another technique I was thinking about was detecting the edges of a filled area. Then iterating through the edges center points and using this points to form a polygon. There are several problems with this technique so I wont explain further.

This is what I want (I just found this and I’m going to read his code):

gkMvVkvdhOI

#4

I have managed to do this:

Now if I join the rectangles I think I have a fast memory cheap method.

#5

Done!

Probably isn’t the most efficient way… But it works and the method is very cheap. :wink:

The code for those interested:
http://pastebin.com/3ayBH2Fu

[UPDATE]

Start
mingrid make: 4ms
mingrid edge: 0ms
mingrid bounds: 0ms

Takes ~4ms to generate bounds for a 700x700 quadtree using a 180x180 mingrid.
I can code to regenerate the bounds only for modified regions (respecting the terrain destruction objective).
I can use the boxes on Box2d to get impact positions and forces and ‘paint’ destruction on the quadtree.
Then regenerate the quadtree region that was updated. Or if i’m just lazy, spend 4ms and make the entire tree again.

The updated code:
http://pastebin.com/xauQXUX1

This:

Costs this:
Start
mingrid make: 17ms
mingrid edge: 3ms
mingrid merge: 4ms
total mingrid: 26ms

generated: 1534

are 1534 static boxes too much? (I think it is just to big :-\ :’( )
26ms seems expensive but if I only update quads that where changed this can be drastically reduced…
The aproximation seems good too…
I don’t know. Seems to me this is the wrong way to go. But I really want to use box2d so I can use box2d lights and don’t work on collision code once more.

Seems like it is a good method after all:
http://zumbi.co.nf/Zomborms/
Not sure how this scales… too much magic involved.