06 Dec, 2008, Rojan QDel wrote in the 1st comment:
I currently code for an SWR MUD, that has expanded far beyond the stock space system. Our issue is that the SWR space system is rampant with ridiculous loops, and when you have upwards of 10,000 ships, looping through all of them to find one ship is massively inefficient. Our MUD has been known to crash when too many ships are engaged in space combat because of the number of looping operations involved in each single command/action and with our space queue system.
Ideally, I would like to find a way to optimize the space system so that it can more efficiently run with large numbers of ships. Could anyone offer any suggestions for what methods/systems would be helpful in this sort of optimization? Thanks!
This probably doesn't help any, but have you solved the problem where players can seemingly fly "through" a planet?
For instance if you have a planet in System X at coordinates 4000 -4000 4000, and a player heads in the direction of that planet, have you ever noticed how if you're off by just so much that you fly through space that *should* be the planet? Say, 4015 -4015 3985, This *should* effectively still be the planet, yet you can fly right through this, and not even be pulled into orbit by the gravity? Like I said, this probably doesn't help you any, but it is something I've been meaning to look into fixing in the SWRFUSS release, I just haven't had the time. =/
Our MUD has been known to crash when too many ships are engaged in space combat because of the number of looping operations involved in each single command/action and with our space queue system.
That in itself doesn't explain a crash. What you might want to do is add garbage collection, when a ship (or another heavy duty object) is destroyed move it to a non playing location and deallocate at a later time in a separate game loop in the update routine. Another important thing to do is using a global pointer to reference a linked list that is being updated with an unpredictable outcome (most often in main update routines like combat ticks), so instead of using obj_next = obj->next you use: global_obj_next = obj->next. When you unlink an object check if the object is global_obj_next, and if that's the case: global_obj_next = global_obj_next->next. If you don't have garbage collection it prevents crashes, and otherwise it stops odd behavior.
Making lists faster is difficult, use an array if you can populate it for 33% or more since they're much faster to traverse.
07 Dec, 2008, Rojan QDel wrote in the 7th comment:
Sorry, it doesn't crash because of the looping, but we get major CPU spikes and massive lag, which sometimes results in the MUD lagging out and having to be killed. We actually do have a 'shipyard' sort of system that removes unused ships from the main loop. We also have a sort of queue for ship actions that uses a global queue, I believe.
How are the lists currently broken down? Is it already at the point of where it's only looping through ships in a specific starystem? Or is it looping through all ships? I can only logically think to break it down to ships in space, in a particular starsystem, then loop through the starsystems individually during combat. Not sure if it really helps, but maybe it breaks it down a bit more.
Identify what you are searching by when you do these massive loops (e.g. looking for something by name?). Then, you can build indices over those queries. For example, if you find yourself often searching for a ship by name, build a map from ship name to ship (using a hash table, for instance). Basically, you need to figure out what you are searching for, and under what restrictions (same system? same immediate vicinity? …) and optimize for that.
When it comes to searching for a specific ship, I think David's suggestion sounds reasonable. To generalize it a little more: One of the things with the SWR space code is that often the entire list of ships is traversed when you're really just interested in a small selection of them. If, as in your example, you have 10,000 ships, you'll find that at any given point in time the vast majority of these will be on the ground. But take a close look at for instance the move_ships() function in space.c. The entire list of ships is traversed twice in that function, first they are moved, then they're checked for collision with other ships. This is a bit wasteful, since only the ships in realspace are of interest.
My current solution to this, and other loops, is to keep three lists of ships. One "main" list where all ships are, then one for the ships in realspace, and finally one for the ones in hyperspace. Thus when I need to update ships in realspace, I only traverse those that are actually in realspace. In addition to any potential performance gains, this also (I think) makes the various loops more focused, and easier to read, because you need fewer if-checks. So when a ship blasts off from a planet, I just attach it to the list of ships in realspace. Then when it jumps to lightspeed, I just move it to the list of ships in hyperspace.
08 Dec, 2008, Rojan QDel wrote in the 14th comment:
I'll likely go with Keberus' suggestion, though expand on it, and create a list of ships in each area, hyperspace, room, ships (hangars), on a planet, owned by a player, in a fleet, and in a structure. This way, each operation will only need to access their specific ship list, which has been pregenerated, rather than traversing the ENTIRE ship list.
There's not much point creating different ways of organizing ships unless you actually loop over the full list looking for just those organizations. Chances are you'll be adding all this organizational complexity for relatively little gain. What Caius described is a very simple reorganization that apparently gets significant gains.
As always with optimizations, especially with respect to choosing data structures, it pays off immensely to do a little homework before rewriting and reorganizing things all over the place.
08 Dec, 2008, Rojan QDel wrote in the 16th comment:
I would essentially be doing what Caius is doing, but creating even more list distinctions for more specific cases, so that in the majority of situations, the smallest possible list is used, likely containing only the necessary data. For example, instead of traversing all ships in realspace, I might traverse all ships in a particular starsystem.
It really makes me happy to see some people actually discussing SWR. I'm going to see if I can prod my coder into making some snippets.. or perhaps I'll clean up my old DN code and release that. SWR needs to be more open with code, IMHO, to go anywhere. It's kind of stale right now. What was the last release? 2006?
Well, If people would help me out more on Smaugmuds.org in regards to the SWR stuff, it might not be so stale. :P Smaug gets the most attention because more people use it that are willing to be a community. If no one's reporting things, or prodding me to work on it, I just put it off more and more. :P