This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Object data storing schemes -- as opposed to background data

Object data storing schemes -- as opposed to background data
by on (#204460)
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! :mrgreen:
Re: Object data storing schemes -- as opposed to background
by on (#204461)
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.
Re: Object data storing schemes -- as opposed to background
by on (#204462)
tokumaru wrote:
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.”
Re: Object data storing schemes -- as opposed to background
by on (#204464)
AndreasSpirakis wrote:
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.
Re: Object data storing schemes -- as opposed to background
by on (#204465)
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.
Re: Object data storing schemes -- as opposed to background
by on (#204610)
@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
Re: Object data storing schemes -- as opposed to background
by on (#204611)
I posted my list of object properties a while ago: viewtopic.php?p=171801#p171801
Re: Object data storing schemes -- as opposed to background
by on (#204613)
nesrocks wrote:
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
Re: Object data storing schemes -- as opposed to background
by on (#204614)
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.
Re: Object data storing schemes -- as opposed to background
by on (#204615)
tepples wrote:
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?
Re: Object data storing schemes -- as opposed to background
by on (#204616)
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.
    tokumaru wrote:
    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?
Re: Object data storing schemes -- as opposed to background
by on (#204617)
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.

NovaSquirrel wrote:
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.
Re: Object data storing schemes -- as opposed to background
by on (#205169)
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.
Re: Object data storing schemes -- as opposed to background
by on (#205184)
AndreasSpirakis wrote:
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.

Quote:
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.
Re: Object data storing schemes -- as opposed to background
by on (#205374)
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.
Re: Object data storing schemes -- as opposed to background
by on (#205375)
Celius wrote:
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.

To solve this problem I only deactivate/unload an object if both its current position AND its spawn position are out of bounds. This way players don't run into that awkward situation when an enemy misteriously vanishes until they move away from the spawn point and close to it again.
Re: Object data storing schemes -- as opposed to background
by on (#205475)
tokumaru wrote:
To solve this problem I only deactivate/unload an object if both its current position AND its spawn position are out of bounds.


That's actually a really good idea. Logically, that makes more sense than my method.

However, for my engine (and possibly others), it might present a different problem to use that method. I have a rolling window of decompressed map data in RAM that is used for collision detection. This window is about the same size as the active zone. In the scenario where the spawn point is on screen, but the object is outside of the active zone, the object would be using bad map data for collision detection. Therefore, it kind of makes sense to prevent the object from moving, and colliding with bad tiles.

Is your AI able to decompress your level on the fly for collision detection?
Re: Object data storing schemes -- as opposed to background
by on (#205476)
Oh yeah, I can see that being a problem. You could freeze objects like you suggested when they're outside of the active zone but their respawn points aren't.

My level compression scheme does allow random access to any part of the level map at any time, but even then it might make sense to implement a "frozen" state to save CPU time.
Re: Object data storing schemes -- as opposed to background
by on (#205607)
Celius wrote:
I have a rolling window of decompressed map data in RAM that is used for collision detection.

Interesting! :D
How did you implement this window, if I may ask? If I would try to include this in my code, then I think I would face two problems:
- Mapping of the map-coordinates to "window-coordinates", e.g. for collision detection. How did you manage this? Using "nice" windows-sizes like 32x16 blocks? (then you maybe could use the "and" opcode to modify the coordinates?!)
- decrunching data on the fly: This needs cpu time and free space in the window, right? How does this work in your example?
Re: Object data storing schemes -- as opposed to background
by on (#205609)
Lazycow wrote:
Using "nice" windows-sizes like 32x16 blocks? (then you maybe could use the "and" opcode to modify the coordinates?!)

That's how I'd do it. As long as the lower bits match, using AND to clear the high bits should work just fine.

Quote:
- decrunching data on the fly: This needs cpu time and free space in the window, right?

This shouldn't be any different than decoding metatiles for drawing new parts of the level to the name tables. It's tied to the scroll: every N scrolled pixels, load new data. Graphics data goes to the name/attribute tables, collision data goes to the rolling window. The rolling windows might even simply contain metatiles, which can be used for both collision and rendering. Using a neat power-of-two size for the window helps with this too.
Re: Object data storing schemes -- as opposed to background
by on (#205723)
Lazycow wrote:
How did you implement this window, if I may ask?


Well, I actually do have an advantage, because my game only scrolls horizontally. I was able to dedicate $600-$7FF to my rolling window, and have every 16 bytes represent a column of metatiles (so $600-$60F holds a column, $610-$61F holds the column right next to it, etc.). It breaks it down to the 16x16 pixel metatile. My screens are only 13 metatiles tall, but I still dedicate an entire 16 byte segment to each column for the sake of simplicity. The beauty of this is that finding the metatile at a given set of coordinates is very easy:

Code:
;XHigh/XLow/YLow represent a set of in-game X/Y coordinates. X is 16-bit, Y is 8-bit due to no vertical scrolling.

lda XHigh
and #$01
clc
adc #$06
sta TempAddH

lda XLow
and #$F0
sta TempAddL

lda YLow
lsr a
lsr a
lsr a
lsr a
tay

lda (TempAddL),y   ;Your tile type


I'm not sure if that's the exact same code I use, but it's roughly the same.
Re: Object data storing schemes -- as opposed to background
by on (#205731)
Thanks for the info! Your map setup is more complex than mine, but your tile-detection code is still faster. :oops: