Object data storing schemes -- as opposed to background data

[AndreasSpirakis]

Hi there. I have a small NES project that supports an animated character who can jump around and collide with background objects. Both the character and the background objects are 16x16 metatiles. To store background data I am just writing #$00s (un-collidable metatile) and #$01s (collidable metatile) directly into PRG-ROM.

Now that I can store background data and collide with it I’d like to move on to storing object data. I’m not sure if “object” is the right term here, but essentially I’m referring to spawn locations for things like enemies or moving powerups. The only object in my project currently is the player, so I’m here to inquire about ways, common or not, to approach this problem.

Thanks so much!

[tokumaru]

Games normally have a separate list containing all level objects, with information such as X and Y coordinates, type (so you know how to initialize and update each object) and possibly other parameters. In games that don't scroll, all objects of a screen are loaded when the screen is. In games that do scroll, the objects are usually sorted by their coordinates and are loaded as the camera approaches them.

Loading an object means reading its information from the list of level objects in ROM and copying it to an area in RAM dedicated to active objects. Due to memory and CPU imitations, game engines can only handle a few active objects at a time, so the game engine also has to deactivate objects that go too far off screen in order to free memory for new objects.

[AndreasSpirakis]

Games normally have a separate list containing all level objects, with information such as X and Y coordinates, type (so you know how to initialize and update each object) and possibly other parameters. In games that don't scroll, all objects of a screen are loaded when the screen is. In games that do scroll, the objects are usually sorted by their coordinates and are loaded as the camera approaches them.

Loading an object means reading its information from the list of level objects in ROM and copying it to an area in RAM dedicated to active objects. Due to memory and CPU imitations, game engines can only handle a few active objects at a time, so the game engine also has to deactivate objects that go too far off screen in order to free memory for new objects.

Got it, thanks. I was hoping the answer was something along those lines.

I have a follow up question to your second paragraph. Do NES devs generally partition parts of their shadow OAM to specific active objects? For example, do they say, “Okay, I will only have X number of goombas on screen at one time, so this part of my shadow OAM will go only towards goomba sprites.” Or do they flesh the system out more to say, “This region of RAM will go towards any active object, and when a new object is introduced it gets the first area of memory available.”

[NovaSquirrel]

Do NES devs generally partition parts of their shadow OAM to specific active objects? For example, do they say, “Okay, I will only have X number of goombas on screen at one time, so this part of my shadow OAM will go only towards goomba sprites.” Or do they flesh the system out more to say, “This region of RAM will go towards any active object, and when a new object is introduced it gets the first area of memory available.”

I've always just had an index that points at the next available OAM slot, and every frame the index gets reset, the OAM list gets cleared, and every active object that's on-screen adds an entry to the OAM list.

I think the main reason you would partition the OAM list like that would be if you wanted to do layering effects, like you have some sprites that you want to always be above everything else, but that could be solved by just controlling the order things are drawn in too.

[tokumaru]

I believe that SMB actually uses a more hardcoded system where certain areas of RAM are reserved for certain object/enemy types, but it's certainly more versatile to have X slots and let objects grab any free slot. Some may advocate that 16 slots of 16 bytes is enough, and very convenient that it all fits in exactly 256 bytes. I actually use way more than that (24 slots of 32 bytes), but it ultimately depends on the kind of game you're making.

As for hardcoding objects to OAM positions, that's bad no matter the kind of game you're making. If there's any chance that more than 8 sprites may share the same scanlines, you absolutely need sprite cycling, and you can't do that right if objects always use the same OAM positions. Most games allocate OAM slots dynamically.

If you don't use any sort of layering, you can start outputting sprites to a random OAM position and advance a prime number of slots each time. That will completely spread the sprites across the entire OAM space.

If you need to respect sprite priorities within the same object (e.g. an overlaid face like Mega Man's), you can randomize the order in which objects are drawn, and fill the OAM linearly. If you need priority between objects (e.g. a sword the player is carrying), you can link child objects to parent objects so they're drawn together in the proper order.

No matter the approach, efficient sprite cycling requires the entire OAM to be built from scratch every frame, and AFAIK, that's what most games do.

[nesrocks]

@Tokumaru
Out of curiosity, what are the 16 bytes per object used for, in your games? I'm programming an object manager right now and I thought about 11 bytes being more than enough for my case, but maybe I'm missing something I haven't thought of yet. Here's mine:

byte 1: object ID
byte 2: attributes
byte 3: X coord low
byte 4: Y coord low
byte 5: X coord high (haven't figured out how to do the whole coords thing yet, so I'm reserving these)
byte 6: Y coord high
byte 7: object state
byte 8: current animation frame
byte 9: current animation frame timer
byte 10: horizontal velocity
byte 11: vertical velocity

[tokumaru]

I posted my list of object properties a while ago: viewtopic.php?p=171801#p171801

[tepples]

byte 1: object ID
byte 2: attributes
byte 3: X coord low
byte 4: Y coord low
byte 5: X coord high (haven't figured out how to do the whole coords thing yet, so I'm reserving these)
byte 6: Y coord high
byte 7: object state
byte 8: current animation frame
byte 9: current animation frame timer
byte 10: horizontal velocity
byte 11: vertical velocity

The Curse of Possum Hollow roughly follows this, assuming "ID" is an actor class, "attributes" are facing direction and palette swap, and "state" is health. Actor class controls which sprite set and which logic routine are used. I often duplicate frames, with two frames pointing to the same metasprite data, to encode state. And sometimes I use the timer for other state-like things and advance the sprite's animation on a multiple of 8 frames.

byte 12: horizontal velocity high
byte 13: vertical velocity high
byte 14: X coord highest (in screens)
byte 15: height of last damage (used for height-dependent damage response)
byte 16: offset into CHR RAM of start of animation frames

There are also about 16 bytes of state reserved for bosses.

EDIT: Here are some of the things tokumaru's engine stores that mine doesn't.

type, bounding box: Determined by logic routine type
next object in same group: Groups are hardcoded to the first or part of the object table, and there are few enough slots that a linear search for type=empty is enough
link to related object: Not used
Y coordinate 3rd byte: Curse scrolls only horizontally
angle: Determined by bit 6 of sprite attribute
slope threshold: all walkers have the same slope behavior
animation script pointer: I use only 1 byte because it's a table index, doubling as a frame number
extended state, general purpose: Only one entity can have extended state, and it's the boss
spawn stuff: Not as necessary, as Curse scrolls only one way

[nesrocks]

In my case state is current state (walking, idle, jumping) for the class' state machine to handle. I may need to add a health byte.
As for the animation frame and animation timer I forgot I had thought about using the low bits for the timer and the high bits for the animation frame, so 1 byte for both things.

[tokumaru]

I think tokumaru's objects are bigger because his engine caches a bunch of stuff.

True. The spawn position for example could be found by taking the object's index and looking up its entry in the list of the current level's objects. That's pretty slow though, specially considering that a bank switch is necessary to access the list. It ends up being easier and faster to cache that information when the object is loaded.

The slope thereshold too: I could maybe repeatedly check the metatiles below the object and look at their height maps searching for the highest point, but that'd be crazy slow. Better cache the value from when the object was at the highest point of the slope.

Another thing you don't see very often is angle information, because a lot of games don't have slopes or don't need proper angular physics. Hit boxes also change when objects rotate, so I have a field for that too. A game without rotation could use the state (e.g. standing vs. ducking) to get the appropriate hit box.

Coordinates are usually smaller than mine too, because most NES games don't have Sonic 3-sized levels. I also avoid packing bits in ways that require decoding before I can use them, I'd rather keep everything properly aligned and ready to use, even if that costs a little more space.

I don't see any of you guys keeping track of the instance ID (i.e. index in the list of object definitions), which should be necessary to control spawning (avoiding multiple copies or respawning after death). Are you handling this some other way?

[NovaSquirrel]

In Nova the Squirrel, I have the usual 16-bit X and Y position, and 16-bit X and Y velocity, where the four velocity bytes can be reused, usually to hold a position (Roto-disc style enemies store the position they're circling around in the velocity).

Aside from those, I have:

• Object type, with the least significant bit being the horizontal direction.
• State (normal, paused, stunned, "active", initializing) but can be a generic byte with some restrictions, like for projectile type.
• Two bytes that are free to use for any purpose. The first one gets initialized with a nybble from the level data, for things like enemy variants.
• A generic timer; most objects automatically reset their state when it hits zero.

  I don't see any of you guys keeping track of the instance ID (i.e. index in the list of object definitions), which should be necessary to control spawning (avoiding multiple copies or respawning after death).

• This.

Usually animation frames are just taken directly from a timer or the state. Is it unusual to have the variables' actual meanings so freeform?

[nesrocks]

In my case I forgot about it (instance ID to prevent double spawning). Tepples doesn't need that byte though, as he mentioned his game only scrolls right.

Usually animation frames are just taken directly from a timer or the state.

Well, how will I know how long the current animation frame has been displayed? Some animations may have frames that switch faster than others.
edit: humm, so I could just have a full byte for a timer and use it to set a frame. Yeah, that's better, no need to know which frame it is.

[AndreasSpirakis]

I made lots of progress because of the help I got in this thread. I now have 16 16-byte slots for objects in RAM and I build my OAM from the ground up every frame. Looking good.

Now I’d like to move into horizontal scrolling (a la SMB) and I have a question. I am fine loading 2x15 columns of metatiles into VRAM when the “camera” scrolls… What I’m having trouble with is incorporating object spawning into this. I haven’t gotten anything working yet, but from what I’ve tried I have a hunch that objects’ spawn coordinates are stored as 16-bit values. If this is the case, and if I also store the camera’s X as a 16-bit value… Then couldn’t I compare the camera’s X to the X of the next object to be spawned as the camera scrolls? And then load the object once the distance between them is less than or equal to 0? This is assuming that object data is sorted by horizontal position.

[tokumaru]

I haven’t gotten anything working yet, but from what I’ve tried I have a hunch that objects’ spawn coordinates are stored as 16-bit values. If this is the case, and if I also store the camera’s X as a 16-bit value…

If your levels are going to scroll, that means your objects live in a space wider than 256 pixels, so yeah, it makes sense to expand the range of the X coordinate of any objects that exist in this space (camera, player, game objects) beyond 8 bits.

Then couldn’t I compare the camera’s X to the X of the next object to be spawned as the camera scrolls? And then load the object once the distance between them is less than or equal to 0? This is assuming that object data is sorted by horizontal position.

Yeah, that's the basic idea. Normally you'd want the "spawn sensor" to be a little ahead of the camera, so that objects don't "pop" as soon as the edge of the screen touches their starting coordinates. If your game only scrolls in one direction (e.g. SMB), you only need one spawn sensor ahead of the camera, otherwise you probably need another one a little behind the camera. Accompanying each sensor, a pointer in ZP can indicate the next "candidate" for spawning in the list of level objects (sorted by X). As the camera moves, you compare the coordinates of the sensors against the coordinates of the candidates to decide whether to load them and move the pointers.

Scrolling in both directions (forward and backward) also means you have to take precautions to not re-load an object that's already loaded or has already been killed/destroyed/picked-up. What I do is keep and array of 1-bit per level object in RAM, and whenever an object is loaded I set its corresponding flag. As long as this flag is set, an object will not be loaded again. When an object is unloaded for going too far off-screen, I clear its flag so it can be re-loaded later, but when it's unloaded because it was destroyed/killed/picked-up I leave the flag as is, so the object never gets loaded again.

[Celius]

I have used the same approach with the 1-bit per object status flag. This works pretty well for preventing respawning.

Another problem to consider is that you should prevent your objects from wandering outside of the "active" zone. For instance, one of the enemies in my game just walks back and forth a short distance, so pretty simple AI. The problem is, if that object becomes active, if the player decides to stop moving, that object could walk outside of the active zone pretty easily (thereby deactivating itself, and not respawning because you've already crossed the "spawn" point). To prevent this, I actually have a "frozen" zone, where objects are "active", but they don't move or do anything until the player gets a little closer to them. Not perfect, but it helps minimize scenarios like this.