In the age of 2D games, computers were limited by slow CPUs and small memory sizes. The Sinclair ZX Spectrum, for example, used a Zilog Z80 8-bit processor running at 4.77 MHz and included 48KB of RAM. In the console arena, the original Nintendo Entertainment System (NES) ran on a 6502 chip. So, game programming was really a case of creating detailed, rich environments on very restrictive platforms. As an example, a typical 640x480 image taken from a digital camera is, by today's imaging standards, pretty low resolution. But stored in 24-bits of color, that image would take approximately 900KB about 20 times the amount of memory available on a classic 8-bit computer.
In fact, reversing this equation, you would discover that the 48KB available on these little machines can barely hold a 128x128 image using 24 bits per pixel for the color. And that's assuming we could use all the memory for the bitmap, forgetting about the operating system (OS) and main program code!
The size of the memory is only one of the problems of coding for 8-bit machines. You might assume that those 48KB of RAM would be arranged in an intuitive fashion, such as a linear array you could freely allocate. But no, old-school memory mapping was more complex. Memory was usually fragmented into sections reserved for specific purposes. Part of the addressing space was taken by the OS, part was dedicated to interrupt vectors (which held the machine code for low-level routines such as keypresses and hardware timers), and part was dedicated to devices such as the color palette, and so on. Coding for one such platform involved knowing the memory map very well, so the programmer understood what could be placed where.
This might sound like history for many programmers, but it is more recent than you think. The IBM PC was coded this way for ages until Windows 95 (and hence DirectX) came along. In the following listing, you can see a traditional memory map of a PC-compatible machine, with the interrupt vectors (IV), interrupt service routines (ISRs), and frame buffer at address A0000H.
1 Mb = 0x10000:0000 1 Mb-1 = 0xFFFF:000F End System BIOS area 896 Kb 0xE000:0000 Start System BIOS area 896 Kb-1 = 0xDFFF:000F End Expansion card BIOS area 768 Kb 0xC000:0000 Start Expansion card BIOS area 768 Kb-1 = 0xBFFF:000F End Video RAM 640 Kb 0xA000:0000 Start Video RAM 640 Kb-1 = 0x9FFF:000F End DOS RAM 0 Kb 0x0000:0000 Start DOS RAM
As a final note on memory, it is important to understand that many systems did not have "secondary storage," such as a hard drive where you can store data and swap it in at runtime. In a modern game, only the data for the current level is usually held in memory; every time a player advances one level, old data is flushed out to leave room for the new data. Many old machines did not have file systems. Data and code were interleaved in an integrated whole, and programmers had to be careful that coding mistakes did not access data zones. These machines came with a program loader that basically dumped data from physical media (tapes, cartridges, and so on) to main memory.
Notable exceptions to this rule were game consoles, which did not need to load memory because the cartridge was the memory, and the IBM PC, which had a reasonable file system thanks to DOS.
Today, it is hard to understand what it means to code for some of the older hardware. CPU speed is now measured in gigahertz, but some of the older machines barely reached the megahertz scale. However, there is more to programming than raw speed. Do you want to code a game like Asteroids, with its simple yet elegant physics and inertia? If you try that as an exercise, you will surely need trigonometric functions such as the sine and cosine. They govern the direction (given the yaw angle and the speed) using the popular equation:
Mathematical signs and whichever axis you call X or Z can vary depending on the convention you follow. But the heart of the equation should be familiar to you. Now, let's stop and consider that simple but devilish equation. You can see that we need two trigonometric evaluations, two multiplies, two additions, and two variable assigns. Simple enough, isn't it? But the situation is far from ideal, especially in 8-bit computers. To begin with, imagine that you don't have that fancy floating-point unit that performs sin and cos for you. Getting headaches? Well, I can hear the advanced readers telling me to revert to lookup tables instead. But wait, there's more. Imagine that you don't have floating-point instructions such as the multiply and the addition. To make matters worse, also imagine that you don't have floating-point numbers, but instead have 8-bit integer values only. Does this sound like mission impossible? Well, that's the world game programmers lived in for about 15 years, and some of them on simpler platforms still code under these restrictions today.
In this chapter we will first cover the data structures that made these games possible. We will then move on to classic algorithms, and wrap up with a summary of popular 2D-age special effects. As a whole, this should provide a good overview of 2D game programming algorithms.