|
|
 |
 |
 | | | | |
 |
|||
 |
||||||
          |
 |
 |
||||
|
Gameboy Advance Resource Management OBJ Sprite Memory Management The sprite image map itself is stored in OBJ VRAM. In BG mode this region is 32k. This is a very small amount of memory to store images. For example a single sprite image can be as much as 4k. It is possible to manage this memory area "manually". You decide how big each type of game element is going to be and you pre-allocate slots for each type. So if each of your main enemies is no bigger than 2k each then you statically pre-allocate a fixed number of slots for AI's and a slot for your main character, some slots for the particles and a small area for the UI. The problem with this is that it quickly becomes unmanageable when the needs of the game change. You run the danger of keeping certain slots always free in case you need to load a font, an extra UI meter, etc. Furthermore, you may need to have a different memory map for each screen type. These two problems interact badly. You may find that you have to write several versions of the same code that will, for example, display a similar in-game UI in different ways depending on the state of the game. This type of management also becomes a code maintenance problem. As the project progresses, as the art needs become clearer you may find yourself having to refigure the memory maps many times. On the other hand this kind of memory management makes you think about exactly what is on the screen at all times, and you can be sure you will never run out of OBJ memory.
Implementing a general-purpose memory manager for OBJ VRAM solves many of the problems above. The code that displays various game elements receives pointers from the allocator and never has to worry about exactly where they are. A memory manager for OBJ VRAM needs to have several properties to be useful. First it needs to be extremely efficient with memory. Given the very small memory area, we need to make sure that we have as much of it available as possible at all times. It also needs to be very careful about memory fragmentation. If for example a small UI element is allocated in an unfortunate location early on, it may keep a larger section of memory off limits for all but the smallest sprites for the duration of a game level. This could mean the difference between being able to reliably display six characters on the screen versus just three. To deal with fragmentation the manager needs to coalesce small blocks of free'd memory into larger blocks. Finally the memory manager needs to be somewhat fast. Absolute top speed is not critical because loading a new sprite involves copying a new image to OBJ VRAM, which takes some time anyway. The blocks allocated into OBJ memory have certain properties that you can rely on to simplify what the allocator has to do. The AGB sprite unit supports 12 different sprite size configurations (8x8, 16x16, 32x32, 64x64, 16x8, 32x16, 64x32, 8x16, 16x32 and 32x64). These configurations translate into a smaller number of absolute memory sizes (32, 64, 128, 256, 512, and 1024 bytes). All of these are powers of two, and all are multiples of 32 bytes. Given that the OBJ VRAM is 32k, we can manage this memory as 1024 32-byte blocks. With such a small number of blocks, we can keep track of which blocks are used and which are free with a single "allocation map" array of 1024 bytes, and we can refer to any allocated memory area with a 16 bit block ID. We fill the elements of the allocation map with one of three values, UNUSED, USED, and CONTINUE. Unused blocks are simply labeled UNUSED. When several contiguous blocks are allocated we label the first allocated block with USED and all of the following allocated blocks with CONTINUE. This way when that memory area is free'd, we will receive the block id of the first allocated block and we know to free all the following blocks until we reach one that is not labeled CONTINUE. We free them by simply labeling all the free'd blocks UNUSED again. Contiguous free'd memory areas will become joined automatically. We allocate blocks only on regions that are even multiple of the desired block size. This way when blocks are allocated they are less likely to create regions that are unusable by blocks of the allocated size or smaller. And when blocks are free'd they are more likely to create regions usable by larger block sizes. For example, if we allocate a single 32-byte region (a sprite that is 8x8 pixels, by 4 bits) and then a 64 byte region, when we free the original 32 byte region we open a space big enough to allocate another 64 byte region. Tile Management in Tile-Based Engines It is straightforward to create tile based rendering engines on AGB. The graphics hardware supports multiple layers of 8x8 pixel tile maps. Typically, you store a set of tiles in ROM. This can be an array of all the tiles in a level, and a set of tile maps. The tile maps are 2D buffers with indexes into the tile array. During rendering, for each layer, you allocate a smaller 2D tile map in BG VRAM, and you copy all the visible tiles into BG VRAM version of the tile set. The RAM tile maps have indexes into the tile set in RAM. You pass the addresses of the tile set and tile maps to the AGB hardware, and the AGB graphics chip does the rest. The only tricky part is keeping track of the mapping between the RAM and ROM versions of the tile set. As you scroll the smaller RAM based tile map around you need to copy new tiles into VRAM as needed and free tiles that are no longer needed out of the RAM tile set. So for example when you copy in a new row into the RAM tile map, you need to read a row from the ROM tile map. This has indexes into the ROM tile set. You have to quickly determine if the referenced tile has already been copied into RAM. If so, you simply use the RAM version of that tile index in the new row of your RAM tile set. If not, you need to allocate a new tile in RAM, copy the appropriate tile from ROM. Whenever a row is removed from the RAM tile map, you need to quickly determine if the tiles in that row are still being used in another part of the map. Only if they are no longer being used is it safe to free that tile from the RAM tile set. To do this we implement three arrays:
To initialize the arrays, you set the RAM-to-ROM and ROM-to-RAM arrays with a magic value that indicates an unused mapping. You need to find a value that is bigger than the largest valid ROM tile index. (As a practical matter, use 0xFFFF. Your options on AGB are to use 8-bit, 16-bit or 32-bit indexes. 8-bit indexes are too small, allowing only 255 tiles. 16-bit indexes allow up to 64k tiles, which is way more than the AGB can support, so there is no need to use 32-bit indexes.) The ref count array is initialized with each entry pointing to the next entry on the list. In other words: initialize entry "0" with the value "1", entry "1" with the value "2", etc. When you need to load a new tile into RAM, you start with the ROM index of the tile you need that was read from the ROM tile map. You check the ROM-to-RAM array. If the value is not the magic unused value, then the tile you want has already been allocated, and the ROM-to-RAM array gives you the RAM index you need. Simply increase the reference count in the ref count array, and write the RAM tile index into the RAM tile map. If the tile has not been allocated then you unlink first element off the free list, and set its reference count to "1", update the ROM-to-RAM mapping, and the RAM-to-ROM mapping arrays. Finally copy the actual tile data into the RAM tile set, at the address specified by the RAM index. When you need to free a tile, you start with the RAM tile index of the tile you need to free. Use this RAM index to check the reference count in reference count array. If the reference count is greater than one, decrement the reference count and you are done. If the reference count is only one, then you need to link this tile back into the free list. Now you need to clear its entry in the ROM-to-RAM array. Unfortunately you only have that tile's RAM index, so you look up its ROM index in the RAM-to-ROM array, and use the ROM index to clear the proper entry in the ROM-to-RAM array. There is one tile that you will want to handle specially, which is the all-transparent tile. In a system with multiple layers it is likely that a large number of tiles in each layer will be copies of the tile that is all transparent (on AGB this is all pixels set to color "0"). You could dynamically manage this tile like the others, but given that this tile is likely to always be on the screen you can special case it. Make this tile always be tile zero in both the ROM and RAM maps. At initialization time, copy the all transparent tile to the first tile in the RAM tile set, and remove it from the free list. Then, whenever you read a zero in the ROM tile map, just copy a zero to the RAM tile map. Don't bother with allocating, reference counting and freeing this tile. There is no need to bother. You will typically save having to do any tile management for about half the tiles being displayed at any time. The nice thing about the allocation scheme described above is that allocation and deallocation are fast constant time operations. You don't have to worry about coalescing allocated blocks because all the blocks you allocate are the same size. In AGB it is possible to have simultaneously 4-bit and 8-bit layers. In the 8-bit layers each 8x8 pixel tile is 64 bytes. In the 4-bit layers each tile is 32 bytes. Each layer can only use one kind of tile, but you can simultaneously display multiple layers that have different bit depths. One way to deal with this is to simply duplicate the system described above. Reserve one region of memory for the 4-bit tiles, and another region for the 8-bit tiles, and make two versions of the tile management data structures. One downside to doing this is that as the number of 4-bit and 8-bit tiles change, the 8-bit tile region will not be able to use free space in the 4-bit tile region and visa-versa. We can extend our allocation scheme to manage tiles of two sizes using the same data area to store both kinds of tiles, but its kind of tricky. The RAM tile maps that are passed in to the AGB rendering hardware use 16 bits to encode each map entry. Only 10 bits of those 16 are used to encode the tile index. The remaining six bits are used to store various flags. This means that the entire tile set for any one map can have no more than 1024 tiles. For 8-bit tiles this is a memory area of 64k, and for 4-bit tiles this is a memory area of 32k. If you want to allocate both 4- and 8-bit tiles from the same shared-memory area, you must be careful to allocate the 4-bit tiles from a single 32k sub region of the 64k data area. For example, if you were allocating from a 64k buffer, you could allocate shared 8- and 4-bit tiles from the first 32k and then allocate only 8-bit tiles from the second 32k. For a 64k tile set region you need to keep track of 2048 32-byte blocks. To implement this scheme we need three linked lists interwoven in the reference count array. One linked list, "list-a" links all the even numbered entries for the first 1024 entries, and the second linked list, "list-b", links all the even numbered entries for the second 1024 blocks. This allows you to allocate only pairs of blocks on even block boundaries. When you allocate an 8-bit tile you use two consecutive blocks to store the tile. When you allocate a 4-bit tile you use a just the first 32-byte block. The second block in the pair that is left free is placed on a third free list, "list-c", which keeps track of left over single blocks that are good only for allocating single 4-bit tiles. To allocate a new 8-bit tile, you check first to see if you can find a free pair of blocks from "list-b" where you can only allocate 8-bit blocks. If this list has no free blocks, then you try allocating from "list-a". To allocate a new 4-bit tile first you see if there are free 4-bit blocks in "list-c". If so you use one of the blocks from that list, if not you use a pair of blocks from "list-a". The first block you use for the 4-bit tile, and the second block you move into "list-c". To free an 8-bit block you determine if the free block belongs in "list-a" or "list-b". 8-bit blocks with a tile index of smaller than 1024 go into "list-a", bigger blocks into "list-b". To free a 4-bit block you need to check if the block that is part of its two block pair is already free. For even numbered blocks this is the following block, for odd numbered blocks you check for the previous block. If this pair block is free then you remove the pair block from "list-c" and add the pair back into "list-a". If the pair block is not free you just add the free'd 4-bit block into "list-c". On the AGB the BG VRAM area is 64k in total, so you cannot use this entire area for tiles because you must save some memory for the actual tile maps. For our sidescroller we need four small tile maps that take up 2k each, leaving 56k for the RAM tile set. So, our shared 4- and 8-bit tile region is 32k and the remaining 24k is used for the 8-bit only tile region. This allocation scheme is extremely fast. Allocating and deallocating tiles in all cases is a constant time operation. This is critical because in a 4-layer sidescroller for example, if you allow each layer to scroll a maximum of 8 pixels per frame in any direction you will need to reallocate a maximum of 500 tiles per frame. The majority of those tiles are likely to already be loaded, so you may not have to actually copy all 500 tiles into memory each frame, but each one of those 500 tiles will need to be checked through the tile allocation and deallocation routines. On the down side this scheme does take significant memory resources. We store the three linked lists we need interwoven in the same array that we use to store reference counts, so this does not take much memory, but the various RAM-to-ROM and ROM-to-RAM mappings can be large. In the configuration we are using for our game engine we are using about 48k of RAM to store all the data. Given that the AGB main system memory is only 256k, this is quite significant. This memory requirement can be significantly reduced by reducing the size of the largest allowable ROM tile set. ________________________________________________________ |
||||||||||||||||||||||||||
|
|
Features
