• FEATURED

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

## Why my quadtree is problematic?

25 replies to this topic

### #21Oberon_Command  Members

Posted Yesterday, 05:31 PM

The objects are being rendered and the collision algorithm is also running at the same time.

That is an error. Run physics, then draw.

L. Spiro

Even if the collision algorithm doesn't mutate any physics state, but only detects collisions for later processing?

Edited by Oberon_Command, Yesterday, 05:32 PM.

### #22babaliaris  Members

Posted Today, 02:36 AM

The objects are being rendered and the collision algorithm is also running at the same time.

That is an error. Run physics, then draw.

L. Spiro

Its working a little better that way.

I think its my tree that do not work's the right way. So lets see steo by step my tree. I wil first show you how i create the tree.

I decided to create a quadtree that will be static. So this is how i implemented it:

I create tree using an array to avoid dynamic allocation.

#-_-_-_-_-_-_-_-_-_-_-_-_-_-Constructor-_-_-_-_-_-_-_-_-_-_-_-_-_-#
def __init__(self):

#Starting coordinates.
self.x  = 0
self.y  = 0

#Starting width and height.
self.width  = 2**32 / 2
self.height = 2**32 / 2

#Array.
self.array = []
self.depth = 5

#Create the root node.
self.array.append( QuadNode(0, self.x, self.y, self.width, self.height) )
#-_-_-_-_-_-_-_-_-_-_-_-_-_-Constructor-_-_-_-_-_-_-_-_-_-_-_-_-_-#

#This is a geometric progression because if you know the depth of a
#tree the number of nodes will be: 4^0 + 4^1 + 4^2 +...+ 4^depth
#===================Calculate Nodes Number Method=================#
def __calculateNodesNumber__(self):
return (4**(self.depth+1) - 1) // 3
#===================Calculate Nodes Number Method=================#

#===========================Is Leaf Method========================#
def __isLeaf__(self, node):
return node.getChild(1) >= self.__calculateNodesNumber__()
#===========================Is Leaf Method========================#

#4 is the step.
#===========================Create Method=========================#
def create(self):

for i in range( 1, self.__calculateNodesNumber__(), 4):

#----------Creating children----------#
#----------Creating children----------#

#Get the parrent of the children.
parent = self.array[self.array[i].getParent()]

#Child 1 Bounds.
self.array[i].width  = parent.width / 2
self.array[i].height = parent.height / 2
self.array[i].x      = parent.x + parent.width / 2
self.array[i].y      = parent.y - parent.height / 2

#Child 2 Bounds.
self.array[i+1].width  = parent.width / 2
self.array[i+1].height = parent.height / 2
self.array[i+1].x      = parent.x - parent.width / 2
self.array[i+1].y      = parent.y - parent.height / 2

#Child 3 Bounds.
self.array[i+2].width  = parent.width / 2
self.array[i+2].height = parent.height / 2
self.array[i+2].x      = parent.x - parent.width / 2
self.array[i+2].y      = parent.y + parent.height / 2

#Child 4 Bounds.
self.array[i+3].width  = parent.width / 2
self.array[i+3].height = parent.height / 2
self.array[i+3].x      = parent.x + parent.width / 2
self.array[i+3].y      = parent.y + parent.height / 2
#===========================Create Method=========================#


Edited by babaliaris, Today, 02:42 AM.

### #23L. Spiro  Members

Posted Today, 10:06 AM

The objects are being rendered and the collision algorithm is also running at the same time.

That is an error. Run physics, then draw.

L. Spiro

Even if the collision algorithm doesn't mutate any physics state, but only detects collisions for later processing?

If physics has not been run, you aren't rendering the most up-to-date scene.  Adding special-case scenarios in which rendering may be accurate in cases where nothing has been moved only complicates the system and renderer.  Don't overcomplexificationatize things.

L. Spiro

Edited by L. Spiro, Today, 10:06 AM.

### #24Alberth  Members

Posted Today, 11:58 AM

    self.depth = 5
...
def __calculateNodesNumber__(self):
return (4**(self.depth+1) - 1) // 3

def __isLeaf__(self, node):
return node.getChild(1) >= self.__calculateNodesNumber__()

This looks somewhat horrible, depth is is a constant, so why do you run a floating-point pow() computation every time someone asks for 'isLeaf' ?

One optimization can be to cache the answer after the first query.

if self.answer is None:
self.answer = (4**(self.depth+1) - 1) // 3
return self.answer

Secondly, 4 == 2**2, thus 4**(self.depth+1) == 2**(2*(self.depth+1)) == 1 << 2*(self.depth+1). Bit-shifting is a few order of magnitudes faster than any floating point computation.

Finally, as self.depth is constant, just compute and store the answer during construction:

    self.depth = 5
self.nodes_number = ((1 << 2*(self.depth+1)) - 1) // 3
...

def __calculateNodesNumber__(self):
return self.nodes_number

further optimization may be possible depending on whether you actually need 'depth' or '__calculateNodesNumber__' at all.

__double_leading_and_trailing_underscore__ : "magic" objects or attributes that live in user-controlled namespaces. E.g. __init__ , __import__ or __file__ . Never invent such names; only use them as documented.

### #25babaliaris  Members

Posted Today, 12:57 PM

    self.depth = 5
...
def __calculateNodesNumber__(self):
return (4**(self.depth+1) - 1) // 3

def __isLeaf__(self, node):
return node.getChild(1) >= self.__calculateNodesNumber__()

This looks somewhat horrible, depth is is a constant, so why do you run a floating-point pow() computation every time someone asks for 'isLeaf' ?

One optimization can be to cache the answer after the first query.

if self.answer is None:
self.answer = (4**(self.depth+1) - 1) // 3
return self.answer

Secondly, 4 == 2**2, thus 4**(self.depth+1) == 2**(2*(self.depth+1)) == 1 << 2*(self.depth+1). Bit-shifting is a few order of magnitudes faster than any floating point computation.

Finally, as self.depth is constant, just compute and store the answer during construction:

    self.depth = 5
self.nodes_number = ((1 << 2*(self.depth+1)) - 1) // 3
...

def __calculateNodesNumber__(self):
return self.nodes_number

further optimization may be possible depending on whether you actually need 'depth' or '__calculateNodesNumber__' at all.

__double_leading_and_trailing_underscore__ : "magic" objects or attributes that live in user-controlled namespaces. E.g. __init__ , __import__ or __file__ . Never invent such names; only use them as documented.

You are right, but that doesn't really matter, because once the tree is ready, nothing of that will run again. All this happen's when the scene is loading.

Edited by babaliaris, Today, 12:57 PM.

### #26DoctorGlow  Members

Posted Today, 03:47 PM

You are right, but that doesn't really matter, because once the tree is ready, nothing of that will run again. All this happen's when the scene is loading.

But if it loads faster (possibly due to this optimization) it's still a win.