Monster spawning algorithm

[liquidsoap]

I am a little stuck on how to randomly spawn monsters throughout a randomly generated dungeon. I have a 2d array that stores the tiles for map. When the map is being generated and I create a room at a random location, how do I choose what enemy to place based on the dungeon level that we are generating. If I am generating the first floor I do not want to spawn dragons, I just want to spawn the easy monters. How do most roguelikes do this effectively?

[Pueo]

    I would (I've never actually done this, so it's hypothetical) give each monster a number, which corresponds to the depth it is suitable for, for example, dragons would get 25, and rats would get 1.  Then, when you make the level, check the depth, choose a monster suitable for that depth, and place it in an empty space. 

    You can also generate "out-of-depth" creatures, where maybe a eel, which is numbered 3, is put on floor 1.

[guest509]

  That's the basics of it. It can get far more complex, but that's the basics.

  You might also do a weighted list for each level or level type.

  For example:
  Level 1:
    Roll 1d6
    if 1-3 then place EMU
    if 4-5 then place GOBLIN
    if 6    then place HOBGOBLIN

  Level 2:
    Roll 1d6
    if 1-2 then place EMU
    if 3-5 then place GOBLIN
    if 6    then place HOBGOBLIN + 2 GOBLINS [sort of a miniboss type fight here]

  Greenskin Lair Level:
      Roll 1D6 [Repeat rolling for a number of times equal to the dungeon level]
      1: GOBLIN
      2: GOBLIN x 2
      3: HOBGOBLIN
      4: HOBGOBLIN x 2
      5-6: GREAT ORC


  That's just some ideas. There are tons of ways to do it. As long as appropriate monster difficulty results you should be fine.

[liquidsoap]

I was thinking about doing this but if the dungeon has 100 levels I do not 100 if statements. Is there a way to use the dungeon level to spawn enemies without all these if statement?

[Ari Rahikkala]

Monster spawning is likely to be some form of a weighted random choice in most games. Well, I'm not sure how many games use it explicitly, but it's likely to be there in some form, and the method is general enough that at least explaining it should be a good way to get you started. The obvious implementation is putting all of the options in a list and iterating over that list twice (one example I found by googling), which should be easy enough to write and more than fast enough unless you have hundreds of thousands of monster types in your game.

Using weighted random choice reduces your question to what should be the probability of each monster type spawning, and that depends entirely on what kind of a game you want to make. Giving a very high frequency to monsters whose challenge level is close to the dungeon depth gives you more controlled, tunable gameplay where you know exactly what the player is going up against at each depth. Making the choice looser - for instance, you could simply have the depth work as a cut-off such that the probability of spawning any monster beyond that is zero, and have uniform spawn probabilities otherwise - gives breezier gameplay where the deeper the player is, the more they're facing comparatively shallow-leveled monsters (and the more of a relative threat a monster of their actual depth is, of course!).

Then you just tune and twiddle as necessary. Maybe give monsters a base frequency (so that red dragons are more common than turquoise spotted mechano-dracolichs, regardless of which one's a greater threat) . Maybe instead of single depth you could give them a level range, and multiply the base frequency by (say) a thousand if the current level is within the range. Or define spawn probabilities as second-degree polynomials of player depth. Have extra multipliers for themed levels, so that maybe the warrens level has a ten times bigger chance of spawning goblins. Have the super extra dangerous mid-game level have a high chance of spawning very out-of-depth monsters. Etc., etc.. Probabilities are simple and powerful things, you can do a lot of stuff with them once you get used to them.

[Pueo]

I was thinking about doing this but if the dungeon has 100 levels I do not 100 if statements. Is there a way to use the dungeon level to spawn enemies without all these if statement?

    I don't know what language you are using, but it should have some form of a switch statement, which is basically a shortcut to 100 if-else-if statements. 
    However, there should be an easier way than that.  I just haven't figured one out yet.

[kraflab]

This is how I do it:

In the text documents that detail the monsters I specify the level they appear on (if you don't keep stuff like this in text files it's time to start!)
When I load the monsters, their spawning data gets shoved into lists.
When I want to place a monster, I pick one from the spawnlist[level] and see if it passes a probability check to see if it should spawn (i.e. rare monsters are less likely to spawn).
You can also have a probability of picking from an out-of-depth list if you so choose.

But ya, obviously hard-coded if statements should not be present here!

[Paul Jeffries]

In my last game I did it by giving each level a "style" which (among other things) contained a list of the enemies that were allowed to spawn on that level.  Separately, each level had a 'points budget' and each monster had a 'points cost' based on how dangerous it is.  When populating the level, enemies were picked at random from the enemy list and their points cost deducted from the budget until it was all gone.  This meant that I could give different levels the same style and hence the same monster set, but varying difficulty, since some levels could spawn more or higher-cost monsters off that list.

Another balancing trick I employed to try and make sure that you weren't faced with all of the monsters being generated in one small portion of the level was to randomly nominate and store a number (based on area) of 'spawn points' within each room during the level generation.  When placing enemies later on I just picked spawn points at random off the list and then discarded them.  This made placement easy (I didn't have to bother checking for obstacles because I knew all of the spawn points were in accessible places) and ensured that no room could have above a certain monster density.

[liquidsoap]

For each dungeon level there will be a list of enemies that are allowed to spawn on that level. Now would I have to actually create every enemy to get the level data in the actual enemy class? Or will I just store the level that each enemy can spawn at somewhere else so I do not have to create each enemy? I am using java.

[kraflab]

I have enemy "instances" stored in the list and then copy them when I spawn something.  You could also just load the relevant data when you want to spawn them.  I'm not entirely sure that is the answer you want because I don't fully understand your question.

[liquidsoap]

ya sorry it wasn't worded very well. When I create my list of enemies that can spawn I would need to go,

enemylist[0] = new Rat();

And do this for every single enemy. Then after run through every element of the list and check,

if(enemylist[0].getMinDungeonLevel() <= currentdungeonlevel) {}

Then make a new list with every enemy where this if statement is true.
Would this be the correct way or is this a waste of memory?

[kraflab]

You really don't (or shouldn't) need to worry about memory.

When I read a text file, it creates Rat and reads minlevel=X and maxlevel=Y.  There is a Spawn object that has the Rat and other information, such as spawn rates.  Then I do list[level].push(Spawn) for the levels it appears on, with the spawn rates included therein.

Nowhere is the level that something should appear on explicitly stored.

I'm sure there are plenty of alternative ways to do this, so do whatever makes the most sense for your system.

[guest509]

  I like what Kraf is doing here. Read from a text file, thus automating the sorting process. I'd never thought of that, I was just playing around with weighted lists and what not.

  Most of my experience is form pen/paper RPG's. They use lists, different lists for different environs and levels.

  As an alternative, and if you aren't up to coding what Kraf is suggesting, you can try this sort of thing for 100 levels.

  Figure out how many enemies you want in the level, you could use a point system as mentioned above, a constant, or random (like 4-7 per level or something).
 
  Roll 2D6 [this will give you 2-12 with a weighted sweet spot of 5-7, 12 is very rare]
  Add Current_Dungeon_Level
  Now check your list [note the lowest number you get is a 3 on level 1, max 13]
  3: Rat
  4: Rat
  5: Rat
  6: Rat  [level 1 'sweet spot'] [cannot occur after level 4]
  7: Bat  ["       "]
  8: Bat  ["       "]
  9: Bat  [cannot occur on or after level 7]
  10: Goblin
  11: Goblin
  12: Goblin
  13: Goblin Mage [1/36 chance to occur on level 1]
   .
   .
   .  
  112: Dragon
 

  In the end you'll figure out what's best for you. How many monsters are you having? The above way only works well with say 25 monsters or so. With more then you'd get into making sublists (rpg's do this). So, for example, if you rolled a 'DRAGON' then you would then roll on the Dragon sublist.

DRAGON SUBLIST
1. Red Fire Dragon
2. Red Fire Dragon
3. Red Fire Dragon
4. Blue Frost Dragon
5. Green Acid Dragon  
6. Ancient Golden Dragon