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.

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.

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.

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.

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.

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

i think its worth to check it out.

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.

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()