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

#1 babaliaris   Members   

107
Like
0Likes
Like

Posted 18 March 2017 - 06:47 AM

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. 



#2 L. Spiro   Members   

25192
Like
5Likes
Like

Posted 18 March 2017 - 11:38 AM

*
POPULAR

#1: 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.
As for inserting things into the quadtree, use my instant-insertion method: http://lspiroengine.com/?p=530
It will improve your insertion performance significantly, but there is still no excuse for moving every object in the scene.

#2: Your implementation is wrong. The bounding box of the object is used to determine where it is in the quadtree (instantly using my method), so if an object is in a cell of a quadtree it means the whole object is entirely in that cell.
That is why you can rely on any point on the object being in the same cell as all other points in the object.


The way your quadtree is working is inefficient and you are mishandling it.
Use an instant-insert quadtree and handle it properly. Stop moving all objects in your scene and move only the camera and player.


L. Spiro

#3 babaliaris   Members   

107
Like
0Likes
Like

Posted 18 March 2017 - 12:39 PM

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, 18 March 2017 - 12:41 PM.


#4 babaliaris   Members   

107
Like
0Likes
Like

Posted 18 March 2017 - 01:33 PM

 

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.



#5 lwm   Members   

2474
Like
4Likes
Like

Posted 19 March 2017 - 04:02 AM

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.


current project: Roa


#6 babaliaris   Members   

107
Like
0Likes
Like

Posted 19 March 2017 - 01:36 PM

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, 19 March 2017 - 01:39 PM.


#7 babaliaris   Members   

107
Like
0Likes
Like

Posted 19 March 2017 - 01:57 PM

I just found this: https://www.gamedev.net/resources/_/technical/game-programming/spatial-hashing-r2697

 

i think its worth to check it out.



#8 Alberth   Members   

8463
Like
1Likes
Like

Posted 19 March 2017 - 02:17 PM

Perhaps try a profiler first to see where the time is spent.



#9 Infinisearch   Members   

2809
Like
1Likes
Like

Posted 19 March 2017 - 07:27 PM

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.


-potential energy is easily made kinetic-

#10 babaliaris   Members   

107
Like
0Likes
Like

Posted 19 March 2017 - 08:25 PM

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, 19 March 2017 - 08:35 PM.


#11 MarkS   Members   

3409
Like
0Likes
Like

Posted 20 March 2017 - 02:52 AM

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, 20 March 2017 - 02:52 AM.


#12 babaliaris   Members   

107
Like
0Likes
Like

Posted 20 March 2017 - 06:28 AM

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, 20 March 2017 - 06:32 AM.


#13 Infinisearch   Members   

2809
Like
0Likes
Like

Posted 20 March 2017 - 06:32 AM

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.


-potential energy is easily made kinetic-

#14 babaliaris   Members   

107
Like
0Likes
Like

Posted 20 March 2017 - 06:39 AM

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/



#15 Infinisearch   Members   

2809
Like
0Likes
Like

Posted 20 March 2017 - 09:10 AM

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? 


-potential energy is easily made kinetic-

#16 MarkS   Members   

3409
Like
0Likes
Like

Posted 20 March 2017 - 10:59 AM

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


He wandered in that direction.

#17 babaliaris   Members   

107
Like
0Likes
Like

Posted 20 March 2017 - 02:32 PM

 

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.



#18 Infinisearch   Members   

2809
Like
0Likes
Like

Posted Yesterday, 10:02 AM

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?


-potential energy is easily made kinetic-

#19 babaliaris   Members   

107
Like
0Likes
Like

Posted Yesterday, 11:05 AM

 

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, Yesterday, 11:08 AM.


#20 L. Spiro   Members   

25192
Like
0Likes
Like

Posted Yesterday, 05:02 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