timohausmann / quadtree-js Goto Github PK

Hello Timo,

First of all great work with the library.

I am writing to you as I noticed that your awesome library is missing a proper LICENCE file. I would be great if we could add it here.
If you're out of time atm, can also prepare a PR for you 🙂

Best,
Maciej

the x and y are 0, the width and height are 10, would it be like A or like B

I tried to use this quadtree to organise a set of tiles in the range from (0 / 0) to (4000 / 4000). There were 16 tiles in total, each 1000 wide and 1000 high. Each sub division of the tree should hold only one tile, so i specified a maximum of 1 element per division. After I inserted all my tiles the quad tree generated 4 sub divisions with 4 elements in each sub division (?). Ok, in doubt, I can live with that but then I tried to retrieve all elements in the given region: x 0 y 0 w 1000 h 1000. That is the upper left sector. I'd expected a result of up to 4 tiles. The function returned 13 of 16 tiles. If you number my 16 tiles (4 x 4 rows and cols) from 0 to 15 (0 upper left, 3 upper right) I'd expected the tiles 0, 1, 4 and 5. In fact I got 0, 1, 2, 4, 5, 6, 8, 9, 10, 11, 12, 13. The same strange behaviour occures in your example. But there I thought it might have something to do with javascript runtime and the movement in the scene. The quadtree seems broken to me. Maybe you could have a look on it...

I have a case where I am using this on the server side and I need to loop through all players, and, on each players loop iteration, I would do a tree retrieve with player object and then insert the player etc etc for up to 500 players. In your opinion is this the right approach? Each player has the x, y, width, and height, and unique id properties.

Pseudo-code:
tree.clear()
tree.insert(allBullets)
for each player in players {
player.update; // update this player position
var objs = tree.retrieve(player) // first retrieve against this player
// do coll checks with objs if any are found

tree.insert(player) // do this after so this player won't be in his own retrieve
}

This way we only loop through the players once and each one is checked against all bullets and the previous players already inserted so all player to player checks are covered.

If the insert method is used to continuously insert a large area of rectangles, and each rectangle overlaps with four sub nodes, the insert method will be infinitely recursive

As pointed out in the README, well, I think that updating points is a great feature to maintain.

The usual thing for this is the typical collision detector for games.

Sometimes I still need to compare half size of the entire object list. This way the algorithm is not very efficient as it is supposed to be. But this is a good demonstration. Maybe there is a better way yet to be found out.

I've tried using this library - seems like it ends up in an infinite loop here:

            while( i < this.objects.length ) {

                index = this.getIndex( this.objects[ i ] );

                if( index !== -1 ) {                    
                    this.nodes[index].insert( this.objects.splice(i, 1)[0] );
                } else {
                    i = i + 1;
                }
            }

I am observing objects that are selected for collision which are not in the node even not in the boundry

While using your quadtree implementation with geographic data I noticed in the split method the bounds are being rounded.

In my case it rounds latitude and longitude.

For example:

https://www.google.com/maps/@37.8113896,-119.7013997,9.98z

rounds to

https://www.google.com/maps/@37,-119,9.98z

I could transform all of my coordinates to some intermediate values but before I do that I wanted to just check in with you. Thanks.

I add random tiles of width 64,64 to my entire window and after adding 1 and doing a collision check at the other side of the window, I still get the first object returned.

Hi,
I'm looking for a quick way to retrieve the node an object belongs to?
When I use retrieve(), it returns the object for given bounds, but if I want to know which node or node path is leading to the object,
is there a way other than manually traversing the tree from top to bottom?
Thanks,

Hi, because the Quadtree is used in collision detection systems, and not all colliders have a rectangle shape. It would be awesome to see support for more primitives as colliders and maybe even support mesh shapes.

Here some info about how to implement this feature:
https://www.youtube.com/watch?v=ajv46BSqcK4

In large data point segments, how do you operate some queries, etc. How do you construct quadtrees with rectangles or line segments?

@timohausmann

Hey there -- thank you for the nice QuadTree implementation! However I'm noticing that there are often objects stored on the parent nodes as well as child nodes -- this shouldn't be the case.

See: http://stackoverflow.com/questions/4981866/quadtree-for-2d-collision-detection

In your fiddle you clear the quad-tree at every animation frame.
I need a more granular approach - to be able to:

1. Modify the coordinates of an object (x, y, width and height)
2. Remove an object
   I'm hoping to use your quad-tree inside of Backbone Game Engine.

I include the javascript library like so, as described in the tutorial.

<script src="/static/quadtree.min.js"></script>

And the code which attempts to use the quadtree:

        // Clear the quadtree of all entities.
        this.quadTree.clear();

        // Re-insert soldiers into quadtree.
        for(i = 0; i < this.troops.length; i++){
            var object = {
                x: this.troops[i].x,
                y: this.troops[i].y,
                width: this.troops[i].width,
                height: this.troops[i].height
            }
            
            // this.quadTree.insert(this.troops[i]);
            this.quadTree.insert(this.object);
        }

And the code which creates the quadtree:

    this.quadTree = new Quadtree({
        x: 0, y: 0, width: 1800, height: 1350
    }, 5);

When attempting to load the page in Firefox, I receive a TypeError exception: 't' is undefined. What on earth is going on?