Spawning and deactiviting enemies as you scroll?
Moderator: Moderators
Spawning and deactiviting enemies as you scroll?
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.
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.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
-
- Posts: 592
- Joined: Thu Aug 28, 2008 1:17 am
- Contact:
Like an aggro radius system? I can't say I'm too fond of that system. Well, at least for old school still games.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.
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?
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
Re: Spawning and deactiviting enemies as you scroll?
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.
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.
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.
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.Dwedit wrote:Another thing to think about is that a monster may have 'buddies'.
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.
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)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?
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).
Useless, lumbering half-wits don't scare us.
I more so meant the technical implementation.. how to, for example, most efficiently check when an enemy needs to be activated and so on.Bregalad wrote: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)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?
Download STREEMERZ for NES from fauxgame.com! — Some other stuff I've done: fo.aspekt.fi
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.Bregalad wrote:What I'd do if I were to do this is to handle on-screen or off-screen enemies exactly the same
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:
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?
What about something like:
Code: Select all
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
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?
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.
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.
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: Select all
; 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
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.
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?p1xl wrote:What do you think?
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.
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.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.
If you do that, you don't have to do this: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.
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.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.
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.
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.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.
Anyway, I said all of this in my first reply to this thread. Maybe I wasn't clear enough.
I know, that was my first suggestion. Did you read my first post? Are my English writing skills that bad?tepples wrote: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.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.
What you have quoted there is a reply to p1xl's suggestion, which involves no sliding window.
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 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?
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.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.
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?p1xl wrote:But (in my naivety) sometimes simplicity is a fair trade for extra CPU. G