How to spawn enemies with multi-directional scroll?

Hi, I'm working on my game, and I've run into an issue with how to spawn enemies as the player moves around.

In Super Mario Bros 3, normal levels are hard-coded to maximum be up to 16 "screens" wide (and a static vertical height). So when it comes to spawning enemies as Mario moves, the game simply has all the enemy data neatly sorted according to their x position. The very first Goomba you encounter in a level is the first entry in the list, and the very last enemy you encounter in a level is the last entry in the list. In addition there is also 16 pointers (one for each "screen") that points to where the first relevant enemy in that corresponding screen is on the enemy list.

So if Mario is on "screen" 2, then the 2nd pointer is checked, which points to a point in the enemy list where the first relevant enemy is located. A tiny loop them checks that enemy's data and the next couple of enemies data to see if it's time to spawn them based on the x position. I assume these 16 pointers are to speed up the process, as a level can have up to 48 objects, and getting a jump start to the right location means the game doesn't need to loop over all 48 enemy entries.




However, my game uses multi-directional scrolling and has arbitrary-sized levels, so one level might be 1 screen high and 8 screens wide, while another might be 3 screens high and 3 screens wide, etc. So not only do I have to check for spawning enemies on both the x and y axis, but this neat sorting trick doesn't work anymore.

So I turn to you, what sort of technique can I use instead? Obviously I don't want to loop over every single enemy entry every frame and manually check x,y every time, it would be too much of a waste.

Group objects into a grid. Determine which grid cells are visible, then iterate each object contained to see if it spawns.

I took the lazy route, and I think it works fine. But there are probably people with better ideas.

What I do is initially similar to the Super Mario Bros 3 route - i sort the object spawns according to their X coordinate (in my case they are 16x16 grid coordinates, not pixel coordinates), and every time the "camera" scrolls horizontally into a new column on my grid, I check if any object exists in that column. Once I reach an object in range, I just check if the Y coordinate is in view, and if not, I move on to the next object in range.
I also check if the object is already currently active, since my engine is designed to only load one object per frame for performance reasons. That isn't really necessary, but the way I design my stages, it's quite rare for multiple objects appearing on the same X coordinate anyway (and super rare to have more than two), which also means that having to check the Y coordinate for a couple of objects in a single frame as you scroll into the next column is completely negligible.

Now, vertical scrolling is of course handled differently, as an item that wasn't spawned previously might need to spawn once you start moving up or down.
Basically what I did was create a second list, sorted by Y coordinate, pointing to the same objects, and apply the exact same logic, except with the coordinates reversed.
It's very redundant, so it takes up extra ROM space (but you could load it dynamically into RAM instead, if you have more room to spare there).

Also, since I'm keeping track of what objects have been killed or picked up, preventing respawns, I actually have my Y-sorted list point to the object's position on the X sorted list, so I know their position in that array. It's essentially the object's "ID".
EDIT: the bit-array used to track if an object is destroyed is actually the same I use to indicate if the object is currently active. If the object is destroyed and can't respawn, it just doesn't set itself as inactive again.

That definitely works, but I was hoping there was some less brute-forcey way to do things. One idea might be to do this while maintaining two lists for each grid cell, one sorted on the x axis and one sorted on the y axis, so that the "quick test" technique can be used for both. Still, that doubles the memory footprint.

Not that it's important to the conversation, but SMB3 also does it by grid coordinates and not by pixel coordinates, I merely simplified things to keep it brief in my post.



That works, but the doubling of space (either ROM or RAM) is annoying. I was hoping somebody would have a wonderful magic technique that works just as well on two axis as SMB3's technique works on one axis.



I thought about this, couldn't you optimize it even more by setting the ID to 0 if the object should never respawn?

Edit: Oh wait that would only work if the object list is in RAM (in SMB3 they are), you'd obviously not be able to do this for a ROM list.

I did a lot of experimenting on these ideas for my current large multi-scrolling metroidvania-style project. After getting frustrated with each approach, I eventually dumbed it down a lot to just brute force. I only iterate through a few objects each frame to save time, but it works just fine. And it's not complicated to write/maintain.

I've used the dual sorted object list approach before (one sorted by X, the other by Y), but in addition to requiring extra ROM for the secondary list, keeping track of which objects were in range also required more RAM, at least in the way I implemented it.

My current solution is to have the list of objects sorted by the main axis (X for wide maps, Y for tall maps), and two pointers mark the leading and trailing edges of the "in range" portion of the list. The pointers are adjusted as the camera scrolls along the main axis, and whenever an object enters the active range, it's secondary coordinate is checked and the object is only activated if that's in range too. When scrolling along the secondary axis, all objects between the 2 delimiting pointers are checked, and activated when the secondary coordinate is in range.

It may seem wasteful to do a bunch of coordinate comparisons when scrolling on the secondary axis, but objects are very rarely so densely packed together that you'll need to check tens of objects at a time. For me, the reduced complexity and ROM/RAM footprint paid off.

Estimate how many cycles it would take.

Brute forcing 5 object spawns at once where each spawn takes 50 cycles is only 250 cycles total. Doesn't sound like a big deal to me.

I suppose not, and I could avoid checking unless there has been some scroll movement.

I guess I could also do some loop unrolling if I'm constantly checking 5 object slots over and over again.

I've used the "object list sorted by X, another list of indices to the first list sorted by Y" approach. I keep track for each edge which object is the next that should spawn in that direction, and once it spawns (or is too far away in the perpendicular direction) I move the pointer forward/backward to the next object in that direction.

I have a prototype implementation here: https://github.com/fo-fo/ngin/blob/mast ... pawner.lua
I believe it is robust. One day I'll convert it to 6502...

I made a thread about this a long long time ago.

My idea was to divide the coordinates system into 8x8 sectors, so you can turn coordinates into a sector number easily by just bit shifting and adding.
Then you can binary search a list for that sector number, then spawn the enemies defined to be inside that sector.
And if you need alive/dead flags, you can do that right there too.

2 extra methods

1 if you want you can make a sparse array

so

You work out how many entities are max on an "axis" with some level of granularity and then you build a 2D array and fill in the empty spots with some dummy value. This way your array has a stride, and you can +stride, -stride to get above below your current location. if you move to the right you check +1, +stride+1, -stride+1 for an object and spawn. if you move up you check, -stride, -stride-1, -stride+1 and check. When you spawn you move to that "node" being your current node. This is basically a grid, but the ranges get a bit loose.

This may or may not eat more RAM/ROM that storing the two sorted lists.

2. if you have something that is a closed off, so a platform level for example, not some open world topdown free for all with no walls. You make Activation tiles/volumes. So you have a data map, and that tile is run script X, and said script will then spawn enemies X,Y,Z etc. This way when you enter an area you step on the tile, enter the "volume" and it spawns the enemies. You can also do this and check the player movement direction so on enter, you spawn and exit you kill if that make sense for you game.

There is no 1 "this is how you do it" it really depends upon your game type, usage, movement style, enemy density, movement speed etc

Alright, thanks for all the input. I've been going back and forth between different techniques, but this is what I settled on:

My game only allows for up to 30 full "screens" in each level, and I've decided to have a max of 8 enemies waiting on each screen. This means that by splitting the different object values into separate arrays, we can keep the offset under 256 and thus use the Y register to read everything out. So 0 to 7 will be screen one, 8 to 15 will be screen two, 16 to 23 will be screen three, etc. And then it's just a matter of reading out values like this:



It's fairly simple, and a lot faster than doing an Indexed Indirect lookup. So doing a brute force check of of all 8 objects isn't so bad after all, as the checks are fast.

Edit: The downside would be that this technique only works if the LevelObj variables are in RAM, since you need to change it for each level.