Sprite mappings

[tokumaru]

I was just wondering how games usually handle this...

Most objects in a game are composed by multiple sprites, we all know that. They probably store the information about how to compose each object in tables. What I'm thinking about is how would games efficiently convert that data into OAM values, specially when only part of the object is visible.

Calculating the position of each individual sprite based on the actual position of the object and verifying if the result is inside the screen seems like a lot of trouble, specially if nearly all 64 sprites are used.

And there are other things to take into consideration, such as sprite flipping. The mappings for each object would have to be scanned in a different order depending on the side it's facing.

Handling all of that could take a lot of the processing time. Does anyone have anything to say about this?

[tepples]

Calculating the position of each individual sprite based on the actual position of the object and verifying if the result is inside the screen seems like a lot of trouble, specially if nearly all 64 sprites are used.

Super Mario 3 slowed down once half of that many sprites were in use.

And there are other things to take into consideration, such as sprite flipping. The mappings for each object would have to be scanned in a different order depending on the side it's facing.

Handling all of that could take a lot of the processing time.

How many metasprites do you plan to have in a shot at once?

[tokumaru]

Super Mario 3 slowed down once half of that many sprites were in use.

That is the problem... I used to think that games slowed down when many enemies were present because of the AI of each one... but since enemy AI is usually very simple, I'm starting to think that drawing their sprites is what takes most of the time...

How many metasprites do you plan to have in a shot at once?

I don't really know yet, but I expect to have a lot going on at once.

I have already coded a routine that will render sprite mappings while doing all the necessary stuff, like flipping and making sure only sprites that are inside the screen are rendered, but I haven't tested it's speed yet.

I'm finishing my scrolling engine now, as soon as it's ready I'll pay some attention to the sprites. I was just trying to think a little ahead. I guess there is no shortcut for this.

[Bregalad]

This isn't a hard task, but you'll most probably never made a super-ultra fast sprite mazing routine either.

What I use is basically indexed table for each enemy, position and direction (tri-dimentional tables !) in order to get each individual sprite set with it's own relative position, palette/flipping, and so on. I incorporated the feature to have a set of "hardware" sprite on a row with consecutive tile index to be on one single "software" sprite, allowing 16x8, 24x8 and 32x8 "software" sprites in order to slightly reduce ROM amount.

The sprite mazing routine tests screen overflow manually for each sprite. The only other alternative is to make a whole object dissapear at once, this should be harder to do but maybe less time consumming.

Eventually I think sprites eat more ROM thant process time. You can also put the limitation that all sprites in a single object are mazed in a 8x8 gird, so that you only have a couple of bits for the position of the sprite (intead of a full byte for both horizontal and vertical position), but you may waste this ROM space back on the CHR ROM / RAM data. Also forcing each object to be single-paletted would reduce this, but also reduce graphics quality.

[Celius]

If you make every object dissapear at once, it'll actually be a lot easier. That way, you'll only have to check if the whole sprite is on screen. If it is, then render it. If not, don't render it.

This'll actually give me a lot to think about for my game. I haven't thought about sprites being halfway on screen yet.

EDIT:
You can check whether or not the object is on screen. If it is, just use 16 bits to calculate the X/Y Coords of each sprite. If the High byte comes out not equal to $00, you'll know it's off screen. For example, if the enemy's right edge is 20 pixels off the right edge of the screen, you'll come out with a value of $114 for the X coord, with $01 as the high byte, and $14 as the low. If the high byte is not $00, it's off the screen.

And also, you can use bounding boxes to determine if the enemy is on screen. If the enemy collides with the edge of the screen, you'll know it should be displayed.

[Bregalad]

What you describe disalows mismatches between enemy/object graphics width/height and it's collision window width/height. I usually give my enemies a smaller collision window that what they actually are large, to give the player some margin (and because not all the area of tiles is used).
However, a per-object drawing condition can be the best for a game with fixed-size objects, such as a RPG.

[Celius]

What you describe disalows mismatches between enemy/object graphics width/height and it's collision window width/height.

I don't really see what you mean. Could you clarify a little?

[Bregalad]

Well, you'd want to have an enemy to be wider and taller on the screen than on the "internal" calculation used to detects hits with BG or other sprites. The techinque you describe use hits to do screen mazing stuff, and personally I like to have both of these be completely separate.

[tokumaru]

Celius, my routine works (does it? I haven't tested!) exactly like you described! It first calculates where the central point of the object is, relative to the camera (object coordinates minus camera coordinates). Some tweaking is done to the resulting coordinates if the sprite is flipped. Then it scans through the sprite definitions, which have the following format:

Code: Select all

.sprite count;
	.relative X coordinate;
	.relative Y coordinate;
	.tile index;
	.sprite attributes;
	(repeat "sprite count" times)

I chose this format for the sprite definitions instead of more compact ones because of this freedom this gives me. Each sprite can use a different palette, they can be asily layered and don't have to be arranged as a grid.

Anyway, the relative coordinates are inverted if the sprite is flipped in that direction, and are then added to the screen coordinates of the object. If the high byte is 0, it is output. The attributes byte is in the regular format that the PPU uses, but this routine receives a mask that is XOR'ed with the attribute byte of each sprite, so that the tiles can be flipped, the piority and palette can be changed, etc. When the flipping bits are set in this mask, this means that the whole sprite is flipped, and the coordinates are to be inverted before the addition.

In theory, it works great, and I can't see a reason for it not to. I'll check soon how well it performs and I'll let everyone know. I'm not sure if I'll perform the bounding box check before rendering them, because the routisne will handle objects that are out of the screen just fine, although it will waste time going through the definitions without ever outputting a sprite. If not many objects are active, this is a good solution, otherwise, the bounding box check may greatly reduce the calls to the sprite drawing routine.

And I believe that what Bregalad said is that each object will then need 2 different bounding boxes, because the one used for collisions between objects is usually smaller than the graphics of the object, to compensate for the fact that it is a box, while most objects are not rectangle.

[Celius]

I suppose you're right about that, but whatever the case, you should just do a check somehow to see if it's on screen. It'll greatly reduce the time of calculations.

So do most games refresh the page in RAM used for DMA completely every update? This would be much more reliable than editing the data that's already there, but it may take a while.

[Bregalad]

Well, on my current game engine, all active objects are on the screen because it only loads a screen at a time, and scolls whole screens, so this avoid this problem. The only way a sprite can be off screen for an object is if the object is close to the border of the screen. The "collision" box of the object can never go across the screen (my routines refuse moving the object if it tries to do so), but that doesn't dissalow actual sprites to overflow the screen, because you'd want the sprite take more place than it's own bounding box. If you don't the game will be hard as the player will (frustatingly) get hurt unfairly just by getting close of an object.

[Celius]

Oh, you have SO much less to worry about then someone making a game that's constantly scrolling (Such as Sonic or Castlevania). My game, which is almost exactly like Castlevania SOTN, has many objects that are off screen. In most rooms in my game, there'll be about 8 to 12 enemies. Only 4 of them can be on screen at once, but the rest are doing stuff off screen. I pretty much have to check whether or not an object is on screen in order to calculate its sprite positions, because if I were to check where every object's sprites are in relation to the screen, I would be calculating the positions of around 96 sprites, while only 64 can actually be on screen. I'd rather not waste that much time.

[tepples]

Getting definitions out of the way early helps resolve Layne's Law issues before they become problems:

• Actor: A game object.
• Cel: An image used to represent the position and state of an actor.
• Sprite: An entry in the display list used to draw cels.

Each cel has two different bounding boxes: the cel border and the hit box.


Figure 1: A cel, 24 pixels by 16 pixels, with three colors plus transparency. The "cel border" encloses the entire cel.


Figure 2: Six 8x8 pixel hardware sprites make up this sprite cel. (Enemy sprite cels in Super Mario Bros. are the same size.)


Figure 3: The "hit box" is the rectangle that encloses most of the non-transparent area of the sprite cel, used for collisions against other objects (not against the screen).

To determine whether an actor shall be rendered, you compare the cel border to the view border. Reject all cels that do not overlap the view in some way. Then for each sprite in the cel, you compare this sprite to the view border and write it to the shadow-OAM if it is inside. Hit boxes are ignored here.

So the case described by Celius would involve 44 tests against the view: 12 for entire cels, and 8 for each of the four actors that can be partially on the screen at once. Depending on how fast the view and actors are moving relative to each other, some of the tests might be skipped from one frame to the next, causing probably-not-noticeable artifacts.

[tokumaru]

Yeah, Bregalad's case sure is simpler than games with scrolling, because you know for sure that all active objects are being displayed, entirely even. So you don't have to clip them or sort them.

I'm still not sure that performing preliminary bounding box checks before rendering sprites is the best choice... In my game, I have RAM for 32 active objects, so I'd call the sprite drawing routine at most 32 times. But I'll hardly have that many active objects (the object RAM is recycled as the camera moves, with objects constantly being loaded and unloaded), and even if I do, not many of them will be represented with sprites.

If I ever approach this limit of 32 objects, I expect it to be because of rows and columns of rings, which appear very often in Sonic games, but these are drawn with the background. A separate individual ring object that is rendered with sprites is avaliable for places where the background rings can't be used,but I don't expect to have many of these.

When you look at Sonic games, you see that not that many objects are active at a time (excluding rings), even though they have 96 RAM slots for objects (maybe the only reason for this is the crazy amount of rings that bounce around when Sonic looses them). And since my game is for the NES, many things that were rendered as sprites in the original games (such as rings, lamp posts, spikes and monitors) will be rendered to the background most of the time. Sprites will only be use in parts where the background can't be used.

In fact, just to make something clear, the fact that many objects can be rendered to the background as well as with sprites is the reason I like 8x16 sprites so much, because I can reuse the tiles.

[Celius]

So the case described by Celius would involve 44 tests against the view: 12 for entire cels, and 8 for each of the four actors that can be partially on the screen at once.

Where does the number 8 come from?