Transcription

Your support is greatly appreciated! https://www.patreon.com/8blit

Welcome to 8-Blit, a channel covering all the tips, tricks, and everything in between for programming your own games for the Atari 2600 from 1977.

There’s one task that computers are really bad at doing… and on the Atari 2600 it’s even worse.

In this episode we talk about two weirdly related topics. Generating random numbers… and creating reproducible long series of randomly ordered numbers… all in only a single byte of ram.

That’s all coming up on this episode of 8Blit.

If you’ve even laid on your belly for hours staring up at the Television while playing asteroids, or fixed your TV when the picture goes all waving by banging it on the top or the side… then you just might like this channel.

We explore the technology and history of arguably one of the most iconic game consoles ever made. It’s a flashback to when things were simple, when the color scheme of your home was some combination of brown and orange, and your friends would come by to play Atari. Click on the subscribe button, including that little bell to stay up to date with new episodes and to gain access to tutorials with a ton of code examples. If you’d like to support future episodes capturing the intrepid spirit of Atari from the 70’s and right through the 80’s, then please consider joining us on Patreon.

More information on how you can become a patron today, in the video description.

Computers are great at following instructions… very specific instructions. When we write our code and run it on a computer, it follows our instructions, one-by-one, exactly how we told it. We can tell it to take two numbers and add them together, and return the sum. We can pass a number through an algorithm and transform it into something else, but that something else won’t be random. Passing the same value again will give us the exact same result. That’s because our algorithm is DETERMINISTIC. All of our code is deterministic… and so is the computer running the code. If we give the same input, we’ll get the exact same result… and that’s what makes computers so amazingly powerful. But, that’s exactly what makes them so bad at random numbers.

A random number is something that can’t be known ahead of time… and a truly random number is something that also can’t be influenced, and has a high degree of entropy… the measure of unpredictability.

Since we can’t write random numbers into our code, we need something external to our code to be our input. On many computers we could pull the time from the onboard clock, but this value CAN be known ahead of time by checking the time before executing the code… it CAN be influenced by waiting for a predetermined time… and it has almost zero entropy… because the clock is at its core is a counter, always counting up one millisecond at a time.

Cloudflare, a tech services company, uses real time images of a wall holding around 100 lava lamps in an attempt to generate random numbers for encryption keys. This technique would have a very high degree of entropy, but it’s still susceptible to influence… it’s not a perfect random number, but it’s close, and sufficient enough to generate encryption keys.

Obviously we don’t need to generate encryption keys for our purposes, so we just have to find a ‘sufficient enough’ source for our needs.

One way to do this involves a title screen for your game, or level, that requires the player to press a button or switch to start the game. If you set an interval timer on startup, and read the intervals remaining when the player interacts with the screen, then you may have a ‘suitable’ random number for your purposes. It’s unlikely, but not impossible for the click to generate the same number over and over again.

Another method is to check the interval timer right after you clear the zero page memory and registers. As we’ve mentioned in an earlier episode, when the ATARI 2600 is turned on, the RAM and stack are in an unknown state, including the interval timer. Since the timer, and all related registers are not located in our zeropage of ram, it remains in a random state even after we clear zeropage. Which is the first thing we do at startup.

Both these methods are great at producing a random number… but what can we do with just a single number? You’d be surprised.

We need to turn this single random number… into many. For this, we’re going to use a Linear-Feedback Shift Register.

Linear Feedback Shift Registers, or LFSRs, produce a sequence of numbers through a series of “taps.” A “tap” is a specific bit within the shift register that’s used as an input to the bitwise operations that generate the next value in the sequence. The tap is usually chosen based on the desired properties of the sequence generated by the LFSR, such as its length and randomness.

The role of the tap is to determine the value that is fed back into the LFSR in order to generate the next value in the sequence. This feedback loop allows the LFSR to generate a sequence of values that are dependent on its previous states, resulting in a sequence that has the appearance of randomness.

By carefully choosing the tap or taps, it’s possible to control the properties of the sequence generated by the LFSR. For example, choosing a tap at a certain bit position can result in a sequence that has a maximum length, known as its “period”. Taps play a critical role in determining the properties of the sequence generated by the LFSR and in making the sequence appear random.

Let’s have a look at how our Linear Feedback Shift Register works.

First we need to get our seed value. We do this by reading the Interval Timer and storing the value into our seed variable.

Next, we jump to our LFRS sub routine.

Here we can see that we get the seed value we previously saved, and then we shift the bits using the LSR instruction for a Logical Shift Right. This shifts all the bit one position to the right. Zero is shifted into bit D7, and the original bit in D0 is shifted into the Carry flag. Now we check the Carry flag, and if it’s a 0 then we’re going to store our value back into our variable so it will be used as the seed value the next time the subroutine is executed. If the Carry flag was 1, then we perform an exclusive OR on our value, using a ‘TAP’ value of hex D4, before storing it back into our seed variable.

This particular ‘TAP’ will be able to generate 255 unique pseudo random numbers before it rolls over and starts over again. You can make this even more random by calling the subroutine even when you don’t need the next number… for instance, calling it at the end of every frame. This will provide you better entropy, because the seed will have been shifted an indeterminate number of times by the time you need to use it. Otherwise, you’re always going to pull the next possible number, and when it rolls over, it will generate the same list of pseudo random numbers in the exact same order.

This brings us to our second topic for this episode, which expands on my last statement.

Linear Feedback Shift Registers aren’t just great at generating pseudo random numbers, they’re great at generating a deterministic series of unique pseudo random numbers. Given the same seed value and ‘TAP’, an LFSR will produce the same series of numbers. Not only that, but if you use an inverse of your ‘TAP’, you can move backwards in the series.

You can see this in use with Pitfall, a game by David Crane and published by Activision in 1982. Pitfall features 255 different screens which you can move through by either going to the left or right. It does this by using a Linear Feedback Shift Register like the one shown previously to generate a reproducible series of numbers, of which you can move forward or backward through the series depending on which side you exit each screen.

Each screen is procedurally generated, and the features of the screen are determined by a single byte. Jack Evoniuk has written an incredibly in depth post covering all the specifices on his blog which I’ll link to in the video description.

Without going into too much detail here, we can break down the bit’s in our single bytes to represent if a feature will be present on the screen and in some cases where it will be located.

The first three bits, D0 to D2 represent the objects on the screen, like the fire, snake, money, silver, gold, ring, how many logs there are, and if they’re rolling.

Bits D3 to D5 determine the Pit type and if there are holes to fall through.

Bits D6 to D7 control the pattern of the trees to add variety to the background. Bit 7 is also used to determine which side of the underground the wall will be located if there is a wall.

Using a linear feedback shift register allowed David Crane the ability to encode the DNA, and the sequence of 255 different screens, using only a single byte of RAM.

The example code for this episode expands on our previous episode to show both, how to generate a random number, and how to use the LFSR to move forward and back through a series of pseudo random numbers

On startup, we’ll generate a random number in order to select which one of four arena’s to show, as well as the initial bearing for the ball.

Pressing Reset (or F2 if you’re using the Stella Emulator), will select a new arena, with a new bearing.

Pressing Game Select (or F1 in Stella), Change to the next arena in the series, with the ball retaining its original bearing.

Switching the Right Difficulty switch to A or B will determine which way you’ll move through the series. A for Advance, and B for Back. In Stella, you can use F7 for A, and F8 for B.

While generating a truly random number is a bit of an ordeal, careful planning and using these tricks should make it easy to give your game a life of its own, a large sprawling world, and new challenges every time you play.

If you found the video interesting I’d appreciate it if you’d hit that like button and share this episode with your friends or online communities, like facebook, reddit, or discord.

If you haven’t already done so, subscribe to the channel and hit the bell to make sure you’re notified when a new video comes out… and finally… keep history alive by supporting future episodes and becoming a Patron. I’m excited to start a larger project which will be spread out through a series of future episodes. It’s going to be a lot of work and there’s lot’s of technical challenges to overcome. Details of the project and more will be made available to our Patrons as the project progresses. Your contribution is greatly appreciated.

More information on how to become a patron will be in the video description.

That’s all for now, thanks for watching, and I’ll catch you later!

Back to top of page