Simulating n-bodies

[matthen]

Hi everyone,

 

I got to a certain stage in my project where I have an orbital gravity simulator that should run quickly. As I progress I'll be updating a live demo on this page:

 

http://ec2.matthen.com/gravity/

 

 

At the moment there are 200 planets of different sizes and masses which start on a grid. The physics simulation runs in a different thread to the rendering by using a webworker.

 

 

 

[Mat Groves]

very cool

[matthen]

I've updated the demo,

 

Now you have a spaceship in the centre of the screen, and if you click you fire its engines:

 

ec2.matthen.com/gravity

 

It'll start with 20 random planets

[TheHermit]

Are you doing this with the full N^2 interactions, or are you doing a coarse-graining trick like Particle-Mesh to do it in N log N?

[matthen]

With all the interactions, but if I find I need to speed it up the first thing I'd do is the particle mesh approximation.

I think it runs pretty smoothly on most devices for 100 bodies, which is a good budget for a solar system in the game I'm making. Running the DE solver in a web worker seems to help a lot with speed.

M

[Markus]

What about a QuadTree ?

I use this in my Game and can do collision Detection with hundreds of circles ....

[matthen]

Yeah quad tree was what I was thinking of (storing centre of mass and total mass). I think for my game the overhead of calculating the tree structure won't pay off

[TheHermit]

Makes me curious if there's any way to get an HTML5 app via WebGL to basically do the math on the GPU. That said, when I've seen CUDA stuff go wrong it can persistently corrupt video memory on the card and make the display unusable, so maybe its best if we can't until the cards themselves are more robust.

[Markus]

Yeah quad tree was what I was thinking of (storing centre of mass and total mass). I think for my game the overhead of calculating the tree structure won't pay off

 

The BEST Implementation ive see is from this one ...

 

http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/

 

it works like a charme ...

In my Game i do the Collision Detection and Movement with a Node.js Server ... there i can move particle calcs on different CPUs..

[matthen]

Cool, thanks for the link.  Hermit, have you seen the proposed WebCL?

 

An update on the demo, it now uses some dynamic delta-t to make the physics more smooth if it's lagging behind a bit. You can now zoom in and out, and hopefully the positioning of your spaceship on the screen should be quite smooth- with it being tugged towards nearby masses:

 

http://ec2.matthen.com/gravity/

 

See if you can maintain your orbit around the planet, as 200 asteroids swarm in.

[Austkast]

so long as the objects that collide in your scene are around the same size you might get more mileage out of a grid based broadphase collision detection, if you ever want to add more particles.  It's very easy to implement too.  And I'm sure you're doing this already, but it's worth saying just in case,  when you calculate the sphere/sphere collision detection make sure to calculate the distance square as sqrt functions are expensive. Anyways, good job on this! hope to see more development in the future.

[TheHermit]

Cool, thanks for the link.  Hermit, have you seen the proposed WebCL?

 

An update on the demo, it now uses some dynamic delta-t to make the physics more smooth if it's lagging behind a bit. You can now zoom in and out, and hopefully the positioning of your spaceship on the screen should be quite smooth- with it being tugged towards nearby masses:

I hadn't seen that, but if that gets done it'll open up a lot of doors to crazy stuff that would otherwise be way too inefficient in javascript to do, so thanks for telling me about it!

 

For your gravity demo, I'm trying to remember all the little tricks to make that kind of thing work more smoothly but most of them are for really big systems, not 200 particles. Are you using Verlet for the timestepping? For gravitational simulations its more stable over long times since it does a better job with energy conservation than Runge-Kutta and the like.

[matthen]

Thanks for the advice on speeding up collision detection. I combine it with calculating the gravitational forces. The below snippet should give some idea:

if (dist < r1+r2) {    s =  1000*Math.min(100,(1/dist)*(square(((r1+r2 - dist)/(r1+r2)))));    collisions.push([objects[i]._id, objects[j]._id]);} else {    s = -G *  Math.pow(dist,-3);}

[source]

 

so there is a repulsive field when two objects get too close together, and that makes them bounce off each other. Calculating dist does require a square root, but both conditions in the if need the square root I suppose.

 

It doesn't use Verlet, just a very standard Runge Kutta. That's fast and seems to get the physics right... at least ellipses close back in on themselves when there are 2 bodies.

[TheHermit]

Verlet and Runge-Kutta are mostly different at long times, and I don't actually think you can see the effects with 2 bodies. Basically, Runge-Kutta's absolute error is smaller, but Verlet's error is less harmful to the stability of orbits because it tends to make mistakes that conserve energy. One way to think of it is that with Runge-Kutta, over time the orbits will tend to grow or shrink, whereas with Verlet they'll tend to precess. It may be moot for your simulation though if you aren't going for very long times, but they use Verlet when doing things like billion-year simulations of the stability of the Solar system because of that particular property.

[Markus]

Wow ... WebCL looks brilliant ... i hope it will be soon Standard in Chrome & FF.

[Austkast]

Oh I see, you need the distance in both cases, if a particle is colliding or if it's not.  Never mind on that piece of advice then.  Anyway, since you guys are one the topic of integration I stumbled upon this a while back when I was trying to do an SPH simulation http://codeflow.org/entries/2010/aug/28/integration-by-example-euler-vs-verlet-vs-runge-kutta/ .  He goes over each integration technique and simulates them in the page side by side...worth a look.  The entire blog is pretty cool and very relevant to this forum as most of it is about webgl and javascript in the browser. I especially like his tutorial on creating a 'From Dust' like fluid/erosion simulation.

[matthen]

Another update.  There is now a fuel tank guage, and a damage guage. If you orbit close to a planet then you start to mine it for fuel. I also did some work on giving the planets textures.

 

Check it out:

 

http://ec2.matthen.com/gravity/

[matthen]

This is now a full working demo game, where you can explore an infinite universe procedurally generated from a seed.  Try it out!

 

http://gravity.matthen.com

[onedayitwillmake]

A simple optimization would be to check the distsquared against min*min, and only then call sqrt on distSquared avoiding as many uneccesary calls as possible