Jump to content

View more

Image of the Day

「筋肉兄貴のスーパーラン!」
夕焼けにガラス・・・(´・ω・`)
ガラスは割りたいでしょうけど、割ったらクリアできないですよ。
(o・ω・o)
 #indiedev  #indiegame #screenshotsaturday https://t.co/fhKO5NJ5ee
IOTD | Top Screenshots

The latest, straight to your Inbox.

Subscribe to GameDev.net's newsletters to receive the latest updates and exclusive content.


Sign up now

Why my quadtree is problematic?

2: Adsense
  • You cannot reply to this topic
25 replies to this topic

#21 Oberon_Command   Members   

5818
Like
0Likes
Like

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.


#22 babaliaris   Members   

107
Like
0Likes
Like

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----------#
            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, Today, 02:42 AM.


#23 L. Spiro   Members   

25192
Like
0Likes
Like

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.


#24 Alberth   Members   

8463
Like
0Likes
Like

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.

 

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   

107
Like
0Likes
Like

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.

 

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, Today, 12:57 PM.


#26 DoctorGlow   Members   

1752
Like
0Likes
Like

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.