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.