Sign in to follow this  
Followers 0
babaliaris

Why my quadtree is problematic?

25 posts in this topic

Hello!

I'm new to this forum.

I'm trying to create a 2D game engine and i've stuck in reducing the amount of checks for collision detection. My first implementation was a brutal collision detection (2 for loops) but that was too slow!!! Then i found out about quadtrees but i run into two problems.

First problem:

My game engine is working in a way that all the game objects inside a scene are moving except the game object that is attached in the camera. This is because i want to give the sense of a moving camera, so i have to move all the game objects (except the player) in the opposite direction that the player wants to move.

This is causing a big problem in my quadtree. The tree is constructed based on the positions of the objects, so in every frame i must re-create my tree because actually n-1 objects are change their position every frame (if we assume that the player is always moving and usually thats what players do  :p ). So i think that a quadtree might not be the correct solution for my problem. I think quadtrees are usefull for static objects. But as i said my world can't work without all objects are moving except the player. Re-creating the tree every frame is sloooooooooooow!!! One of the solutions i thought about was to not re-create the tree from scratch (because i know that creating new objects is a very slow operation plus the garbage collector is also slow) but to re-insert all the objects again inside the tree and at the same time removing the previous objects from the nodes (This is good because i don't have to remove them and then insert the new objects, because that would take double time). But this is also very slow because i need to insert n-1 objects in every frame to update my tree.

 

Second problem:

First see this picture: https://s26.postimg.org/dh5wos5l5/Untitled.png

The blue point is the position of the red object in the world. In the image you can see the worst position of the red object for collision detection. The position of the object is inside the first quad so if i search my quadtree for collision detections i will only check with objects inside the first quad. But as you can see in the picture the red object can collide with objects in the other 3 quads too. So my conclusion is that quadtrees are working only with single points not with rectangles, or my implementation is wrong.

One way to solve this is that when i'll search my quadtree for collision detection i will do 4 searches not one. One for the left up corner, one for the left down, one for the right up and last one for the right down corner.

 

How my quadtree is working:

Objects are inserted into the root. If the root reach a certain amount of objects (for example 20) the node splits to 4 subnodes and the objects are moving to the 4 subnodes based on their position. If an object can't fully fit intside one of the 4 subnodes it stays in the parent. The same logic applies to every node. So if i insert now a new object in the root it will find the corrent place inside the tree to be placed. Every time i insert a new object i also check if the node where the new object was placed needs to be split. So my tree do not have a depth limit.

 

My last conclusion is that quadtrees might not be the best data structure for my problem. I've searched so many times in the web and i can't find what to do!!! I hope you will help me.

Thanks. 

0

Share this post


Link to post
Share on other sites

Posted (edited)

If you want to give the illusion of moving the camera, then move the camera. It is unacceptable to move every single object in the scene but one instead of moving just the camera and one.

 

But how am i going to create a camera effect by moving only the player? I can only render objects inside the window resolution. How am i going to make objects disappear while my player is moving and new objects appear? The only way to do this is by moving all the other objects except the player and from what i've searched, games works likes this. Its not the player that is moving but the world, thats what i read somewhere in the web.

So is there a way to create a camera effect without moving all the other objects? If yes i would like to know it, it will be very useful.

Edited by babaliaris
0

Share this post


Link to post
Share on other sites

 

If you want to give the illusion of moving the camera, then move the camera. It is unacceptable to move every single object in the scene but one instead of moving just the camera and one.

 

But how am i going to create a camera effect by moving only the player? I can only render objects inside the window resolution. How am i going to make objects disappear while my player is moving and new objects appear? The only way to do this is by moving all the other objects except the player and from what i've searched, games works likes this. Its not the player that is moving but the world, thats what i read somewhere in the web.

So is there a way to create a camera effect without moving all the other objects? If yes i would like to know it, it will be very useful.

 

I found the solution! I will try it and i will come back to discuss further problems.

0

Share this post


Link to post
Share on other sites

Its not the player that is moving but the world
 

Game engines are usually separated into two parts. The simulation, where all the game objects live, and a renderer, which pulls all necessary information from the simulation to draw what the camera sees. The simulation works in "world space" and doesn't even need to know that a renderer exists. A camera is just another object within the simulation.

When the renderer wants to draw the world as seen by a camera, it constructs a view matrix for the camera. This matrix is what conceptually moves the world around the camera. But you don't do this yourself. That's the GPU's job, and it is very good at it.

You may want to read a bit about world, view and projection matrices.

4

Share this post


Link to post
Share on other sites

Posted (edited)

I created the quadtree. My results are:

With brutal collision detection the game was lagging with max 30 objects on the scene.

Now with the quadtree i can have 100-200 game objects max without lagging and that depends on where these objects are inside the scene. 

What do you think about this improvement? Can i do better?

I think 100 objects per scene is still not enough. I was wandering if i can have maybe 10.000 objects :P without lagging.

Edited by babaliaris
0

Share this post


Link to post
Share on other sites

babaliaris are you moving every object in the world every frame because they are actually moving them around or because you haven't implemented a camera yet?  If its because you haven't implemented a camera yet work on that first, because not only is it the right way to do things but its also faster and less confusing.

1

Share this post


Link to post
Share on other sites

Posted (edited)

babaliaris are you moving every object in the world every frame because they are actually moving them around or because you haven't implemented a camera yet?  If its because you haven't implemented a camera yet work on that first, because not only is it the right way to do things but its also faster and less confusing.

 

I changed that implementation and did this:

def renderScene(screen):
    
    for sprite in allSprites:
        
        sprite.render(screen, camerax, cameray)



class Sprite:

    def render(self, screen, camerax, cameray):
        
        render_x = self.pos.x + camerax
        render_y = self.pos.y + cameray
        screen.blit( self.image, (render_x, render_y) )

So every time i want to give the illusion that the camera is moving, i just update the camerax and cameray only, not the position of all sprites. The position of the sprites do not change but because of the camerax and cameray they render in different positions.

 

My problem now is this:

As you can see i go through all game objects to render them. Is there a way to divide my game world (with a quadtree) and say something like that:

 

If my camera box boundary is close to a subarea of my world, take that subarea and render only the sprites of that area.

I'm sure that this is delaying my game engine. Because if i have 1000 objects into the scene i must render every single object but this is not required because actually only a few of them will be inside the camera bounds. Of course the worst case is all of the objects to be very close to each other but this almost never happens in a game.

def renderScene(screen):

    visibleArea = quadtree.search(camerax, cameray, cameraWidth, cameraHeight)

    for sprite in visibleArea:
        sprite.render()
Edited by babaliaris
0

Share this post


Link to post
Share on other sites

Posted (edited)

How are you rendering the sprites? Are they 3D models or 2D quads with textures applied? What graphics API are you using (DirectX, OpenGL, openGL ES, etc.)? If you are using a hardware accelerated graphics API and rendering screen aligned quads with textures, even a low end modern GPU would practically sleep while rendering 1000 game objects. There is something going on behind the scenes that is causing the slow down; something you haven't mentioned. Edited by MarkS
0

Share this post


Link to post
Share on other sites

Posted (edited)

How are you rendering the sprites? Are they 3D models or 2D quads with textures applied? What graphics API are you using (DirectX, OpenGL, openGL ES, etc.)? If you are using a hardware accelerated graphics API and rendering screen aligned quads with textures, even a low end modern GPU would practically sleep while rendering 1000 game objects. There is something going on behind the scenes that is causing the slow down; something you haven't mentioned.

I didn't create the render engine by my self. My game engine is actually a wrapper of an other game engine called pygame https://www.pygame.org/news. Actually pygame is not a game engine but it has the basic tools like sound playing, image drawing etc that lets you create your own game engines.

Now in order to to render a game object i'm just drawing the image of that game object in the screen using the blit method of pygame https://www.pygame.org/docs/ref/surface.html#pygame.Surface.blit and i'm doing this every frame.

I also fill the screen with a color in every frame in order refresh the canvas.

Something like that:

def render():
    
    #This loop run's every frame.
    while the game is running:
        screen.fill(black)
        screen.blit( gameobject[i].image, gameobject[i].pos.toTuple() )
Edited by babaliaris
0

Share this post


Link to post
Share on other sites

How are you rendering the sprites? Are they 3D models or 2D quads with textures applied? What graphics API are you using (DirectX, OpenGL, openGL ES, etc.)? If you are using a hardware accelerated graphics API and rendering screen aligned quads with textures, even a low end modern GPU would practically sleep while rendering 1000 game objects. There is something going on behind the scenes that is causing the slow down; something you haven't mentioned.

His original post for the quadtree was about collision detection not rendering.

 

As you can see i go through all game objects to render them. Is there a way to divide my game world (with a quadtree) and say something like that:   If my camera box boundary is close to a subarea of my world, take that subarea and render only the sprites of that area.

You;re on the right track, I suggest you actually google an article on quadtrees to see how one is implemented.  Also you should look up how cameras are handled with a matrix in 2d, it's interesting and has some flexibility you currently don't have like scaling and rotation.

0

Share this post


Link to post
Share on other sites

Maybe because i'm using python and pygame i can't speed up more the engine. Maybe i need to create everything by myself from scratch with a lower lever language like c or c++.

 

Also i think pygame is using openGL.


 

How are you rendering the sprites? Are they 3D models or 2D quads with textures applied? What graphics API are you using (DirectX, OpenGL, openGL ES, etc.)? If you are using a hardware accelerated graphics API and rendering screen aligned quads with textures, even a low end modern GPU would practically sleep while rendering 1000 game objects. There is something going on behind the scenes that is causing the slow down; something you haven't mentioned.

His original post for the quadtree was about collision detection not rendering.

 

 

As you can see i go through all game objects to render them. Is there a way to divide my game world (with a quadtree) and say something like that:   If my camera box boundary is close to a subarea of my world, take that subarea and render only the sprites of that area.

You;re on the right track, I suggest you actually google an article on quadtrees to see how one is implemented.  Also you should look up how cameras are handled with a matrix in 2d, it's interesting and has some flexibility you currently don't have like scaling and rotation.

 

Yes you are right. My camera for now do not support rotation neither scaling.  But i think i'm a little stupid :p What i'm actually trying to do is solve problems that already have been solved the last 30 years. Maybe i should read a book or something and pause my project for now. I have found this book but i don't know if its good: http://www.gameenginebook.com/

0

Share this post


Link to post
Share on other sites

Maybe because i'm using python and pygame i can't speed up more the engine. Maybe i need to create everything by myself from scratch with a lower lever language like c or c++.   Also i think pygame is using openGL.

How many objects can you handle now? 

0

Share this post


Link to post
Share on other sites

His original post for the quadtree was about collision detection not rendering.


He wandered in that direction.
0

Share this post


Link to post
Share on other sites

 

Maybe because i'm using python and pygame i can't speed up more the engine. Maybe i need to create everything by myself from scratch with a lower lever language like c or c++.   Also i think pygame is using openGL.

How many objects can you handle now? 

 

100-200 max. If there are more, the fps drops to 0-20.

0

Share this post


Link to post
Share on other sites

100-200 max. If there are more, the fps drops to 0-20.
 

I'm not really familiar with python or pygame but that number does seem kind of low.  But I have some questions that might help someone else help you better.

For the 100-200 objects max, is that collision only or rendering too? What about AI?

Is that just moving objects or static objects as well?

Is that with the quadtree or without?

what version of python are you using?

Are you using hardware acceleration for your blits?(only relevent if you are including rendering)

Post your collision code.

What are your machine specs?  i.e. are you doing this on a 10 year old netbook?

0

Share this post


Link to post
Share on other sites

Posted (edited)

 

100-200 max. If there are more, the fps drops to 0-20.
 

I'm not really familiar with python or pygame but that number does seem kind of low.  But I have some questions that might help someone else help you better.

For the 100-200 objects max, is that collision only or rendering too? What about AI?

Is that just moving objects or static objects as well?

Is that with the quadtree or without?

what version of python are you using?

Are you using hardware acceleration for your blits?(only relevent if you are including rendering)

Post your collision code.

What are your machine specs?  i.e. are you doing this on a 10 year old netbook?

 

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

Until now i only tried n-1 static objects and one moving player.

I use the quadtree to get a list every frame and check if the  player collide's with at least one of the objects in the list.

I'm using python 3.5

I don't even know what is a hardware acceleration for blits. (Graphics card or something else?)

I have 8 GB ram, a 6-core AMD processor at 5 GHZ, windows 7 64, and an AMD randeon R9 series.

 

self.x and self.y are offsets which i can change in order to increase the size of the "invisible rectange" which i use for collision detection. origin.x and origin.y are the sprite's coordinates.

    #Collision algorithm.
    def checkCollision(self, other):
        
        #Check the rectangles x coordinate.
        if self.origin.x + self.x + self.width >= other.origin.x + other.x:
            if self.origin.x + self.x <= other.origin.x + other.x + other.width:
                
                #Check the rectangles y coordinate.
                if self.origin.y + self.y + self.height >= other.origin.y + other.y:
                    if self.origin.y + self.y <= other.origin.y + other.y + other.height:
                        return True
Edited by babaliaris
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

Posted (edited)

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
0

Share this post


Link to post
Share on other sites

Posted (edited)

 

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
0

Share this post


Link to post
Share on other sites

Posted (edited)

 

 

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
0

Share this post


Link to post
Share on other sites
    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.
0

Share this post


Link to post
Share on other sites

Posted (edited)

    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
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0