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

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW »

What way would you suggest for placing the enemy characters in a top-down game that scrolls screen-by-screen? (I.e. the enemies are loaded anew with every new scren.)

Declaring what kinds of enemies and how many appear on every screen is pretty simple.

But how do I do their initial placement on the screen if I don't want to have them start in a fixed location?

First of all, they shouldn't be allowed to appear too close to the hero. So, when the hero enters the screen from the left, they cannot be positioned too far on the left side, so that he doesn't get hit unfairly.

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.

And if the value points to a wall, I could simply add 1 until it doesn't anymore, but this would mean that tiles right from a wall are more likely to be picked than other tiles.

But do you know of any other, more elegant ways of choosing enemy start positions on a screen?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

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

Post by tepples »

Instead of adding 1, make clustering less obvious by choosing the next square Galois-style. Perform one bit of a CRC calculation on it.

Code: Select all

jsr random8
placeloop:
  sta xyposition
  jsr evaluate_position
  bcc position_ok
  lda xyposition
  asl a
  bcc :+
    eor #$D9
  :
  dec total_failures_left
  bne placeloop
jmp clear_and_start_over
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW »

I have a bit trouble wrapping my head around this.

Can you please explain in prose what this code is doing here?
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

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

Post by FrankenGraphics »

In Metal Gear, enemy placement is fixed and deliberate. For the most part, everything is balanced and fair; There's a few tough entryways that aren't, iirc. This has the side effect of rooms being predictable once you've learned them.

Zelda relies more on having enemies appear after a while. MG has that too, but less so. Unlike MG, Zelda will sometimes warn the player of their placement with a puff of smoke.

If you have the cpu time, you don't need to go from left to right row by row when placing enemies randomly. You can have a pregenerated array (fixed at assembly time) with all possible positions in a room semi-randomly shuffled. Then when enemy placement begins, pick a number (randomly) in that array to start from. Then step forward (wrapping around the array) until a legit position is found. Optionally draw a new seed for the next monster, or just step on*, rnse and repeat. You can also check for the position tested if it is too close to the player characters' initial position, so it's not only for wall detection.

*Just stepping on means certain patterns of enemy placement might appear. On the other hand, it should mean no monster is risking being placed overlapping another.
Last edited by FrankenGraphics on Tue Oct 17, 2017 1:00 pm, edited 1 time in total.
Celius
Posts: 2158
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

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

Post by Celius »

One solution would be to have a rough area where an enemy should start. The area would be, say, 5x5 metatiles. Instead of having an exact location for the enemy, you would indicate the location of the area, and have the enemy start in a random non-solid tile within the area. This way you can still design screens with a general sense of where enemies will be when the player enters the screen.
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW »

FrankenGraphics wrote:In Metal Gear, enemy placement is fixed and deliberate.
Of course, fixed placement would be pretty mundane to design. I will actually do this additionally for specific opponents, but not for most.
FrankenGraphics wrote:Zelda relies more on having enemies appear after a while.
This one would be a different issue, though. Even if an opponent appears some time later, you still have to apply the basic appearance rules. (Except maybe that you don't need to pay attention anymore to where the hero is standing.)
So, the question whether we use timing or not is a separate feature, but it doesn't influence the actual initialization code itself.
FrankenGraphics wrote:You can have a pregenerated array (fixed at assembly time) with all possible positions in a room semi-randomly shuffled.
This could require a lot of ROM space.
Actual graphics are stored as variable-length meta tiles, so no matter whether it's a stone or a house, it only requires three bytes on the screen (x, y and meta tile index for a lookup array).
But also having a list of possible start points could be much. If only 25 % of all tiles are walkable, this is still 60 additional bytes per screen.
Celius wrote:One solution would be to have a rough area where an enemy should start. The area would be, say, 5x5 metatiles.
I'm not sure whether this solves the issue. It still has pretty much all the problems that I have with the whole screen anyway: I still have to react to placement in solid tiles and I still have to take care that the enemies don't appear too close to the hero's side.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

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

Post by FrankenGraphics »

This could require a lot of ROM space.
You only need one, and that will work for every room/screen. You could have more, but the use is debatable (maybe it could have some subtle effect on an area-for area basis for example, but it doesn't sound like it is worth it). I mean, if you're doing collision checks for monster spawning, that makes up for it not being unique to each particular room. EDIT: For clarity, the purpose of the array is to shuffle the order of positions you're stepping through. It is not directly tied to the layout of any particular room.
tepples
Posts: 22708
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

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

Post by tepples »

DRW wrote:I have a bit trouble wrapping my head around this.

Can you please explain in prose what this code is doing here?
I'll take this as a request to repost my code with the comment detail cranked up to "scary":

Code: Select all

; Choose a random number from $00 to $FF, where one nibble represents
; the horizontal (X) position and the other the vertical (Y).
jsr random8

; This is a label, a place where execution will continue later depending on
; decisions taken by other parts of the code.
placeloop:

  ; Save the X and Y positions for later use.
  sta xyposition

  ; Call a subroutine that determines whether the position in A is a
  ; valid placement for this object, based on not overlapping walls,
  ; distance from the player, etc.
  jsr evaluate_position

  ; The routine returns whether the position is blocked in the
  ; carry flag. Carry set means the position is blocked; carry
  ; clear means the object may be placed at the position.
  ; So if carry is clear, continue the rest of placement.
  bcc position_ok

  ; Choose a different position based on this one.  Start by
  ; multiplying the X, Y coordinates by 2, allowing the most
  ; significant bit of the coordinate stored in the low nibble
  ; to carry into the least significant bit of the coordinate
  ; stored in the high nibble.
  lda xyposition
  asl a

  ; Linear feedback shift register formula: If the multiplication
  ; by 2 overflowed, XOR the with the polynomial of the LFSR.
  bcc :+
    eor #$D9
  :

  ; This routine has a bug: if xyposition is chosen as 0, it never
  ; gets changed.  Fixing this is an exercise for the reader.

  ; If the placement routine has had to move too many things on
  ; this screen, it may have fallen into an unfixable situation.
  ; Remove all randomly placeable objects and start over.
  dec total_failures_left
  bne placeloop
jmp clear_and_start_over

User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW »

FrankenGraphics wrote:You only need one, and that will work for every room/screen.
One start positions array for the whole game (or a major number of screens)?
Do you mean it in a way so that all enemies can only appear in, for example, these places?
Screen.png
Screen.png (2.21 KiB) Viewed 5030 times
I don't think this would work. If the places have to be always walkable, that limits the level design too much (even if I have 10 different arrays).

And if I have to include collision checks with the ground, what's the advantage of the array? I could simply generate random numbers for my regular screen array and check the collisions just as well.

If this array is just a list of positions in the way that if one position is occupied, the game takes the next one in the array instead of the next closest tile on the screen, I don't really need an array.
I could just say:
Generate a position in my screen array.
If it is occupied, add the value n to it until the position is free.
After every check, turn n into another value (for example, n can be 1, 2, 3, 5, 7, 11, 13 or 17).
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
User avatar
DRW
Posts: 2225
Joined: Sat Sep 07, 2013 2:59 pm

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

Post by DRW »

tepples wrote:I'll take this as a request to repost my code with the comment detail cranked up to "scary"
Thanks.

That's the reason why I rather discuss general concepts instead of reading actual example code. It tends to have too much stuff that isn't really necessary for understanding the solution.

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.

By the way, if it doesn't work after a certain amount of tries, instead of starting over I would simply start moving along the array entry by entry from the last position, so that it's guaranteed that I will definitely find a valid location in time. I mean, otherwise, that algorithm might fail hundreds of times.
My game "City Trouble":
Gameplay video: https://youtu.be/Eee0yurkIW4
Download (ROM, manual, artworks): http://www.denny-r-walter.de/city.html
Celius
Posts: 2158
Joined: Sun Jun 05, 2005 2:04 pm
Location: Minneapolis, Minnesota, United States
Contact:

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

Post by Celius »

DRW wrote:I still have to react to placement in solid tiles and I still have to take care that the enemies don't appear too close to the hero's side.
This is true. The one nice thing to this approach is that you potentially could get away with manually positioning the areas to always be away from where the player starts. But this could create an issue if you have lots of screens that you can enter from all sides. You would have to position the areas to be away from the edges of the screen.

If the whole screen is up for grabs, I would personally go with the approach of picking a random tile on the screen and having a routine that validates whether or not that spot is allowed. The routine would test all scenarios where the tile is not allowed, and if it doesn't meet any of those conditions, it is allowed. The scenarios where a spot is not allowed seem to include:

-Solid tile
-Too close to player
-Another enemy is already in that spot

In the event that the routine says the tile is not allowed, you would just pick a new random tile and try again. Don't try to go up or down a tile from what you tested; just test a totally random, different tile.

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.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

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

Post by FrankenGraphics »

Do you mean it in a way so that all enemies can only appear in, for example, these places?
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. The point of such an array is that:

-You can somewhat finely control the likelyhood a position being a spawn point by including a certain position n times in your array.
-The array could potentially do double-duty as a defacto LUT for specific enemy placement when not looked up with a randomized index.
-You can easily exclude positions you don't want if your doors/openings will always be in the same spot (zelda dungeons).
-Shuffled is not the same as random. Depending on the length of the sequence, it may be possible for the player to detect the "designer's hand", or more importantly, learn the pattern, which may appear fairer than pure randomness. Tthere may be a connection to the skill roof. The observant player will learn what to expect and act accordingly.
-A bit of an afterthought: you can keep different arrays for different types of monsters to differentiate their spawn behaviour. Some may spawn more concentratedly in the middle, in corners, along walls. Some may spawn scattered, others more likely in clusters.
-You can have a smaller arrays and assigning it an offset if you can find a use for that.
User avatar
Sumez
Posts: 919
Joined: Thu Sep 15, 2016 6:29 am
Location: Denmark (PAL)

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

Post by Sumez »

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?

Or is it a somewhat procedurally generated thing, where the "random" layout of each room is the essence of the challenge?


I'm a big advocate of well designed RNG in video games, meaning that any random descision isn't just white noise (such as in the image above), but based on a number of recognizable patterns or algorithms. A good example would be a boss fight where the boss has an array of different attacks it can use, but instead of distributing them randomly, some will be more likely than others - but the player can never be sure what to expect, so you'd have to keep your distance to see what the boss does before trying to countering it. And again, once an attack occurs that could be three bullets firing in the general direction of the player, but with a random offset between X and Y pixels, making it more challenging to dodge, forcing the player to gauge the action and react quickly.

The reason I'm mentioning this is that I think this applies very much to level design and enemy spawning mechanics, too. So if your games falls in the former camp of moving around through a designed level, I feel like the enemies spawning should be a part of that design, too. A simple example could be a room being set to have four skeletons, one gorgon and three killer robots, and each of those could have 5-10 different possible set spawn points that they populate randomly. That way a player who has played your game before knows what challenges they are going to face in the next room, but will never be able to anticipate the constellation.

I'm sorry in advance if this theory is not applicable to your game at all.
User avatar
FrankenGraphics
Formerly WheelInventor
Posts: 2064
Joined: Thu Apr 14, 2016 2:55 am
Location: Gothenburg, Sweden
Contact:

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

Post by FrankenGraphics »

meaning that any random descision isn't just white noise
Well worded. Randomness needs to be tamed/conditioned. It can sometimes be unpleasant without.
User avatar
gauauu
Posts: 779
Joined: Sat Jan 09, 2016 9:21 pm
Location: Central Illinois, USA
Contact:

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

Post by gauauu »

I agree with Sumez -- it depends on the game design constraints.

What I did in my GBA Anguna game (which has more processing time than the NES):
- some enemies have fixed positions, some are random
- I randomly pick an enemy position, if it's no good, I just try again. If it can't spawn after X number of tries, it gives up and doesn't spawn

What I did in my Atari Anguna game (which is more limited than the NES, and had a limited number of room layouts):

- For every room layout, I picked 8 different possible reasonable enemy spawn locations (far from doors where the player enters, not on a wall, etc), and randomly picked one. This ran into problems with extra-large enemies, but otherwise worked.
Post Reply