Quirky Quad Trees Part 2: Dynamic Objects In Trees
ฝัง
- เผยแพร่เมื่อ 7 ต.ค. 2024
- In this follow on video, I modify our Static QuadTree to allow its contents to move dynamically, and build a simple game demonstrating large arenas, with many thousands of moving objects, updated, rendered and interacted with at high speed.
Play In Browser: community.onel...
Source: Coming soon!
Patreon: / javidx9
TH-cam: / javidx9
/ javidx9extra
Discord: / discord
Twitter: / javidx9
Twitch: / javidx9
GitHub: www.github.com...
Homepage: www.onelonecod...
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) 😂
Lmao
Glad you're feeling better! Always a good day to see your videos :D
Ah , get well soon. Gall Bladder issues suck for sure!
Don't forget to call Free(&Gall_blader) so you don't suffer a memory leak inside your body 😁
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.
@@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.
Oh no! Glad you're better and back!
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.
@@javidx9 my friend had his removed and he said he couldn't eat many fried or oily things afterwards
Yes, glad to see you safe and well
Me, a C# coder, watching your c++ videos just because I enjoy your voice and explanations. That's how awesome these vids are.
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!
100% agreed
Glad you're back! You've taught me more about coding than anyone, including my college profs...!
I'm glad to hear you're better!
So glad you're fine! Get well and even better!
Glad to hear you're fully recovered! Nasty things, gallstones. Thanks for another very informative video and take care!
Thanks for another awesome video Javidx9! I hope you are feeling good! Your work is so creative and inspiring!
Glad to have you back!
A magic formula you might want to look into is Gargantini's linear quadtrees.
Great to have you back and delighted you are feeling better, John Ireland
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.
glad to have you back - hope you get spared from such stuff in the future 😅
Hey, nice to hear from you again! Thanks for the great video and all the best
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.
Excellent content again! Please take good care of yourself!
Glad you're back! Speedy recovery and great video as always!
Welcome back sir! Glad to hear your okay!
Totally worth waiting! Thank you, sir!
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 🖖
I kind of want to watch this again JUST to hear you talking about all the BOOGS in that forest. :)
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!
No need to apologize, when life hits its does so. Glad you're better again
Hey Javid! I'm glad you're doing better! My dad went through that.
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?
Glad to know that you're doing well, Javid. Welcome back!
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 !
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.
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!
Glad you're doing better dude, love the vids!
Glad you're feeling better 😷
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
Great work as always, good to have you back!
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)
Good to see you back and look forward to more excellent tutorials soon
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.
Nothing to apologize. We are all just glad you are fine!
so excited to see u again
That 5000 bugs line killed me
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!
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.
I love your videos man. Hoping to see more cool tricks soon :D
feel better javid!
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.
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.
A very good description of both can be found in paragraph 13.3 of courses.cs.vt.edu/cs3114/Fall08/Quadtree.pdf
Hope you're alright man. Don't worry about the delay, you had bigger fish to fry! Welcome back.
its been 82 years!
OMG :-O hope you're well now.
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.
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
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.
😁
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.
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.
Dont worry mate, i hope you good right now! Thank you for your videos!
good one
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?
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?
@@javidx9 Apologies, yes that's what I was implying. 🙂 Thanks for replying.
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.
@@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.
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. 😄
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
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 )
as always :) Gold on TH-cam
Glad ur back.
Is there going to be a next part to the multiplayer series?
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?
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.
Binary space partition data structure next?
When we gonna get "3d engine from scratch part 5 - no longer in the console"? Been waiting on that one to drop for awhile.
Glad you're back :)
assume you have to determine the closest other object (or/and occupied cell, for speed) every frame, ie, dynamic distance field
variable density paint program, very nice :) how about compression
LOD textures, in one program
do you like worms games, not the snake ones
what a tree murder, how about trying to optimize the more the bugs, the less the cleared forest, bushes
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
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.
Where is the source code?
Welcome
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.
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.
Thanks! The code is in the pixel game engine repo, in utilities folder.
@@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.
@@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?
@@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.
@@javidx9 Can I ask where was your images directory located in relation to the .sln file directory?
After 24 hours of playing, I have yet to find one of the 500 special books. 😉
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?
Sorry I forgot to mention the video, the A* algorithm regarding to path finding
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!
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..?
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
Finally
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.
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))
Hey Javid, have you considered making some Rust content?
Sadly, I have almost zero interest in Rust.
Yayyyyyyyyyyyyyyyyy your better 💜💜💜💜
Well, there is the thing that the C++ creator himself said about lists vs vector: th-cam.com/video/YQs6IC-vgmo/w-d-xo.html
So, if you need to iterate the list often it is more costly than the copy, shift, stuff vectors do when resizing.
I got lost as soon as iterators got added. I have no idea what they do and mean
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
jungle
vacced?
Hey dadio.
Sorry for your lost gall bladder. Not using the kiddo excuse.
Anyone looking for a good deed: Xournal+ could use these optimizations.
15:00 in, but why not using the selection box's bounds to remove?
...or get the coordinates from the object(s).
"Yes me lord."
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!?
first
i beat everyone
congratulations
😎