   Large number of orbiting bodies
  Hello everybody,I've been working on a space trading simulation set in our own solar system for a while now. One of my design goals for the game is the consistent usage of realistic Newtonian physics.So far I've finished most of the "infrastructure plumbing": DirectX 9 renderer, GUI System, file management, etc.My initial prototype for the simulation of planetary orbits worked quite well, but only for a limited number of bodies (updated all positions every single frame).However, I'd like to go as far as to calculate the exact position of each asteroid in the asteroid belt (approx. 400,000 objects). Naturally nobody will take notice to this kind of overkill calculation but if something happens to a specific asteroid (mining operation built, homing beacon placed, etc.) I want that to be persistent.Now here's my problem: I have a huge list of bodies with Kepler orbits (simple 3D ellipses). Calculating the exact position of one of these bodies at any given time is pretty cheap. But how do I do an "inverse search" (find all bodies close to a certain point in space at a specific point in time) without going through every single body in the list?Basically I think I need some kind of space partitioning algorithm that handles the fact that bodies constantly change their relative positions to each other.One of the ideas that came to mind was using some sort of orbit hierarchy:Pick 100 or so "master asteroids" and recursively divide the rest of the asteroids among them as children and grandchildren; analogous approach for planets and their moons.If two bodies are associated in this hierarchy that means their orbits always stay close together. Only when a visibility check gives you a positive result for a master body you need to check its child objects.What do you think? Could this be a good approach? Or maybe something completely different?My primary goal is: Make it look like the real thing (no inconsistencies), but mathematical perfection not required.Regards,Bastian   
  Hi transwarp,Great game concept, can't wait to see more about this. As for handling huge amounts of gravitationally interacting bodys, I know there's been developed a number of methods. I did a google search a while back and found a bunch of them described without breaking sweat. Can't remember what they're called just now, but I'm sure you'll find them easily by googling "multibody gravitational interaction" or similar. Good luck!Cheers,Mike   ;  one solution might be some sort of kd-tree/octree structure that keeps all your object inside, but not just objects but their potential positions for some period of timeso every frame you only have to update positions of those objects that waited long enough. and also those in visible leafs of a tree.when you add object to tree you can for example find it's position for current frame and n+1000th frame, find bounding box for both and use it to put object in your tree. then you put all objects into priority queue sorted by smallest expire time. and at each frame pop objects from it, update their position and bounding boxes and put them back with new expire time. then while drawing you normaly do kd/octree based rendering where before drawing contents of each leaf you update object position.;  I would suggest a spatial hash over a quad-tree or kd-tree, simply because rehashing a moving object each frame can be considerably cheaper than updating a dquad/kd-tree.   ;  @h4tt3n:Thanks. You can find some preliminary information on the game here: http://epic.nanobyte.de/It's still very early in its development, so a lot is bound to change.@biki_:That sounds like a great solution, thanks. :) I'll definitely give that a try.@swiftcoder:I've never done hashing with spatial coordinates, I'll have to look up some decent hashing algorithms. Sounds like a good performance optimization and is probably easier to implement than tree structures.   ;  It sounds like what you want is a good n-body simulator; there's a great resource (very) briefly describing the primary algorithms and giving tons of references at http://www.amara.com/papers/nbody.html -- I strongly recommend, in particular, looking at the sections on Tree Codes.  Best of luck with it!   