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

Object spawning logic in commercial games

Object spawning logic in commercial games
by on (#81818)
I've been thinking about good rules for object spawning/deactivating for my platformer engine, and started to think about how commercial games handle stuff like that. Hopefully we can get a discussion going to add to the earlier thread about spawning.

SMB3
Objects can be spawn from both directions. Their initial movement direction changes based on which side of the screen spawns them, so they always head towards the hero. They don't respawn if they've been killed (although pushing them into pits doesn't count as a kill).

The game seems to spawn enemies a little bit before the screen scrolls to the spawn point, so they scroll into view smoothly.

Bucky O'Hare
Enemy spawning is somewhat buggy (although some might call this a feature). If a spawned enemy is killed, and the edge of the screen is still inside the 16(?) pixel spawn location, scrolling one pixel or so to the right will spawn it again. This is another one of those things that while understandable from programming point of view, is unintuitive to the player.

Spawning isn't pixel perfect, i.e. it doesn't take the sprite bounding box in account. Sprite simply appears on the spawn location, seems to be centered on the screen edge horizontally most of the time. Also with frame stepping it's possible to see that objects on the right side of the screen are facing the wrong way for a single frame after spawning.

Common
In both games, objects don't have to be very far from the screen edges to get deactivated. There are situations when this makes the player think the enemy vanished into thin air. For example when enemy is walking right on a narrow cliff, the right edge of screen is just past the enemy spawn point and the enemy gets deactivated when it goes outside the visible window. Now when player scrolls to right, the enemy appears to have vanished. Sorry, hard to explain. :)

In SMB3, I *think* the deactivating rules change depending which direction the hero and the enemy are moving. If screen is scrolling to right and the enemy is moving left, the enemy disappears immediately after leaving the screen. However if enemy is moving right also, it doesn't. Or so it seems.

---

Anybody have anything to add?

by on (#81823)
A lot of old PC games used a separate update region from the screen region. When a spawn location entered the update region the enemy would spawn, and when the enemy was no longer in the update region it would deactivate. Some games used an update region that was two or three times as big as the screen, giving a more persistent feeling to the action.

by on (#81828)
But then DOS games could afford a bigger sliding window/update region because 8086 CPUs had 16-bit machine words, unlike the 8-bit machine words of 6502 CPUs. An 8086 program thus didn't need to do a 2-machine-word comparison with carry to determine when something was going in or out of the sliding window.

Super Bat Puncher persists while a map segment is loaded on the screen. Anything offscreen persists in a stopped state.

by on (#81838)
Both games you listed have very limited scrolling, which actually makes enemy/object spawning much easier. SMB3 levels are at most about 2 screens tall, and Bucky O'Hare only scrolls in one direction at a time.

Things get really tough when there's free scrolling, I'll tell you that. the solution I found was to store the list of enemies/objects sorted by X coordinate and keep pointers to the leftmost and the rightmost active objects. As the screen scrolls horizontally, the pointers are adjusted to include/exclude objects into/from the active range. When the screen scrolls vertically, all objects between the 2 pointers (hopefully not many) have their vertical coordinates checked, and if they are in range they are activated.

There are a lot of details that can't be overlooked for everything to work right, such as only deactivating objects when both their current coordinates AND their spawn points are outside of the active area, otherwise they might be prematurely deactivated and will not respawn properly. Another important thing is to have a "dead" bit for each object, that you can use to prevent activation of objects that are already active, as well as to make them permanently dead.

by on (#81914)
tokumaru wrote:
Things get really tough when there's free scrolling, I'll tell you that. the solution I found was to store the list of enemies/objects sorted by X coordinate and keep pointers to the leftmost and the rightmost active objects. As the screen scrolls horizontally, the pointers are adjusted to include/exclude objects into/from the active range. When the screen scrolls vertically, all objects between the 2 pointers (hopefully not many) have their vertical coordinates checked, and if they are in range they are activated.

If I understand right, you're keeping pointers to the objects whose spawn points are "visible", and then checking the *next* object (in either direction) as the screen scrolls to see if it should be spawned (and the pointer updated)?

Does your engine handle object bounding boxes? When scrolling right, it would have to adjust the spawn point based on the left side of the bounding box, and vice versa. Or two separate spawn points would have to be stored, one for the left and one for the right side.

I guess it might also be useful to have an option to have the objects sorted by Y coordinates instead for vertically oriented levels. The level data exporter could then figure out what ordering would be more efficient at runtime.

Hmm, I wonder if it would be overkill (or work at all) to have 4 pointers, one for each side of the screen, and two object lists, one sorted by X and one by Y.

Time to do some C++ & SDL prototyping, I think.

by on (#81925)
thefox wrote:
If I understand right, you're keeping pointers to the objects whose spawn points are "visible", and then checking the *next* object (in either direction) as the screen scrolls to see if it should be spawned (and the pointer updated)?

Exactly!

Quote:
Does your engine handle object bounding boxes?

No, it doesn't.

Quote:
When scrolling right, it would have to adjust the spawn point based on the left side of the bounding box, and vice versa. Or two separate spawn points would have to be stored, one for the left and one for the right side.

Ideally, yes, but I figured that would be too much trouble. I just make the "active area" wide/tall enough for objects to be loaded a little before coming into view (i.e. the "active area" is a bit larger than the screen).

Quote:
I guess it might also be useful to have an option to have the objects sorted by Y coordinates instead for vertically oriented levels. The level data exporter could then figure out what ordering would be more efficient at runtime.

Yeah, I considered that. The engine would check if the level is vertical or horizontal before running the object spawning logic. But since I don't plan to have vertical levels in my current project, I haven't given much thought to this.

Quote:
Hmm, I wonder if it would be overkill (or work at all) to have 4 pointers, one for each side of the screen, and two object lists, one sorted by X and one by Y.

I also considered that, but decided that would waste to much ROM. If I had WRAM though, I'd consider calculating the secondary enemy list at runtime.

This is one aspect of game programming that I consider particularly tough to implement. It's one of those things that you think you have considered everything, and then a little detail you haven't though about shows up and screws everything, so you end up having to rethink the whole thing over. Things are a little easier when you have more RAM, but processing power is what you really need to make this trivial. I really like these challenges though, and they are the main reason I like NES coding so much! =)

by on (#82059)
It's weird to see this come up when I was just trying to plan this out the other day (and with 4 way scrolling, too).

So basically the idea is to have to check as few objects/enemies as possible? I'll let you guys know if I work anything out, probably before I implement it because it's nice to hear if I'm doing something bass-ackwards,

by on (#83495)
Quote:

Does your engine handle object bounding boxes? When scrolling right, it would have to adjust the spawn point based on the left side of the bounding box, and vice versa. Or two separate spawn points would have to be stored, one for the left and one for the right side.

I guess it might also be useful to have an option to have the objects sorted by Y coordinates instead for vertically oriented levels. The level data exporter could then figure out what ordering would be more efficient at runtime.

Hmm, I wonder if it would be overkill (or work at all) to have 4 pointers, one for each side of the screen, and two object lists, one sorted by X and one by Y.

Time to do some C++ & SDL prototyping, I think.


This works really well in practive and is what I'm using. The best part is you only need to check for spawns when you move the scroll window, its transition triggered instead of continuously tested for trigger.

There are a couple of good optimizations I found. If you have < 256 spawn points, you can just keep 8-bit indices instead of pointers, and the y list can be be a list of y-sorted indices into the x-sorted spawn list.

Each entity spawned also can keep the index of the spawn point it was spawned from so that it can "reload" the spawn point when it gets killed off.

by on (#83498)
I still like the method that I came up with, which I described in the other thread, it's basically a binary search every time a new 128x128 pixel area is exposed. When scrolling horizontally, it's 3 sections exposed, when scrolling vertically, 3 sections exposed. Even 6 binary searches is lightning quick.

by on (#83499)
Dwedit wrote:
I still like the method that I came up with, which I described in the other thread, it's basically a binary search every time a new 128x128 pixel area is exposed. When scrolling horizontally, it's 3 sections exposed, when scrolling vertically, 3 sections exposed. Even 6 binary searches is lightning quick.


Took a look, and I have a question. Is the binary search used so that you can have empty sectors, since not every 128x128 region has to have enemies? Otherwise you'd just have an array of sector indices or pointers you could index directly I'd wager.

by on (#83508)
The problem with object areas is that you have to be very careful with object placement. If an object is too wide/tall and you place it too close to the edges of the area it's in, it will "pop" into view, instead of smoothly scrolling in.

For sprites that's unpleasant, but not game-breaking. But if you have background objects that are drawn along with the rows/columns of background (which I do), parts of the object will not be drawn, because it wasn't loaded when those parts scrolled into view.

That's the reason I stopped using "blocks of objects" in favor of a sorted list of all objects.

by on (#83590)
This is also something I found difficult to implement in my game, and it even has very simple scrolling (only scrolls horizontally).

I have an "activity zone" of about 2 screens, (one half off the left edge of the screen, the full screen being displayed, and the other half screen sticking off the right edge) which defines the region in which enemies can be active. I implemented a maximum object count for this zone: 8 intelligent objects, 16 simple objects. If anything falls outside of this zone, it gets deactivated. If anything comes into this zone, it is activated unless the maximum object count is met. This can potentially create problems, but I have designed my enemies and levels so that enemies don't roam too far from their spawn points, and a worst case scenario should only result in about 6-8 active objects on screen. This is something I would figure almost any game has to do because you risk having too many objects consuming resources (cycles, RAM, sprites, etc.).

Actually, another thing I implemented was a "freeze" zone. An object is able to move around most of the activity zone, but towards the outer edges, objects will stop moving. They will remain active, but they will not move. This is to prevent things like an enemy immediately walking out of the activity zone as soon as they are spawned. It's not a perfect solution, but it works well enough for me.

In terms of storing objects, I have objects sorted into screens from left to right with one 4-bit X coord and Y coord defining their sub position within each screen. These coordinates only allow them to adhere to 16x16 pixel sections when they spawn, but that's not a big deal. I have also accepted a limitation of 1 object per 16 pixel wide section of the screen. This has allowed for more simple activation checks. All I have to do is pull up the list of objects within the screen of the activation point, and then compare their spawn point's X coord with the activation point. As soon as it finds an object's X coord equal to the activation point's X coord, that object is spawned and no more checks need to be performed (remember, only one object can spawn per given X coordinate). If it encounters an object with an X coord beyond the activation point, checks automatically cease because the objects are sorted, and all other objects to be checked are also beyond the activation point.

And yeah, what tokumaru said about the dead/active bits is very important. There's nothing like killing an enemy on it's spawn point and having it infinitely come back to life (immediate aggravation!).

by on (#83597)
Celius wrote:
Actually, another thing I implemented was a "freeze" zone. An object is able to move around most of the activity zone, but towards the outer edges, objects will stop moving.

Sort of like how Super Bat Puncher remembers the position of every enemy on the screen, but as soon as they leave the screen, they freeze and their AI resets.

Quote:
There's nothing like killing an enemy on it's spawn point and having it infinitely come back to life (immediate aggravation!).

Unless you're grinding healing items or weapon energy (go Mega Man) or weapon drops (hi Kirby) or experience (any JRPG ever).

by on (#83600)
tepples wrote:
Celius wrote:
Actually, another thing I implemented was a "freeze" zone. An object is able to move around most of the activity zone, but towards the outer edges, objects will stop moving.

Sort of like how Super Bat Puncher remembers the position of every enemy on the screen, but as soon as they leave the screen, they freeze and their AI resets.


I'm not sure I understand. What happens when the AI is "reset"?

tepples wrote:
Unless you're grinding healing items or weapon energy (go Mega Man) or weapon drops (hi Kirby) or experience (any JRPG ever).


Or Metroid. I can't tell you how many times I've gone to those warp zone type things to kill the flying bugs to fill my energy tanks.

It's funny you should bring this up though. I was talking earlier about how I had "intelligent" and "simple" objects. I forgot I recently changed how I refer to what I've been calling "simple" objects. I have "intelligent" and "spontaneous" objects. Intelligent objects are ones on the enemy placement map. Once they are dead, they are dead forever. They also have more RAM allocated to them so they can do more complex things. Spontaneous objects can be made out of thin air (usually bullets, or something similar). I was thinking of including some enemies in my game as spontaneous objects. This way, I could have something like the warp zone thing in Metroid as an intelligent object, and have that keep shooting spontaneous bug objects. This way, you could still harvest energy and ammo, but you wouldn't have to deal with certain enemies constantly respawning.

by on (#83605)
I'd just use a object map ID number to relate an object (in your active object table) to a numbered enemy (in your object map). An object ID of 255 would indicate a temporary object, such as a bullet.
No need for a separate table, or special memory format. You could even make temporary enemies that disappear when they move too far away.

by on (#83609)
Dwedit wrote:
I'd just use a object map ID number to relate an object (in your active object table) to a numbered enemy (in your object map). An object ID of 255 would indicate a temporary object, such as a bullet.
No need for a separate table, or special memory format. You could even make temporary enemies that disappear when they move too far away.


If I'm understanding correctly, you are saying to treat spontaneous objects kind of the same way as intelligent objects (so just one format), but assign spontaneous objects a reserved ID that indicates they are spontaneous. Is that correct (somewhat)?

With the system I use, my main concern would be RAM usage. I don't know if people do it really differently, but I have implemented a system of slots for these intelligent and spontaneous objects. Each intelligent object is given 22 bytes of RAM, and each spontaneous object is only given about 7.

If I were to treat intelligent objects and spontaneous ones the same way, I would be wasting a lot of RAM for things like bullets (all I need is an X coord, Y coord, and maybe 1-2 bytes of RAM to work with for special movement. Oh, and an ID). The other concern is that since objects would all be using the same slots, spontaneous objects could accumulate in the active zone and prevent intelligent objects from spawning. This is very bad. If anything should be prevented from spawning, it should be a spontaneous object, not an intelligent one.

by on (#83611)
I treat all my objects the same. They have a "setup" routine, where they install themselves to one of the free object slots in RAM, using parameters (X and Y position, etc) from the stack. These objects can either come from the list of objects in ROM (similar to your intelligent objects) or be created by another object (spontaneous), from the point of view of the object it doesn't matter, since they just grab the parameters from the stack.

The main difference is that spontaneous objects have invalid pointers to the table of states in RAM, so they don't write anything back when they die. Simple objects will indeed underuse the RAM that's allocated to them, but I don't mind having this in exchange of generalization. I have 24 active object slots, things must be pretty busy for all of them to be used... I don't expect that to happen very often.

by on (#83618)
I see how it would work, and I guess it makes a difference also if your enemies don't throw a lot of projectile weapons. In my game, things shoot fireballs, rocks, drool lava out of their mouths, etc. So there are a lot of things flying around.

And with my set up, I've dedicated a lot of RAM to other things (animation slots, a sprite drawing stack, the OAM page, a music engine, a two-page copy of the screen for fast collision detection, etc.). Needless to say, I have very little left to work with after coding all that, so I would be in trouble if I decided to make everything universal.

Just curious, how many bytes do you allocate to an object? At first I feel like 22 bytes is a lot for a simple game like mine, but then things like object IDs, coordinates with precision, status bits, velocity, etc. all start adding up.

by on (#83621)
Celius wrote:
tepples wrote:
Celius wrote:
Actually, another thing I implemented was a "freeze" zone. An object is able to move around most of the activity zone, but towards the outer edges, objects will stop moving.

Sort of like how Super Bat Puncher remembers the position of every enemy on the screen, but as soon as they leave the screen, they freeze and their AI resets.

I'm not sure I understand. What happens when the AI is "reset"?

It means the enemy's AI goes into the "sleep" state, the same state the enemy was in before you encountered it. This frees up CPU time, and it collapses the enemy to just its index in the map's enemy list, its coarse X position, and its coarse Y position. I don't know exactly how Super Bat Puncher works, but some engine architectures have a limited number of simultaneously active "intelligent" objects, and putting an enemy to sleep might free up such a slot.

by on (#83626)
Celius wrote:
I've dedicated a lot of RAM to other things

I see... I too have used nearly every byte of the stock 2KB of RAM, I have only a few ZP bytes left.

Quote:
Just curious, how many bytes do you allocate to an object? At first I feel like 22 bytes is a lot for a simple game like mine, but then things like object IDs, coordinates with precision, status bits, velocity, etc. all start adding up.

I have 28 bytes per object, with 24 of them the total is 672 bytes for the active objects. That amount seems OK for most objects, but I imagine that some really complex objects might need more than 1 slot. In that case the additional slots don't have any A.I., they are only used as extra memory for the master object.

by on (#83633)
Quote:
I see... I too have used nearly every byte of the stock 2KB of RAM, I have only a few ZP bytes left.

Well it's fun because I only use half of both main RAM and zero page currently in my game engine.

Note that to save memory, you might not allow TOO much objects to be loaded at a time on the screen (I personally choose 8 slots), and also you should recycle variables if their utility is mutually exclusive. You say you have 24 slots, I think it's way too much. Even if you load all 24 slots with something chances are that your engine will lag terribly.

For example, in a projectile you don't need any variable to remember it's hit points, so you can use this variable to store the speed of the projectile instead (this is just an example).

That way I was able to fit all my object-related variables in arround 200 bytes.

by on (#83635)
Bregalad wrote:
For example, in a projectile you don't need any variable to remember it's hit points

Unless different projectiles using the same sprite have different damage amounts, or unless a projectile is programmed to disappear after a certain distance. Where there's memory, game designs will expand to fill it.

by on (#83637)
Bregalad wrote:
Note that to save memory, you might not allow TOO much objects to be loaded at a time on the screen (I personally choose 8 slots)

With multi-directional scrolling you have to be a bit more generous... Objects can appear from all sides, and preferably a while before they scroll in, so you need at least twice what you'd need in a static-screen game.

I'm trying to mimic the way Sonic games work, and if I'm not mistaken they have 96 object slots. Obviously it's not common to have that many active objects, but if you use debug mode to manually place that many objects the game becomes insanely slow.

I also don't plan on having 24 active objects all the time, but I want to avoid the disastrous situation that would be to refuse a slot to an important object, such as the level's boss.

Quote:
and also you should recycle variables if their utility is mutually exclusive.

Oh, I do that a lot.

Quote:
You say you have 24 slots, I think it's way too much. Even if you load all 24 slots with something chances are that your engine will lag terribly.

Sure it will lag, but I really don't plan on having that many objects very often, I just want to be prepared for slightly busier areas. In a free scrolling games enemies can walk to areas they wouldn't ordinarily go to, depending on how the game is played, so even if you design the areas to not have too many objects grouped together they might still move around and gather into larger groups. I just want to be prepared.

Also, since some objects might use more than 1 slot, it's a good idea to have some room to breath.

Quote:
For example, in a projectile you don't need any variable to remember it's hit points, so you can use this variable to store the speed of the projectile instead (this is just an example).

Oh yeah, I do that too.

by on (#83642)
tokumaru wrote:
I also don't plan on having 24 active objects all the time, but I want to avoid the disastrous situation that would be to refuse a slot to an important object, such as the level's boss.

Some games handle this by evicting a relatively unimportant object. Kung Fu even has an animation for when an enemy gets evicted before the boss battle: it walks toward the trailing edge of the screen. So does Super Mario Bros. 3: when Mario grabs the card, enemies turn into coins.

by on (#83644)
tepples wrote:
Some games handle this by evicting a relatively unimportant object.

Yes, this is something I want to implement too. I'll probably make their importance relate to their codes, to make it easy for important objects to identify objects that can be evicted.

by on (#83646)
tokumaru wrote:
Celius wrote:
I've dedicated a lot of RAM to other things

I see... I too have used nearly every byte of the stock 2KB of RAM, I have only a few ZP bytes left.

Did you count a sound engine in to the RAM budget yet? :)

by on (#83647)
thefox wrote:
Did you count a sound engine in to the RAM budget yet? :)

Heh, good question! Indeed, I don't have a sound engine yet, but I reserved around 200 bytes for one. No matter what happens I'll have to make an engine that uses that many bytes or less. I don't think this is unrealistic... do you? =)

by on (#83649)
tokumaru wrote:
thefox wrote:
Did you count a sound engine in to the RAM budget yet? :)

Heh, good question! Indeed, I don't have a sound engine yet, but I reserved around 200 bytes for one. No matter what happens I'll have to make an engine that uses that many bytes or less. I don't think this is unrealistic... do you? =)

Yeah that should be enough, I think FamiTone uses a bit less than that. My sound engine uses ~300 bytes currently I think, but it also has a lot more features and some room for optimization. Hopefully I can get it under 256 bytes...

by on (#83651)
I have a very simple sound engine I'm currently using. It only uses about 112 bytes (though I think I'll have to use about 16 more due to a complication when switching between sound effects). The sound engine doesn't support pitch bending, which is a feature I omitted to save RAM and ROM consumption. So 200 bytes should definitely work.

And there are many workarounds for unsupported features. An echo, for example, you can do with a volume envelope (your engine should support volume envelopes for the square waves). Or in a lot of cases, you can get away with using volume fluctuation or trilling between two notes instead of having vibrato done with a pitch bend. Though I'll say it really doesn't sound the same. If you listen to FF1, CV1, or SMB1, you can really tell the pitch bend is missing.

tepples wrote:
tokumaru wrote:
I also don't plan on having 24 active objects all the time, but I want to avoid the disastrous situation that would be to refuse a slot to an important object, such as the level's boss.

Some games handle this by evicting a relatively unimportant object. Kung Fu even has an animation for when an enemy gets evicted before the boss battle: it walks toward the trailing edge of the screen. So does Super Mario Bros. 3: when Mario grabs the card, enemies turn into coins.


This is one of the main reasons I separated spontaneous and intelligent objects. A spontaneous object cannot appear and disallow an intelligent object from appearing. I've also included a unique master routine for every level in my game. This routine has the authority to override anything done with the main engine. So I can technically say "when you get to this point in the level, destroy all enemies and make room for the boss" in that routine. Actually, this routine is the one that handles events of any kind.

tepples wrote:
It means the enemy's AI goes into the "sleep" state, the same state the enemy was in before you encountered it. This frees up CPU time, and it collapses the enemy to just its index in the map's enemy list, its coarse X position, and its coarse Y position. I don't know exactly how Super Bat Puncher works, but some engine architectures have a limited number of simultaneously active "intelligent" objects, and putting an enemy to sleep might free up such a slot.


That sounds like deactivating the enemy...? :?

With what I do, I just prevent the enemy from acting until it gets out of the freeze zone. Say you have an enemy that paces back and forth. If you move so that it just spawns, walks towards you, and walks away (past its spawn point), it will essentially disappear until you walk back, and then reveal its spawn point again. My solution was to stop the enemy if it's in the freeze zone, which is next to the inactive zone. This does mean that enemies are only deactivated by the player killing them, or moving so that the frozen enemy is pushed into the inactive zone.

Probably a better solution is the one where you check if the spawn point is in range, and only deactivate them if the spawn point is not. But for certain reasons like collision detection, I can't have enemies acting outside of the activity zone. My two-screen copy of the screen allows me to really quickly search for the tile being stood on (The formula is (XCoord AND $01F0) + (YCoord / 16) + $0600). Thus, if enemies act outside of a 2 screen zone, they will be colliding with garbage, which could be disasterous.

by on (#83656)
See also previous discussion on sound engine RAM use.

Celius wrote:
tepples wrote:
It means the enemy's AI goes into the "sleep" state, the same state the enemy was in before you encountered it.

That sounds like deactivating the enemy...? :?

There's a difference between deactivating the enemy in place, which is what SBP does, and deactivating the enemy and sending it back to its spawn point, which most NES platformers appear to do.