Making an N-Body Simulation

Рет қаралды 17,011

Күн бұрын

Пікірлер: 49

@DeadlockCode Жыл бұрын

If you're having issues, read this first and if it doesn't solve your problem, leave a comment and I'll respond as soon as I can. Problem 1: Description: The bodies either, exist for a while but suddenly disappear, or more likely they exist for only a couple of frames before disappearing. Reason: Two or more bodies share the exact same floating point position. This results in the distance becoming exactly zero, and we all know division by zero is bad. It's particularly bad here because then the acceleration will become NaN and because NaNs are contagious, the velocity and position will also become NaN. This results in whatever method you have for rendering to stop working, maybe it even crashes. Solution: Either check if the bodies have the same position, and then just don't compute the acceleration for those bodies, or my preferred approach, do 'mag.max(epsilon)' for the final unclamped magnitude in the acceleration calculation. Why it works: This solves the problem because there is no longer a division by zero, instead a division by epsilon, which is very tiny depending on implementation. This results in the division becoming huge (but importantly not Inf) and multiplying that with the r vector, which is (0, 0), results in a (0, 0) acceleration towards that body which is like they never tried interacting in the first place. For clarity, epsilon is 1.1920929E-7 in my program, and the max function returns the larger of two floats.

@davidpiepgrass743 9 ай бұрын

I would think if the particles collide, you combine them by holding momentum constant and show a big burst of light :)

@rorymacdonald7529 11 ай бұрын

love it! i've been wanting to get into particle/n-body simulations. gonna take a shot at it over winter!

@lightninghell4 5 ай бұрын

how did it go? have you implement any speedups to handle more particles?

@NeroDefogger Ай бұрын

I'm also working on that

@jsbaasi 11 ай бұрын

Brilliant video, loved the graphics and the soothing music. Looking forward to your implementation of the BH algorithm!

@primalaspid7197 11 ай бұрын

Just found your channel and your videos are absolutely amazing! Huge potential there!

@FredGlt 11 ай бұрын

4:26 One small improvement you could do for accuracy is to change the equation of the position from (P = Po + V * T) to (P = Po + Vo * T + 0.5 * A * T^2), where Po and Vo are the values computed at the previous step of the simulation. This is because the accurate way to obtain the speed's and the position's equations is by integrating (a = dv/dt) and then (v = dp/dt) instead of approximating these two equivalences directly. It might not sound like much, but I’ve seen other content creators with projects such as softbody and gravity simulations where it has greatly helped accuracy as well as stability.

@jacquelinelafole8342 6 ай бұрын

Runge Kutta 2 ? isn't it ?

@axionbuster 8 ай бұрын

For the Barnes-Hut, using the Z-order curve (by bit interleaving) and then building the tree bottom-up from the lowest layer (where every particle becomes a node) and up (lower level of detail) is a speedy way of accomplishing it. From that point on, you can calculate the approximate view angle (or the tangent of the angle) by a simple division. If the angle is too large (about 10 degrees), you go deeper into the tree, but if it’s small enough, you treat the node as a particle and then move on. Once the tree is built, the depth-first traversal is an embarrassingly parallel problem. I built my tree using the left-child-right-sibling (LCRS) data structure, which is dimensionally independent and memory efficient simultaneously.

@academyofuselessideas Жыл бұрын

Fantastic! Many people will say that reinventing the wheel is wrong but those are people often obsessed with efficiency... keep reinventing! what matter is that you enjoy it... It is also great that you chose rust for your simulations. Perhaps, for other videos you can use rust's flamegraph to show what parts of the algorithms are consuming the most resources... Another possible question here is how the simulation is affected by numerical error... one of the issues with the n-body problem is that at some point the numerical errors accumulate fast which forces you to reduce the delta t... another interesting improvement would be to make the delta t adaptive... It is a very interesting problem! keep it up!

@DeadlockCode Жыл бұрын

Thank you so much for your thoughtful comment! I'm glad you appreciate the approach of exploring and reinventing concepts from the ground up. And I agree that the joy of creation often outweighs efficiency, especially when it comes to understanding and implementing complex/interesting algorithms and concepts. Using rust has been a great choice, and I'll try to incorporate flamegraph (or other profiling tools) in future videos. Showing resource consumption can indeed provide valuable insights into where the bottlenecks of algorithms are. Numerical errors are an interesting topic and accumulating errors are important to acknowledge. Implementing adaptive delta-time would also be a possible future endeavor. Although, my goal with this simulation was never realism nor accuracy, shown quite well by the fact that I completely ignored the gravitational constant. I just want to build up the basics of the problem so that in future videos, I could see how far I can push it without removing the feeling that each body is interacting with every other body. So far I have implemented and optimized the Barnes-Hut algorithm and I'm currently working on a video about it. One funny thing is that the videos take way more time to make than the code itself. Beyond that, I have recently read up on the fast multipole method (FMM) which seems interesting and I'm really looking forward to implementing my interpretation of that one too. Although as the algorithms become more complex, the videos become more difficult to make digestible. But, I'll try my best. Thanks again for the great comment, it means a lot! Side note: I took the liberty of checking out your channel (repay the favor so to speak), and your channel pitch alone is just amazing!

@academyofuselessideas Жыл бұрын

Nice! yes, making videos take time but hopefully you're having fun doing it! WRT the gravitational constant, it is not a big big deal that you make it equal to 1. You could claim that you are using some sort of Natural units! (check the wikipedia page for natural units)

@HoSza1 Жыл бұрын

Did you test it with only two bodies? If you fix one object somewhere on the screen, then the other should move in an ellipse like curve and if you don't clear the screen but keep the former states if the other object drawn you might notice it keeps spiraling towards the fixed object.

@DeadlockCode Жыл бұрын

Yes, I have tested it and I noticed that the body spirals out (due to the Euler method's tendency to 'overshoot'). To counteract this, the usual approach is to just reduce the time step, but a more sophisticated solution would exchange the entire integration method for something more stable (e.g. Leapfrog or Velocity-Verlet). A more simple solution to substantially reduce the error is to just replace "self.pos += self.vel * dt;" with "self.pos += self.vel * dt + acc * (dt * dt * 0.5);" in the bodies' update function. Edit: Removed mention of RK4 as it is not symplectic and would therefore not solve this problem. Thanks to @Not_Even_Wrong for pointing that out.

@joshuachan6317 9 ай бұрын

@@DeadlockCode TL;DR: acceleration's SI unit is ms^-2 doesn't mean you can get the displacement by multiplying a with t^2 😂😅 (Been there) After some calculus, you may get something like s = ut + ½at²

@newfilms4061 Жыл бұрын

this is so well made, congrats!! you deserve so many more subs 💪💪

@chocholatebunny 11 ай бұрын

The quality of this video has made me a sub, keep going friend, you're making some great content and even better Rust content!

@moritzfechtner5245 11 ай бұрын

Continue your good work, looking forward to the next video.

@jonathanbaincosmologyvideo3868 10 ай бұрын

Can you perhaps show where this solution is applied? Try perhaps Mercury's infamous Perihelion Precession !

@uuserneame8461 Жыл бұрын

very nice, cannot wait to see more

@a1000joys 9 ай бұрын

Fantastic video. Well done.

@unveil7762 11 ай бұрын

Wow!!! You are a great teacher!!! ❤ thanks!! This was REALLY helpful 🎉

@firegreat3420 11 ай бұрын

You have just gained a sub, man.

@Jsong-ft9fv 2 ай бұрын

SO COOL MAN

@NeroDefogger Ай бұрын

I also have my simulator, you can check where I explain it a bit, the simulations I do at the end are very scuffed, the simulator works much better now, I'm trying to use it to discover more forces, btw interesting the calculating both objects at the same time to try to halve the complexity

@danielbecker9160 11 ай бұрын

Great video, but i believe you can improve the accuracy of the positions, At 4:28 you stated that p_{n+1} = p_n + dt*v_n, but i believe you actually want to update the positon based on the average velocity over the time interval (v_a = 1/2*(v_n + v_{n + 1}), which gives us the formula for position as p_{n+1} = p_n + v_n*dt + 1/2*a*dt^2, (i.e. the displacement formula for uniform acceleration)

@DeadlockCode 11 ай бұрын

Yes, that is correct. That formula would be more accurate but I wanted to keep it as simple as possible since it’s an introduction to the concept. If accuracy is a concern you should probably use other integration methods such as leapfrog or RK4. Just remember; there are pros and cons to every method.

@miguelmyers9546 9 ай бұрын

Nice work

@vladde 11 ай бұрын

very nice video!!

@b_dawg_17 Ай бұрын

“Any Turing-complete language” was a filthy nerd snipe 😂 no way I’m programming this in redstone 😝

@Miparwo Ай бұрын

Maybe is faster to calculate the gravitational field, which should not be sensible to distant particles.

@davidpiepgrass743 9 ай бұрын

I look forward to your next video! Have you considered using the faster "Fast-Multipole" method instead of Barnes-Hut? My impression is that you just have to compute interactions between pairs of distant quadtree nodes (or something like that) instead of interactions between individual particles and distant quadtree nodes.

@DeadlockCode 9 ай бұрын

Yes I have considered it. I think interactions between different quadtree nodes is the right idea but there has to be more than that since I’ve heard that the FMM is O(N) and making a quadtree from N positions takes O(N log N). I have found some scientific papers about it but I haven’t had the time to read them yet. edit: spelling

@ful7481 Ай бұрын

how about using something like fast inverse square root?

@18o4 10 ай бұрын

Is the code available anywhere? I've been trying to replicate this simulation but the particles just get launched away from the center

@DeadlockCode 10 ай бұрын

github.com/DeadlockCode/n-body

@walterbrownstone8017 3 ай бұрын

It's it possible to make a relativistic n body for the electric force, rather than gravity?

@isuckatmc1728 5 ай бұрын

where is the next video? i want to optimize my code

@DeadlockCode 5 ай бұрын

Yeah, sorry about that. It’s been taking longer than expected due to ‘life being life’ but I’m working on it. In the meantime, there are a few resources already out there about the Barnes-Hut algorithm. There’s a great article by Tom Ventimiglia and Kevin Wayne or alternatively a video by William Y. Feng, both of which are really good, but sadly they don’t show you how to implement it. If you’re ok with just code, there are some repositories on GitHub that you can explore but most (if not all) lack explanations. So if you want code and explanations in one package, I guess you’ll just have to wait.

@alexandratsankova5825 11 ай бұрын

You might be able to use "fast inverse square root" or (i remember it being called) Quake inverse root for the calculations, it might speed up the calculations, but I'm not sure by how much. Also not sure, but it might be possible to use some type of threading to speed up the calculations. But it might be tedious in order to not get overlaps between the threads (and thus not have to use locks/mutexes)

@DeadlockCode 11 ай бұрын

I tried the fast inv sqrt but it didn't actually improve anything. I suspect it's because cpus have come so far since then and now the sqrt + divide instructions are just faster than all the things you have to do for the 'fast' one. Maybe it's still faster in some situations but at least not in mine. About threading, it would definitely make it faster but I feel like it's a lame way. In my mind it's like saying that buying a new cpu it is an optimization. I try to focus on things that make the cpu do less work with the same (or similar) results instead of things that make it do more work in the same time. I just find it more interesting to optimize an algorithm rather than to slap more threads on it. On the other hand, it's basically 'free' performance so I might show some results from it in the next video.