Coding Challenge #98.1: Quadtree - Part 1
Vložit
- čas přidán 8. 07. 2024
- In this multi-part coding challenge, I implement a Quadtree data structure in JavaScript and visualize it with p5.js. Code: thecodingtrain.com/challenges...
p5.js Web Editor Sketches:
🕹️ Quadtree Parts 1 & 2: editor.p5js.org/codingtrain/s...
🕹️ Quadtree - Part 3: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 Quadtree - Part 2: • Coding Challenge #98.2...
📺 Quadtree - Part 3: • Coding Challenge #98.3...
🎥 Next video: • Coding Challenge #99: ...
🎥 All videos: • Coding Challenges
References:
💾 Quadtree repo: github.com/CodingTrain/QuadTree
🗄 Quadtree on Wikipedia: en.wikipedia.org/wiki/Quadtree
Live Stream Archive:
🔴 Quadtree Live Stream: • Live Stream #128: Quad...
Related Coding Challenges:
🚂 #65 Binary Tree: • Coding Challenge #65.1...
🚂 #68 Breadth-First Search: • Coding Challenge #68: ...
🚂 #72 Frogger: • Coding Challenge #72: ...
Timestamps:
0:00 Introducing today's topic: Quadtrees
1:34 N squared problem
4:30 Big O notation
8:23 QuadTree class
11:15 Capacity
12:26 Insert points
13:30 Create a subdivide function
20:11 Recursively add points
21:12 Check if point is within boundary
26:49 Visualize the Quadtree
30:30 Use mouse clicks to add points
32:43 Edge cases
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: czcams.com/users/thecodingtrainjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#quadtreedatastructure #quadtreecollisiondetection #javascript #p5js
Just started teaching collision detection, those references are priceless 👌
WOW! I have been following your P5 videos for months and didn't even know this concept existed.
But yesterday I managed to build a quadtree on my own with no tutorial to decrease my grids processing time and I got it right just by imagining the outcome I wanted and messing around.
So how the hell did CZcams know I was looking for this and put this in my recommendations the next day??? Crazy
Omg this is exactly what I need for my simulation, THANK YOU so much for how clear you explain these stuffs!!!
I was going crazy from how dry every fucking person talking about Algorithms is. This keeps my attention, thank you!! What I needed!!
I think you missed an important thing!
When you put for example 11 points in a quadtree (with capacity 10), only the 11th point is stored in one of it's quadrants. Wouldn't it be better if all the 11 points are divided between the 4 quadrants? So what I mean is this: Shouldn't only the most specific quadrants (the leafs of your tree) hold the points? Then you could go recursively down the tree to find the quadrants that are not divided (the leafs) and there you find all the points that are in that specific quadrant. Because now you have points that are stored in a "higher" quadrant (one of the parent quadtrees) and exceed the capacity of a "lower" quadrant. In other words: the capacity of a small quadrant can be exceeded because because you also store points in quadtrees that are divided.
Ps: I love your videos! Especially your coding challenges!
That's an interesting question.
This definitely could be done, but I'm not sure how much it would improve efficiency in the end. And for simplicity it works "good enough" without doing so. I'd love to try adding this as a feature and see how it works!
I guess the only "slower" part about this approach is the construction: you have to give the points of a quadtree to its quadrant instead of keeping them stored in the quadtree itself. But the efficiency of the important part will stay the same: the search for points in a quadrant. Because you go down the tree no matter what! The amount of points you check is the same in both approaches.
I just found it a bit weird that in your design, there can be more points than the capacity in a quadrant. Capacity doesn't mean " max amount of points in an area" anymore when quadrants that are subdivided hold points themselves! It thought " max amount of points in an area" was the purpose of this variable?
Much love
Simeon
The problem comes when you are comparing the points; where you shouldn't be comparing any points in a quadrant that has been divided. The comparisons should only ever occur in the smallest child so having 10 points in the parent even though it has been divided is not true to the algorithm
Thanks for all this feedback! Suggestions for improvements can now be added as issues or pull requests to: github.com/CodingTrain/QuadTree
This was great. Never knew about a Quadtree.
This is the thing I wanted to learn but can't find any good tutorial. Thank you so much!
Just amazing man. So simply explained a "rather" complex looking data-structure.
first video I've seen from this channel. Just subscribed. Well described and actually very fun to watch. Cheers.
You sir, are a credit to your profession. Thank you for making such an understandable, for the layman even, introduction to this topic!
just watched your pak choi recipe video :) Looks delicious
I really like your enthusiasm!
my fave channel :)
In subdivide you could refactor by setting w and h to this.boundary.w/2 and thus.boundary.h/2 and reduce the number of divisions for that section to 2 from 16
I think others have said but only the lowest limbs of the tree should have the points, because two points could be on top of one another but one could be several steps away based on what order they were added to the array. One way to do this would be to refactor the if !this.divided, if it's divided then its point array should be kept empty so the point down through the tree, if it's not divided and there's space add the point here else subdivide and hand off the collected points from this branch down the tree structure.
You also do more checks than you need to for what rectangle each point is in because you check it in the rectangle and you check it after it arrives rather than before you send it, 16 checks for every layer the point passes through, if instead you check it's in the global rectangle at the start (4 checks for the top layer) then it can go in the tree and for each sub layer it passes through you only need to check if it's in the North vs South and East vs West, so 2 checks per layer seudocode: if inBoundaries(point) then tree.insert(point) and if point.y
great video. A small note : at 6:06 its actually *log2(1000) = 10 (with round up) * 1000 = 10.000* because the log in this case has base 2 (not 10 as the calculator has by default)
Yup, this was the comment I was looking for
Wouldn’t it be log4(1000) since it’s a quadtree?
@@davidmooers4072 log4(N) can be expressed in terms of log2(N) as:
log4(N) = log2(N) / log2(4) = 0.5 * log2(N)
All my tension was relieved when he said the word "visualize"😂
Wow. Simple, to the point demo
Oh! So that’s what a quad tree is. I want to say, you explained it really well and it was easy to follow, and being able to follow is a big compliment, because I wasn’t wearing my contacts, and was watching on my phone, so most people would be hard to watc, but you are easy :P
I love the scheme for mapping conventional x and y coordinates to cardinal directions. I always imagine a map of the US: everything gets higher as you move toward Florida.
This method is easily applicable to octrees as well. Thanks!
You can partially rebuild quadtree sections... you can change only the sections of a quadtree where the points change. Given its all a tree, just implement some tree-shaking to eliminate dead points and add new ones whenever your graph changes. Should be much faster.
How to do that? Can you explain lil bit more about the algorithm?
When inserting a point and you are over capacity and you subdivide and put that one point in one of the subtrees, shouldn't the points from the current tree also be distributed into those subtrees? So that only leafs have points ?
Thats exactly whats happening.
excellent video - really helpful to see you work it out as you write it, I learned a lot, very clear and understandable. thanks - subscribed!
Another way to do it would be, instead of "broadcasting" the new point to all the subdivisions and let them figure it out, to push the point to only the subdivision that could take it. It doesn't really matter when to do the check, but it seems to me more logical to let the parent feed each child instead of throwing them the pot... I know... best analogy EVER.
that defeats the purpose, because then you have to iterate over all of them always
@@jayocaine2946 yeah, I don't know what I was thinking 5 years ago but it made sense. I guess what I tried to say is, feed the points to the root, and let it route the points ONLY to their corresponding quad, so that quad can then route the point again. Binary search, but 2d.
At 18:00, when you created local variables to the function to make it more readable, you should've let w = this.boundary.width / 2, and let h = this.boundary.height/2, that way your formulas would be even more short and readable.
Great tip, thank you!
A minor thing I'm usually mindful of when writing non-exercise code: I might call those rectangles Quadrant, or something like that, just because one's brain will never expect a Rectangle to have its origin point at the center. Someone else reading the code might get the wrong idea, and also not feel the need to double check if it works as expected. Or I might read the code in 6 months and get the wrong idea myself. :)
Nice! Learned a lot!
33:35 there is a problem here, you can clearly see that some squares contain more than 4 points yet did not subdivide. I suspect this is, as was pointed out by others, because a tree that is subdivided is still allowed to contain points.
There is a bug in the rectangle.contains function, where he is including points in a rectangle where p.x >= (r.x - r.w). This is wrong. Should just be p.x >= r.x
@@sigmareaver680 Are you sure? The rectangle has its "pivot" in its center, so if the point get past the center on the left, it returns false, and it means it does not contains it although it does.
I think it's correct. by subtracting by the x.position by the width we make sure that the comparing point does not get past the further left limit.
damn. coding live is like the ultimate pair programming
Wow, so much excellent feedback! I've created this repo -github.com/CodingTrain/QuadTree - in order to allow pull requests to improve the implementation.
The link is broken, remove the ")" at the end of the url :)
thanks should be fixed now.
Quick Question: At 25:10
When he does things like not passing the required number of arguments to the QuadTree Constructor. Why is there no error while editing the code and or running it ?
great class! i enjoined and learn a lot! thank you!
cool tut!!!
Thank you!
Thank you sir you are the best
Don't forget to make use of your editor. You can forward highlight the duplicates of "this." and replace them with nothing, when you are refactoring at 18:02
A general note about optimization:
In many programming languages it's not a good idea to use the *new* keyword every call to update(). Reason being - in many cases this means that the operating system needs to talk to your hardware to allocate extra memory for the new object, and it carries a lot of overhead.
This can be avoided in many cases.
For example, in the case of the quadtree, it is possible to bound from above the maximum number of nodes that you'll ever want to use (probably depends on the max number of allowed collidable objects.
What you can do is a technique called pooling. You pre create an array full of rectangles ready to be use() and release(). When you want a rectangle you query this array and get a reference returned to you, and you just set the values, and set a flag to 'used'. When you're done, it simply sets the same flag to 'free'.
Since the quad tree is potentially and probably rebuilt every frame, this can significantly boost performance.
Note: it doesn't reduce the amount of operations, but it cuts overhead which in practical scenarios might play an important role.
For further reading Google 'pooling programming'.
lol, who are you teaching? I'd say this is pretty common knowledge.
Awesome vids. =))) Super nice
I felt your pain trying to figure out what to call the nodes of the tree
also linear interpolation makes figuring out how to set the values so much easier
I like your video. it is very straighforward.
When you were talking about the west on the right side, I was like "wow I never noticed, your camera records in mirrored image"
😂
I was stuck with this point, thinking why my implementation doesn't match the one in this video.
Still not sure, why he did (y - h/2) for north.
Is there an external concave lens used in the camera?
The parent should probably check which quadrant to insert into, instead of having each child check and verify. That way it's possible to bypass the boundary check completely if the point was sent from a parent. i.e "insertRandom" vs "insertInto"
Thank you !!!
Really helpful tutorial, thank you very much. One small tip:
At 17:40 you could've used the destructuring syntax from ES2015 like so:
let {x, y, w, h} = this.boundary;
Oh, great tip, thank you!
You're a genius !! When I see that I wan't learn Javascript !
I applied the QuadTree to a chart of dynamic nodes. It seemed to work but it feels a bit clumsy. Now, I came across the KDTree that seems to be more appropriate to my problem. It is used to find nearest neighbors in a multi-dimensional space. I think it could also work for your example. The code is much smaller and the logic is easier to apply.
I searched your vids and see that you have actually touched on the subject in this one. #70: Nearest Neighbors Recommendation Engine. But, you don't actually refer to the KDTree.
I wish I'd known about quadtrees before I wrote my 3D diffusion-limited aggregation sim in Processing. It has 12,000 particles which is 144,000,000 checks per frame. As you can imagine, it's incredibly slow!
"this is a thousand times THIS" *pointing at 1 million and then 10 thousand*. Not sure if I'm positive about this, Dan, how did elementary school go for you?
Loved it x)
Hi Dan, I love your channel so much and Thanks for the videos.
I kinda curious, do processing or p5 have a matrix calculation built in it so that we can perform a vectorized calculation?
Matrix and vector arithmetic is very simple to implement yourself if it doesn't.
Thanks Conrad. Sure do, but if we implement them ourselves, can we really avoid the for loop? while if there are built-in matrix calculation, we can avoid looping with vectorized code and the implementation would be faster of course.
Have you considered using quaternary numbers to reference section?
hi thats a great video! wonder, can i just use the QuadTreeNode ? it seems that i can save some cpu.. no?
This man does the equals sign at the beginning of the Google query.
I love you!
I love this guy! It would go a long way if he would spend a couple hours learning js a little more idiomatically. It hurts to watch the editing and operations struggles 🙏🏽
Thanks for the feedback! Are there some specific moments or bits of code you can share that I should take a closer look at?
@@TheCodingTrain Look into default parameters (to set capacity), destructuring assignment (un-nesting props, let {x, y, w, h} = this.boundary @ 17:30), and spread syntax (for return arrays/objects). Also, check out multiple cursors for fast simultaneous edits in your vscode/atom. You are awesome!
you need at most 2 xy points to define a square, and 4 xyz points for a cube, so nodes or boxes or whatever don't need dimensions, just 2 points to decide where to store a particle in each iteration. Perhaps you only add quad levels when you're adding a second point at that same node... and not until then... with a preset maximum depth.. moving already noded points to downstream quads. Perhaps this datastructure can be used in real time, with particles assigning themselves to the proper node at certain times, and events are raised when other particles are within their zone of interaction? Real Particles have a size, so edge-cases become even more complicated!
2 things:
First - the iteration number or complexity of the old one, nor the optimized one isn't bigening in an exponential rate... It's by a n^2 factor.
Second - the log calculation you have done on the calculator(on the Internet) is by a base of 10, while your nlogn complexity is not.
Just thought you should know...
Love your channel keep it going :)
Yes, thank you for these corrections!
Yes, thank you for these corrections!
So instead of using log10, we should use ln or it's a generic log?
@@ilieschamkar6767 I'm going to have to rewatch the video to answer that, my comment was 3 years ago 😅
I'll try to remember to do it later
@@orr4945 I've read in a comment that technically it should be log4, because we are dividing each quadtree four times
Thanks nonetheless :D
I tried your algorithm against a linear search (also using the same search window) and for some reason the linear search is going faster than the quadtree search? tried changing number of points, bucket size and searcharea / quadrants' size.
19:23 As you look done redoing your cardinal directions I have to ask why the north ones have -y and the south ones have +y?
For normal math where the origo is bottom left you would have to swap the + and - for the y, so I'm wondering if your origo is for the top left?
Shouldnt the Points that are in a quad be removed from that quad when it is subdivided and added to the correct child quads? So the points are allways the leafs of the tree?
I don't understand why there is no response to this valid question. Do you have anything that you can add to this yourself?
@@pravinpoudel1307
yes that is how it "should" be. when subdividing all points should be pushed into the 4 new quadtress and ofc removed from the parent. this way the ending quadtree of each quadtree are the containers of the data, not the parent nodes.
this makes data collection when you need it easier because you don't have to check EVERY tree, just the ones that are not subdivided.
How would it cope if you had a quad tree with a node capacity of 4 and you add to it 5 points with the exact same coordinates?
@@Fogmeister however you want i guess. but i think it would treat two points as 1 though it takes 2 slots in your array.
@@kayfoster7385 ah yeah, I've done this myself now and you can set a "max depth" for the entir tree. So that if you do get this scenario your don't end up with infinite recursion.
That bell is going to drive me crazy. D:
Great tutorial. Can you please help me with one question, in the class QuadTree of your code, the properties "this.northwest, this.northeast, this.southwest, and this.southeast" are all defined in subdivide() method of the class other than in the constructor method. Is it legal to do so, or is it better to put the following expressions: (this.northwest = null; this.southwest = null; this.southwest = null; this.southeast = null;) in the constructor method,then we can set their values in the subdivide() method. Many thanks for your help and time.
17:30 -> with es6 you can do something like : let { x, y, w, h } = this.boundary;
thanks for the tip!
can you use quadtrees to detect collision if you are not using points but circles?
can you do some videos on 2d physics engines? hit detection, collision resolution, angular momentum, etc? its too hard to learn on my own!
I have a question about quadtrees for collision detection. Why not just establish a fixed grid where each square corresponds to an array, and when an object enters a square it gets pushed into that square's array, and then each object only checks for collisions between itself and other objects in the same array as it?
How would you make the squares to be more like rectangles or any other shape? So they are not even squares within squares.
did I catch a bug or I missed some step, the first point before the capacity is not divide into any of the four region?
Looked for info on scene graph basics
Watched this, to be continued
Hmmm no part 2
Vid posted today, pfff gotta wait... Great info anyways, thanks!
How does it handle points on the edges of quads.. and the edge of the outermost..
I'm attempting to follow along hoping that it'll be more clear to me exactly how this functions, but at 10:17 my console still tells me that Rectangle is undefined even after referencing it in my HTML file. What's going on?
For everyone who is interested I've implemented and tested QuadTree against naive and "spatial hash grid"(SHG) algorithms. Here are results of these tests relative to naive algorithm:
100 entities: QuadTree is 20% slower, SHG is 2x faster.
500 entities: QuadTree is 3x faster, SHG is 8x faster.
1000 entities: QuadTree is 4.5x faster, SHG is 18x faster.
5000 entities: QuadTree is 17x faster, SHG is 88x faster.
10000 entities: QuadTree is 25x faster, SHG is 151x faster.
As you can see SHG is much faster than quadtree, it is also mush simpler to implement and consumes less memory. Though you should take this with grain of salt, as my implementation may lack something important.
Sorry for my bad english, I am french. You are drawing each point many times in your show function, because you should draw them when a quadtree is not subdivided.
Salut! I think that would be true for a tree system that passes its objects (points) down to a child node (quad). This quadtree system keeps its own points, and only passes points to a child quad that are *in addition to* its capacity.
...je pense.
Red Hen dev yes it's that
Great Shiffman!!! o/
You're so awesome, thanks for all
30:08 That larger cell near the top left definitely has more than 4 points.
The QuadTrees should be pushing their points down to their child tree when they subdivide. Right now cells have their own points AND their children have points. Unless you're not just using the leaves for storing the points, then go off I guess.
Also seems weird to instantiate a new QuadTree every time you subdivide, but that's just silliness with the naming.
@Ubayla
Correct. I think he needs to add within insert(point) after this section
if (this.points.length < this.capacity && !this.divided) {
...
}
Here:
if (!this.divided) {
this.subdivide();
for (var i = 0; i < this.points.length; i++) {
this.insert(this.points[i]); // Move points. down into divided quadrants
}
// Empty parent node's points
this.points = [];
}
I was laughing so badly hahaha.
Hey that's a really good video! I have one question: Could I theoretically use this code and somehow change it to an octree by adjusting the rectangle to a cube and adding the according z coordinates? Or if this doesn't work, is there any other way? This would be a big help! Thanks!
Absolutely you could do that! If you follow the basic theory of what he is doing, it shouldn't be terribly hard to implement! Of course drawing it to the screen is a different matter but yes you are very much correct!
I did exactly that. I would suggest creating the children in a for loop instead of assigning each of them a variable upon subdivision, though
The number of checks is actually 10 choose 2. 10! / (8! * 2!) = 90 / 2 = 45. The combination rule!
So big question here:
aren't u supposed to not have points in the connecting nodes of a quad tree? U are assigning points till a square is full, then for the next point you subdivide. But aren't u supposed to reassign the points that u already had assigned to the square to the subdivided squares?
I did a collision detection quadtree for 2d polygons and it took me 10 plus hours 😂
Hello! I have a problem with the insertion function, I dont know java, Im using GML(gamemaker language) which is object oriented.
I've been watching this video for like 8 hrs straight trying to figure out how to store object or class(if its how you describe it in java?) coordinates in to an array(which is the points array).
is it the object you're storing in the array or is it the objects coordinate? or both?
or am i doing it wrong? any tips? thankyou for giving a time! :)
So one thing that might help is that this is done in javascript, not java! Fundamentally different languages. In his code, he is storing Point objects (objects are *instances* of a class) in the points array. The points themselves then contain the coordinates. So, he would call a points coordinate by saying this.points[0].x; I do not personally know GML or how strongly typed it is, but what you want in this example is an **array** of **points**. So like you said, it is the object he is storing in the array.
Great video! one question though, every internal node in the tree currently contains 4 points itself with this piece of code, while its children also contain 4 points each, which comes down to 4*4 + 4 = 20 points for each internal quadtree node with height 1. Aren't KD-trees defined to use only their leaves to store points in? (4*4=16)
His tree is a bit "special" :P
Does the quadtree need to divided from the center point or can it be from the top left? Seems unnecessarily complicated to break out from the center.
It does not need to be from the center at all. I think the reason he chose the center is so that it's easier to determine the x and y coordinates of the sub boundaries. But yes you absolutely do it from the top left as well you'd just have to adjust your numbers!
In the subdivide function, instead of setting the x,y,w,h manually, you could instead have javascript do it for you! By replacing those with
let { x, y, w, h } = this.boundary;
Thanks for that wonderful channel) Your videos make coding fun! I hope one million subscribers get very quickly \_0_0_/
at 19:00 u have for NE and NW y-h/2 shouldnt it be y+h/2 because its where u currently are + half of the height to go up.
and SW SE should be '-' ?
with your rectangles where is 0,0 ? is it top left? im trying to do x,y,w,h into top_left x1,y1 bottom right x2,y2
the math is confusing me
i do not watch ur channel all the time but when i do see some of ur videos [ usually randomly ] i feel like i won't release !
I’m probably really late to ask this lol, but why does he not give the points already in the parent quad tree branch to the children subdivided quad tree branch, and then remove those references to the parent one? If let’s say it were to be used as a collision detection system, wouldn’t it cause problems not doing that?
at 36:00 instead of all those "if/else if" you can do:
return this.northeast.insert(point) || this.northwest.insert(point) || this.southeast.insert(point) || this.southwest.insert(point);
Thanks for the tip!
UwU
In your insert function, you almost had it, you only have to put the equal on two sides, solves the point in both.
36:30 hurts my eyes. just return a conditional with an OR operation with the 4 method calls
29:21 I think the points are drawn multiple times because that happens in the recursive function show(), maybe that's why it becomes very slow ^^
I don't think so -- since each quad only renders (shows) its own points, not the points of the parent quad, which has already rendered the points held in its own array. In other words, the function works by a parent quad rendering its own points, and then calling the show function for its child quads and *not its own show function again*.
The confusion (if I'm correct here) is about what 'recursion' mean here. In a sense, this isn't true recursion, because the function isn't calling itself, but the equivalent function belonging to a different (child) object. So, the 'recursion' here refers to the recursive nature of the parent-child quad relation for this data structure.
No they aren't. A point is only in one of the four quadtree's.
Actually what's happening is when a fifth point is added, the four original points are not divided into the four quadtree's.
Why quad and not binary here? Why divide the space by 4 instead of 2? Does it make the implementation easier with 4?
If you want to implement the printing of the quadtree without changing the structure you should use a visitor ;)
In the end, I think you do not need a QuadTree and Rectangle class. You can combine both of them into a QuadTreeNode, like you would normally do on a tree (there is no Tree but TreeNode)
Thanks, yes it's true! Thank you for the feedback! I wanted to have a Rectangle class so that the end user of the library could create geometry regions (also a "Circle" for example) without having the make a full node.
one question. Where is the x Position from the boundary, its centered or its topleft Corner or something?
x and y of the boundary are it's top-left position. (x, y) are offset by width and height (or w and h in his examples)
The one thing that is confusing me, and that I notice in yours aswell, is that you can draw more than the capacity in a square? If two are drawn before the first division, they are not counted for any further divisions in the given square. Not sure how much this matters, I think thats just for debugging and the algorithm still works, but not sure if thats a problem or not.
Usually you only check each particle to another particle once. You don't check the particle to itself and you check particle A to B and but not B to A again. But I'm sure you know that but just skipped over that.
What would be more interesting is a fast way of dividing a surface into triangles on each particle. Like you have a 2D plane with "obstacles" and
You gotta transfer all the tree's points when it's subdivided to its subtrees!!!!!!!
Why is it a problem towards the end 35:20 that the points are not part of multiple quads? wouldn't it actually be better in some cases to have them be part of multiple quads? so that way the particle/point is being collision checked in both of the quads.
Sorry for commenting so late but only just had the need to watch this vid, keep up the nice work man!
Nice! I always wonderd how colision detection is reduced to a useful amount of checks.
mostly through a combination a grid/tile engine implementation and being smart about what to even check with the information on the direction of the vectors mostly (ie, don't check the direction noone's going)
when you break down things into bigger tiles, you can avoid having to check a ton of expensive pixel or vector calculations
because you can already determine the objects aren't close enough by their tile/grid coordinates, and can already break out, which is most of the time for most checks when you have a lot of objects going around, so it scales like crazy with a lot of objects.
you can even choose to store the tile/grid coordinate AND the relative offset in the objects themselves,
it's way more data, but saves a couple of divisions and rounds in the main loop for when you need that extra object count.
if you just dupe the same monolithic object a gazillion times it's pretty cheap.
big saver there
but if they are close, then check their offset from that tile center, only when that passes, do the expensive stuff
that can still use raymarching to cheapen up the finer calculations, but most of that can be avoided by a simple grid coordinate system combined with the the object's relative position offset, to just break out all the non-contenders as quickly as possible.
the gains are already huge on a simple flat tile grid with no children.
when you think about it, an octree is really just a glorified tile/grid engine type of thingie :D