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
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
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?
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.
@@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 (:
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.
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!
Thanks for uploading, William. It helped a lot.
Yep, well done explanation.
Oh
That was ur old channel
Thank you! This helped a lot!
i dunno i was specifically looking for it thank you
"squares are simple shapes and computers are very fast"
this actually sounds like a cool quote
Gotta love when random school projects are better at explaining the concept then the teacher
yo, which course are you pursuing?
9 years later this video just save my life and my project
A long time ago I was playing Worms and wandering about that cool destructible terrain. Thanks for explaining how it could be implemented.
squares are simple shapes and computers are very fast...✨
Your voice gets MUCH louder at 1:03 and then gets quiet again.
That's cause that line was really important
Thanks so much!! Now I can finally go and read the complex description my class gave and understand it clearly now.
This video is still helping people 6 years later
Very simple, concise explanation. Thank you!
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
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
Great explanation of quadtrees.
The terrain example reminds me of Worm's terrain system. I guess they used quadtrees aswell.
0:19 "...just like Worms or Tanks..."
WE CAN ACTUALLY APPLY THIS!
Holy... but thanks anyway
Thanks. Very interesting and informative
that volume difference at 1:00 hahaha
So, the value of the root is the width and height of the canvas?
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?
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.
@@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 (:
I'm from 2024 drop your year
I like this explanation, thanks :D
I need u to be my teacher ngl 😭😭😭
still waiting on the Octree Explanation video
Concise and excelent video! Thank you
So this is how that game Worms was done... niiice
Wow ! :o
Can you do more explanation on this topic? Like how the octree programming code looks like?
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.
Neat little video, dude! Great explanation.
Does it approximate the gorund
dumbest comment in history
Excellent video!
Great video, thank you!
very simple thanks
damn thats smart
Thanks ! I just understand how quadtree works in spatial indexes !
Great Help Bro~~~~!
very great explanation, this is pretty short explanation yet so easy to understand
great video and clear explaination
Pretty good video!
very straightforward
thanks
Great explanation it really helped.
Thank you a lot!
very nicely explained in simple terms.
Nice explanation boy-o
*my next challenge
Thank you
Thanks !
Can you share code