Only because threads can vary in their timing of when they run because they can be used by the OS. But if you write the code correctly, it will be deterministic because the objects won't vary according to which got updated first.
@@rorymax yeah but an entire os could be considered chaotic. Some process depend of the internet. The system is so complex it will never be deterministic unless unplugged from the internet and the code is running without an OS. Still an interesting topic tho, I want to dig deeper.
@@pascha4527 oh it’ll still be deterministic, there would just be so many variables that you’d never be able to replicate or even know all the starting conditions. But if you had all those variables, and enough time and computation power, you’d be able to determine the outcome
I would try out rust if I were you. It's like C++, but has a first party build system and package manager. It's also memory safe without a garbage collector!
Thanks for the new video! I've not done much related to programming, but collision optimization has been an interest of mine for quite a while. It's great to see such an easy explanation into spacial partitioning.
Back when I was growing up, Black and White 2 by Lionsgate was my jam. In the screen before the main menu, a bunch of particles streamed into a box and made the Lionsgate logo.... but you could also mess around with them using your mouse and screw the whole thing up. But if you didn't, it always ended up perfectly. I used to wonder how on earth they managed to implement a physics engine that kept producing the same result over and over, and now almost a decade later you've answered that lingering question. Keep up the amazing work!
I love seeing the grains appear in the crystal lattices that appear. I'd love to see this applied with more physics rules to simulate microstructures to create visual aids for understanding alloys, solid state chemistry, etc.
This is so satisfying :) It would be interestig to see how the chicken picture changed if you re-run the simulation with the exact same settings, except slightly changing the settings of one single object. Like i depiction of the butterfly effect. The more complex the interaction is, the more warping of the chicken should be visible.
Amazing video as always!! I love how you show a simple version of the code as a demonstration tool. Very similar to Sebastian Lague, I really hope I could get this good at video making at some point.
Watching the objects construct the image is so satisfying!! I'm sure if you made videos dedicated to showcasing more images being filled, and even made shorts, they would be very successful!
I LOVE YOUR VIDEOS!!! Your code is so elegant in so many ways, and your videography is perfect, plus your voice, just everything man, seriously awesome!
Such a joyful video dude. (I scrambled myself around 2 months ago to optimise an application with thousands of collidable objects , couldn't get the multithreading tho) Awesome job!
This is mind blowing. I always thought fluid/particle simulation is something very complicated, but here it is effortless. Thanks for the sources! I'll try to make my own engine using platform-independent compiler and graphic library.
I absolutely love how well you demonstrated the issues of multithreading in a very visual manner by showing how multiple threads could not produce the same deterministic result if overlaps between threads are not properly handled. I really feel like I learned some valuable things from this video. Thanks, it was awesome!
I know the acronym STEAM is a bit of a reach (STEM + Arts), but this work is truly at the intersection of science and art. Well done - and beautifully explained!
man, this is depressing and impressive at the same time. I've spent a whole year in last year of my BSc making a 2d physics engine and its still was wonky af to a point that its an embarrassment to show anyone, and here you whoop it up in like 2 months that is effectively a perfection
You also have to concede that thr yter only uses 2d circles, whose collisions are veryy easy to check and require much less work! Dont beat yourself up about it
You're going to learn a lot by trying, failing, then either figuring it out or seeing how someone else did it. The older you get, you don't stop failing when you try something new or difficult, you just know how much time to give yourself to figure it out. I get why it's depressing and impressive, but I hope that you're still excited to solve these interesting problems just so you can feel your own brain grow, you'll get there before you realize!
Each improvement increases the probability of the next improvement. You didn't spend a year making a 2d physics engine. You spent a year improving the quality of all future physics engines you will go on to build.
also he can only do this in two minutes because he spent years working on improving his skills and understanding. Keep going and you'll be amazed at how much progress you make.
This is so fascinating. I'm going to school so that I can work on stuff like this and it makes me so excited when I see videos like this. Thanks for all the insight.
I would be really interested to see the addition of other shapes to the simulation. Adding polygons or even non convex shapes would be a lot more challenging but very interesting.
Here's an interesting problem I ran into some months ago. I'd like to propose it to you and see if you come up with something cool, if you're interested. Imagine a 2D plane populated by entities with circular colliders, not dissimilar to what you're doing here. There is also an attractor entity which moves around arbitrarily. Each simulation step, the entities find the direction of the attractor as a normalized vector and store it as an intended direction of motion. They then check for collision with one another, and when overlaps are found, they add the response vector to their stored vector, so that they end up with a sum of all their desired motion vectors. This vector is then normalized and multiplied by the desired speed of the entity, so that they will move toward the attractor while repelling one another if they get too close. So far so good. The issue arose when I started using SIMD to accelerate the simulation and allow for more active entities. The SIMD radically improved the rate at which they can all find the direction toward the attractor, but for collision I ran into the problem that the data for the SIMD was not sorted into regions in order to accomplish the grid optimization like you did here. It's possible to sort them by their x positions, but it seemed like rearranging them this way for every update would take up more time than the SIMD calculation would save. Unfortunately, I set that project down because of some life issues and now I don't know if I still have it around, but I'd be interested to hear if you have any ideas about to deal with this kind of problem. Thank you for the great videos!
@@andreyrumming6842 Mainly, yes. The SIMD registers hold four 32-bit values, so I would select an entity to test and load it into a register twice (x,y,x,y) and then have a pointer to the other entities that would be used to load the other registers, then increment by 4 and continue loading, etc. By interleaving the loads and the math it was possible to get good performance from this, because one register could be working while the next is loading, and each register is doing the math for two entities at a time. This required the position vectors to be serialized, so each entity had an index into an array of x,y pairs. This meant that sorting the pairs would also require updating the indices in the owning entities, which was another layer of complexity. I'm certain that big game companies with fancy physics engines have some way that they're able to cheaply sort entities so they don't have to do On^2 collision tests every frame. I just don't know what that method is. Alternatively, they may all just be doing this kind of thing in CUDA or something.
This is an awesome video! It seems to me if you wanted to simulate objects with an arbitrary radius you would need each cell to be the size of the largest object. I'm not sure if there's a better way to do it, but maybe that's a good idea for a follow up video?
you could make the object register into multiple cells and also read a larger neighborhood. That being said, as far as I know there are other space partitioning techniques which don't use a fixed grid and are more adaptable
Wow! So cool! I have loved the idea of known-future-simulation-states for 'formation' effects (I work in vfx) and this really did that in a superb way, top work Pezzza!
Great video, it was already clear from your previous ones but you underscored it well here :) Also I think you should switch the order of y and x loops at 5:00 for better memory access in canonical order
I am not using 2D arrays (which are indeed row major). I use column major because it allows for better load balancing between threads since in the simulations of the video objects are horizontally spread
A great tutorial! I usually just do a dt step followed by N collision steps, gotta try your substepping method sometime :) I've once made a similar tutorial, without threading but with friction, damped springs, and ball-stick collisions.
The big advantages with sub steps is that, since objects travel smaller distances in one physics frame, errors are a lot easier to handle for the solver and it also greatly mitigate the tunneling effect, leading to way more stable simulations
@@tetryds I've done some chemistry simulation in Lennard-Jones potential, it's pretty fun to play with, trying out different combinations of interaction parameters. I have several videos on this topic on my channel.
@@tetryds Molecular simulations are not exactly difficult though. There is much to do in implementation but the principles are not much more difficult than this.
Awesome as always! I'm curious if the grid-iterating approach causes any kind of bias in the physics? Like if updating the collisions left-to-right in the grid adds any kind of preference for stuff moving to the right?
I'm curious about that too.. For something like this, I'm not sure how much further benefit could be obtained by using k-d trees. Tho I'm by no means an expert on them, in this case I wouldn't think the empty space would cost much different, and the objects are all the same size, so not much dynamic adjustment is needed in that regard. The one time I tried implementing them, it cost more in performance to manage the kd-tree, than it took to just run everything in a fixed-grid like this video used. Tho again, I probably wasn't using them as expertly as other people might.. heh
Never tried them but I tend to think that very simple / straightforward and cache efficient structures generally win, specially if the world size isn’t huge
@@user-dh8oi2mk4f I don't remember, it was years ago and I was barely comprehending tutorials on it at the time, as it was. I just remember the feeling like it was the programming equivalent of chasing after a perpetual motion machine, or teetering on the edge of "The Tyranny of the Rocket Equation".. lol
Dude I am a high schooler and i wanted to make a thread pool for multithreaded collision detection and i even thought there would be issue with 2 threads writing to the same Ram adress and i would have fixed it in the same way.i am feeling proud that I thought of all the same optimisation as you.i first thought of a qaud tree but couldn't find a way to multithread it
That's awesome! The overall structure looks like a polycrystal and those imperfections - like dislocations. The hexagonal planar structures look exactly like graphene.
It's been a long time since the last time I paused a video and go down to intentionally click sub+like before I finish a video because I don't want to forget about it. More content this quality sir and you're on top of RU-vid.
Fantastic! Really beautiful simulation! I have also invented the same technique by myself (I know that I'm not the first who though about it but at least I figured it out by myself), but never got to realize it. Glad to see how well it actually works! Probably it will run a couple dozen times faster if you run it with CUDA.
Incredible work! I'm not into programming, yet you managed to make it really interesting, even for me. Worth a lil' subscription imo. Also, your accent sounds like you're french. Edit: just checked and yep you are
Very interesting video, I've actually been thinking about implementing my own basic physics checker for a really tiny multiplayer game to increase the efficiency and lower the server requirements (though I'm using C#11, but the algorithmical / threading issues apply all the same) thanks a bunch for this very interesting video
Hey Pezzza! I really love watching your videos, they're really entertaining! The style of video you make is very underrated and very helpful to people like me who have a little bit of experience in programming. After watching this video I was inspired to make something physics-based and was wanting to make something like a simulation of atoms, with protons, neutrons, electrons, and a couple of other subatomic particles, but got a little lost on how to handle the forces and interactions between them (not to mention it's been a few months since I last did a physics simulation, so I'm a bit rusty). I was wondering if you could perhaps create something like this in a future project?
The color mask on the objects that you did may have been the coolest fucking thing iver ever seen 😂 just the way it goes from randomly colored dots everywhere to a perfect image in the blink of an eye
Checking for a collision between grid cells can be done only for half of the neighbouring cells. For example you can only check left, top-left, top and top-right neighbours. All other collisions for examle between current cell and right neighbour, will be checked once that neighbour becomes current cell
Yes absolutely, I still do the full check since it is like doing 2 solver iterations but faster that really doing 2 iterations and it help a lot with stability
This video gave me the push the ditch a physics engine for my project and write my own. They are way too smart for my needs, and a simpler one like this (with some additions that fit my needs, like grouping objects or base displacement on weight) will provide a much better base for the logic.
