Enemy placement in screen-by-screen top-down game

[gauauu]

While it's possible that there could be dozens of tests with a "not allowed" result, I doubt it would cause a big delay as the screen is loading.

This is true. You can test a LOT of tries in the transition between rooms without causing a delay would bother the player.

[FrankenGraphics]

Having a low number of spawn points per room is probably the most straightforward way to limit randomness. If you are reusing rooms, you also have to decide wether that is unique to each actual room clone, or just the room type (like how spawn points are decided in metroid).

[tepples]

All in all, the only really important part of your code is this:

Code: Select all

  ; If position is not possible:
  lda xyposition
  asl a
  bcc :+
    eor #$D9
  :
  ; Check again.

Although I still don't get why it's the value $D9. This is probably some mathematical stuff.

That's what I hinted at with the name "Galois". Évariste Galois was a French mathematician who developed group theory and finite field theory, on which linear feedback shift registers (LFSRs) are based. You can try any of several numbers to ensure that you don't hit a loop too fast. In fact, I may have made an error in the choice of $D9.

[Bregalad]

Then there's the problem that they shouldn't be allowed to be placed in tiles that are walls, unless they can fly.

I have an array of 16 x 15 bytes that defines which tiles are walls and which are walking ground.
So, generating a random number from 0 to 239 isn't a problem.
After generating it, I could adjust the value and move the position up, down left or right if the character would be too close to the player's side.

Well, if you're going to place enemies semi-randomly, you can just pick a random place, and see if it is excluded. Then, if the place is excluded, you just repeat the random number generation again, and loop until you end up having a place which is not excluded. It is excluded if it falls in one of the cases you mentionned : Too close to the player, a non-flying enemy on a solid tile, or another randomly placed enemy already being there.

This can take more time but since it's when the room is loading and not during action, this is a non-issue.

[DRW]

About the whole issue of "pick random spot, if it doesn't work, pick another one": The problem that I have with this is the unpredictability. Moving away from an unallowed tile in a specific fashion will eventually reach a valid tile. But doing another random value means that this could potentially happen very, very often.

No, i mean the array would cover all coarse positions on the playfield (except outer walls etc, if any) that are nominally eligible for placement, but have their order shuffled in a way decided by the game designer.

I still don't quite understand how you mean it.

What kind of game is this? Is it a completely designed interconnected world where you want to apply randomness to the enemy spawning in order to keep the game challenging and keeping the player on their toes?

It's "Zelda"-like, i.e. completely designed. Fixed positions for certain enemies are of course also possible, but that's a mundane thing to program and doesn't require a thread. (Likewise, enemy movement is a totally different topic altogether.) But I'm looking for good ways for randomly or semi-randomly appearing enemies.

Having a low number of spawn points per room is probably the most straightforward way to limit randomness. If you are reusing rooms, you also have to decide wether that is unique to each actual room clone, or just the room type (like how spawn points are decided in metroid).

Fixed points per room is the simplest to program, but it requires a lot of ROM space. And if I only use six positions or so, that's pretty limited.

I assume rooms on the overworld won't be reused that much. Although I might consider this for dungeons. But even then, it's only the layout, not the enemy placement.


What algorithms does "The Legend of Zelda" use?

[FrankenGraphics]

I still don't quite understand how you mean it.

Suppose all spawn points are aligned to the attribute grid (they don't have to, but for the sake of making an example).
You'd have all possible spots labeled* like so:

That's our imagined table of spawn point ID:s.

A row is 0-F for making it easy for us to understand what position it represents.

Now, we create a shuffled array:
11, A1, AE, 1E,
22, 92, 9D, 2D,
11, A1, AE, 1E,
33, 83, 8C, 3C,
(add in all you want - but exlude outer walls and doorways)

The array points to which of tile an enemy is spawned. In this example, since 11, A1, AE, 1E appear twice as often as the other ones, they (the corners) are twice as likely to be positions where enemies spawn. It's like having a modified deck of cards where some cards would appear twice, thrice or not at all. Also, the deck is rigged in a certain order.

With the one and only array-approach, you'd want all legit positions to appear at least once. With more arrays, they can be smaller and exclude certain spots if you want to. For example, it could be enough for a certain enemy type to only be able to spawn in corners, in which case you'd need only 4 bytes for that monster type. You'd better move their priority up in the list, then, as their spots are few. Another monster type may only spawn in a centered quarter of the screen. You get the idea.

The pick position procedure could be as follows:

Randomize an index.
Start there.
Vacant spot?
- if yes, place enemy, dec index (or alternately randomize index again). if index = 0, start from top, pick next enemy to place.
- if no, dec index. If index = 0, start from top.
Loop until all enemies in the list are placed or in case there are no vacant spots left to place in (fail level count?), escape.

This way you could tailor 'randomness' pretty efficiently, at the cost of having at least one array. With more arrays, you can have varied "patterns of likelihood".


*It's a mental labeling - you don't need to store this information in ROM. The integers stored in the array can be used for moving the spawn decision to the correspondent position.

What algorithms does "The Legend of Zelda" use?

I don't know, but there's a disassembly here:
http://computerarcheology.com/NES/Zelda/


Post script:
I originally got this idea when contemplating the fortunate/unfortunate side features of the 'random table' in the Lone Wolf adventure book series.

It was the game constructors' intention to work as a makeshift die. You'd close your eyes and point your pen, and see what you got.
The fact is that the player will get familiar with the table and know what regions have high numbers, low numbers, high risk, low risk and so on. In this particular game, i think it's bad because it is meant to substitute a ten-sided dice but works nothing like it. There is potential, however. You can modify the chances of certain numbers by modifying their rate of appearance. You can modify the width of relations to neighboring numbers. You can modify the algorithm which picks a cell (you could have a set of methods how to pick a number). And the fact that the player can learn patterns can be used for good, because what you want is not randomness - it is patterns with a touch of chance large enough to keep the player alert/previously explored areas fresh.

[Celius]

About the whole issue of "pick random spot, if it doesn't work, pick another one": The problem that I have with this is the unpredictability. Moving away from an unallowed tile in a specific fashion will eventually reach a valid tile. But doing another random value means that this could potentially happen very, very often.

Is your concern getting stuck in an endless or very long loop where you keep testing random tiles that aren't allowed?

If your RNG code is pretty reliable, this shouldn't be an issue, as eventually all tiles will be tested in a time span that is not perceivable to the player. I do understand the paranoia, and lack of comfort relying on something random, because even though it's super unlikely, the player could "win the lottery" and be forced to wait through a hundred thousand tests that result in "not allowed". The funny thing is that even that might take less than one second.

The main problem I suppose is that you might test the same tile more than once if you just leave it random. A simple solution is to have an array with values 0-239, and shuffle that array. Start at the beginning of the array and test that value. No matter what the result is ("allowed" or "not allowed"), you just move on to the next value. This would also simplify the criteria for "not allowed", because you wouldn't need to check if an enemy has taken one of the random tiles. Once a tile is tested, it's never tested again.

[Bregalad]

The problem that I have with this is the unpredictability.

If you're relying on a RNG the result is obviously going to be unpredictable. However, for reasons mentionned by Celius, this is acceptable when loading a new room. It would not be acceptable during action.

Personally in my game which is also screen-by-screen and top-down, I have enemy placement with one nybble (4 bits) for each of X and Y placement. It's not like it's a LOT of ROM space to waste one byte per enemy... Since the bosses and possibly teasure chests have to be placed at a specific place, you need a way to have non-random placement anyway, so I doubt adding random placement on top of that saves any ROM space, even if it saves one or two bytes per enemy who uses it, the code doing it might largely compensate that. However purely gameplay wise I imagine random enemy placement might be much more interesting and less repetitive, especially for replaying the game a 2nd time. You could also have difficulty levels, and more easily add new enemies without changing much else.

[gauauu]

Since the bosses and possibly teasure chests have to be placed at a specific place, you need a way to have non-random placement anyway, so I doubt adding random placement on top of that saves any ROM space, even if it saves one or two bytes per enemy who uses it, the code doing it might largely compensate that. However purely gameplay wise I imagine random enemy placement might be much more interesting and less repetitive

That's exactly why I supported both. Some rooms really need a specific placement to work correctly. Some benefit from randomness to keep them interesting.

[darkhog]

My solution would be probably randomizing position again until it isn't near the player or in a wall.

So the algorithm would be (in pseudo code)

1. Randomize enemy's position
2. If the enemy is in the wall or too close to player, go to 1, else carry on.

[Sumez]

Honestly, I don't think saving cartridge space is a good enough excuse to make enemy spawning completely procedural. You need at least some kind of setting for how spawning behaves in each room if you want the game to work well, though of course I guess that's just my opinion.

If cartridge space is an issue, find a way to compress the data.
With my previous suggestion of having some preset spawn points chosen at random, one effective way to save space would be to make each zone relatively large, for example a 32x32 bit tile, or even 64x64 (meaning each enemy type's spawn map could be contained in a single 16bit bitmap per room!), and just make sure at least one tile within that larger tile is always a valid location (so if you spawn a 16x16 enemy on a 64x64 tile, you'd just pick a new random number & $0F, and increase the index until you find a valid tile).
You could also have more complex spawn maps but reuse the same ones across multiple rooms or enemy types, since you'll probably often find yourself repeating very similar spawn patterns even in rooms that are otherwise very different in their deisgns. Then each spawn map would always be a single 8 bit index at worst.

[DRW]

Thanks for all the suggestions.

In the end, we decided for a pretty simple way that has also been mentioned here:

I will generate a random number and if it isn't a valid spot, I'll do this a few times more. If it still doesn't work after, for example, 10 times, this specific opponent will not trigger at all and the player was lucky.

This way, the algorithm is very easy, without lookup tables or some additional rules. And it has a definite finish point for the rare case where the randomizer really cannot find a suitable location.

Honestly, I don't think saving cartridge space is a good enough excuse to make enemy spawning completely procedural. You need at least some kind of setting for how spawning behaves in each room if you want the game to work well, though of course I guess that's just my opinion.

I don't think that's necessary. If the monster can walk to any point on the map that's not a wall, it can also spawn on any point of the map. If I have soldiers who attack in formation, I will skip the radomization in the first place and simply put them in fixed positions. But if I have a horde of wolves, why shouldn't they be in completely random locations?

If cartridge space is an issue, find a way to compress the data.

It's not only the cartridge space, it's also the hazzle to define this for every screen.
So, you don't just have the actual layout of the screen, but also tactical rectangles for enemy placement. Nah, that's too complicated.

[rainwarrior]

If it still doesn't work after, for example, 10 times, this specific opponent will not trigger at all and the player was lucky.

I think it's a very good call to have a fallback like this.

There are simple cases where you can guarantee your PRNG will eventually produce a valid result, but it's very easy for edge cases to slip through the cracks when you start adding all the little constraints that come up in a real system.

[FrankenGraphics]

But if I have a horde of wolves, why shouldn't they be in completely random locations?

I think that's a good approximation of a "disorganized", "chaotic" or even "wild" trait, and wolves would fall in the third category.

one could also think of wolves having a lookput at the point with the best view, and it will call its pack when in line of sight. Those could either be randomly placed or come in from the edge of the field.

I think that's the options i'd consider for spawning wolves.