N body simulation.

[Schroedingers-Hat]

Divide objects up to bins of m<1, 10,100 etc, then place each object into a binary search tree. One each indexed by x, y, and z. This will result in k trees after O(building a tree(n)) (I think O(n)) operations. Then start from an object and traverse each tree until the effect of gravity is less than a preset value, setting a flag for each object we pass to avoid duplicates. This should result in something roughly O(n)+k O(a log(n/k)). Where a is the average number of objects which will have a significant effect for any given object. A similar technique can be used for collision detection in a speed of light limited simulation.

[capnrefsmmat]

Do you want to do a separate N-body simulator with gravity, relativistically, or do you want to incorporate collision detection and gravity into the current system?

I can imagine a future simulator which has a toggle switch for gravity...

[Schroedingers-Hat]

Well, I was planning on including acceleration, and ability to add forces (combined electromagnetism/relativity demonstrations are rather informative) to this demo. If I already have an integrator for this (esp. one that can handle Maxwell's equations) then adding Newtonian gravity will be trivial. Weak field approximation or gravito-magnetism are very similar to Maxwell's equations, so I don't see too much extra trouble in making something accurate enough that Mercury would precess (although I don't know how accurate our numbers would be. Acid test, I guess.).

Also, a binary search tree is a terrible idea. Smoothsort is better in every single way.