Quirky Quad Trees Part 2: Dynamic Objects In Trees

[@javidx9]

Sorry for the delay folks! Play the example demo here: community.onelonecoder.com/members/javidx9/CreepyCrawleyCapture/ and also FOR SALE: ONE USED GALL-BLADDER (may contain stones) 😂

[@SpringySpring04]

Lmao Glad you're feeling better! Always a good day to see your videos :D

[@dune2themaker]

Ah , get well soon. Gall Bladder issues suck for sure!

[@Crysis762]

Don't forget to call Free(&Gall_blader) so you don't suffer a memory leak inside your body 😁

[@milktobo7418]

Do some research. 5 and 10 year outlooks after gall-bladder removal is very grim. Without it you will have your organs fail much quicker than normal. Fix your diet ASAP.

[@dune2themaker]

@@milktobo7418 In one word: No. Gall stones won't be fixed by any diets. You will die of gall stones if you don't "fix" it. (remove the gall bladder and stones). Also, if the surgery would have consequences where people would die of organs failing... it wouldn't be performed.

[@SolaFideSolusChristus266]

Me, a C# coder, watching your c++ videos just because I enjoy your voice and explanations. That's how awesome these vids are.

[@Kaltinril]

Oh no! Glad you're better and back!

[@javidx9]

Hey thanks Jeremy, I don't recommend gall bladder removal. It's not so much the operation, it's more the fact you can't sit in a chair for a month afterwards. Makes coding a challenge.

[@Kaltinril]

@@javidx9 my friend had his removed and he said he couldn't eat many fried or oily things afterwards

[@lozD83]

Yes, glad to see you safe and well

[@randylynn2057]

IMO - there's no better human doing coding on youtube than Javid!! Thank you always for your videos, content, and education. Glad the hospital episode is all better!

[@AMZG]

100% agreed

[@hiraeth1967]

Glad you're back! You've taught me more about coding than anyone, including my college profs...!

[@dimarichmain]

So glad you're fine! Get well and even better!

[@shadowleague2486]

A magic formula you might want to look into is Gargantini's linear quadtrees.

[@SassyToll]

Great to have you back and delighted you are feeling better, John Ireland

[@lorenzvo5284]

No need to apologize, when life hits its does so. Glad you're better again

[@DaTux91]

Glad to hear you're fully recovered! Nasty things, gallstones. Thanks for another very informative video and take care!

[@LifeIsACurse]

glad to have you back - hope you get spared from such stuff in the future 😅

[@isaacmiller4333]

Hey Javid! I'm glad you're doing better! My dad went through that.

[@mr_noodler]

Thanks for another awesome video Javidx9! I hope you are feeling good! Your work is so creative and inspiring!

[@ISKLEMMI]

I'm glad to hear you're better!

[@sebastiannicolaikaupe5175]

This was a nice series, thanks! What had me initially wondering, though, was the use of iterators while modifying the container they belong to. Turns out, this seems to be a special feature of std::list, whereas using std::vector in this way wouldn't have been possible. Didn't know that beforehand. Kinda makes me wonder how it is implemented.

[@richardmeyer418]

Glad to see you back and that you're doing better. Thanks for taking the time to educate us plebs. 🤯 I speak for myself, of course.

[@JonRowlison]

I kind of want to watch this again JUST to hear you talking about all the BOOGS in that forest. :)

[@haoyuwang268]

Excellent content again! Please take good care of yourself!

[@floydmorgan7739]

Welcome back sir! Glad to hear your okay!

[@gedaliakoehler6992]

Glad you're back! Speedy recovery and great video as always!

[@bernardorojas91]

It’s good to know your okay after that health issue. Might need to start looking into your diet ? I’m glad your doing better . Keep up your great work! Cheers amigo !

[@tapiocaferoz02]

Nothing to apologize. We are all just glad you are fine!

[@vincentcleaver1925]

Glad to have you back!

[@blarghblargh]

Oof, had my gallbladder removed about 10 years ago. The run-up events were the most painful in my life, lol. Good luck to you! Watch out for digestion after red meat once you're off the special diet

[@rishitsingh6621]

Glad to know that you're doing well, Javid. Welcome back!

[@MrKingmantas]

My dissertation was about quad trees and spatial hashing. Never thought about your project, looks really cool. Also I just started my graduate job after uni. Feeling great. Love your work btw.

[@javidx9]

Thanks, I think spatial hashing is the correct approach for the situations it's viable in. I'm pleased you're feeling positive! Good luck!

[@nils-kopal]

Really nice… only thing I missed is a smashed bug image when you clicked on one 😂. Also, very good you are back on track and healthy. Greetings 🖖

[@danhnguyen789]

Thank you so much for sharing such a great video! I wonder if you could expand the idea to an octree. I'd love to watch it too!

[@ilieschamkar6767]

Thank you so much for this couple of videos. It would be cool to see the difference in memory footprint between the static and the dynamic versions of the quad tree or some other benchmarks as well. I'm wondering, how an octree would differ?

[@dandymcgee]

Hope you're alright man. Don't worry about the delay, you had bigger fish to fry! Welcome back.

[@sephjfox]

Glad you're feeling better 😷

[@joaovitorgutkoskipaes1850]

Totally worth waiting! Thank you, sir!

[@oracleoftroy]

Your items know where they are, right? Instead of the linear search, you could have used the quad tree to search by location (or at least narrow down where to search). It wouldn't be as fast as what you are currently doing, but it would be faster than the linear search. In a situation like this where every single item is updated every frame, it seems like it might be better to bulk erase the entire tree and then re-add all the items. You wouldn't need iterator stability in that case, or any back pointers in the first place, so you can go back to vectors which would probably be faster (measurement needed, but cache misses with link lists add up). You should be able to design it so that it reuses already allocated memory as well, avoiding more extra overhead. You can always use two different trees for static and dynamic items. I'll have to dig out my Quad tree code. I was messing with them a few months before your first video came out, so it was neat seeing the different design decisions we made.

[@Merivio]

Merivio 0 seconds ago You might be able to mathematically determine which quad an item belongs in. That opens up potential for insertions to be as efficient as removals. For example, say every position and quad-size is a power of 2. You can find the quad-depth by dividing the item’s largest diameter, and location using its position. You would need a list of pointers to quads but this might be even more efficient, though I don’t know for sure.

[@davidstewart4228]

Good to see you back and look forward to more excellent tutorials soon

[@neozoan]

Oh goodness, Javid. My wife had her gallbladder removed a good 10 years back. She was in tremendous pain. So sorry you had to go through that.

[@dontbealoneru]

Dont worry mate, i hope you good right now! Thank you for your videos!

[@Crazen2]

Glad you're doing better dude, love the vids!

[@Linscape99]

That 5000 bugs line killed me

[@DerPille]

Great work as always, good to have you back!

[@EvilNui]

When it comes to visible tiling of a texture, there is a conceptually simple trick I like. 1. have a texture that is seamless with itself even when rotated by 90, 180, 270 degrees. 2. randomly rotate each tile. This breaks up the pattern at a large scale, and we still only have one texture.

[@patlecat]

OMG :-O hope you're well now.

[@Nodsaibot]

its been 82 years!

[@alexanderramirez158]

feel better javid!

[@yashenkin]

try using unique_ptr instead of shared_ptr for subtrees cause it has some redundancy against a unique_ptr (unique_ptr are almost raw pointers in the terms of performance and exactly same as raw pointers in the terms of occupied memory while shared ptr has strong/weak counters, storage space and additional indirection during dereferencing it)

[@xiben22_qaq87]

so excited to see u again

[@davep7176]

I love your videos man. Hoping to see more cool tricks soon :D

[@MrJloa]

You can also divide your game area into a grid of a size of your viewport. Then searching items on your world would narrow the search of youe viewing port in o(1) coz finding that cell in the grid would be as easy as i = x/w|0; j = y/h|0 Doesnt narrow the search below the viewport size like with quad trees, but narrows to the size of the viewport instantly and is faster coz we don't need recursions anymore. This technique might be better if your world is large, u have fixed viewport ie no zooming allowed and u dont have millions of items inside viewport. This strategy might be good for some RPG or RTS. Or may be u could also merge both strategies a grid + quadrant with little depth limit like 2/3 for the viewport grid cell. This would benefit both worlds, though zooming must not be allowed

[@birake8609]

good one

[@xbinxpurp6118]

Hello, I have been watching your videos and very happy I have found a new channel, wondering how long you had been around for! great videos I just had to come to your latest video to comment just to let you know how much help you have given me. you have my like and subcribe. alot of tutorials I cannot stand peoples voices but Im sure you get it alot but your voice is nice and subtle to listen to when learning if i am not watching and just listening. thanks for your content! cheers!

[@laureven]

as always :) Gold on KZbin

[@cesarecorsi5968]

Hi! i have a question .. if i wanted to build the tree with an abstract class how could i proced? Because the quad tree item instantiate the class itself but in the case of any abstract class is impossible to do that. Any suggestion? i've already tried with smart pointers but i can't figure it out.🙏 Thanks and sorry for bad english

[@cesarecorsi5968]

Got it! I simply modified the code of QuadTree Item and the insert method of the container a little bit. In the QuadTree Item instead of storing an instance of item, i stored a shared pointer to it, and in the insert method of the container instead passing a const reference to a OBJECT_TYPE i pass a reference to an shared pointer. i hope i explain myself in a good way, if anyone has another suggestion let me know. 😁

[@kwazar6725]

Glad ur back.

[@OktayCansinEmiral]

Welcome

[@DamienFromPoison]

I was wondering, where you were, but good to hear that everything is fine again. I hope your wife is well, too, as it must have been terrible for her, to see you in pain.

[@nooscrim3674]

What would happen at edgecases, eg. all rectangles are at the center, or forming a cross at the center of quadtree? All of them would be in the first quadtree and searches would be linear?

[@javidx9]

Yeah pretty much, it's a spatial structure which is really only optimal when things are distributed somewhat evenly. That being said, it's entirely context dependent too, so it can have surprising use cases.

[@mycotina6438]

Amazing video, crystal clear explanation! Enjoyed it so much. One question though, a little bit out of topic maybe. Currently I was following Karoly course on light transport (from the two minutes paper channel) -- They mentioned there a kd-tree data structure, which at a glance, looks very similar to quadtrees in regards of the idea and objective. I wonder which is preferred in practice, or maybe there's such condition when quadtrees work better but in others it will be kd-tree? Would love to hear some explanation on this.

[@krytharn]

A very good description of both can be found in paragraph 13.3 of courses.cs.vt.edu/cs3114/Fall08/Quadtree.pdf

[@starjohnson3040]

Glad you're back :)

[@CareyMcDuff]

When you draw the shrubs randomly on the screen, why do they appear so evenly spread? Shouldn't they clump up in random places? Is there a function that prevents a shrub from being drawn on top of another? (If so, apologies for missing it )

[@krytharn]

After 24 hours of playing, I have yet to find one of the 500 special books. 😉

[@CollinBaillie]

Why wouldn't you use the area under the mouse as a discriminator for your quad tree search? It lends itself well to the "Contains" functionality, and would have stopped you needing to add all that extra code. Sometimes, it's not about the memory usage. In fact sometimes it's not about computer resources at all, how about the human factor? Explain to me if I'm wrong, but you didn't really gain anything adding all that code, computationally at least, but you added another level of complexity for human maintainers of the code.

[@javidx9]

Well your point is valid of course, but let's not get too excited. "All that extra code" is about 25 lines in total. The "dumb" example presented is worst case, and assumes you simply don't know the position of the object you are searching for. Therefore it's yielding a worst case of O(N^2*log(N)). Adding additional information about location helps of course, but doesn't structurally tell us where the item is stored, so we can reduce the search to O(log(N)), as we still need to dive down the tree to find the containing quad. The final result, with the minimal book keeping overhead is O(1). The whole point of my approach to this solution is an expectation of many objects, so i felt it necessary to make sure bidirectional linkage between physical space and structural space is maintained.

[@BudgiePanic]

Binary space partition data structure next?

[@simaesthesia]

Really pleased that you have recovered okay! Great video as always. Instead of scaling the rendered detection rectangle, could you make a small modification to detect coloured pixels within the texture instead?

[@javidx9]

Thanks Simon! I'm afraid I can't visualise what you are asking. Do you mean the translucent white rectangle? And if so, do you then mean detect pixels within its area?

[@simaesthesia]

@@javidx9 Apologies, yes that's what I was implying. 🙂 Thanks for replying.

[@javidx9]

Detecting pixels within an area is actually pretty tricky 😄 since all this occurs on GPU there's no reasonable mechanism exposed by PGE for reading back areas you've rendered. You can, but it's far from trivial.

[@simaesthesia]

@@javidx9 Having reviewed my comments I suppose what I was trying to get at is; could you add another level to the tree based on the pixels in the bush "tiles". I just had my 8-bit head on, and have subsequently realised that even that idea has its fundamental flaws. I totally understand the non trivial approach to pixel detection and was trying to think of a way of mapping the pixels in the tree "in advance". Bit of a DOH moment! Best wishes.

[@javidx9]

Well I suppose you could keep the quad tree going down to the pixel level. It would be extreme, but no reason at all why it is not viable. You could store colour and and ID to the graphic, or an index and ID. 😄

[@Jkauppa]

assume you have to determine the closest other object (or/and occupied cell, for speed) every frame, ie, dynamic distance field

[@Jkauppa]

variable density paint program, very nice :) how about compression

[@Jkauppa]

LOD textures, in one program

[@Jkauppa]

do you like worms games, not the snake ones

[@Jkauppa]

what a tree murder, how about trying to optimize the more the bugs, the less the cleared forest, bushes

[@Jkauppa]

2d/3d-dda on grid/quad/oct-tree is the most useful individual ray tracing algorithm (most robust), assuming all worst cases, all rays individually accelerated in the grid, think a very dense voxel fog or tree leaves

[@Lymedin2010]

Love your videos! Could you PLEASE, please, please do a Star Fox clone on-rail movement, something like this YT video "Star Fox's Rail Movement Mix and Jam"? There has been a recent surge, buzz, & nostalgia for Starfox games.

[@ciberman]

Is there going to be a next part to the multiplayer series?

[@badwrong]

Well, there is the thing that the C++ creator himself said about lists vs vector: kzbin.info/www/bejne/j4LWZ3x5Ytuao9E So, if you need to iterate the list often it is more costly than the copy, shift, stuff vectors do when resizing.

[@squitz7056]

Where is the source code?

[@villson3960]

Finally

[@stuntfax9004]

Yayyyyyyyyyyyyyyyyy your better 💜💜💜💜

[@onogrirwin]

When we gonna get "3d engine from scratch part 5 - no longer in the console"? Been waiting on that one to drop for awhile.

[@alphenex8974]

Couldn't this be sped up way more by using instantiating for the rendering? Quadtree would only need to be used for updating the dynamic objects and instantiating rendering would do most of the heavy lifting of the rendering..?

[@Otakutaru]

Hey Javid, have you considered making some Rust content?

[@javidx9]

Sadly, I have almost zero interest in Rust.

[@ivanhoegc]

Hi javidx9, Thanks for your excellent work. In the absence of your code being posted, I have been working through the video, laboriously transcribing. I have struck a problem with the return from the DynamicQuadTree insert because VS22 says that " 'return': cannot convert from 'initializer list' to QuadTreeItemLocation". I have searched but have not been able to find anything relevant, so I am wondering whether you have any suggestions as to the source of the problem. I have the language set to c++20.

[@javidx9]

Thanks! The code is in the pixel game engine repo, in utilities folder.

[@ivanhoegc]

@@javidx9 Thanks for the prompt response. I see that the code is for the quadtree only (including quite a few differences). I had been hoping to get the tutorial code working, but I guess splicing in the new tree will be the next challenge.

[@ivanhoegc]

@@javidx9 Hello again, sorry to be a pest. I got the first part going and pressed on to try to reproduce the JungleExplorer part. When trying to populate with the trees, the program crashes while trying to calculate the vUnitSize factor. This is the error message - "Exception thrown: read access violation. **olc::Renderable::Sprite**(...) returned nullptr. The program '[9496] pge_test1.exe' has exited with code 0 (0x0)." The call trace points to line 3966 in the engine. Any thoughts?

[@javidx9]

@@ivanhoegc sounds like it didn't find your sprite file thus remains set to nullptr. Since it needs the file, to know the dimensions, I suspect when it tries to calculate unit size, it fails.

[@ivanhoegc]

@@javidx9 Can I ask where was your images directory located in relation to the .sln file directory?

[@CB66941]

I've only watched until 23:00, but I have a question. Did you also change m_pItems under DynamicQuadTree from a vector to a list? I am not sure if you showed that earlier

[@quentinquadrat9389]

Sorry, my English is not good, so I may not have understood all facts. Why not at 12:49 simply adapt your remove algorithm to erase by Rectangle instead of by Item ? With the mouse cursor, you know in which quadtree node you are pointing in. So just iterate on Items in this node. If the eraser diameter is too big, iterate on parent nodes. At 15:44 removing an element inside a vector when elements are independent can be simply swapping this element with the last one and then reduce the size of the vector of 1 element. Therefore, list is not necessary.

[@DFPercush]

I think he's just using search to obtain a list of items to remove, and then he can pass that directly to the remove() function. Kind of like remove(search(area))

[@gonzalodiazexcoffon7269]

Hi, im from Argentina. Im doing some homework for my university about pathfinding, do you mind if I use your video and the content in it for academical purposes?

[@gonzalodiazexcoffon7269]

Sorry I forgot to mention the video, the A* algorithm regarding to path finding

[@javidx9]

Hi Gonzalo, I've no problems at all with any of my output being used for academic purposes, though I do appreciate a citation where appropriate. Good luck with your work!

[@skejeton]

jungle

[@nolan412]

Hey dadio.

[@nolan412]

Sorry for your lost gall bladder. Not using the kiddo excuse.

[@nolan412]

Anyone looking for a good deed: Xournal+ could use these optimizations.

[@nolan412]

15:00 in, but why not using the selection box's bounds to remove?

[@nolan412]

...or get the coordinates from the object(s).

[@nolan412]

"Yes me lord."

[@ThoughtsOrange]

I got lost as soon as iterators got added. I have no idea what they do and mean

[@javidx9]

They allow the quad tree to be treated like any C++ container type, permitting traversal of all the elements in the tree in a conventional manner

[@user-hz5eh8sv9z]

Hi! do you accept orders for money to create a plugin based on the customer's ideas for the Revit program? I think this will be an easy task for you. I can write by mail more precisely if you are interested!?

[@rexinferi]

vacced?

[@MaxCE]

first

[@MaxCE]

i beat everyone

[@nates9778]

congratulations

[@GNARGNARHEAD]

😎