Quadtree Explanation

Рет қаралды 114,846

Күн бұрын

Пікірлер: 63

@williammanning7207 5 жыл бұрын

Wow! I uploaded this thing for a school project 4 years ago and now suddenly it has 33k views? What a neat surprise. I'm glad it's helped people!

@TheWebPotato 4 жыл бұрын

Thanks for uploading, William. It helped a lot.

@VirtuelleWeltenMitKhan 4 жыл бұрын

Yep, well done explanation.

@longjohn7992 3 жыл бұрын

Oh That was ur old channel

@cancername Жыл бұрын

Thank you! This helped a lot!

@sunofabeach9424 6 ай бұрын

i dunno i was specifically looking for it thank you

@qwertyuuytrewq825 5 жыл бұрын

A long time ago I was playing Worms and wandering about that cool destructible terrain. Thanks for explaining how it could be implemented.

@NoVIcE_Source 9 ай бұрын

"squares are simple shapes and computers are very fast" this actually sounds like a cool quote

@baoduyhoangnguyen571 7 ай бұрын

9 years later this video just save my life and my project

@justhallowed8499 4 жыл бұрын

This video is still helping people 6 years later

@Thesoccerdood 9 жыл бұрын

Thanks so much!! Now I can finally go and read the complex description my class gave and understand it clearly now.

@acking0273 Жыл бұрын

ik this is eight years old at this point but still very cool, definitely going to testing with these too see how the visualization of the tree changes with terrain changes

@Ro_void 8 ай бұрын

Gotta love when random school projects are better at explaining the concept then the teacher

@jaadoo3591 7 ай бұрын

yo, which course are you pursuing?

@LucasofAppalachia 7 жыл бұрын

Very simple, concise explanation. Thank you!

@CYON4D 7 жыл бұрын

Great explanation of quadtrees. The terrain example reminds me of Worm's terrain system. I guess they used quadtrees aswell.

@oliverludwig6148 5 жыл бұрын

0:19 "...just like Worms or Tanks..."

@Kaiju_Tea_Party 7 жыл бұрын

Your voice gets MUCH louder at 1:03 and then gets quiet again.

@nathanielsaxe3049 6 жыл бұрын

That's cause that line was really important

@breemudi 3 жыл бұрын

squares are simple shapes and computers are very fast...✨

@cholushkin 3 жыл бұрын

Hmm, I tought we don't really need a quadtree in games like worms. There you just need to store a bitmap. And all game logic such as physics collision deyection, explosions and so on works with bitmaps. Good example of using a quad tree is finding a closest objects for a big ammount of moving objects

@manxuma123 Жыл бұрын

Thanks. Very interesting and informative

@TheRickCh 4 жыл бұрын

Concise and excelent video! Thank you

@guillermoraya3363 2 жыл бұрын

Neat little video, dude! Great explanation.

@zainulmuttaqin7565 3 жыл бұрын

very great explanation, this is pretty short explanation yet so easy to understand

@martinschurig1131 7 жыл бұрын

Excellent video!

@guanpenggao1463 3 жыл бұрын

great video and clear explaination

@afonsodolmen4759 3 жыл бұрын

So, the value of the root is the width and height of the canvas?

@Rouliousin 6 жыл бұрын

Thanks ! I just understand how quadtree works in spatial indexes !

@WhompingWalrus 3 жыл бұрын

Would this be much more efficient than storing the terrain as a 2d grid of binary values, and just interpolating if the display resolution is higher than pixel density?

@raniem4368 3 жыл бұрын

Yes, Because if you have a giant section with no terrain border, with your approach you would need to check each pixel. In this approach you check a section of pixels instead.

@WhompingWalrus 3 жыл бұрын

@@raniem4368 Ah that makes perfect sense - you only really store detail where it's necessary with this method, rather than always using the maximum amount of detail even on simple geometry/data. Thanks (:

@magicalpopsicalyt1 9 жыл бұрын

I like this explanation, thanks :D

@gummiglas5571 2 жыл бұрын

that volume difference at 1:00 hahaha

@abdelz1617 2 жыл бұрын

Great video, thank you!

@boz9370 5 жыл бұрын

Great explanation it really helped.

@izzyblackout1090 6 жыл бұрын

Can you do more explanation on this topic? Like how the octree programming code looks like?

@storerestore 6 жыл бұрын

Octrees are similar but extend into the third dimension. So instead of a rectangle at the root you have a box, and instead of subdividing it into four rectangles you subdivide it into 8 boxes. Traversing the tree to check for collision with a point can be done with a recursive algorithm that starts with the root box/rectangle: 1. Check whether the node contains the point 2. If it does not, return no collision 3. Check whether there is some element that you could collide with within the node (this should be a single flag for each node) 4. If there is not, return no collision 5. Check whether this node has child nodes 6. If there are not, return collision 7. Call into the function again for each child 8. If any of the calls to the children return collision, return collision There are some optimizations that can be made here at the expense of clarity. Some obvious ones: to avoid call overhead if you know that all points you'll check are contained within the root node, you can do the initial check whether the point is in a node for each child at step 7. You can also avoid unnecessary calls by returning early at step 7 if you find a collision, since a collision with a point can only ever occur within a single node.