Java-Gaming.org Hi !
Featured games (90)
games approved by the League of Dukes
Games in Showcase (798)
Games in Android Showcase (234)
games submitted by our members
Games in WIP (865)
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  
  [solved][libGDX] QuadTree Implementation Malfunction  (Read 17665 times)
0 Members and 1 Guest are viewing this topic.
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Posted 2016-05-14 20:52:14 »

Hello JGO community,

I followed this tutorial when creating a QuadTree class and made a few modifications based on the feedback on the tutorial. Everything works as expected until I start clearing and inserting entities, as indicated in the tutorial, each frame. Before clearing and inserting, there are multiple quadrants and only 7 entities are marked for collision detection. However, after clearing and inserting, there is only one quadrant and all 33 entities are marked for collision detection. I would post a video, but it seems redundant as all I said is happening in the video.

Here is the QuadTree code:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
63  
64  
65  
66  
67  
68  
69  
70  
71  
72  
73  
74  
75  
76  
77  
78  
79  
80  
81  
82  
83  
84  
85  
86  
87  
88  
89  
90  
91  
92  
93  
94  
95  
96  
97  
98  
99  
100  
101  
102  
103  
104  
105  
106  
107  
108  
109  
110  
111  
112  
113  
114  
115  
116  
117  
118  
public class QuadTree {
  private static final int MAX_OBJECTS = 1;
  private static final int MAX_LEVELS = 3;

  private int level;
  private Rectangle bounds;
  private Array<Entity> entities;
  private QuadTree[] nodes;

  public QuadTree(int level, Rectangle bounds) {
    this.level = level;
    this.bounds = bounds;
    this.entities = new Array<Entity>();
    this.nodes = new QuadTree[4];
  }

  public void draw(ShapeRenderer shapes) {
    shapes.setColor(Color.MAGENTA);
    shapes.rect(bounds.x, bounds.y, bounds.width, bounds.height);
    for (int i = 0; i < nodes.length; i++) {
      QuadTree node = nodes[i];
      if (node != null) {
        node.draw(shapes);
      }
    }
  }

  public void clear() {
    entities.clear();
    for (int i = 0; i < nodes.length; i++) {
      if (nodes[i] != null) {
        nodes[i].clear();
        nodes[i] = null;
      }
    }
  }

  private void split() {
    final float x = bounds.x;
    final float y = bounds.y;
    final float w = bounds.width / 2f;
    final float h = bounds.height / 2f;
    final int level = this.level++;

    nodes[0] = new QuadTree(level, new Rectangle(x + w, y, w, h));
    nodes[1] = new QuadTree(level, new Rectangle(x, y, w, h));
    nodes[2] = new QuadTree(level, new Rectangle(x, y + h, w, h));
    nodes[3] = new QuadTree(level, new Rectangle(x + w, y + h, w, h));
  }

  private int getIndex(Rectangle r) {
    int index = -1;

    float verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2f);
    float horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2f);

    boolean topQuadrant = r.getY() < horizontalMidpoint && r.getY() + r.getHeight() < horizontalMidpoint;
    boolean bottomQuadrant = r.getY() > horizontalMidpoint;

    if (r.getX() < verticalMidpoint && r.getX() + r.getWidth() < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      } else if (bottomQuadrant) {
        index = 2;
      }
    } else if (r.getX() > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      } else if (bottomQuadrant) {
        index = 3;
      }
    }

    return index;
  }

  public void insert(Entity entity) {
    if (nodes[0] != null) {
      final int index = getIndex(entity.getComponent(BoundsComp.class));
      if (index != -1) {
        nodes[index].insert(entity);
        return;
      }
    }

    entities.add(entity);

    if (entities.size > MAX_OBJECTS && level < MAX_LEVELS) {
      if (nodes[0] == null) {
        split();
      }

      int i = 0;
      while (i < entities.size) {
        final int index = getIndex(entity.getComponent(BoundsComp.class));
        if (index != -1) {
          nodes[index].insert(entities.removeIndex(i));
        } else {
          i++;
        }
      }
    }
  }

  public void retrieve(Array<Entity> entities, Rectangle r) {
    if (nodes[0] != null) {
      final int index = getIndex(r);
      if (index != -1) {
        nodes[index].retrieve(entities, r);
      } else {
        for (int i = 0; i < nodes.length; i++) {
          nodes[i].retrieve(entities, r);
        }
      }
    }
    entities.addAll(this.entities);
  }
}


Here is the clearing and inserting code:
1  
2  
3  
4  
5  
    quadTree.clear();
    ImmutableArray<Entity> entities = getEntities();
    for (int i = 0; i < entities.size(); i++) {
      quadTree.insert(entities.get(i));
    }


I have no idea what I'm doing wrong. Thanks in advance!

Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #1 - Posted 2016-05-14 21:03:47 »

Well, I spent quite amount of hours trying some things out and after QuadTree failed to work, I simply decided to post on the forums since I was very frustrated. I have realized the problem was in the constants MAX_OBJECTS and MAX_LEVELS. Since the values were too low, it resulted in only one quadrant and all objects on it. I just changed MAX_OBJECTS to 4 and MAX_LEVELS to 1000 and now it works.  persecutioncomplex Roll Eyes

Scratch that. Now some entities aren't even recognized for collision detection. Oh, maaaan!!!!  Angry
And after some time, it glitches out and marks all entities for collision detection no matter where I go.

Are there any obvious mistakes in the code? If not, I will post more details (including a video) soon.

Offline VaTTeRGeR
« Reply #2 - Posted 2016-05-14 21:38:33 »

Doesn't this corrupt the level of the node that is being split in line 43:

1  
final int level = this.level++; // level of child node is lower than parent node o.O


and should instead be:
1  
final int level = this.level+1; //parent node now has lower level than child node


maybe someone else finds something in the lower half Tongue
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #3 - Posted 2016-05-14 21:43:06 »

Doesn't this corrupt the level of the node that is being split in line 43:

1  
final int level = this.level++; // level of child node is lower than parent node o.O


and should instead be:
1  
final int level = this.level+1; //parent node now has lower level than child node


maybe someone else finds something in the lower half Tongue

Oh maaaan, this is exactly why I love programming. One such a small error and your head explodes. Roll Eyes

Thank you so much! Grin Grin

Offline Riven
Administrator

« JGO Overlord »


Medals: 1369
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2016-05-15 01:43:12 »

1  
boolean topQuadrant = r.getY() < horizontalMidpoint && r.getY() + r.getHeight() < horizontalMidpoint;

This will never yield true, unless r.getHeight() returns a negative number ofcourse.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings!
Offline chrislo27
« Reply #5 - Posted 2016-05-15 02:11:10 »

1  
boolean topQuadrant = r.getY() < horizontalMidpoint && r.getY() + r.getHeight() < horizontalMidpoint;

This will never yield true, unless r.getHeight() returns a negative number ofcourse.

I think this code (which was mainly copied from the tutorial) is designed for a Y-down system. The first clause isn't even needed because all you're really checking for is if the body is above the midpoint.
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #6 - Posted 2016-05-15 09:42:28 »

Thank you Riven and chrislo27!

I did some tweaking on the code and nothing seems to completely fix it. I'm confused about the implementation and don't even know how to properly write getIndex method. I'm so confused. I understand how broken the getIndex method is and I'm so confused by the horizontalMidpoint, verticalMidpoint and all of the checkings performed. If I used contains method in Rectangle class, would it be more expensive?

The code in the video is as posted originally.

<a href="http://www.youtube.com/v/lykaPKPhOZA?version=3&amp;hl=en_US&amp;start=" target="_blank">http://www.youtube.com/v/lykaPKPhOZA?version=3&amp;hl=en_US&amp;start=</a>


After some tweaking, entities selected for collision detection are all that are located in one of the largest regions the player is in.



getIndex method code used in screenshot:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
  private int getIndex(Rectangle r) {
    int index = -1;

    float verticalMidpoint = bounds.getX() + (bounds.getWidth() / 2f);
    float horizontalMidpoint = bounds.getY() + (bounds.getHeight() / 2f);

    boolean topQuadrant = r.getY() > horizontalMidpoint && r.getY() + r.getHeight() > horizontalMidpoint;
    boolean bottomQuadrant = r.getY() < horizontalMidpoint;

    if (r.getX() < verticalMidpoint && r.getX() + r.getWidth() < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      } else if (bottomQuadrant) {
        index = 2;
      }
    } else if (r.getX() > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      } else if (bottomQuadrant) {
        index = 3;
      }
    }

    return index;
  }

Offline chrislo27
« Reply #7 - Posted 2016-05-15 16:30:30 »

The top and bottom quadrant check differs if your world is Y-up or Y-down.

I actually made my own quadtree implementation after seeing this post yesterday.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
   /**
    * Returns index of where an element can be placed. Returns NODE_PARENT if it doesn't fit.
    * @param element
    * @return node ID (parent, NW, NE, SE, SW)
    */

   private int getIndex(E element) {
      int index = NODE_PARENT;

      final float xMidpoint = nodeBounds.x + nodeBounds.width * 0.5f;
      final float yMidpoint = nodeBounds.y + nodeBounds.height * 0.5f;

      boolean topHalf = element.getY() > yMidpoint;
      boolean bottomHalf = element.getY() + element.getHeight() < yMidpoint;
      boolean leftHalf = element.getX() + element.getWidth() < xMidpoint;
      boolean rightHalf = element.getX() > xMidpoint;

      if (leftHalf) {
         if (topHalf) {
            index = NODE_NW;
         } else if (bottomHalf) {
            index = NODE_SW;
         }
      } else if (rightHalf) {
         if (topHalf) {
            index = NODE_NE;
         } else if (bottomHalf) {
            index = NODE_SE;
         }
      }

      return index;
   }


However, that is for a Y-up system. The only change you need to make for a Y-down system would be to swap the top and bottom checks.

1  
2  
boolean topHalf = element.getY() + element.getHeight() < yMidpoint;
boolean bottomHalf = element.getY() > yMidpoint;


If you'd like to view the rest of my quadtree's code you can do it here.
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #8 - Posted 2016-05-15 19:24:56 »

I appreciate your help so much!

I forgot to add that I'm using LibGDX. As I looked into the code you linked, I see you're using LibGDX, too. The problem I face is the fact we're both using the same library and that it works for you, but not for me. I literally copied your code and quad tree is not working. At this point, I'm not even sure if I'm just cursed or what. I literally copied your code and it doesn't work. What?! Where is the problem here? How to even find the problem? I'm kind of freaking out right now because I cannot understand how it can work for you, but not for me. I even tried the solution for y-down systems just for the sake of it, but, logically, it didn't work.

I don't know where to look for the error. It cannot be in my BoundsComp class since it extends Rectangle and implements Component. Plus, the bounds of it are rendered so I can clearly see they are correct.

Here is the visual demonstration of what happens when I put your code in:


Offline chrislo27
« Reply #9 - Posted 2016-05-15 19:34:48 »

How are you inserting your entities into the tree? I'm doing it every logic update like this:

1  
2  
3  
4  
5  
6  
entityQuadtree.clear();
for (int i = 0; i < activeEntities.size; i++) {
   Entity e = activeEntities.get(i);

   entityQuadtree.insert(e);
}
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #10 - Posted 2016-05-15 19:36:30 »

I'm doing it on every update to the World class which happens each time Screen updates.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
  public void update(float deltaTime) {
    quadTree.clear();
    ImmutableArray<Entity> entities = engine.getEntitiesFor(quadTreeFamily);
    for (int i = 0; i < entities.size(); i++) {
      quadTree.insert(entities.get(i).getComponent(BoundsComp.class));
    }

    engine.update(deltaTime);
    viewport.getCamera().update();
  }


quadTreeFamily is declared like this:

1  
    this.quadTreeFamily = Family.all(BoundsComp.class).get();


I'm using Ashley extension for LibGDX, so that's what that is.

Offline chrislo27
« Reply #11 - Posted 2016-05-15 19:41:02 »

What actually is the problem? Is it that the entities aren't being registered for detection by other entities? Maybe a different way to test it is to randomly place the entities for testing rather than have it be a grid.
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #12 - Posted 2016-05-15 19:44:59 »

What actually is the problem? Is it that the entities aren't being registered for detection by other entities? Maybe a different way to test it is to randomly place the entities for testing rather than have it be a grid.

Lime rectangle in the screenshot represents player. Gray and blue rectangles represent walls, but blue rectangles are walls that are marked for collision detection by player. So, the problem is the fact entities are not registered for collision detection.

I will try to test it differently, although I doubt it will have different results. Just to add some more background to all of this, I'm creating Bomberman-like game and I actually need it to work with the grid like this. Does a game on that scale actually even requires quad trees? I don't even care anymore at this point, but all I want is to learn how to implement QuadTree so I can feel some sense of accomplishment again.

EDIT:
Wow, man. It actually works now. How would I go about creating a grid? Have some special entities that will be checked how? Combine spatial partitioning and quadtree? Use only spatial partitioning? Any suggestions?

Offline chrislo27
« Reply #13 - Posted 2016-05-15 20:01:09 »

Glad to see it works. I made a test for it anyway, which has the same colour coding as yours.



You can see that some entities are still called for checking when they're far away: that's because they don't fit directly in a node.

Since Bomberman is a grid-based game you can have a 2D grid of walls (boolean if you only need wall/not wall). However, if you don't want to really mess with having two separate collision detections (the entities and the walls) you can stick with what you've got. The quadtree definitely helps with collision due to the large number of walls, so keep using it.

Glad to help!
Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #14 - Posted 2016-05-15 20:13:24 »

THANK YOU, SIR!

Thank you for helping and providing useful information! I will give you cookies (them karma points) after the JGO systems allows me to.

I originally thought about implementing grid based collision detection, but since my next project will be some platformer, I thought I'd want to learn some broad phase algorithm for narrowing the amount of collision checks to perform. I decided to split the entities in two: one will be the part of the map you would get after creating it in Tiled or similar map editor and the second will be entities, particles and that kind of stuff that will be partitioned with quad trees. All of the collision checks will be sprinkled with bitwise collision filtering.

I wish I could abstract collision detection so I don't have to rewrite it with a different genre of game, but hey, I like it this way, too.

Again, thank you so much! Smiley


Side note: This is what happens with quad trees when you have a grid of entities:


Offline chrislo27
« Reply #15 - Posted 2016-05-15 20:30:25 »

Funny coincidence: I'm doing a little open-world platformer-ish game right now, so AABB collision was required.

You can check out this package of my AABB stuff. The resolver will take a list of entities (from the quadtree, preferably) and spit out a collision result (you should pool these) of what happened. It doesn't have broad-phase checking as of right now, but I'll take the time right now to implement it.Just added broad-phase checking to the resolver - it makes use of the path bounds rectangle that PhysicsBody can provide.

It works quite well. I use the resolver even with blocks (I pool a bunch of PhysicsBodies for the blocks) and it works perfectly. Other moving bodies work pretty well with it and it's quite fast with the quadtree.

Offline Ivan Vinski

Senior Devvie


Medals: 5
Projects: 1
Exp: 3 years


Learning how to place those pixels nicely.


« Reply #16 - Posted 2016-05-15 20:33:25 »

Thanks! I will remember to check it all out when time comes!  Grin

Pages: [1]
  ignore  |  Print  
 
 

 
Riven (28 views)
2019-09-04 15:33:17

hadezbladez (3957 views)
2018-11-16 13:46:03

hadezbladez (1434 views)
2018-11-16 13:41:33

hadezbladez (3954 views)
2018-11-16 13:35:35

hadezbladez (765 views)
2018-11-16 13:32:03

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

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

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

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

nelsongames (3834 views)
2018-04-24 18:15:36
Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

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
java-gaming.org 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‑gaming.org
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!