Quadtree test

[tommohawkaction]

Hello all I’ve been messing around with Quadtrees lately, and I have came across this guys implementation which has some sort of weird effect

I followed this tut

Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

However please correct me if im wrong but the way Im using it makes entities not detect collision when moving from one node to another
Here is an image… of a sim I just made (All entities bounce of each other) You should see clearly what I mean

Untitled

Untitled

I made some changes to the code which fixes this issue but I find it rather odd why no one else has mentioned this… I feel like I have made a mistake somewhere

Here was my fix

	public void insert(Entity e){
		if(nodes[0] != null){
			List<Integer> indexes = getIndex(e.getGlobalPosition().x, e.getGlobalPosition().y, e.getWidth(), e.getHeight());
			
			if(indexes != null){
				for(Integer i : indexes)
					nodes[i].insert(e);
				
				return;
			}
		}
		
		// Fits in this quad
		objects.add(e);
		
		if(objects.size() > MAX_OBJECTS && level < MAX_LEVELS){
			if(nodes[0] == null){
				split();
			}
			
			for(int i = 0;i < objects.size();i++){
				Entity o = objects.get(i);
				List<Integer> indexes = getIndex(o.getGlobalPosition().x, o.getGlobalPosition().y, o.getWidth(), o.getHeight());
				if(indexes != null){
					for(Integer iq : indexes)
						nodes[iq].insert(o);
				}
			}
		}
	}

It basically uses the dimensions of the entity to see if it collides in any other node, then adds them all to an array for checking… the only issue with this is there is a higher chance of doing the collision check on the same entity twice, but its faster then checking every entity

[sarcastibots]

I’m not aware of any shortcuts around checking all nodes that an object intersects for collisions. Pretty sure I mentioned object insertion into multiple nodes in a blog post I wrote on spatial hashes for collision detection and likely any sources I referenced did too. So maybe the author was working with point objects that have no height or width, or that multiple node intersections is handled during collision detection and not object insertion.

the only issue with this is there is a higher chance of doing the collision check on the same entity twice

I haven’t read your collision checking code but if you’re only checking an object for collisions twice you probably have a bug. You’ll want to check for collisions with all objects in all nodes intersected by the object in question. Which potentially means lots of collision checks way more than two. As you point out this is still much faster than collision checking without a spatial index.

[h.pernpeintner]

No, you’re not doing it wrong, You encountered a known problem with (oct or) quadtrees when your objects have a size The problem that you check an collision between two objects twice is maybe because you iterate over all nodes… and don’t skip collision with nodes already handled by before from “the other object’s view”. But I didn’t take a look at the code.

The simplest solution is to collapse four cells of your quadtree and insert all nodes in the parent node, until every single objects fits completely into one node. As expected, this has worse runtime behaviour. Another solution would be to use a loose octree quadtree (this is googleable)…this uses a relaxed bound for each node.

[tommohawkaction]

@h.pernpeintner

No, you’re not doing it wrong, You encountered a known problem with (oct or) quadtrees when your objects have a size The problem that you check an collision between two objects twice is maybe because you iterate over all nodes… and don’t skip collision with nodes already handled by before from “the other object’s view”. But I didn’t take a look at the code.

The simplest solution is to collapse four cells of your quadtree and insert all nodes in the parent node, until every single objects fits completely into one node. As expected, this has worse runtime behaviour. Another solution would be to use a loose octree quadtree (this is googleable)…this uses a relaxed bound for each node.

Ah thanks, but for the checking objects twice is because I put the same object in two different nodes as their bounding box collides over both nodes… is this correct way of doing it?

[h.pernpeintner]

[quote=“tommohawkaction,post:4,topic:58927”]
Correct is whatever solves your problem. As you noticed already, checking twice costs twice as much as a single check but this accalerates your insertion/update for moving objects and you have plenty of them, it could be worth the price. I would tend to say that it is rather not correct, because I can’t think of a performance benefit over other solutions, such as a loose tree.