Introduction
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.
Shadow OAM
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.