Hi there!
Im trying to implement a simulation of the solar system with multi-client support and Im not sure how to properly manage such a large area efficiently.
The solar system is huge. How do I efficiently figure out which object to tell the client he can see?
Anyone tackle a similar problem before and have any suggestions?
Thanks in advance!
Most probably you should store data about your objects in a database and use an entity system to control them. The actual renderings/spatials would only be created when something is near enough to see it (simple distance check/database query), with a model that is adapted to the view distance. Then you can also move the world around the camera instead of the camera though the world to further lessen issues with large numbers / overflow.
It’s a big problem.
Something else for you to consider - larger objects can probably seen from further away.
(i.e. stars you can see light years away, planets anywhere in the solar system, moons as you approach a planet, space stations as you approach the moon, fighters as you approach the station…etc…)
Partition the world between “known” stuff that the client can just know about (for example planets unless they move/need exploring/etc) and stuff that needs to be updated.
Once you know what stuff is dynamic your next job is to scope out the problem. Work out what can see what when and that will help you immediately see that some possible implementations are better than others.
Good luck 
Thanks and sorry for taking so long to respond, finals week and some consulting work came due.
In the away time Ive had some ideas bouncing around that i think fall in line with what you both suggested.
I think this is in line with what zarch suggested, I considered setting stars on the backdrop as point-lights loaded form a file client-side. This is data that never changes, and at least keeping it in a file allows me to expand to a multi-starsystem simulation in the future if i should so choose.
Planets should be similarly file-configured with orbital data, and i plan to provide a client-side engine for parsing that data and inflating a scripted object based on GMT. My assumption is that since the client is required to be synced with the network time in order to reliably communicate, this information doesn’t actually need to be transmitted.
Can yall think of any case this might not work?
As far as physics enabled objects (players, incoming rounds, asteroids, etc), I’ve been thinking of several approaches and I’m not sure which might be viable or completely terrible ideas.
A simple approach is to cube the system into chunks so that a 3x3 chunk cube is still within the precision threshold for the floats. The server would then keep objects in each 1x1 chunk notified of the objects in the other 26 adjacent chunks. Coordinates the client receives would be relative to their local zero. A benefit to chunking in this manner that i see is the ability for the server to trim load by unloading chunks that are not adjacent to a chunk containing a client.
Another idea i haven’t quite fleshed out: using a clustering algorithm to generate a local coordinate system based on client locations. I get the vibe that this could be very efficient approach, but I haven’t put my brain on it for very long.
Norman, Ive been wondering how I might be able to leverage the database to handle some of this nearest neighbor type of calculation. Is this in line with the chunking idea, or are you creating some sort of hash of coordinates and applying a bitmask to it or something?
Again thanks for the help so far guys.
1 Like
Seems to me the perfect job for an octree, storage however can get a bit tricky.
@zzuegg said:
Seems to me the perfect job for an octree, storage however can get a bit tricky.
In my experience, like quad trees, oct trees seem to rapidly degrade into regular grids... and then the oct tree is only overhead since it requires a tree search where as a regular grid cell can be found with simple math.
For example, as soon as you set a minimum split size then you are generally better off just using a fixed grid of that size and then applying sparse grid techniques for tracking/storage.
Oct trees and quad trees aren't even good at tracking neighbors. In the best case, it's a sibling and in the worst case it's a distance cousin.
1 Like
@pspeed said:
Oct trees and quad trees aren't even good at tracking neighbors. In the best case, it's a sibling and in the worst case it's a distance cousin.
I simply add a calculated key as identifyer to each trunk, for example key="xpos:ypos:zpos:size"
Then in combination with a database/hashmap you can still get the neightbors trough a simple calculation. At the cost of memory i still have the best of both worlds
@zzuegg said:
I simply add a calculated key as identifyer to each trunk, for example key="xpos:ypos:zpos:size"
Then in combination with a database/hashmap you can still get the neightbors trough a simple calculation. At the cost of memory i still have the best of both worlds
But what do you get from the oct tree that a regular sparse grid wouldn't provide?
I have stored all the map content in a octree and i use it to load data when necessary. The octree gives me the advantage of eliminating a lot of unneeded distance checks…
And maybe it is going to be usefull when i try to implement a culling algorithm in the future…
@zzuegg said:
I have stored all the map content in a octree and i use it to load data when necessary. The octree gives me the advantage of eliminating a lot of unneeded distance checks...
And maybe it is going to be usefull when i try to implement a culling algorithm in the future..
I just don't really see how. Its root is not context sensitive really. I also don't really understand how you avoid distance checks over using a sparse grid. Like I said... in the best case your neighbor is your immediate sibling but in the worst case you have to go all the way back to the root to find it.
Do you have a minimum split size or do you let it split forever, basically?
I'm not saying there isn't an advantage, I've just never found one. I don't know how many GIS apps I started as quad trees before ripping it all out again and just using a sparse fixed size grid. You get O(1) lookups instead of O(n log n) or whatever.
1 Like
Isn’t the advantage of the octree that you can define a range search by simply getting the subtree of objects that defines that volume? For instance if your octree has a resolution of .25m and you want to find all objects within a meter of you, (pseudo code) localnode.getParent().getParent() would give you the node to use as the root for all objects in that 1m3 volume. This then be leveraged to define the scene graph for the client. Say you want to notify the client of all objects within a meter of it you could send it the subtree it belongs to.
I see how this is helpful and can make server-to-client communication simple, but what does this do to the overhead of the server and the simulation of movement, collisions, etc?
Either way this discussion has triggered an idea with me that Im going to try and ill let yall know how it performs. Im going to grid the system off and use the 27 grid cube method i described earlier. I think this lends itself to a distributed server model rather well. My plan is to have a world controller that manages the grids and notifies various simulation servers to manage the scene graphs needed for each 3x3 cube.
1 Like
@stephanator said:
Isn't the advantage of the octree that you can define a range search by simply getting the subtree of objects that defines that volume? For instance if your octree has a resolution of .25m and you want to find all objects within a meter of you, (pseudo code) localnode.getParent().getParent() would give you the node to use as the root for all objects in that 1m3 volume. This then be leveraged to define the scene graph for the client. Say you want to notify the client of all objects within a meter of it you could send it the subtree it belongs to.
I see how this is helpful and can make server-to-client communication simple, but what does this do to the overhead of the server and the simulation of movement, collisions, etc?
Either way this discussion has triggered an idea with me that Im going to try and ill let yall know how it performs. Im going to grid the system off and use the 27 grid cube method i described earlier. I think this lends itself to a distributed server model rather well. My plan is to have a world controller that manages the grids and notifies various simulation servers to manage the scene graphs needed for each 3x3 cube.
But if you are deep down in a leaf at a boundary that leads all the way back up to the root then nearest neighbor is actually quite expensive.
Better (in my opinion) to have a regular grid and just mathematically go right to your neighbors in constant time. Oct trees are useful if your bounded queries are always aligned with the larger grid sizes... otherwise, the best case is worse than a regular sparse grid and the worst case is much much worse.
I mean, there is a trade off. An oct tree with no minimum size will answer perfect queries but it may take a while. Each oct tree leaf cell then by definition has at most one object in it. Alternately, you can use a fixed grid and let the cells have more than one object figuring that on the whole this number of objects is small. It's kind of the same theory as a hash table. Pick an agreeable split size and then handle collision in the buckets. And like a hash table... bucket lookups are constant time O(1). Even better in this case is that they are spatially organized so you know the adjacent buckets are +1/-1, etc.
1 Like
Out of interest do you use any particular sparse grid implementation or roll your own? I know I’ve done something similar in the past just by using a HashMap of (coord->data) but I’ve no idea if there is a better way. (I’ve never needed a big sparse grid or a highly active one so I’ve never researched it).
@zarch said:
Out of interest do you use any particular sparse grid implementation or roll your own? I know I've done something similar in the past just by using a HashMap of (coord->data) but I've no idea if there is a better way. (I've never needed a big sparse grid or a highly active one so I've never researched it).
Essentially, I use hashmaps. Though in my case the data was coming from files or a database, so the hashmap was just an LRU cache. The data was still indexed by a key constructed from the cell coordinate, though.
1 Like
You could also have a list of the objects sorted from most visible to less visible.
- Visibility of “infinitely far” objects should be proportionnal to their size and to the distance squared, I think, since twice as far means half as much apparent diameter, hence one fourth of the actual surface. From that, you can sort all object according to distanceSquared() * diameter (maybe squared too?).
- The closest objects won’t easily get out of sight, unless you travel at insane speed; you can refresh thei distance every minute maybe.
- Same for really far objects.
- Visible and invisible objects that are susceptible to change ( abs(visibility-treshold) < a fixed value) should be refrehed more often, like every 10 seconds?
All those values depend on your speed, of course.
@pspeed said:
Essentially, I use hashmaps. Though in my case the data was coming from files or a database, so the hashmap was just an LRU cache. The data was still indexed by a key constructed from the cell coordinate, though.
Ok, so we used essentially the same approach then :)
I was just wondering since I did it that way because it felt right and worked well at the time but I never did any proper research on it.
@carpentier-ch said:
You could also have a list of the objects sorted from most visible to less visible.
- Visibility of "infinitely far" objects should be proportionnal to their size and to the distance squared, I think, since twice as far means half as much apparent diameter, hence one fourth of the actual surface. From that, you can sort all object according to distanceSquared() * diameter (maybe squared too?).
- The closest objects won't easily get out of sight, unless you travel at insane speed; you can refresh thei distance every minute maybe.
- Same for really far objects.
- Visible and invisible objects that are susceptible to change ( abs(visibility-treshold) < a fixed value) should be refrehed more often, like every 10 seconds?
All those values depend on your speed, of course.
That's not as helpful as you might think. In particular remember that this is a server-client situation. The server needs to know what data to send to the client and when .... so having to maintain a sorted list for every connected client and update the sorting etc would be very inefficient.
Ok, here is how my first-stab at architecting it would go:
The location of all stars and other super-massive bodies would just be known about.
Three (probably, maybe more, maybe less) sparse maps. Each with a different grid size.
Lets say top grid:
1LY resolution:
Contains large objects (large planets/etc)
0.25LY resolution
Contains medium objects
All planets/moons/space station/large asteroids
1AU resolution
Contains small objects
Asteroids/ships/etc
Server just maintains the contents of each grid inside the sparse map. It sends to clients data on the current and all surrounding cells and then updates as that data changes. Initial data would have timestamp, position, velocity - so the client can then simulate accordingly. You only need to send a data update when an acceleration is applied. Update the position as well at that time (and maybe at occasional intervals too) to make sure any drift is corrected for.
Server needs to be the one that keeps track of what grids the client is subscribed to to prevent map hacks.
Rather than subscribing to 27 cells I would use cells two or three times as big and subscribe to 4. As you approach the edge of the current cell in any direction then the cells in that direction are loaded. To prevent repeated context switches I would do:
x 0-33%, load current and left
x 33%-66%, load current and keep last seen loaded
x 66%-100%, load current and right
Same on Y and Z. If close to two borders then also load the diagonal. Worst case you end up with 7 cells loaded if you are right in the corner of one cell.
You actually end up sending a similar amount of data (similar volume) but with fewer channel switches and subscriptions to manage and no repeated context switches if someone goes back and forth over a boundary.
It needs refining and there may be a better approach out there but it is where I would start from
2 Likes
@zarch said:
Ok, here is how my first-stab at architecting it would go:
The location of all stars and other super-massive bodies would just be known about.
Three (probably, maybe more, maybe less) sparse maps. Each with a different grid size.
Lets say top grid:
1LY resolution:
Contains large objects (large planets/etc)
0.25LY resolution
Contains medium objects
All planets/moons/space station/large asteroids
1AU resolution
Contains small objects
Asteroids/ships/etc
Server just maintains the contents of each grid inside the sparse map. It sends to clients data on the current and all surrounding cells and then updates as that data changes. Initial data would have timestamp, position, velocity - so the client can then simulate accordingly. You only need to send a data update when an acceleration is applied. Update the position as well at that time (and maybe at occasional intervals too) to make sure any drift is corrected for.
Server needs to be the one that keeps track of what grids the client is subscribed to to prevent map hacks.
Rather than subscribing to 27 cells I would use cells two or three times as big and subscribe to 4. As you approach the edge of the current cell in any direction then the cells in that direction are loaded. To prevent repeated context switches I would do:
x 0-33%, load current and left
x 33%-66%, load current and keep last seen loaded
x 66%-100%, load current and right
Same on Y and Z. If close to two borders then also load the diagonal. Worst case you end up with 7 cells loaded if you are right in the corner of one cell.
You actually end up sending a similar amount of data (similar volume) but with fewer channel switches and subscriptions to manage and no repeated context switches if someone goes back and forth over a boundary.
It needs refining and there may be a better approach out there but it is where I would start from :)
I'm only trying to simulate the solar system, not the galaxy ;) I'm aiming big but not that big lol
If i understand correctly, your % thresholding is essentially making 27 cells anyways. lower third X you load the one you were in and the one your in now, middle X you don't load anything, but keep what you had, last third X and your loading the new one. 1/3^3 = 1/27 ;)
The idea is that the simulator server maintains a separate scene graph for each cell containing at least one client.
Objects in the local cell are added to the local scene graph, and any neighboring scene graphs. At worst case a client could be updating 27 scene graphs simultaneously, but would only receive updates from the scene graph of the cell they're in, ever. My understanding of the messaging system is that i can register listeners to various scene graphs, so the data is received once server-side, and read 27 times(worst case).
In this manner the client only ever has to be registered for updates from one cell, not the 7 max from my understanding of your example. Considering the vastness of space, and my working resolution of 200km for the cells, the likelihood of a client updating more than one graph is rather slim, only happening in the cases of two clients passing within ~700km of each other(worst case).
In a case of high client density in one cell, each applies updates to the graph, but they all receive the same update from the server. In the case of multiple high density cells adjacent to each other, each client still at worst is being copied to 27 graphs, and still only ever receives from one.
This does not have to be O(n) for the server however, as each cell can run its own update loop(and probably will) and simply send an update to the surrounding cells over IPC, and waits for an update from each active adjacent cell before sending the update to its clients. This keeps the cells in sync, and at worst the cell behaves as if it had 27 more clients.
Now to facilitate fast moving clients, i could send the slower clients, "fuzzy" knowledge of a client further out, and the faster clients would get the lower-res coordinates of the map. For instance, I'm traveling .5 AU/h and i may be able to tell that somewhere in that .25 AU cube there's a ship, but to find it i would need to slow down and approach.
This could be a good use of that multiple resolution grids as you suggested.
Anyways I'm thinking on my feet as you guys suggest things, so i am by no means wed to the idea. Tear me a new one if i missed something.
Again thanks for all the suggestions. I'm making more progress on the architecture over the last week than i have in a year.
I would organise it the other way around: Only put the data in one cell, the client listens to all interested cells.
The distances etc were just examples, scale them to however you need for your game and if you can get it down to one layer then great
It doesn’t really matter whether you do 27 or 7 grids (as you say the 7 grids are 3 times as big so in many ways they are equivalent). Personally I’d rather keep the number down just as it makes managing them easier. Just be careful to avoid the switching issue with someone repeatedly crossing the boundary. Imagine the worst case scenario of a fight happening right on the boundary with ships/missiles/etc crossing it back and forth all the time. You need to cope with that case.