Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (769)
Games in Android Showcase (230)
games submitted by our members
Games in WIP (855)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Quadtree 2d terrain physics  (Read 10176 times)
0 Members and 2 Guests are viewing this topic.
Offline Lucasmontec

Junior Devvie

Medals: 3
Exp: 5 years

« Posted 2015-05-12 06:21:37 »

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 (
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:
<a href=";hl=en_US&amp;start=" target="_blank">;hl=en_US&amp;start=</a>

I have this
Offline Varkas
« Reply #1 - Posted 2015-05-12 13:25:41 »

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.

if (error) throw new Brick(); // Blog (german):
Offline Lucasmontec

Junior Devvie

Medals: 3
Exp: 5 years

« Reply #2 - Posted 2015-05-12 17:22:57 »

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
         } 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):
<a href=";hl=en_US&amp;start=" target="_blank">;hl=en_US&amp;start=</a>
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Lucasmontec

Junior Devvie

Medals: 3
Exp: 5 years

« Reply #3 - Posted 2015-05-12 19:32:54 »

I have managed to do this:

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

Junior Devvie

Medals: 3
Exp: 5 years

« Reply #4 - Posted 2015-05-12 20:18:14 »


Probably isn't the most efficient way... But it works and the method is very cheap. Wink

The code for those interested:


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:


Costs this:
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  Undecided Cry )
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:
Not sure how this scales... too much magic involved.
Pages: [1]
  ignore  |  Print  

EgonOlsen (1572 views)
2018-06-10 19:43:48

EgonOlsen (1632 views)
2018-06-10 19:43:44

EgonOlsen (1144 views)
2018-06-10 19:43:20

DesertCoockie (1572 views)
2018-05-13 18:23:11

nelsongames (1173 views)
2018-04-24 18:15:36

nelsongames (1639 views)
2018-04-24 18:14:32

ivj94 (2395 views)
2018-03-24 14:47:39

ivj94 (1605 views)
2018-03-24 14:46:31

ivj94 (2691 views)
2018-03-24 14:43:53

Solater (883 views)
2018-03-17 05:04:08
Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08

Deployment and Packaging
by gouessej
2018-08-22 08:03:45

Deployment and Packaging
by philfrei
2018-08-20 02:33:38

Deployment and Packaging
by philfrei
2018-08-20 02:29:55

Deployment and Packaging
by philfrei
2018-08-19 23:56:20

Deployment and Packaging
by philfrei
2018-08-19 23:54:46 is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!