Strategies for dealing with the four sprite palette limit?

[Drakim]

It is possible to make mid-level palette changes completely dynamic if you load/unload palettes as objects are activated/deactivated. Each object's initialization code can check if its palette is already loaded, use the index where the palette is, and increment a counter indicating how many objects are using that palette. If the palette isn't available, load it in the next available slot and set its use count to 1. When deactivating an object, decrement the number of uses of its palette accordingly, and if that becomes 0, free the palette slot.

That way you don't have to worry about hardcoding palette changes to scroll positions, you can place enemies freely when designing your maps, you just have to mind the distance between areas patrolled by differently colored enemies, so that a palette slot is guaranteed to be available when an enemy using new colors shows up.

This is the system I'm currently using, plus the added functionality of objects having a list of palettes (ordered by desirability) so that if all four palette slots are taken, it will settle for second, third, fourth, fifth, etc, choice. Obviously if there are zero matches the object despawns instantly.

Furthermore, I recently added so that each palette choice on the list can point to different sprite CHR data, meaning that there can be specially adapted patterns for dealing with tight color situations. For instance, my fireball sprite is usually red and white, but it can "downgrade" to just white if it finds a palette with the colors "white, blue, green" and there is nothing better available. When it does this, it changes it's CHR data to be some patterns which has the red trimming part removed in favor of a 100% single color version.

I don't do this for everything, most sprites look terrible with too few colors, but it's a great alternative for objects that tend to randomly spawn everywhere (so you can't tactically plan it's placement out in the level editor) and objects which would seriously annoy the player if they just failed to spawn (Mario's fireballs!)

[kuja killer]

wow that was umm... very confusing and i barely understand any of it. from tokumaru's reply.

[Drakim]

wow that was umm... very confusing and i barely understand any of it. from tokumaru's reply.

Just think of it this way:

Imagine a game that starts out empty, nothing is going on. But then a Goomba walks in from the right. When that happens, one of the four sprite palettes is changed to suit the Goomba's color scheme. That first palette is marked as "occupied".

Then a Koopa Troopa walks in, and he needs different colors from the Goomba, so the second sprite palette is "occupied" by him. So now two out of four palettes are taken.

But then the Goomba walks too far and falls off the edge! He is gone, and so, the first sprite palette which he was using is no longer "occupied", it's free to be used by something else. Now only one out of four palettes is occupied (by the surviving Koopa Troopa). We just keep this up as new enemies appear and die, constantly adapting what palettes are used and which are not, depending on what sort of enemies have appeared.

Normally you'd only be able to have four different objects on screen at once by doing this, but you can be clever and make two enemies with the same coloring scheme "share" one palette slot rather than taking different ones. Instead of marking if a palette is "occupied" or not, you mark down how many objects are currently using it, and treat the palette as unused and free to be changed if that number is 0.

Understand now?

[Sumez]

I'm making a co-op kinda thing, so I'm using one palette for player one, one palette for player two, and now I'm left with two palettes for all the enemies and objects they encounter. Furthermore, I usually want black outlines on my enemies which means enemies can have a grand total of two sets of two different colors.

I think it's a given that the two palettes for your main characters should be reused for enemies. You want the main characters to stick out, but there's a limit to how much you can afford sticking out in an NES game. I would never reserve any palette to just one purpose.

But, that runs into a wall if you are planning on changing the palettes, for instance like when Mario gets a fire flower and switches to a new yellow and white palette. Unless you are willing to have enemies also magically change colors out of the blue along with Mario then reusing palettes is difficult.

This entirely depends on the game of course. Mega Man is entirely designed around palette changes, and his powerups will change color whenever he does. More ideally, if a palette change for your main character is required (and honestly, it really isn't!) I'd reuse one of the palettes otherwise designated for enemies.

The downside here is that this requires you to use at least that one palette for every stage in the game. The "upside" is that you're now allowed to add a third palette to your main characters for a more vibrant look that I'd say the character you're staring at for the entire game deserves. The classic example here is the Contra guys, who share a palette for the upper body, but have individual pant colors. You don't have to overlap sprites to make use of multiple palettes, and since your main characters are probably going to be bigger than 8x16 in size anyway, you might as well add another palette.

But it's entirely possible to change the palettes on-the-fly inside of a level depending on what enemies appear. Doing so offers a number of pitfalls though, what to do if all four palettes are already in use when a new kind of enemy appears? Simply delete it?

Rainwarrior already mentioned how the palette limitations is one of the defining limitations of an NES game. However, in general one thing I think really affects how any 8-bit game plays is how both gameplay and level design is tightly controlled by how the game deals with its limitations.
The classic example is Super Mario Bros. You can freely destroy almost any block in the game. This would use an excessive amount of memory if the game allowed you to scroll backwards. So it doesn't.
Similarly, for games with a multitude of different enemy types, I'd design stages around not running into more types than intended in one area. One of my favourite examples for how to do stuff in an NES game is Shatterhand. This game dynamically loads enemy sprite graphics into the CHR with bank switching whenever an enemy of that type appears, along with the color palette needed for it. That allows for much more detailed and animated enemies, but just like with the palettes it obviously means you can only have so many different types on screen at any time. But because the game switches out its set of enemies almost constantly, and the player will perceive the entire stage as "one area" the game ends up feeling incredibly varied.
It's not unusual for an old game to have a glitch where tricking an enemy into following you into a new area will completely screw up its graphics because games are doing this.

[tepples]

Similarly, for games with a multitude of different enemy types, I'd design stages around not running into more types than intended in one area. One of my favourite examples for how to do stuff in an NES game is Shatterhand. This game dynamically loads enemy sprite graphics into the CHR with bank switching whenever an enemy of that type appears, along with the color palette needed for it. That allows for much more detailed and animated enemies, but just like with the palettes it obviously means you can only have so many different types on screen at any time. But because the game switches out its set of enemies almost constantly, and the player will perceive the entire stage as "one area" the game ends up feeling incredibly varied.
It's not unusual for an old game to have a glitch where tricking an enemy into following you into a new area will completely screw up its graphics because games are doing this.

The Curse of Possum Hollow does the same thing with CHR banks as how you describe Shatterhand. Two enemy sprite sheets are allowed to be active at once, and some enemies are designed to share a 1-page sprite sheet (such as larger zombies and ants, or rats and ground hands). If active enemies use more than two different sprite sheets, they are put in a queue to spawn once an enemy is defeated, after which point they pop into view. Late in development, I wrote a tool that searched the level definitions for cases of possible pop-in, based on which enemies use which 64-tile sprite sheets, but there are still a lot of places in the game where you can lure enemies into a place where you can keep other enemies in the queue. Is pop-in more objectionable than corrupt graphics?

[Sumez]

If the game in question doesn't have a natural method to keep enemies from following you (that's very easy for most beat'em ups since they tend to block progress until you killed all enemies on screen), I'd personally just despawn the enemy that isn't "intended" to be active at this point.

If you're able to keep an enemy alive in a way that prevents new enemies from spawning I think that makes it too easy to cheese the game and play it in a way that wasn't intended. I can't recall any titles, but there are definitely games out there where this is a known strategy.

Of course that could still be interesting to explore for speedrunners etc. if it's not too obvious.

[Drakim]

For despawning long-lived enemies who follow you, one technique can be to have a flag on enemies that can mark them as "expendable". If some new enemy wants to spawn and there is a lack of resources (palettes, CHR banks, object slots, etc) then the game does sweep over the active enemy list and deletes some "expendable" enemies.

You raise the "expendable" flag on enemies under whatever conditions you feel is fitting, such as them being too far away from their starting point, or having lived too long, and so on.

Thus, enemies can still "chase after" you and will only despawn when it becomes an issue. The player won't be able to exploit the game by intentionally dragging enemies along with him, but they also won't disappear unless absolutely necessary.

[Sumez]

That works for a completely dynamic design where any enemy can appear anywhere. But personally I actually enjoy the idea of designing a stage around which object will appear where. I really think it's a big part of the identity of old-school games.