Jump to content

View more

Image of the Day

Adding some finishing touches...
Follow us for more
#screenshotsaturday #indiedev... by #MakeGoodGames https://t.co/Otbwywbm3a
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.


Sign up now

Why my quadtree is problematic?

4: Adsense

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.


  • You cannot reply to this topic
25 replies to this topic

#21 Oberon_Command   Members   

5985
Like
0Likes
Like

Posted 22 March 2017 - 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, 22 March 2017 - 05:32 PM.


#22 babaliaris   Members   

108
Like
0Likes
Like

Posted 23 March 2017 - 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----------#
            self.array.append( QuadNode(i) )
            self.array.append( QuadNode(i+1) )
            self.array.append( QuadNode(i+2) )
            self.array.append( QuadNode(i+3) )
            #----------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, 23 March 2017 - 02:42 AM.


#23 L. Spiro   Members   

25554
Like
0Likes
Like

Posted 23 March 2017 - 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, 23 March 2017 - 10:06 AM.


#24 Alberth   Members   

9196
Like
0Likes
Like

Posted 23 March 2017 - 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.

 

By the way, your double leading and trailing underscore names are not advised by PEP8:

https://www.python.org/dev/peps/pep-0008/#descriptive-naming-styles , last item

__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.


#25 babaliaris   Members   

108
Like
0Likes
Like

Posted 23 March 2017 - 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.

 

By the way, your double leading and trailing underscore names are not advised by PEP8:

https://www.python.org/dev/peps/pep-0008/#descriptive-naming-styles , last item

__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, 23 March 2017 - 12:57 PM.


#26 DoctorGlow   Members   

1780
Like
0Likes
Like

Posted 23 March 2017 - 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.






Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.