Tuesday, October 20, 2009

Sprites à Priorité Dynamique

Voilà typiquement le genre d'environnement qui était pénible à construire avec l'ancienne version de LEDS et qui devient simplissime avec le curseur de copie et autres nouveautés.
Mais c'est aussi le genre d'environnement qui pose problème au moteur de jeu dans sa version ".999" parce que j'utilise les deux plans de tiles comme arrière-plan alors qu'à d'autres endroits dans le jeu (p.ex. quand Bilou est dans un arbre), il se situe en fait _entre_ les deux plans.

Bushes like these were typically the kind of background that was a real nightmare to build with the previous release of LEDS. And with the "copy cursor" and "pull to foreground" modes of the new prototype level editor, it's really easy and funny. On the other hand, it was also the kind of background that challenged the game engine. It is acutally built by "flattening" the two layers in such a way that i never need more than two tiles at a place, and yet simulate much more planes. Unfortunately, as i wish some elements to hide Bilou (such as walls and trees in secret places), Bilou actually stands "between" the two layers i'm using here, while in this specific case, he should be on top.

Le résultat, c'est que souvent, les pieds de Bilou étaient masqués, comme sur l'image ci-contre, soit parce que j'avais oublié de repasser l'herbe en arrière plan, soit parce qu'il y avait déjà un autre élément de décor par-derrière l'herbe.
Quand j'avais lu les spécifications techniques de la console Genesis, j'avais été plutôt étonné de voir qu'il n'y avait que deux plans de tiles. Or, Sonic est parfois devant le décor et parfois derrière (sans compter l'image de fond, bien sûr, qui occupe le 2eme plan). Le truc, c'est que contrairement aux console de Nintendo, la Genesis permettait de définir pour chaque tile si les sprites avait priorité ou pas pour l'affichage.

As a result, it is common to see Bilou's feet hidden by the grass in the latest demo, either because i forgot to move the grass to the bottom layer, or because it has to be on the front layer due to some other object (e.g. vines or bushes) in the background. I'm trying to address this by reproducing in software the technique used in the SEGA Genesis, as illustrated in Sonic II.

Je vais donc tenter de reproduire cette approche en software: puisque je dois tester les "flags" de chaque tile lors du déplacement de Bilou, je peux assez aisément en ajouter un qui force Bilou (et les autres sprites) à "passer par-devant le décor" quand ils sont au moins partiellement en contact avec ce tile-là. Ca risque bien de compliquer un rien l'édition de niveaux, mais ça devrait valoir la peine...

Despite the Genesis had only two "scroll layers" (against 4 for the DS), it dynamically evaluated tile-to-sprite priority: while all the tiles involved in the "tunnel" on the picture above were on scroll layer A, Sonic can be hidden by the "front pillars" and still seen in front of the dark checker tiles. I'm unsure whether this implies that rings in Sonic were sprites, though. I cannot change the DS hardware, but i can mimmic this technique by having some of the tile attributes (F_RAISER) that forces any sprite that hits it to appear above all the "scroll layers" rather than between "F scroll" and "B scroll" for this specific frame. It's still to be tested.

1 comment:

PypeBros said...

-- "heard" in a talk of 2001 at GDC --

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 6 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.
Listing 1 is some example code for an OAM memory manager.