If you have one person on a server, the server needs to process the location of one person, receive the location of one person, and send the location of one person to one person. 1, 1, and 1 * 1, which equals 1.
If you have two people on a server, the server needs to process the location of two people, receive the location of two people, and send the location of two people to ... two people. 1, 2, and 2 * 2, which equals 4.
If you have six people on a server, blah blah blah, you now have to send out 36 messages with player location data. If there are ten people you have to send out 100 messages.
And if it's Dalaran, and there are two hundred and fifty people, you need to send out sixty-two thousand, five hundred messages. The number of location messages you need to send is the number of players squared. Dalaran doesn't lag because it has a ton of players, it lags because the Dalaran server needs to tell every player in Dalaran about almost every other player in Dalaran.
It's also why instanced worlds are so attractive to MMO developers -- two hundred players split to four different servers is 10,000 outgoing location messages, while two hundred players on one server is 40,000 outgoing messages.
Of course, the problems that require n^2 computations for every n data points are bad but they aren't the worst. The worst are the problems that are x^n, where every additional data point multiplies the previous result by x (where x is the amount of processing it would take to do whatever computation once). I bring this up because the popular addon QuestHelper, which computes a "fastest" route between quest objectives, is performing a well-known x^n problem ("The Traveling Salesman Problem") every time it recalculates your optimal route**. Even when it's slow I'm amazed at how fast it goes.
**assuming the addon isn't faking it. I'm also assuming it is doing some optimizations that result in the computation being a constant factor less than x^n.
Posts
0 comments:
Post a Comment