Quad tree optimizations ?

clemetayer

Hello,

I'm making a game where I'm using a quad tree implementation have terrain parts that are destructible.

The implementation I made is running fine, but I have the feeling improvements can be done, maybe by using the GPU a bit more, or techniques that I might not be aware of.

So I'm making this post to know if it is possible to optimize it. This could help making bigger destructible terrains and (maybe?) use blocks with physics.

Here the code of my implementation (i commented it to explain the general principle) : The conversion from a sprite texture to multiple physical blocks covering it : https://github.com/clemetayer/Diggo/blob/master/Diggo/Scripts/Scenes/Maps/DestructibleSprite.gd The code of a physical block that can be destroyed : https://github.com/clemetayer/Diggo/blob/master/Diggo/Scripts/Scenes/Maps/BlockDestructible.gd * The block is a simple StaticBody2D with a sprite and an Area2D inside it : https://github.com/clemetayer/Diggo/blob/master/Diggo/Scenes/Utils/Blocks/BlockArea.tscn

Also, this is in a super work in progress state, so if you want to run the entire project, there might definitely be some issues.

dotted

Hm, for what it is worth, I would suggest considering using the physics engine to do all the collision detection for you. Besides running natively (c++), you can relieve yourself of having to manage collision detection yourself and let engine inform you of collisions.

Megalomaniak

This discussion was caught in the moderation queue since you have not confirmed your account yet.

Upon creating your account you should have received an account verification email. The confirmation email may have been incorrectly flagged as spam, so please also check your spam filter. Without confirming your account, future posts may also be caught in the moderation queue. You can resend a confirmation email when you log into your account if you cannot find the first verification email.

If you need any help, please let us know! You can find ways to contact forum staff on the Contact page. Thanks! :smile:

clemetayer

@dotted said: Hm, for what it is worth, I would suggest considering using the physics engine to do all the collision detection for you. Besides running natively (c++), you can relieve yourself of having to manage collision detection yourself and let engine inform you of collisions.

Thanks for the answer ! I think I am already using the physics engine to detect collisions. I was just wondering if there was any obvious optimization issues, but if there is not much I can do, that's still fine, the current code runs pretty smoothly as it is.

dotted

Well the call isBlockColliding is manual collision detection. This may be more than fine than using the physics engine contact/collision code such area Area body enter signals. Depending on your needs, the signal itself indicates you need to subdivide.

clemetayer

Hello, just a quick update, I came across this video from MrEliptik recently, which pretty much did what I had in mind :

https://youtube.com/watch?v=aBxk-n61SjM

I like this idea, since it doesn't create collision shapes recursively (which is costful in performance if this is done very often (like every frame for instance)), it is also fairly simple.

Specifically, I was aiming for something very similar to (which is mentioned in this video) :

https://github.com/matterda/godot-destructible-terrain

Plus, since you can set a texture in a Polygon2D, there is no need to worry about the sprite management inside it.

Oh, and my previous message may seem a bit rude, that was not intentionnal, English is not my first language... What I meant to say that the collision detection was indeed using the "on_body/area_entered", however, when subdividing the collision areas, I created a method to check if the new collision will collide with the body entered, to avoid creating it if that's the case (and save some resources). Still, this was not the best way to do it (which was the reason of this topic).