Fast Pseudo Random Number Generator

Games need a good pseudo random number generator (PRNG). Flipping cards, rolling dice, determining hit points, choosing whether to fire a bullet or not, all these are random choices. Random is a strange phenomenon though. The set of numbers 1,1,1,1 is just as random as 4,2,1,3 — even though I carefully hand-picked both sequences, the latter looks more random. A shuffled list of numbers is perceived as being more random than a list of truly random numbers.

It is a well-known fact (or actually, myth) that computers do not do random numbers; instead they are computed and therefore they are predictable. This was true until computer scientists found that real-world noise like typing speed, mouse movement, networking interrupts, and hard drive rotation statistics may be used for entropy: a source for random number generation. This is only a source though and the produced random number sequences may still be predictable depending on the algorithm used. Cryptographically safe RNGs aim to make it impossible to guess the next random number. There is a kind of chicken-and-egg relation here: crypto functions need good RNGs to be able to scramble the input; the scrambled output appears as random as any random data. Therefore the crypto function can be used as a RNG.

Anyway, there are some problems when it comes to games. Fast-paced action games may make hundreds of random choices every frame. At 60 frames per second, we don't want to take too much time generating random numbers. Therefore cryptographically safe RNGs are off limits, we are going to have to settle with a more predictable PRNG.

Another problem is that at 60 fps, we might quickly drain the entropy pool. We can't afford having to wait for new entropy, and we don't want the operating system to run out. So even though modern operating systems can supply fairly truthful random numbers, we are not going to bother and stick with “decent enough” instead; we are going at it old-skool and calculate the pseudo random numbers by ourselves.

PRNG requirements for games:

• it must be fast
• it must show good distribution
• not repeating numbers often
• no cryptographically safeness required

In them old days, we would use rand() and seed it by calling srand(). rand() is a notoriously bad PRNG and you should not use it nowadays. The BSD man page even calls it “bad random number generator”. It has a low period, meaning that after a while the same prefix starts to repeat. This is a bad habit for a PRNG.

I personally have bad experiences with rand(). My Tetris clone would happily generate the same block over and over again, giving some really bad gameplay experiences. I started handing out bonuses for this, but it didn't make it more fun. The game notably improved when I switched to a different PRNG.

The modern, new and improved equivalent of rand() is random(). It should be noted however that there might be a portability issue here; random() may not be available on your platform of choice.

Mersenne Twister
A popular modern PRNG is the Mersenne Twister. It is named after the Mersenne prime number that it uses. It is a well respected PRNG, and an easy choice for C++ programmers, as it is included in the C++11 standard library. The C++11 way to get some random numbers is:

#include <random>

    std::random_device rd;     // only used once for seeding
    std::mt19937 rng(rd());    // select Mersenne Twister
    std::uniform_int_distribution<int> dist(0, 1000);
    int n = dist(rng);

The Mersenne Twister is relatively slow for game code. Apparently it badly stresses the CPU cache.

XorShift

The most simple and fastest decent PRNG there is, is the XorShift algorithm. It simply does a couple of bit-shift and exclusive-OR operations, and that's it. It has four internal state variables that you should initialize (in a more or less random manner, as you see fit).

uint32_t xorshift128(void) {
    // algo taken from wikipedia page
    uint32_t t = state.x ^ (state.x << 11);
    state.x = state.y;
    state.y = state.z;
    state.z = state.w;
    state.w = state.w ^ (state.w >> 19) ^ t ^ (t >> 8);
    return state.w;
}

XorShift is incredibly simple, but good enough for games. In that respect, it is a perfect fit for our purposes. There are XorShift* and XorShift+ variants, that use multiplication and addition respectively, and produce 64 bits values.

Statistical Analysis

In a feeble attempt to prove that XorShift suffices, I calculated the standard deviation for a series of numbers between 0 and 1000 generated by rand(), random(), std::mt19937, and xorshift128(). They all produce a standard deviation around 285, meaning that they all exhibit the same fairly high spread of values. In that sense, we can say that probably they all produce sets of random values usable for games. This is by no means an extensive analysis of the PRNGs, of course. There exists a test suite named TESTU01 for testing PRNGs, but I'll leave it up to the math and computer scientists to play around with that.

For now, I'm happy to have found that the XorShift PRNG is exceptionally fast, while still producing decently enough pseudo random numbers. It is a perfect fit for games.

Two interesting links for further reading:

• Eternally Confuzzled about rand()
• Dr.Dobb's on Lehmer numbers

Wrapping Worlds

In the classic game Pac-Man, there is a tunnel in the middle of the level, when you go in on one side, you emerge on the other side of the screen. It plays an important part in gameplay, as you can use it to evade the fast red ghost.

In the classic Defender, if you fly your spaceship far enough to the right (or left, as you can go both ways), space will wrap around and you will eventually return to the same point. The game world of Defender is cylindrical.

You will find this technique of wrapping worlds a lot in classic 2D games. It doesn't work well for 3D games, because of their level of realism and immersiveness, it feels weird if a 3D world wraps. [The irony is that the real world does seem to wrap around, as observed by a traveller on the ground]. On the other hand, I always I feel weird when reaching the edge of the obviously square world in 3D games.

Anyway, wrapping worlds are a lot of fun for 2D retro style games, and I couldn't find much information on the net how to go about and implement such a thing. So I devised a couple of methods and wrote them down here.

1. The straightforward way

Wrapping is simply achieved by using the modulo operator. If the player moves off the map, her new position is mod the world width. Consequently, when a player moves off the map on the right, she re-emerges on the left. That was easy.

But not so fast. A monster chasing the player will effectively see the player being teleported from the right side of the map, to the far left side of the map. The monster will now change direction, and has to travel all the way across the map in order to get near the player again. So to fix this, you might set a flag that a monster is not allowed to turn if ... But there is more. A similar problem exists for monsters that live in the left side of the map. They will not see that the player is actually close nearby, until the player is teleported in over the right edge of the map. By now it's becoming clear that wrapping is not as easy as it looks.

2. Overscan areas

Rather than having the map just be the map, allow the player (and everything else) to exist in a boundary outside the world. The boundary area is like an overscan area.
This region is a copy of the other side of the world. Once the player ventures too far, teleport everything in the overscan area to the other side.

The overscan area should at least be a screen wide to work properly. Maps should also be at least two screens wide. This method is relatively costly on memory because it duplicates large parts of the map.

3. Far offset

The previous method still has a problem with the direction of monsters that are outside the screen.
A way to solve this is to have the game take place at a far offset. The problem with wrapping is partly because we're too close to zero. By translating the origin to, say, 100,000, we're largely preventing the problem of monsters heading the wrong way. It's mostly a band-aid though as the situation still does exist. Eventually the player may reach the zero line, at which everything needs to be rebased at the far offset again. It is unlikely that any player will venture so far that she wrapped around the world a dozen times, but nevertheless possible.

4. Sliding window

Let the area around the player be a sliding window that glides over the map. The area should at least be what's visible on screen, but may be larger to allow off-screen monsters to come in and attack.

The sliding window uses ‘stripping’ to phase in and phase out relevant parts of the map. For example, as the window slides to the right, a vertical strip slides into the window on the right, and a vertical strip slides out of view on the left. This works particularly well for tiled maps. Monsters can be frozen into the tile map, and come to life as soon as they come into view. The coordinates of alive objects are relative to the sliding window (they are no longer in ‘map’ space) and therefore there is no directional problem when the world wraps.

I implemented each of these and they all work. What seems to me the best method however is the sliding window technique. Even for games that are not tile based at all, you may want to consider adding a tile grid anyway. The sliding window technique makes a clear distinction between objects that are alive, and objects that are not worth spending time on. You can enjoy a massive world with millions of objects without breaking a sweat. And what's fun, the world wraps.

Rock solid frame rates with SDL2

For fast-paced action games you need to have a steady framerate. If the framerate is not steady, you are likely to see stutter. It's a periodic wobble, jerky movement, as if a frame was skipped. It's very annoying, and once you see it, you can't unsee it. I ran into this problem and for a moment there, I just blamed SDL, heh! In forums online, I found more people complaining about stutter with SDL. The accepted answer on StackOverflow for this problem was wrong. Game dev forums did turn up some good tips. Finally, I was able to piece it together. Apparently this topic is not well understood by many—and the ones who do get it right don't seem to get just what the problem is. It has indeed to do with frame rate, but it's not skipping. Something else is up.

Loop the loop

Games run in a loop. You update some monsters, do the rendering, and cap the frame rate by delaying until it's time to display the next frame. It's likely to be programmed something like this:

    move_monsters();
    render();

    float freq = SDL_GetPerformanceFrequency();

    now = SDL_GetPerformanceCounter();
    secs = (now - last_time) / freq;
    SDL_Delay(FRAMERATE - secs * 1000);

    swap_buffers();

NB. You might also use SDL_GetTicks(). SDL  2 offers new performance counter functions. These have much greater precision than SDL_GetTicks().

We've subtracted the time that the game was busy, so to complete a frame we need to wait the remaining time. This is exactly where the bug is, odd as it may seem. To prove it, try timing SDL_Delay() calls in a loop:

    float freq = SDL_GetPerformanceFrequency();

    t0 = SDL_GetPerformanceCounter();
    SDL_Delay(30);
    t1 = SDL_GetPerformanceCounter();

    printf("time slept: %.2f msecs", (t1 - t0) / freq * 1000.0f);

Result:

    time slept: 31.51 msecs
    time slept: 31.31 msecs
    time slept: 34.06 msecs
    time slept: 32.15 msecs
    time slept: 34.54 msecs
    time slept: 33.07 msecs

But we asked to sleep only 30 milliseconds! How can this be?

The problem is not so much with SDL as with the operating system. This can be proved by replacing SDL_Delay() with usleep(), and the problem persists. Even if you try the insanely precise nanosleep() call, the problem persists. Sleeping is inaccurate—despite the fact that modern computers are very capable of doing high precision timing.

Some try fixing this by sleeping a little less, and then doing a busy loop to get as close to the sleep time as possible. This almost works, but it it isn't perfect and you will still see stutter. The non-deterministic nature of a multitasking operating system gets in our way.

Thou shall wait

So, the system is incapable of sleeping an exact amount of time. How about not sleeping at all.

The trick of sleeping until the next frame is probably a spin-off of the waiting for vsync trick. But sleeping isn't the same thing, and it doesn't work because it doesn't necessarily bring you in sync with anything. So instead of sleeping, we are going to wait for vsync.

    sdl_window = SDL_CreateWindow(title, x, y, w, h, SDL_WINDOW_OPENGL);
    gl_context = SDL_GL_CreateContext(sdl_window);
    SDL_SetSwapInterval(1);

This is for use with OpenGL. It will enable the swap interval (wait for vsync) before swapping the render buffers. You can remove any SDL_Delay() calls, because during the swap interval the program already sleeps. If you are using the SDL render functions, it's done like this:

    renderer = SDL_CreateRenderer(win, -1,
        SDL_RENDERER_ACCELERATED|SDL_RENDERER_PRESENTVSYNC);

Now SDL_RenderPresent() will wait for vsync before presenting the buffer.

Moving on

That's only half of the story. The problem of stutter is not solely caused by an inaccurate sleep timer. It stutters because movement is too rigid:

    new_pos = old_pos + speed;

This sort of code always advances the position, no matter whether time advanced evenly or not. So in the case where time did not advance perfectly in line with the desired rate (which is impossible, as we saw earlier), this code will produce stutter.

To solve this problem, we must write code that can handle variable timings. It works just like in physics class:

    float delta_time = (now - t0) * (float)freq;

    new_pos = old_pos + speed * delta_time;

With SDL_GetPerformanceCounter() and SDL_GetPerformanceFrequency() you can calculate the time step for this frame in seconds. Note that delta_time holds a small value, so crank up the speed. If your game world is defined in meters, you can simulate things rather faithfully with speed in meters per second.

At last

Lo and behold, our frame rate is now rock steady and scrolling is super smooth. It's locked down at 60 fps, with very low CPU usage, even on my five year old computer. Like with Columbus' egg, it's easy once you know how.

My advice for testing is to create a large checkerboard and scrolling that across the screen. If it stutters, you will see it. Also try disabling the vsync just for fun, and watch the fps counter go nuts.

Memory Management: the SLUB allocator

Last time I wrote about the SLAB allocator, a method for caching objects in a pool. And then I read about SLUB, the slab allocator that is present in modern versions of the Linux kernel, and got a bit carried away with it. SLUB is brilliant due to its simplicity, and like the Linux kernel, by now I have thrown out my SLAB code in favor of SLUB. That's how it goes with the software lifecycle; out with the old, in with the new. Descriptions of how these allocators work often either do not go into enough detail, or are way too cryptic to understand, so I'll do my best to shed some light.

Pool allocators basically cache objects of the same size in an array. Because we are talking low-level memory allocators here, the absolute size of the array is always going to be a single page. A single page is 4 kilobytes. [Yes, I know hugepages can be 2 megabytes, and sometimes even a gigabyte, but for the sake of simplicity we'll work with regular 4k pages here].
To keep track of what array slots are in use and what slots are free, they keep a free list. The free list is just a list of indices saying which slots are free. It is metadata that has to be kept somewhere. The difference between SLAB and SLUB is the way they deal with that metadata (and boy, what a difference it makes).

In SLAB, the freelist is kept at the beginning of the memory page. The size of the freelist depends on the number of objects that can fit in the page. When the objects are small, more objects can fit into the page and the freelist will be larger than when the object size is large, not as many objects can fit in the page.
SLUB is much more clever than this. SLUB decides to keep the metadata elsewhere, and uses the full page for object storage. The result is that SLUB can do something that SLAB can not: it can store four objects of 1k each in a 4k page, or two objects of 2k, or one object of 4k in size. This is something that SLAB could never do.

But what about the metadata? SLUB puts the free pointers inside the memory slots. The objects are free, so this memory is available for us to use.
The other metadata (like, where is the first free object? What is my object size?) is kept in a Page struct. All pages in memory are tracked by an array of Page struct. Beware the confusion here, a Page struct is not the actual memory page, it just represents the metadata for that memory page.

All we did was take that little bit of metadata from each slab, and store it elsewhere. The net result is that we can make use of memory much more effectively than before.

In our last implementation we used C++ templates to make things type safe. While this makes sense from a C++ programmer's perspective, it doesn't make any sense from a memory allocator's perspective. The memory allocator has bins for sizes, not for types. This alone is reason enough not to code it using templates. Stroustrup himself said that object allocation and object creation are separate, and there's no arguing with that.
Therefore the SLUB is implemented as a plain C code, and it turns out very straightforward and easy to understand. You have 4k of memory, the number of objects you can store equals 4k divided by object_size. The first free object slot is page_struct.free_index. When you allocate an object, return the address of slot[page_struct.free_index]. Update the free_index and zero the object's memory, of course. And that's all there is to it, really.

The engineers at Sun actually took into account CPU cachelines and had slab queues per CPU. This may have been a good idea in 1992 but becomes kind of crazy when you realize that today's supercomputers comprise tens (if not hundreds) of thousands processor cores.
SLAB also needs to take into account object alignment, which is automatic in SLUB as long as the object size is a multiple of the CPU's word size, and this is already taken care of by the compiler when it packs and pads a struct. At the end of the day, SLAB is unnecessarily complicated, over-engineered. SLUB says: Keep It Simple, Stupid!

Caches
When the slab runs out of free memory slots, you will want to get a new page and initialize it as a new slab. Likewise, when a slab is entirely free, you will want to release the page. This is trivially implemented using malloc() and free(). It's more fun however to actually cache these pages in a linked list. The pointers for the linked list can again be members of Page struct, it's metadata after all.

The Linux kernel optimizes for speed by keeping linked lists of full, partially full, and empty pages. When an object is allocated or freed, it always looks at the partially full list first. If after allocation the page is now full, the page is moved to the full list. If after freeing an object the page is now empty, the page is moved to the empty list.

You may wonder why it holds on to empty pages rather than releasing them immediately. The answer is that getting a new page may well take a long time. So, the empty list is an insurance policy that the cache can always quickly get a page.
If the cache is empty, it will have to get a new page from an other allocator. The Linux kernel implements the buddy allocator for managing blocks of pages. Implementing buddy allocator code is a bit complicated (and fun), I might write about that some other time.
Anyway, slab allocators are fascinating, and it's nice to know how they work. You can't talk about SLAB without talking about SLUB, and noting that simplicity beats complexity.