Some more bugs and problems
A few players pointed out that the odds of creating various items have changed.
This led me to do some research, like looking at the entropy samples in the server generated logs. It does, indeed, seem that there is a slight bias towards the lower numbers.
My host confirmed that in FreeBSD 5 some things changed:
The history (in the man pages) says it all...
A random device appeared in FreeBSD 2.2. The early version was taken
from Theodore Ts'o's entropy driver for Linux. The current implementa-
tion, introduced in FreeBSD 5.0, is a complete rewrite by Mark R V
Murray, and is an implementation of the Yarrow algorithm by Bruce
Schneier, et al.
So I guess now we should look at developing our own pseudo random numbers generator algorithm, to have some consistency next time we change the OS.
One other problem is that today, when I logged in, my health was half of the normal health... And I don't remember losing over 600 points of health, especially that I didn't visit PK maps, and with my stats, it is highly improbable some monster got me so bad.
There have been some other reports in the past regarding bots being either dead, or with very low health in non PK maps.
Finally, the problem that I've mentioned in my previous entry, is that the new machine, while theortically 3 times faster, it makes very little difference in how much CPU time the game server takes. Basically, on the old machine we had about 15% with 500 players and bots on, and with the new machine we have pretty much the same CPU usage..
Other things, however, such as compiling the server, or backing up the users, are significantly faster.
My theory is that what's really using the CPU is not the actual instructions, but the waiting for the memory. Due to the nature of a MMO server, a lot of memory is iterated many times each second, which makes the CPU cache less effective. This is pretty difficult to solve, because there is no effective way to use less memory.
Me and learner discussed about various improvements that can be done (most of the CPU is used by one little function) and despite Learner's best effort to optimize it, he only got a marginal speed gain.
In case you are curious what that function does, it is the function which keeps track of who sees who. It has to be called 4 times each second, and it looks sort of like this:
for(number of players+number of ai)
for(players on the current map)
check to see if the players see eachother, only when one of the players moved
do stuff
Given the fact that we have 4K players+ai (in total) this can lead to pretty large loops.
Of course, the function is more complext than that, and yes, it skips the players that are not logged on, or on a different map, etc.
We discussed various optimizations, such as using threads, or possibly rewritting the whole function in assembly..
This led me to do some research, like looking at the entropy samples in the server generated logs. It does, indeed, seem that there is a slight bias towards the lower numbers.
My host confirmed that in FreeBSD 5 some things changed:
The history (in the man pages) says it all...
A random device appeared in FreeBSD 2.2. The early version was taken
from Theodore Ts'o's entropy driver for Linux. The current implementa-
tion, introduced in FreeBSD 5.0, is a complete rewrite by Mark R V
Murray, and is an implementation of the Yarrow algorithm by Bruce
Schneier, et al.
So I guess now we should look at developing our own pseudo random numbers generator algorithm, to have some consistency next time we change the OS.
One other problem is that today, when I logged in, my health was half of the normal health... And I don't remember losing over 600 points of health, especially that I didn't visit PK maps, and with my stats, it is highly improbable some monster got me so bad.
There have been some other reports in the past regarding bots being either dead, or with very low health in non PK maps.
Finally, the problem that I've mentioned in my previous entry, is that the new machine, while theortically 3 times faster, it makes very little difference in how much CPU time the game server takes. Basically, on the old machine we had about 15% with 500 players and bots on, and with the new machine we have pretty much the same CPU usage..
Other things, however, such as compiling the server, or backing up the users, are significantly faster.
My theory is that what's really using the CPU is not the actual instructions, but the waiting for the memory. Due to the nature of a MMO server, a lot of memory is iterated many times each second, which makes the CPU cache less effective. This is pretty difficult to solve, because there is no effective way to use less memory.
Me and learner discussed about various improvements that can be done (most of the CPU is used by one little function) and despite Learner's best effort to optimize it, he only got a marginal speed gain.
In case you are curious what that function does, it is the function which keeps track of who sees who. It has to be called 4 times each second, and it looks sort of like this:
for(number of players+number of ai)
for(players on the current map)
check to see if the players see eachother, only when one of the players moved
do stuff
Given the fact that we have 4K players+ai (in total) this can lead to pretty large loops.
Of course, the function is more complext than that, and yes, it skips the players that are not logged on, or on a different map, etc.
We discussed various optimizations, such as using threads, or possibly rewritting the whole function in assembly..
posted by Radu at 2:26 PM
5 Comments:
You may want to look at the GNU Scientific Library (gsl) (http://www.gnu.org/software/gsl). This has a large selection of pseudo-random number generators, including different random distributions (especially of interest for building games/simulations are the gaussian and binomial distributions).
As with most GNU stuff, this is highly portable.
Otherwise Knuth (vol.2, Ch,3) is *the* introduction to PRNG, and includes implementations of at least one very good algorithm.
How to use pRNGs is another matter. Different generators are needed for different purposes; for example, a random integer generator does not produce a random bit stream (there may be no correlation between integer values, but there may be correlation between bit patterns). For the same reason, you cannot do, for example, "RND()&0x00FF" and expect to get a random number.
More relevant for you maybe the issue of turning a random integer into a float -- "(float)RND()/(float)MAX_INT" may give you a random number in the range 0..1, but not a random float; all possible values are not proportionally represented, particularly if you then deal with very small probabilities.
.trollson.
Thanks for the input.
Yes, we did think about those methods as well, and we are trying to find something that would satisfy all the requirements, mainly a random number generator that is relatively homogeneous.
That is very important, because if we have a bias towards some ranges then many things will be messed up..
About the loss of health - good thing it finally hit you, because you might feel a bit more inclined now to try and find this bug. I'd be really interested in hearing what did cause this - the more spacy and rare the effects, the more interesting the bug. :-)
About the expensive function:
This is just an idea, but maybe you could partition the maps into quadtrees. That way you would only have to check the people in the players particular and adjacent nodes. The downside is you would have to update what node the player is in whenever he moved. You would probably have to do this eventually if you ever wanted to make seemless maps (like Runescape, when you don't switch maps, but just walk from one area into another). I think seemless maps would be nicer anyway, it seems silly you can't see into Portland from whitestone when you are standing by the exit.
Just some ideas.
Partioning the map in quad trees is done on the clientside. On the serverside, doing that would be totally unoptimal.
One huge map versus smaller maps, well, there are pros and cons for both. If you have your game divided in smaller maps, it's easier to navigate (not get lost), less complex to implement, faster, and the map making can be done by multiple people at the same time, without having to worry about the map seams, and so on.
Currently, we have no plans or desire to go to a monolithic map model.
Post a Comment
<< Home