Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (541)
Games in Android Showcase (133)
games submitted by our members
Games in WIP (603)
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  
  QuadTrees / Spatial Data Structures  (Read 4498 times)
0 Members and 1 Guest are viewing this topic.
Offline Marksman Ken

Senior Newbie





« Posted 2010-05-25 10:50:30 »

Hi,
It was suggested to me here in these very forums that QuadTrees would be very useful for my problems and I researched into them and the theory looks great but the problem is I dont even know how to start implementing them in Java....

At first I thought it might just be a new type of collection but now Im starting to think it will be more complex than that.

Has anyone used quadTrees before for anything?
For me its to stop the program from drawing/calculating graphics offscreen and also for calculating the closest object to the mouse cursor which I am currently doing by iterating over a list and checking each object which proves waaaaay too slow when you are talking about thousands of objects at once.

Thanks,

Ken
Offline Marksman Ken

Senior Newbie





« Reply #1 - Posted 2010-05-25 12:21:23 »

So heres roughly how I think it would work just to show I've made an effort into thinking about it.

So I have a QuadTree class which has 4 subsequant collections (lets say sets for my purpose) which represent quadrants. So each of those sets have 4 more sets and each other those 4 sets which have 4 sets etc.
But of course they are only split up into 4 sets if its required.

What I cant quiite think of is how do I know when to split up a set into 4 quadrants and given a list of coordinates how would the quadTree class know where to put the points within its self...

Another thing I thought of is that I dont want the 4 quadrants to be split evenly because over a big area that could prove inefficient, but determining where the centre goes is yet another question.

The thing is Im sure I could figure something out but it needs to be 100% efficient because otherwise it defeats the point in the first place and it could make or break my project.

Thanks,

Ken
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #2 - Posted 2010-05-25 12:44:27 »

So I have a QuadTree class which has 4 subsequant collections (lets say sets for my purpose) which represent quadrants. So each of those sets have 4 more sets and each other those 4 sets which have 4 sets etc.
You wouldn't have four collections, but four child nodes.

Quote
What I cant quiite think of is how do I know when to split up a set into 4 quadrants
Usually you create the whole tree recursivly, dividing up the area into smaller quadrents at each step. Then you choose some threshold amount to decide when to stop recursing.

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  
class QuadTreeNode
{
  private QuadTreeNode[] children;
  private int x, y, width, height;
  private Set contents;
  public QuadTreeNode(int x, int y, int width, int height)
  {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;

    contents = new HashSet();

    if (width > 100 && height > 100)
    {
      int halfW = width / 2;
      int halfH = height / 2;

      children = new QuadTreeNode[4];
      children[0] = new QuadTreeNode(x, y, width/2, height/2);
      children[1] = new QuadTreeNode(x+halfW, y, width/2, height/2);
      children[2] = new QuadTreeNode(x, y+halfH, width/2, height/2);
      children[3] = new QuadTreeNode(x+halfW, y+halfH, width/2, height/2);
    }
}


Quote
and given a list of coordinates how would the quadTree class know where to put the points within its self...
Again, you do this recursivly. So you insert into the top level node, which tries to insert into all the child nodes and stops when it can't go any further.

Quote
Another thing I thought of is that I dont want the 4 quadrants to be split evenly because over a big area that could prove inefficient, but determining where the centre goes is yet another question.
I wouldn't bother with this IMHO. Firstly since your objects will be moving then the optimal point to split will be changing all the time. Easiest to leave it centered and get a generally good coverage than chose an off-center position which may end up being worse over time.

If you're worried about the extra nodes then make the quad tree sparse and only create child nodes when you actually need to insert something into them.

Quote
The thing is Im sure I could figure something out but it needs to be 100% efficient because otherwise it defeats the point in the first place and it could make or break my project.
It doesn't have to be perfect, the algorithmic gains (checking a subset rather than checking all objects) should provide a good improvement with even the most badly written quad tree.

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Marksman Ken

Senior Newbie





« Reply #3 - Posted 2010-05-25 13:03:42 »

Ah thanks for the great reply. I will look at this in more detail.

Well for the nature of what Im doing I might not have constant movement and the objects may be spread over a large area but your correct, I will just try to make something that works and then worry about more performance gains if its still not enough later.
Offline Marksman Ken

Senior Newbie





« Reply #4 - Posted 2010-05-25 19:29:14 »

Ok so I've started using the code you have gave me which is great but Im trying to taylor it to my needs more. first off I need to be thinking in imaginary units like metres instead of working in pixels because my graphics will be scalable. So although your 100 pixal threshold might work for an average game it would would not work in my case. The resolution of the QuadTree would need to adapt to the size of the area Im working with whether it be 100m or 100,000m.

Here is a better example of what Im after:
http://donar.umiacs.umd.edu/quadtree/points/pointquad.html

Thats a brilliant little applet!
Offline Orangy Tang

JGO Kernel


Medals: 56
Projects: 11


Monkey for a head


« Reply #5 - Posted 2010-05-25 22:06:23 »

Ok so I've started using the code you have gave me which is great but Im trying to taylor it to my needs more. first off I need to be thinking in imaginary units like metres instead of working in pixels because my graphics will be scalable. So although your 100 pixal threshold might work for an average game it would would not work in my case. The resolution of the QuadTree would need to adapt to the size of the area Im working with whether it be 100m or 100,000m.
So, what your actual problem?

There's nothing special about that 100 value, nor is the actual units specified, it can be whatever you want it to be.

Is the size of your world known beforehand or can it repeatedly grow larger and larger? What exactly are you looking for?

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline Marksman Ken

Senior Newbie





« Reply #6 - Posted 2010-05-25 22:38:21 »

Sorry If Im too generic.
It can change completely at any time, either in number of points or size.
So I've started writing a class that allows for more flexibility, Ill show you what I have so far.

Quote
class QuadTreeNode{
      private QuadTreeNode[] children;
      private double x, y, width, height;
      private Set<Point>contents;
      private BoundingBox boundingBox;
      public QuadTreeNode(double x, double y, double width, double height){
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;

        boundingBox = new BoundingBox(x,y,x + width, y + height);
        contents = new ArraySet<Point>();
        children = new QuadTreeNode[4];
    }

    public int size(){
        return contents.size();
    }
     
    public boolean isInside(double x, double y){
        return boundingBox.isInside(x, y);
    }

    public void split(double x, double y){
        double halfW = width / 2;
        double halfH = height / 2;
        children[0] = new QuadTreeNode(x - halfW, y - halfH, width/2, height/2);
        children[1] = new QuadTreeNode(x - halfW, y, width/2, height/2);
        children[2] = new QuadTreeNode(x, y - halfH, width/2, height/2);
        children[3] = new QuadTreeNode(x, y, width/2, height/2);
    }

    public void add(Point point){
        if(children[0].isInside(point.getX(), point.getY())
                && children[0] != null){
            if(children[0].size()>0){
                children[0].split(point.getX(),point.getY());
            }
            children[0].add(point);
        } else
        if(children[1].isInside(point.getX(), point.getY())
                && children[1] != null){
            if(children[1].size()>0){
                children[1].split(point.getX(),point.getY());
            }
            children[1].add(point);
        } else
        if(children[2].isInside(point.getX(), point.getY())
                && children[2] != null){
            if(children[2].size()>0){
                children[2].split(point.getX(),point.getY());
            }
            children[2].add(point);
        } else
        if(children[3].isInside(point.getX(), point.getY())
                && children[3] != null){
            if(children[3].size()>0){
                children[3].split(point.getX(),point.getY());
            }
            children[3].add(point);
        } else {
            contents.add(point);
        }
    }

      private class BoundingBox{
          private double minX, minY;
          private double maxX, maxY;

          BoundingBox(double minX, double minY, double maxX, double maxY){
              this.minX = minX;
              this.minY = minY;
              this.maxX = maxX;
              this.maxY = maxY;
          }

          public boolean isInside(double x, double y){
              if(x > minX && x < maxX)
                  if(y > minY && y < maxY)
                      return true;

              return false;
          }
      }
}

Its not finished yet but it should give you an idea. I need tio figure out how to get and alter the tree as data changes.
So now I have my tree if I have an x and y coordinate how would I go about using the tree to find the closest point in an efficient way?

EDIT: I have also come across another problem, I do not have set extents to the active area so if I setup a quadTree and then a point is added outside its extents Im abit stuffed...
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 847
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2010-05-25 23:37:20 »

So many bugs in so few lines Smiley


Your children are all over the place. Not even within the parent. This fixes it:
1  
2  
3  
4  
        children[0] = new QuadTreeNode(x + 0*halfW, y + 0*halfH, halfW, halfH);
        children[1] = new QuadTreeNode(x + 0*halfW, y + 1*halfH, halfW, halfH);
        children[2] = new QuadTreeNode(x + 1*halfW, y + 1*halfH, halfW, halfH);
        children[3] = new QuadTreeNode(x + 1*halfW, y + 0*halfH, halfW, halfH);


Order matters in &&
1  
2  
if(children[0].isInside(point.getX(), point.getY()) && children[0] != null)
if(children[i] != null && children[i].isInside(point.getX(), point.getY())


Use a loop:
1  
2  
3  
4  
5  
6  
7  
for(int i=0; i<4; i++)
   if(children[i] != null && children[i].isInside(point.getX(), point.getY())
   {
      if(children[i].size()>0)
                children[i].split(point.getX(),point.getY());
      children[i].add(point);
   }



Even with these fixes, the code you have won't really work well. The strategy of which child should take the point is not fully thought through.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Marksman Ken

Senior Newbie





« Reply #8 - Posted 2010-05-25 23:53:07 »

Thanks for the advice, yes they where silly mistakes from rushing, I need to sort out the code once I've got it working.

I dont know what is wrong with my strategy though, I thought it would be a very scalable system.

I think I may have come up with a system to find the closest point but I havent checked or tested it yet.

Quote
public Point getClosestPoint(double x, double y){
        Point closestPoint = null;
        if(isInside(x,y)){              //is the point within the bounds of this node?
            if(contents.size() > 0){    //Does this node contain any points?
                double closestDistance = contents.get(0).distance2DSquared(x, y);
                for(Point p : contents){
                    double distance = p.distance2DSquared(x, y);
                    if(distance < closestDistance){
                        closestPoint = p;
                        closestDistance = distance;
                    }
                }
            } else {
                if(children[0] != null && children[0].isInside(x,y))
                    closestPoint = children[0].getClosestPoint(x, y);
                if(children[1] != null && children[1].isInside(x,y))
                    closestPoint = children[1].getClosestPoint(x, y);
                if(children[2] != null && children[2].isInside(x,y))
                    closestPoint = children[2].getClosestPoint(x, y);
                if(children[3] != null && children[3].isInside(x,y))
                    closestPoint = children[3].getClosestPoint(x, y);
            }
        }

        return closestPoint;
    }

    public boolean containsPoint(Point point){
        if(contents.contains(point))
            return true;
        if(children[0] != null && children[0].containsPoint(point))
            return true;
        if(children[1] != null && children[1].containsPoint(point))
            return true;
        if(children[2] != null && children[2].containsPoint(point))
            return true;
        if(children[3] != null && children[3].containsPoint(point))
            return true;
        return false;
    }

If you have a better solution for me please do share as I am not exaclty an advanced programmer or specialist in this area but at least Im trying...
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #9 - Posted 2010-05-26 00:15:41 »

Seems to me like you're overcomplicating it, but I didn't really read much of that.

Typically you can craft your QuadTreeNode class to do the work for you.

1  
2  
3  
4  
5  
6  
7  
8  
9  
public Point getClosestPoint(double x, double y)
{
    QuadTreeNode bestNode = root.getClosestPopulatedNode(x,y);
    for (int i = 0; i < bestNode.getDataCount(); i++)
    {
        Point p = bestNode.getDataAt(i);
        //etc.
    }
}


Almost all tree traversal should be done by the tree itself. You should avoid all that sort of thing outside the tree as much as possible. In the above case, you would have getClosestPopulatedNode traverse down the tree finding the deepest node that also has data in it (following usual QuadTree traversal techniques). If you searched all children in a particular branch, search a different branch. Same as usual recursive traversal.

See my work:
OTC Software
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 847
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #10 - Posted 2010-05-26 06:01:53 »

1  
2  
3  
4  
5  
6  
7  
8  
                if(children[0] != null && children[0].isInside(x,y))
                    closestPoint = children[0].getClosestPoint(x, y);
                if(children[1] != null && children[1].isInside(x,y))
                    closestPoint = children[1].getClosestPoint(x, y);
                if(children[2] != null && children[2].isInside(x,y))
                    closestPoint = children[2].getClosestPoint(x, y);
                if(children[3] != null && children[3].isInside(x,y))
                    closestPoint = children[3].getClosestPoint(x, y);


Seriously, read your own code, try to understand what it does, and then fix it.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Marksman Ken

Senior Newbie





« Reply #11 - Posted 2010-05-26 07:18:54 »

Riven seriously, you might not like my method and you might think my code is messy but I don't sew any major problems in it. Maybe it's you who doesn't understand what I'm trying to do. If your just picking small faults with my code that's fair enough but it's not the purpose I'm here for.
My idea was based on the applet:
1. Does this node have points?
2. If not then it must have 4 more nodes
3. Run this same method on the 4 nodes
4. Eventually it would come to a point where there are no more children nodes where the points in the last node are checked.

Maybe it isn't the correct way and has fundimental problems but at least it was an attempt at a solution instead of just critising my lack of knowledge. If it's so easy why don't you tell me what the answer is?

Demonpants yes I see the best way would be to find the node first but isn't that pretty much what I'm doing above? I know it's over complex but I couldn't think of another way that would suit an arbiruary tree size and complexity. I don't know anything about quadTrees or their techniques which is why I'm here.

If there is a website that shows some useful techniques I could study then do tell me because I am a newbie and I think people like Riven forget that....

I'm actually building a simple terrain modelling tool, not a game itself and I think I haven't thought it through completely as I can't see how quadtrees could be effective in my needs now. I might start looking for another spacial data structure. I know of one program that uses triangulation for example. Any help or direction would be appriciated.

EDIT: I have been searching and I think I may have a better solution possibly, instead of using QuadTrees I could use R-Trees? Does anyone have experience with these:
http://en.wikipedia.org/wiki/R-tree
Offline lhkbob

JGO Knight


Medals: 32



« Reply #12 - Posted 2010-05-27 15:14:33 »

I've implemented an R-Tree in Actionscript. It was a couple of years ago but I remember that it's a beast to write, many hundreds of lines of code that could go wrong. It's a complex datastructure, especially compared to quad trees. If you're having difficulty with a quad tree implementation, I would suggest you avoid the R-Tree.  The R-Tree has its benefits but in all honesty, I think the simplicity of a quadtree and octree are preferred for many simple solutions (which is also why I'm not planning on writing a KD-tree).

Offline Marksman Ken

Senior Newbie





« Reply #13 - Posted 2010-05-28 12:05:06 »

Ah thanks for the great reply. Im glad you've told me that now, I think I will take your advice and avoid even considering them....
I would go with QuadTree but Im not sure how to make use of them in my situation. Is there any way of expanding a QuadTree effectivly without having to recreate the whole thing once you add something outside the initial extents of it?
Offline indexunknown

Junior Devvie





« Reply #14 - Posted 2010-05-28 12:36:14 »

static structures won't get you anywhere, octree is the 3d version of quadtree and here's a good article that might give tips and ideas: http://www.cs.nmsu.edu/CSWS/techRpt/2003-004.pdf
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #15 - Posted 2010-05-28 13:59:38 »

Ah thanks for the great reply. Im glad you've told me that now, I think I will take your advice and avoid even considering them....
I would go with QuadTree but Im not sure how to make use of them in my situation. Is there any way of expanding a QuadTree effectivly without having to recreate the whole thing once you add something outside the initial extents of it?

Each child of an octree node is itself an octree, so you can build a bigger octree that encompasses the new point and assign your existing tree to be one of the child nodes.
Offline Marksman Ken

Senior Newbie





« Reply #16 - Posted 2010-05-29 19:39:29 »

Ah that looks like an interesting document, I will give it a read.

Yes it did cross my mind that I could enclose the other existing tree in a bigger tree but getting the program to know how to do that might be tricky. How would it determine where the new extents of the tree would be?
Offline ryanm

Senior Devvie


Projects: 1
Exp: 15 years


Used to be bleb


« Reply #17 - Posted 2010-05-30 07:48:15 »

Each child node covers a quarter of the area of its parent, so the new root node should cover four times the area of the existing root node. Just double the width and height in the appropriate direction to encompass the new point.
Two alternative approaches:
  • Keep the existing tree structure as it is and just expand the bounds to include the new point - this would mean that every point in the tree would have to be removed and re-added though.
  • Just keep a separate unstructured list of points that fall outside of the tree boundary. If there aren't many of them this is the easiest solution
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Mr.CodeIt (24 views)
2014-12-23 03:34:11

rwatson462 (54 views)
2014-12-15 09:26:44

Mr.CodeIt (45 views)
2014-12-14 19:50:38

BurntPizza (86 views)
2014-12-09 22:41:13

BurntPizza (110 views)
2014-12-08 04:46:31

JscottyBieshaar (80 views)
2014-12-05 12:39:02

SHC (91 views)
2014-12-03 16:27:13

CopyableCougar4 (98 views)
2014-11-29 21:32:03

toopeicgaming1999 (157 views)
2014-11-26 15:22:04

toopeicgaming1999 (154 views)
2014-11-26 15:20:36
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
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!