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

Spawning and deactiviting enemies as you scroll?

Spawning and deactiviting enemies as you scroll?
by on (#67903)
So now I'm wondering about what good ways there are to handle enemies as you scroll around.

So you have your 4-way scrolling map. You have enemies placed at various locations, in no particular order.

What we need is a way to tell when an enemy is about to be scrolled onto the screen, so it can wake up.
We also need a way to tell when an enemy has gotten far away enough from the screen and should deactivate.

Then we need to decide whether it deactivates in the location it left the screen, or returns to its spawn location. And if it returns to its spawn location, it should not reappear if the spawn location is on the screen. (Some games spawn enemies in visible areas on the screen! I think The Nerd mentioned Ninja Gaiden as one of them)

One approach I can think of is to have a complete object table for every single enemy in the level, then do range checks as you iterate over each enemy. This is probably not the best way to do it, as it compares every single object's position, and that's slow.

Another approach is to add objects from a passive list into the active list as you approach them. Then you still need to look at a range of objects from the passive list as you scroll. Still a lot of checks though. Maybe force the checks to occur only every 32 or 64 pixels or whatever. But then you get slowdown if you scroll left and right repeatedly on a seam.
Games which scroll in only one pair of directions have it easy, since they only need to look at one object to decide to spawn more.

Another thing to think about is that a monster may have 'buddies'. There could be three monsters behind the screen boundary waiting to attack the player. If you used an algorithm where each object activates separately, you could slowly approach the edge, wait for the first enemy to attack you, move back, then kill it. You could take out the monsters one at a time. In that kind of situation, you'd want to activate them all at once, even if the buddies are farther away from the screen. I think this also may apply for deactivating as well.

by on (#67906)
Quote:
Another thing to think about is that a monster may have 'buddies'. There could be three monsters behind the screen boundary waiting to attack the player. If you used an algorithm where each object activates separately, you could slowly approach the edge, wait for the first enemy to attack you, move back, then kill it. You could take out the monsters one at a time. In that kind of situation, you'd want to activate them all at once, even if the buddies are farther away from the screen. I think this also may apply for deactivating as well.


Like an aggro radius system? I can't say I'm too fond of that system. Well, at least for old school still games.

by on (#67911)
This is actually quite an interesting topic that I don't think has been discussed before. Has anybody checked how the commercial games do it?
Re: Spawning and deactiviting enemies as you scroll?
by on (#67919)
I haven't implemented this yet, but what I plan on doing is having the list of objects/enemies sorted by horizontal coordinate in ROM. In RAM, two pointers indicate the leftmost and rightmost "active" objects (the space between them is somewhat wider than a screen, so that objects have some time between being loaded and scrolling into view). The scrolling engine is responsible for moving these pointers left and right as the camera moves.

Whenever objects enter the active range, their vertical coordinates are checked and if they are also in range they are loaded. When scrolling vertically, all objects between the two pointers are checked, and if their Y coordinates are in range, they are loaded.

I plan on doing the range checks every few scrolled pixels, like you mentioned. Maybe 16 or 32, so that range checks consist basically of checking if the coordinates of the objects belong in the new "stripe" that scrolled in, something that can quickly be done by comparing the highest bits of the coordinates to the index of the "stripe".

Another important detail is that each object has a bit in RAM indicating if they are dead or alive. When an object is loaded, it sets its bit to the "dead" state, to prevent it from being loaded again in case its original position gets in range again.

Some care must be taken when deactivating objects. You can only do it when they are off screen and their spawn point is out of the active range. This is something that objects have to check themselves. I chose to leave this responsibility to them because some of them can get away with simpler logic (the ones that don't move, for example), so there is no need to use the same complex logic for everyone. One way I though of implementing this is that objects keep an internal "can-deactivate" flag, and have them watch the indexes of the stripes that enter and leave the active range (these are "broadcast" by the scrolling engine), so that they can modify the flag as their spawn point enters and leaves the active range.

Dwedit wrote:
Another thing to think about is that a monster may have 'buddies'.

In this case, I suggest you create an object whose only purpose is to group other objects. They are dummy objects pointing to lists of actual objects that you load all at once when the dummy object gets in range.

If we are talking objects that are always linked, you don't need that kind of sophistication. When you load any of the sister objects you just look around (a few entries before and after it) for the other one(s) and load them all at once.

by on (#67924)
Quote:
This is actually quite an interesting topic that I don't think has been discussed before. Has anybody checked how the commercial games do it?

Most just delete enemies when they go off screen and they keep re-spawning when you scroll back to their original position. Some games have flags for when you kill an enemy, but most don't. (note that I didn't disassembly anything, it's just speculation from what I observed)

What I'd do if I were to do this is to handle on-screen or off-screen enemies exactly the same, but just not display off-screen enemies. Also, if this is too slow, I'd have the AI be simplified if the enemy is off-screen, but this might not be necessary, as what is really slow is usually drawing sprites (not the AI itself).

by on (#67929)
Bregalad wrote:
Quote:
This is actually quite an interesting topic that I don't think has been discussed before. Has anybody checked how the commercial games do it?

Most just delete enemies when they go off screen and they keep re-spawning when you scroll back to their original position. Some games have flags for when you kill an enemy, but most don't. (note that I didn't disassembly anything, it's just speculation from what I observed)

I more so meant the technical implementation.. how to, for example, most efficiently check when an enemy needs to be activated and so on.

by on (#67931)
Bregalad wrote:
What I'd do if I were to do this is to handle on-screen or off-screen enemies exactly the same

You do realize that depending on the size of the level you could have, I don't know, say, up to 70 enemies? Definitely way too much to process (CPU bottleneck) and to maintain states of (RAM bottleneck). Your idea would only work if the levels were really small and had only 20 or so enemies.

by on (#67939)
I don't have a lot of NES dev experience, but on other platforms I often implement patterned baddies as an FSM for the patterns with a counter/timer for states that need tweening.

What about something like:
Code:
byte 0
  b0-6 pattern state (init,chase,jump,explode,etc.)
  b7   is the baddie active
byte 1 counter/timer
byte 2-3 X coor
byte 4-5 Y coor

That would give you 42 baddies in 256 bytes; loaded when the level loads.
When a baddie goes far enough off screen it would be deactivated, but it keeps it's state. Each frame (or set of frames if you split up the loop) you'd scan over the 42 baddies.

If bit 7 is on then you update the baddie by jsr-ing to the update routine referenced by the pattern state (via jmp table?).
If it's off you check if the baddie should be activated. If it needs to be activated, flip the bit then jsr to a routine that initializes the oam based upon pattern state.

It might be possible to pack the bits in a little tighter too, like if your level was only 16x16 screens then you could save a byte on the coors.

I don't know if this would be fast enough however. I'm still learning the limits of the NES.
What do you think?

by on (#67942)
Here's what I guess existing games do:

Each map has an array of enemies. The entries are sorted by X coordinate to allow bidirectional traversal within a sliding window. When you spawn an enemy, first check that the enemy's index in the array doesn't belong to any active enemy; if so, fail. This check shouldn't take more than 12 cycles per element in the array.
Code:
  ; input: A = index of critter in the map's enemy table
  ldx #MAX_ACTIVE_CRITTERS-1
findCritterInTable:
  cmp activeCritterIndex,x
  beq alreadyExists
  dex
  bpl findCritterInTable
  ; omitted: find a slot and spawn the critter

If an enemy falls out of a sliding window surrounding the camera, remove the enemy from the table so that it can respawn when the player returns to its spawn point.

And if you want, keep a bitmap of which enemy indices have been destroyed, and check that before spawning. For 256 enemies, this takes 32 bytes.

by on (#67943)
p1xl wrote:
What do you think?

I think 6 bytes in not enough for an active object/enemy. Where will you store his type? Health/hit count? Animation frame? Fractional coordinate? Speed?

In my engine, I have dedicated 28 bytes for each of the 24 active objects, and even with that amount of RAM I'm not sure how I'll handle certain objects. Like I said before, objects are loaded and unloaded as the camera moves, so they have to backup their state to a dedicated location of RAM if they want to remember it when they are loaded again.

I honestly don't think that iterating over all the objects in the level every frame is practical at all, even if all you do is check how far from the camera they are. You'd have to subtract the camera's coordinates from the object's coordinates, compare the results against a threshold to separate the close objects from the distant ones, and then you still have to run the AI for the close ones. That looks like a lot of wasted CPU if you have 50+ enemies in the level.

by on (#67945)
tokumaru wrote:
I honestly don't think that iterating over all the objects in the level every frame is practical at all, even if all you do is check how far from the camera they are.

You wouldn't have to if they're sorted by the primary scroll direction. Then you'd only have to iterate when your sliding window moves, and only over the areas that have been added to or removed from the sliding window.

by on (#67946)
tepples wrote:
And if you want, keep a bitmap of which enemy indices have been destroyed, and check that before spawning. For 256 enemies, this takes 32 bytes.

If you do that, you don't have to do this:

Quote:
When you spawn an enemy, first check that the enemy's index in the array doesn't belong to any active enemy; if so, fail. This check shouldn't take more than 12 cycles per element in the array.

I'd rather not spend 12 * (active objects) cycles every time an object is loaded, since changing the bitmap to pretend it was destroyed would be much faster.

You could conceptually see the bitmap as load/don't load instead of dead/alive. The object having been destroyed is a reason to not load it, but so is the fact that it is already loaded.

Quote:
If an enemy falls out of a sliding window surrounding the camera, remove the enemy from the table so that it can respawn when the player returns to its spawn point.

Both the enemy and its spawn point must be outside of the window for it to be unloaded. If you check only its current position, his spawn point might still be inside the window and the enemy will appear to have vanished if you decide to chase it after it went off screen. If you check only the spawn point, the enemy might disappear while still on screen.

Anyway, I said all of this in my first reply to this thread. Maybe I wasn't clear enough.

by on (#67947)
tepples wrote:
tokumaru wrote:
I honestly don't think that iterating over all the objects in the level every frame is practical at all, even if all you do is check how far from the camera they are.

You wouldn't have to if they're sorted by the primary scroll direction. Then you'd only have to iterate when your sliding window moves, and only over the areas that have been added to or removed from the sliding window.

I know, that was my first suggestion. Did you read my first post? Are my English writing skills that bad?

What you have quoted there is a reply to p1xl's suggestion, which involves no sliding window.

by on (#67949)
tokumaru wrote:
I think 6 bytes in not enough for an active object/enemy. Where will you store his type? Health/hit count? Animation frame? Fractional coordinate? Speed?


Type is stored in the state, as is animation frames. Fractional coors could be stored as fixed point in the x,y words. Speed is built into the state as well. You're pretty much substituting rom space for the extra ram by hard coding constants. Hit count would probably need another byte or nybble.

tokumaru wrote:
I honestly don't think that iterating over all the objects in the level every frame is practical at all, even if all you do is check how far from the camera they are. You'd have to subtract the camera's coordinates from the object's coordinates, compare the results against a threshold to separate the close objects from the distant ones, and then you still have to run the AI for the close ones. That looks like a lot of wasted CPU if you have 50+ enemies in the level.


Now this is where I don't have experience. You're probably correct. But (in my naivety) sometimes simplicity is a fair trade for extra CPU. Good thoughts tho.

by on (#67952)
p1xl wrote:
But (in my naivety) sometimes simplicity is a fair trade for extra CPU. G


I could be wrong (I have little to no experience programming the NES), but from what I've read you pretty much should never do anything that uses extra CPU on the NES if there is an alternative; The NES is extremely limited on CPU resources. Am I correct in saying that?

by on (#67953)
p1xl wrote:
Type is stored in the state, as is animation frames. Fractional coors could be stored as fixed point in the x,y words. Speed is built into the state as well. You're pretty much substituting rom space for the extra ram by hard coding constants. Hit count would probably need another byte or nybble.

I guess this could work for a very simple game, where levels have few enemies of few different types that do few different things. Maybe something like SMB?

by on (#67955)
Quote:


You do realize that depending on the size of the level you could have, I don't know, say, up to 70 enemies? Definitely way too much to process (CPU bottleneck) and to maintain states of (RAM bottleneck). Your idea would only work if the levels were really small and had only 20 or so enemies.

If you have levels this big without any kind of separation, you're going to run out of memory anyway as the NES is only 2k and cannot load so many enemies or pointers to map data at a time (assuming no SRAM or wathever).

But even if about 20 enemies are loaded at a time, the execution of all off-screen enemies might end up so fast it wouldn't be a bother. Even if it is too slow, just implement a "if far to the camera then don't move nor do any kind of collision detect" thing. When logging code from my game I figured that most of the time I had time to compute player and even a few enemies before VBlank even finishes ! Mazing the sprites in OAM is what really draw some significant CPU time.

by on (#67959)
cartlemmy wrote:
p1xl wrote:
But (in my naivety) sometimes simplicity is a fair trade for extra CPU. G


I could be wrong (I have little to no experience programming the NES), but from what I've read you pretty much should never do anything that uses extra CPU on the NES if there is an alternative; The NES is extremely limited on CPU resources. Am I correct in saying that?


Yeah, but it's not too bad. OAM-cycling ('mazing', as Bregalad had said) is one thing that is pretty intensive. That means shifting around 256 bytes (for all 64 sprites) so they won't vanish when >8 of them are on a line. Things like hit detection can also suck up some CPU time, so that's a good place to optimize, but you may find that there's plenty of time leftover.

NES CPU is 1.789 Mhz, maybe it can be compared somewhat to the C64, which has a lot of impressive stuff done on it, but it has a 6502 running at 1Mhz. Atari 2600 is 1Mhz also, but it's kept very busy handling the display, while maybe all the game logic runs during vblank.

NES CPU speed can visualized as scanlines, literally also, using the PPU 'emphasis' bits in monochrome mode. Average instruction length is (just a wild guess) 3.5 cycles, and with NTSC there's 262 scanlines (including vblank) and each scanline takes 113.666 CPU cycles.

by on (#67963)
tokumaru wrote:
I know, that was my first suggestion. Did you read my first post? Are my English writing skills that bad?

No, my skills are that bad. I should have just said "QFT".

Memblers wrote:
NES CPU is 1.789 Mhz, maybe it can be compared somewhat to the C64, which has a lot of impressive stuff done on it, but it has a 6502 running at 1Mhz.

And a lot more bandwidth from the CPU to the VRAM.

by on (#67964)
Bregalad wrote:
If you have levels this big without any kind of separation, you're going to run out of memory anyway as the NES is only 2k and cannot load so many enemies or pointers to map data at a time (assuming no SRAM or wathever).

My game has no SRAM and can handle levels up to 32768x16384 pixels, with up to 512 objects. That doesn't mean it needs any more RAM than games with smaller levels. The whole level map is in ROM, as are the object definitions.

Wasting computational resources on things that are too far to be noticed by the player is not professional at all. It's quick and straightforward and will work well on a handful of occasions, but will introduce several limitations to your program because you are wasting resources that could be better spent elsewhere.

Quote:
Mazing the sprites in OAM is what really draw some significant CPU time.

That's because your method of "mazing" the OAM is slow. If I recall correctly you first write all the data to shuffle it later, meaning that you are making a lot of accesses to that memory (write, read, then write again). There are sprite cycling methods that require a single write to RAM (no need to post-shuffle the sprites) which are probably much quicker than what you are using.

by on (#67970)
My game uses two 6-bit linear-feed back shift registers, one seeds the other. That places all the sprites into random OAM slots with all except sprite 0 being used. I haven't torture tested it yet and hope that when there's overflow it won't just repeatedly put the same sprites in the lower slots.

by on (#67977)
Quote:
If I recall correctly you first write all the data to shuffle it later, meaning that you are making a lot of accesses to that memory (write, read, then write again).

Huh ? I don't do that. What I do for my "current" game (that I haven't worked on at all since about than 6 months) is that I first sort the sprites so they are drawn in the desired order (top-down graphics) which is an unnecessary step for side view games. Then it just mazes sprites, and I made sure the method is as quick as possible. For each hardware sprite, it adds one constants to the X/Y coordinates, check if it's on screen, etc... I made sure it's fast, and use some self-modifying code to do the cycling without loosing much time. Yet it still take some time. I'm not saying its terribly slow, I can have a large amount of enemies (about 6/7) before the game lags, something that not many NES games I know can do (and those who does are space shooters).

Quote:


Wasting computational resources on things that are too far to be noticed by the player is not professional at all. It's quick and straightforward and will work well on a handful of occasions, but will introduce several limitations to your program because you are wasting resources that could be better spent elsewhere.

This is right - if it works for you by all means go for it ! The longer time spent to implement correctly enemies that goes far to the camera is a trade-off to have an engine supporting very large areas without re-loading anything. I guess it all depends on the game you're willing to make. I was just pointing out it wasn't necessarly.

by on (#67983)
Bregalad wrote:
Quote:
If I recall correctly you first write all the data to shuffle it later, meaning that you are making a lot of accesses to that memory (write, read, then write again).

Huh ? I don't do that. (...) I first sort the sprites so they are drawn in the desired order (top-down graphics) (...) Then it just mazes sprites (...) For each hardware sprite, it adds one constants to the X/Y coordinates, check if it's on screen, etc...

Well, maybe I'm not fully understanding your method, but when you say that you "first sort the sprites" I understand that they are being written down once, and when you say that "for each hardware sprite, it adds..." I understand that you are reading the data, modifying it and writing down again...

I understand that your game has a top-down view that requires closer objects to be in front of distant ones, and this complicates the sprite cycling process, but I'm sure there is a "good enough" method that requires writing the data down only once.

You see, in my opinion there is no possible way flickering will ever look good. If it's flickering, the scene is already "ruined" in a way, so I think that any effort to make it look better is futile, which means that an overly sophisticated sprite cycling method is unnecessary. As long as the play can tell where the objects are you should be OK.

I'm not telling you to change your game or anything, each programmer uses what he thinks is best for his games, I'm just saying this because you often blame the "sprite mazing" for huge CPU usage, while this isn't necessarily the general case, it's just your particular case.

This sprite cycling thing is pretty off-topic though, so we'd better drop it.

by on (#67989)
Well I have to read sprite data from ROM before mazig it into the OAM page (with modified flags and coordinates). You can't maze sprites form no data as you seem to imply... exept if all enemies have their OWN hardwired independant sprite mazing routine but not only it'd be very complicated to code and end up a huge waste of ROM.

by on (#67990)
We obviously aren't understanding each other. Let's just leave this sprite business for another occasion, shall we?

by on (#68109)
I've just come up with an idea of how to store enemies for a level!
This is basically designed for my game, but if it works for you too, great.
I might be using the terms Objects, Enemies, and Monsters interchangeably, you get the idea.

Divide the level into 8x8 square sectors. I'm using a 16x16 map of 8x8 sectors, so there are up to 256 sectors. No, these are not like Doom's sectors, it's just a name I'm making up for the 8x8 tile areas. And there will also be up to 256 different objects.
Have a sorted list at the beginning of all sectors which have objects. So sector #0 might have objects, or sector #26 may have objects...
Then have a corresponding list of the first object # for that sector. So sector #0 would start at object #0, or sector #26 may start at object #3, etc... Also have one more byte indicating the last object number.

Then have an object coordinates table. 3 bits for X position within that sector, 3 bits for y position within that sector, leaving 2 bits to select the color of the object. Then have another table to tell what kind of object it is, one byte should be enough.

So that's 4 arrays:
* Sorted list of sector numbers for the objects
* List of each first object # corresponding to the sector number list (happens to be sorted as well)
* Object coordinates within a sector and color
* Object type

Now for the other part, activating and deactivating the enemies...
We have an array of 256 bits to indicate that scrolling should not spawn a monster. The bits are set whenever a monster is created, and cleared whenever a monster leaves the area. When you kill a monster, the bit is not cleared, so that enemy doesn't come back.
Whenever you expose a new sector while scrolling, create all objects at that sector. So you create a row of up to 3 sectors worth while scrolling vertically, and a column of up to 3 sectors worth when scrolling horizontally. You can use binary search to find the sector, then look up its first enemy number.
When an object is more than 64 pixels off the screen, destroy it and clear the bit. But it might still be offscreen... Oh well, then move it back to its starting location as long as the starting location is still offscreen but within the exposed area.

This also makes all objects in the same sector "buddies" which will be created at the same time so the player can't take them out one at a time.