A big part of making a successful Gameboy Advance game is managing system resources. In this paper I present algorithms and code for managing one of the most important resources on AGB: the various kinds of memory. These types include: OAM memory, OBJ sprite memory, tile management for tile engines (like sidescrollers), and general purpose memory management. Each of the various kinds of memory on AGB has special restrictions that require special attention to how memory is allocated. Furthermore, because of some of the inherent restrictions on how memory can be allocated we can tailor the memory allocation routines for each memory type for added efficiency.
Code listings for all the systems described in this paper are available on: http://oroboro.com/rafael/gdctalk.html
AGB Memory Architecture
The AGB has 9 different memory areas: System ROM, CPU External Work RAM, CPU Internal Work RAM, Register memory, Palette RAM, OBJ VRAM, BG VRAM, OAM and CART ROM. Some of these areas are either not dynamically managed (System ROM, Register memory, and CART ROM) or are trivial to manage (Palette RAM).
Palette RAM Management
The Palette RAM memory area is 1k, just enough memory to store two 256-color palettes with 16 bits of color resolution per palette entry (actually only 15 bits are used, but the storage is 16 bits). For these you simply block copy the palettes to the two palette blocks and you are done. It is possible to implement a palette stack where palettes can be pushed onto the stack and the palette manager simply keeps the top of the palette stack on the palette area and copies palettes that are lower down in the stack to a buffer in work RAM.
OAM Memory Management
The OAM memory area is 1k, and is used to store 128 8-byte entries. Each entry represents one sprite being displayed. The entry has room to store the screen coordinates of the displayed sprite, a reference to the sprite data in OBJ VRAM, a bunch of flags and other display parameters. Moving a sprite on the screen, or changing its display parameters (flipping, transparency, Z-depth, rotation) is a matter of tweaking the OAM entry associated with that sprite. Managing this memory would be trivial except for the fact that the Z-depth of the sprites is determined by where the sprite appears on the list. OAM entries near the top of this memory area (smaller memory addresses) are displayed on top of sprites lower down in memory. There is a rough scale four-layer priority scheme in OAM memory—that can be done using the priority flags in each OAM entry—but for finer-scale Z-ordering the OAM entries must be stored in Z-depth order.
Keeping the OAM entries sorted can be a big pain. Ideally, when you allocate an OAM entry, you want to store the entry number so that you can change its display flags to move the sprite around on the screen. This requires that either the entry number never changes, or whenever it changes (due to Z-depth changes) you have to track down all references to this OAM entry number and change them.
For our game engine we decided that we want the finer control of Z-depth and that a call back scheme or reference-counted OAM entries was too much trouble. So we implemented a system whereby we keep two versions of the OAM data. One version resides in the hardware OAM memory area, and another version, the "Shadow OAM" is allocated in CPU External Work RAM. The work RAM version includes some extra data entries to help manage Z-depth without changing the memory order of the OAM entries. The Shadow OAM has a copy of each OAM entry, plus the Z-depth of each OAM entry and a linked list pointer, an 8-bit reference to the OAM entry with the next highest Z-depth.
Every game frame (which happens every hardware V-blank) we copy the Shadow OAM to the hardware OAM in Z-sorted order. This way the hardware OAM can change its order as necessary, while the order of the OAM entries in the Shadow OAM stays fixed. All other game systems that need to change the display parameters of a sprite can make changes to the flags in the Shadow OAM with full confidence that during the lifetime of any given sprite its location in the shadow OAM will never change.
The OAM manager also sets the OAM entry's BG Priority flags appropriately. It is enough to just define the Z-depth of each BG layer, and the BG priority flags will be set appropriately.
For most modifications to the sprite's display parameters, game systems can simply write new flags into the Shadow OAM. To change the Z-depth is a little more involved, so we provide a function to change the Z-depth that will update the linked list. Given that we provide only a singly linked list to encode the Z-depth, changing the Z-depth involves searching from the top of the linked list until you find the appropriate spot. There are usually far fewer elements on the screen than the maximum ( 128 ), so this has not been a problem for us. There are various ways to eliminate even this cost. One could implement a doubly linked list by allocating just one more 8-bit list pointer ( total cost: 128 bytes ). One could also subdivide the Z-depth range into segments each of which has its own linked list. For example one could implement a Z-range for game UI elements, another for a particle system and another for characters. In this case it is likely that only the characters would have many Z-depth values, and OBJ memory limitations are such that you are unlikely to have more than six of these on the screen at a time.
The cost of refreshing the hardware OAM is linear with the number of sprites being displayed, and the majority of the copying can be done using DMA. The total memory cost for this system is almost neglible, 1k. The code itself is stored in ROM, so its cost is even less of an issue. If you don't need fine scale Z-depth for your project it might not be worth the small amount of time it takes to maintain the Z-order linked list pointers and the time it takes to refresh the hardware OAM every frame.