Interesting Findings in Video Game Development
Not long ago, I came across an interesting story from old times of video game development involving Random Number Generators. I want to share this here. But before discussing this story, let’s go back in time to get some background.
In 1985 Nintendo redesigned the game console market. Nintendo released the Nintendo Entertainment System (NES) in the United States of America. The NES was a redesign of the Famicom, the Family Computer, which already took the Japanese video game market by the blitz. Two years earlier, the video game market crash occurred. The oversaturation of consoles, poor games, and the rise of personal computers made video game consoles unattractive. As many people lost their jobs and money and the market was tired of video game consoles with home computers coming up, this was quite a huge risk to failure for Nintendo. Nintendo had brands that excited the kids. These were the craftsman Mario and the hero Link, made famous in Legend of Zelda.
The NES and the Problem of Randomness
Unlike the home computers of the time, there was one very big shortcoming with the Nintendo Entertainment System. The system had no source for random numbers. However, there was still a need for random numbers. Of course, you would not need random numbers for a puzzle game, but its randomness gives a play, something like pepper is for the soup. A game that is not predictable but demands chains players to their chairs.
So imagine a 30-year-old programmer who goes through the task of creating a computer game called Final Fantasy. Nasir Gabelli, an American-Iranian game developer, had the challenge to do it quickly. Although he had already gained experience with game projects on the Apple II, he now had a particular objective with his new game. He was required to think about the problem of randomness. While home computers like the Commodore C64 had a hardware timer or a sound chip that developers could use to generate a seed (See my series on Random Number Generators on Yammer for more reference) and random values, the NES had nothing.
Nasir found an interesting approach to solving this problem. Instead of scanning libraries for solutions, remember no internet, he did the following: He created a table with random numbers which came up to his mind. In the game code, Nasir implemented a pointer to this table. He incremented the pointer to make the game read from the next position of this table whenever he was required to make something random. Playing around with making his table more random, taking the memory of a total of 48 kilobytes into account, it got 256 bytes long. And this became the core of one of the most successful games ever. Imagine that this kind of randomness would be a vital factor in security. Danger, Will Robinson! For video games, that was enough at that time.
The NES Version of Tetris
However, there was another interesting thing happening with the NES. Nintendo was working on converting the very popular title Tetris, a game by a Russian software developer. While the history of that game and all the problems of the Russian developer with it, in a time of communism, would already be stunning enough, the way to handle randomness in it is as interesting alone.
The NES version of Tetris, released in 1989 by Nintendo, implemented a 16-bit Fibonacci Linear Feedback Shift Register (LFSR) to generate a stream of pseudo-random numbers. This LFSR is a type of shift register that creates a sequence of binary values based on the previous value in the sequence. It’s Fibonacci because it uses the Fibonacci sequence as so-called feedback taps. In a 16-bit version, the generator has a shift register that can hold 16 bits or binary digits (0 or 1).
In an exemplary first step, the sequence is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0].
At positions 14 and 15, we got our taps.
At each step, the leftmost position gets shifted, and a new value is calculated by XOR-ing the values at the feedback tap positions. So you got professional and non-deterministic randomness.
But why this randomness? If you need to understand the game. You have to fill lines by arranging different shapes. Tetris has seven figures. And it is vital to generate the first and the next items randomly. While all this randomness helped develop the next shape items, it could not prevent one specific issue. It could not stop the shapes from repeating themself two times after each other.
So Nintendo coupled their Random Number Generator with a history check to reduce the occurrence of piece floods (repeating pieces). The process involved: Choosing a sample. Checking if it was the same as the last, and it was. Selecting a new part but only once.
The final piece dealt with was determined by the result of this check. Nintendos check had some other troubles, but what is the world without errors?
The story of Nasir Gabelli with his random number generator and the NES version of Tetris serves as a reminder of the creativity of game developers in the face of limits. And on the other hand, it serves as a warning if we look at Cybersecurity. Who solved what limitations by a simple table, maybe even 256 bytes?