The brilliance of javidx9 is his humility, not once does he tell anyone that he has a PhD in computer science, and the head engineer of a major robotics company, he just wants to share the beauty of his craft with others in a gentle and kind way. I really like and respect people like him, thank you for making great videos!

@vid2422

2 жыл бұрын

Wow that's truly impressive assuming it's true (no offence I just can't believe anything I hear)

@bravefastrabbit770

2 жыл бұрын

@@vid2422 That’s right you shouldn’t just believe whatever is thrown your way, but instead make inductive inferences. If this Very knowledgeable tech guy who clearly operates on a level of abstraction way beyond the average person, says he had a PhD, and not just shows off but shares & teaches his knowledge on a far higher level than others within the same domain. I think its pretty fukken safe to assume he is being truthful, especially when everything about him just reeks of congruence 🤦🏼‍♂️

4:05 I will *not* stop giggling! lol

Such a coincidence! I was implementing, experiencing and burning my brain with quad trees and moving particles, I tink I will have a iconic OLC help :D

"I will assume this space is a square... and I am illustrating that perfectly with this rectangle..." -- Javidx9 hahahahahahha

One of your best videos, this was a real treat.

I'm not sure why people think that recursion is "bad". As long as the time and space complexity of the recursive algorithm is logarithmic, it is guaranteed to run efficiently. When the problem is inherently recursive, like the one brilliantly explained in this video, the code is absolutely more elegant and usually shorter. Great video BTW!

@ThankYouESM

2 жыл бұрын

I found out the really painful way that the recursive can run out of memory.

@jhfoleiss

2 жыл бұрын

@@ThankYouESM When we're starting out learning recursive algorithms this happens more often than we care to admit! It's ok! As you gain more experience, you come to realize the patterns that are associated with efficient recursive algorithms (and the ones that are not!).

@quentinquadrat9389

2 жыл бұрын

Recursion is bad with languages that does not know how to deal with recursively such as C, C++, Java ... (no tail recursion elimination) If you use language made for recursively (such as OCaml) this of course make algorithm simpler and code optimized (recusion becomes and iteration). And quadtree is not always an logarithmic algorithm: you can obtain "degenerated" quadtree: for example, an empty scene with highly detail house with plenty of rooms in the corner of your scene. You quadtree will looks like a list. Ok in this case you fire the graphical designer :D

David, I would like to give you so much appreciation for your tutorials, especially this one.

GREAT!!!! to see you back making videos my friend! John in Ireland, I have learn so much from you, thank you

great video, reminds me of the data structures and algorithms course I took last year. One assignment was putting map data into a quadtree to speed up location selection.

Like many have already said, the format of these "lessons" is invaluable, it so practical to comprehend. I've been mulling quad trees for an upcoming project and this is a great way to get the additional insight I need to make better technical decisions. -Really going to enjoy this, thank you.

I have been following along your channel for awhile now and its great! Cool thing is that your way of teaching is so efficient that I can remake these programs in completely different languages and pixel engines while creating the same thing! Can't wait to see what you have next for us. I quite like the game engine series too. They are great fun!

your videos are a goldmine of information, thank you

Fun fact: Because nodes in a list is "scattered", require memory allocation and node data is addressed indirectly, it is so slow that storing the data in a vector us usually quite a bit faster, even when you have 1mill elements. TLDR; Always check.

Amazing !!! Can't thank you enough for the amount of stuff I learned in this 1 hr 🔥🙌🏼

This got my attention right away, because I happens to muse about the same exact problems a couple years ago when I was creating my game during a college project. Unable to find a proper keyword back then, I ended up with a custom made algorithm. Quite effective and fast but with a lot of limitations, it only works for tiled maps and definitely doesn't support dynamic movement of objects. So I'm very excited how you'll make this dynamic!

im glad to have you back, im not even a native english speaker or program in c#/c++ this days but i learned more with you that my my college professors.

This was quite brilliantly mind-blowing, and you handling it in a modern c++ stl like workflow made it even more so. Thank you so much! This is such a powerful data structure! Also thank you for touching on the dirty word of recusing, hope u do more of this boundary crossing as I've since uni felt there's a lot of potential there... Just one i don't intuitively get

@javidx9

Жыл бұрын

Thanks buddy! Part 2 does indeed cover moving objects.

Yes!!!! Finally!!! Spatital partition video!!! Thanks David!¡¡¡¡¡!!

Wonderful explanation, thanks! I will show this to my CS students. I am looking forward to see part 2 :-)

Good video, explains in an easy way how quad trees work! I have some optimization thoughts anyway :) The first thing, it's that list, I understand that iterators not getting invalidated is a big advantage, but I'm not sure that it makes up for the speed that vector gives while iterating millions of objects. In this case, contiguous memory becomes huge. The other thing, but this is purely a design choice, I would have directly stored pointers (I think this could be a good place for raw pointers) in the tree, and used an external container to keep the objects. The idea is that the tree is purely a search structure and doesn't "own" the objects.

At university I used oct-trees (3d quad trees) to speed up some n-body simulations for galaxy formation. They're pretty cool!

@rishitsingh6621

2 жыл бұрын

Can I get the source code?

@JamesClarkUK

2 жыл бұрын

@@rishitsingh6621 afraid not, I haven't had access to it for a long time

@jamilaelkadia6630

2 жыл бұрын

how does octree work? since models have 3 dimensions, it's not easy areas

@JamesClarkUK

2 жыл бұрын

@@jamilaelkadia6630 you use the volume of the node instead of the area

@TheMrDemonized

10 ай бұрын

​@@jamilaelkadia6630it works the same as quad tree but with 8 octants representing cubes

As you said there are multiple ways of implementing quadtrees and you picked one. I think the main flaw with this approach is that if an object overlaps children 1 and 2, and I am only looking at child 4, the overlapping objects will be rendered as part of the parent, even though they are not visible. The alternative is to add objects to all the children they overlap, but in that case they will be rendered multiple times, which can also have bad side effects (especially when using transparency). In that case, your container can help if you store each item as a pair (object, rendered). You set that Boolean to true if the search determined the object must be rendered. However that requires you to clean those booleans on each frame. What you can also do is store the frame counter instead. This approach also breaks your quadtree's implementation of size. That is fixed by your container, but one could also keep track of the counter on each node and increment that counter when inserting an object. Finally, your approach automatically builds a tree of depth 8 if an object doesn't cross any edge. What I like to do is to split a node only if it reaches a critical amount of objects (say, if there is more than 20 objects, then I start splitting them). This is best for static trees though, as managing that gets quite hairy when working with dynamic trees. As always, it really depends on what you need. Thanks for the great vid!

Ty for your deep and quality videos!

Yayy another javid video!

Such a gr8 and usefull and fun this channel has thank you a lot my friend.

javidx9: pans the camera youtube compression: goodbye

Great tutorial as always

Hey Javidx9, nice to see you posting again. Hope all is well with the family. I am wondering, what would we need to do if we were to allow the rotation of our canvas?

@jhfoleiss

2 жыл бұрын

I would use a bounding box to represent the area of the shape.. thus the search/insertion logic would remain the same.

Ah the channel that made me love c++

What's interesting to me the most is that while these data structures are cool and all, taking the idea and applying it to your specific project is going to be objectively better, for example, platformer that's limited to either vertical or horizontal levels with little space in orthogonal direction, can work better if you have a vector of vectors, and in some less dynamic cases, vector of ranges into some static data structure, and if you can ahead of time limit the maximum size of a given level, you may aswell have statically allocated array, blazingly fast and no risk of memory leaks no matter what terrible programmer touches it. For example, let's say you're making a mario clone, and you subdivide each world into 32 tile wide chunks, and each of those chunks can have up to 16 objects (enemies) that aren't terrain... You can take player's coordinate, and use it to index into this array of chunks simply by using x / 32, which is very fast because power of two division is just a bitshift. Search is also fast, because you only ever need to check up to 16 objects in a given chunk, linear search will more than suffice. There, it's definitely not an octree, it's something faster and more cache coherent than octree, and fits this style of game perfectly. For vertical levels, you'd use y coordinate... For levels that have both you could have a matrix and divide into chunks by x and y and index into linear array directly via x * width + y... It's a bit less local but in the end will still be faster than an octree unless that octree is designed to have limited recursion which again, is just specialization for a structure that's in its idea, generic. Instead of an octree which has a lot of indirection, it's just dumb array that minimizes indirection. In the end, it all boils down into setting up your data in a way that makes binary search as easy as possible. For a very big world, ideally, you'd have a chunk system, and loaded chunks would be in a virtual matrix that follows the player, once again you can index into individual chunk by simply dividing up coordinates of object of interest to check which chunk you should look in. Games like minecraft seem to do it this way. Not to say that octrees aren't useful... After all, the idea behind them is how I came up with more efficient implementations when problem is well defined.

Great video, this and other ressources helped me to implement and understand a quad tree, but i dont get such insane result changes. I think it is because i test against 100-300 units rigth now. I believe a quad tree is better the more stuff is going on, so here i will test it soon with around 10k things and will see if it makes a difference. But nice video and nice dude, really nice to watch.

Great video!

Very cool. Another data structure that I like for spatial data is the gist index. These are a type of btree where subtrees may overlap. This helps to deal with the problem that the centre lines in world space probably intersect a lot of shapes. Why should the centre be special, anyway? The drawback is that a single shape may appear in more than one subtree, so the final filter is a little more involved than just checking the bounding box.

I love you, for what you do!

25:04 this right mr. officer

Hope you upload part 2 soon

When is the 2nd part coming out? I like when quadtree examples have the rectangles appear and you can see it subdivide. I think it demonstrates the point better than tracking the numbers.

Maybe octrees next...would a great to look into 3d partitioning... Big thumbs up for this one...

Don't forget that you can use a deque instead of a list. The vector is a poor choice if you don't know how many items to allocate (or reserve) in advance and you want to store pointers to the items in the container. The deque gives you a good compromise between a vector and a list in this situation. Another alternative is to use a vector as your main container, but to store indexes rather than pointers to the objects in your quad tree.

I see you store the subtrees using shared_ptr. Is that just a matter of habit or are there use-cases where you'd want to share ownership of these subtrees with other entities?

@jonatanlind5408

2 жыл бұрын

An interesting use case should be 'persistant data structures' though in this video it is probably a force of habit. These are typically characterised by how each node is read-only after construction. This allows for large datastructures to share internal data with other permutations of itself with minimal data duplication. As an example a simulation can use a quadtree to keep track of objects and this quadtree is a permutation of itself from the previous iteration. More interestingly perhaps is how such a quadtree can be copied for, say, serialization to disk with no data duplication and without introducing data races.

@quentinquadrat9389

2 жыл бұрын

If shared_ptr are purely internals (not exposed by public methods) it's indeed better to use unique_ptr (lighter but you need C++14 since make_unique is not given with C++11). If your class have getters on smart pointers, I prefer returning the reference of their content since the issue of shared pointer is who is the real owner ? At 21:58 deleting smart pointers (the root node) will implicitly delete children node, but we have to care that this implicit recursion does not make stack overflow like any recursive functions. In all cases, I would have tried a quadtree implementation without any allocations at all if possible: array

I had this on in the background while I was playing wow lol so I could be wrong as I wasn't paying full attention but you're already storing objects in shared pointers which means you can get away with having a vector instead of a list anyway? you then get the speed advantage of a vector as apposed to a list with little drawback (unless you're constantly adding and removing items of course)

Hey Javid, a nice follow up for a quadtree is the generalized KD tree, just saying... :)

hey nice to see you back my man

Awesome

Quad trees can be useful also when pixelating an image. I did this manually for Minecraft art by drawing grid lines to subdivide various parts of a non-blocky image. Its 3D sister, octrees, are good for voxelising 3D meshes. I'm not sure if Minecraft does the octree approach or the more complicated Marching Cubes algorithm.

@MCSteve_

2 жыл бұрын

no the game is completely rasterized. with a chunk loading system

@RealNekoGamer

2 жыл бұрын

@@MCSteve_ oh, I see

At 25:15, you first calculate if the item fits inside the child and then check if you can actually create a child. If you are actually at max depth, it's useless to check if the child can fit the item, you won't be using it anyway. So, as a small performance improvement you should put the check on max depth BEFORE the calculations for the child fit.

How wonderful video and channel this is. found it very informative channel, subbed and liked . a fellow creator

You could use a vector, just need to clear quadtree if vector resizing causes a reallocation. If you initialize vector larger than you would need, you only need to clear quadtree if inserting will cause reallocation. If you check vector size vs allocated amount before inserting, you will avoid glitches. If code is multithreaded, need to mutex insertions. A cheap price to pay on inserts, compared to always allocating on new insert with list.

Are you going to do a tutorial on how to generate a dynamic mesh from a quad tree?

Hello! I have long been interested in developing applications with a graphical interface, tried many GUI libraries (Qt, FLTK, WxWidgets, etc.) in C ++. I have always been interested in how the above-mentioned frameworks work (drawing queues, event processing). I tried to use the SFML graphics library and create a set of widget classes, but there were many questions about their effective rendering, event handling, and organization of the main program loop. So I have a question. Can you suggest some resources where I can get acquainted with the architecture of GUI libraries (with retained mode) and examples of their creation, because there is a great desire to try to create something of your own to gain new experience in this field? Sorry that it's not related to this topic) Thank you in advance!

Probably that's later in this video or a future one (haven't finished yet), but I had to write one of these for something recently and ultimately I ended up using Morton curve encoding which achieves almost the same result implicitly with a fraction of the memory and CPU cost.

@javidx9

2 жыл бұрын

Morton curves work well when combined with a hashmap and give great performance, if you can reduce your problem to the integer domain easily enough. Adding floating point area into the mix makes it a little more complicated however. Still people should read up on Morton for their implementations.

This reminds me of bounding box hierarchy traversal in ray tracing

Doesn't C++ allow adding custom iterators on your arbitrary data structures?

if you store the previous search results, frame by frame, you can get even faster "cached" results, because assumption the view point will not change much

@Jkauppa

2 жыл бұрын

if you want a static draw order, then store the draw order in the pointer list, ie, z-order depth, then paint into z-buffer

@Jkauppa

2 жыл бұрын

epic dude!

Nice information. However for 2d spatial acceleration I've never needed to use a quad tree. Instead the simpler spatial map has always done the job and is quicker then a quad tree to implement and at runtime. So it would have been good to hear what a spatial tree gives you over a simple spatial map, if anything. By spatial map I simply mean adding a reference to all objects to one large array where the objects X and Y coordinates are divided by some 'cell size' and that produces an index into the array (each array location is an array or list of objects at the location). If your world is absolutely huge with big areas on empty space, I believe spatial maps are more memory efficient (no need for any cells covering these empty spaces) , but apart from that are there any other benefits?

@jmscreator

2 жыл бұрын

I agree here, but it really does depend on the size of the world and the density of the objects, as well as the grid cell size.

Thanks for the video! I love the use of modern C++. Selfish idea: a series on WGS84 could be fun (totally nothing to do with me having to learn it soon 😉).

Hello Javid, I've recently been exploring graphs visualization for various graphs and trees. I was wondering if you can perhaps do something similar with Pixel Game Engine. I like your explanations and I'd like to see how you think through a problem like visualizing (eg. Binary Search Trees).

@jmscreator

2 жыл бұрын

A binary tree can be represented in nodes, where each child node rotates based on the parent connection.

@ashwinalagiri-rajan1180

2 жыл бұрын

@@jmscreator ok?

I was wondering why you were dividing the size by two when it should a quarter of the area, then I realised that size is a vector2, so you're doing 2 divide by twos :D

@javidx9

2 жыл бұрын

Lol yeah I guess you get used to working with coordinates that little oddities like that become second nature 😄

C++ One Love❤️❤️❤️

Enjoyable video. Would like to mention that you COULD use a vector instead of a list, if you referred to items in the vector by index instead of by their address (pointer or iterator). Then, even if objects in the vector are relocated due to reallocation, their offset from the beginning (wherever it is or becomes) remains the same.

Literally did the same mistake, but in my case I forgot to call initialize so I didn't have the size initialized :)))

All this time and the grape soda is still on the desk untouched...

You killed me with the balls joke

Question, during the last part of the video, where you changed the linear search from a vector to a list, do you then also need to change it from Debug to Release? Because I tried it with Debug and the screen was just plain white without showing anything, but for Release it worked fine. Why is that?

@javidx9

2 жыл бұрын

Because debug on a slowish machine is very very slow! It probably never even drew the first frame

@CB66941

2 жыл бұрын

@@javidx9 thank you for the explanation~

Nice, long time no see

3:32 ...what is "Space Thing on Twitch" lol. I am very curious now :D

@javidx9

2 жыл бұрын

Well you can start here, and watch all the mission logs on javidx9 extra channel! kzread.info/dash/bejne/gG2h0NqKfJfSaJM.html

It would be funny to imagine an artist (non-programmer) who only knows the audio track and has to illustrate it. ("I want to calculate the area of any children I might potentially have")

This might be a stupid question but at 37:38 why did you write typename there? Don't we write typename when we create the template and not when we use it?

@javidx9

Жыл бұрын

Templates of templates of templates can start to look a little ambiguous to the compiler. Typename helps it along.

why are the pointers to the subtrees shared_ptr instead of unique_ptr

hello i got the vita3k emulator code so i want to make it for android HOW I CAN MAKE THAT POSSIBLE?

@__top_5250

2 жыл бұрын

I ASKED HERE BECAUSE WHEN I GO TO REDDIT OR QUORA I CAN't pass throw verification of any browset

You very smart man

Can i use quadtree for more efficient tilemap rendering?

@javidx9

2 жыл бұрын

If all your tiles are same size, no, you always know where you are in a such a tilemap anyway. If they vary in size then quadtree is perfect for it.

Wouldn't deques instead of lists solve all the issues you're using lists for, while still being faster to iterate?

I wonder what is being used in 3D these days... In 2D it's quad trees, in 3D it used to be oct-trees, but now it seems to be bounding volume hierarchies

4:01 I love you.

How on Earth can I get this to work with a remove function? I've been trying for hours but there's this type conversion error and I can't figure it out. Has anyone gotten a working remove function?

QuadTrees Oct trees Binary space partitions K-d trees The four spatial partitioning data structures you should be aware of.

@Redmat527

2 жыл бұрын

What about bounding volume hierarchy?

@BudgiePanic

2 жыл бұрын

@@Redmat527 I haven’t encountered that one before. Add it to list.

@Ash_18037

2 жыл бұрын

You also completely missed the simplest (and often best) partitioning data structure: spatial maps (bins). So many people completely overlook these in favor of cooler sounding Quad trees etc when they only need bins.

The Quad Trees get a bit quirky at night...

"It's called Root because it's the top level of the tree." Zero irony, straight-faced. :D

where is the second part

43:40 But what about spatial acceleration structures through the medium of dance?

balls. kek.

Why `std:shared_ptr` for the quadtree children rather than `std:unique_ptr`?

It might be worth the memory savings to just re-calculate the child rects every single time rather than storing them. If this performance matters to you, benchmark your own implementation and find out!

The more modern C++ crawls to get the more ugly its syntax gets… 😩 If only you could learn Rust. Thanks for the primer on Quad 🌳s.

@javidx9

2 жыл бұрын

I agree that "modern c++" syntax gets messy, well the template stuff does, but I have absolutely zero interest in Rust.

Part 2 when? Are you ok? Lost motivation?

@javidx9

2 жыл бұрын

Quite soon actually. All will be explained in the video, but I needed some emergency surgery from which I've been recovering! Much better now though.

Why does this algorithm remind me so much of the classical Doom algorithm for fast rendering.

8:16 "Rather than fiddling about with the standard random library..." float(rand()) / float(RAND_MAX) * (b - a) + a; Seems like TWO uses of the standard random implementation. I was hoping for some sort of fancy modulo hack.

@anter176

Жыл бұрын

the random library has more advanced RNG than rand, which are better but more fiddly than just using rand.

Quad trees are cool, but why does nobody talk about R-trees? They're so much cooler.

@dandymcgee

2 жыл бұрын

I found out why.. because they're wayyyyyyy harder to implement. 😅 But still way cooler!

This is at the edge of my understanding but Quad trees as implemented in this video seems like "just" binary trees. Well two of them.

A few issue with this. You are storing 128 bytes for the rects of child nodes in the parent, these could be easliy computed on the fly, added to this you are heap allocating the child nodes at different times. These combined mean it is just a recipe for cache misses. The code also creates empty nodes up to the max depth until a rect contains the body, this is very wasteful and really you should not split a node unless it is required, such that it exceeds the maximum bodycount per node and depth is less than max depth. If a body spams more than one node then just store a reference to the body in each node that collides with, there is no need to store anything at a place other than a leaf.

Spatial acceleration structure? I barely know her.

yo

those arent balls, those are circle, i think

first

Stop giggling!

J

First

Stop laughing you say. I made it as far as Balls for everybody...

Would you ever consider stop using Hungarian notation for variable names?

@javidx9

2 жыл бұрын

Nope