Author Topic: Monster generation  (Read 33454 times)

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Monster generation
« on: January 12, 2014, 05:44:29 PM »
So I migh have asked this before, but how do you guys usually go about deciding monsters for a level?

Right now I build an array of all the possible monsters but the problem is that I need to set how many times the monster shows up in the array in each level meaning I need to have a monster probability for each monster for each floor. Do you guys do it a different way?

Snargleplax

  • Rogueliker
  • ***
  • Posts: 50
  • Karma: +0/-0
  • snargleplax
    • View Profile
    • SnargleQuest dev log
Re: Monster generation
« Reply #1 on: January 13, 2014, 01:52:13 AM »
Depends so much on what results you want.  Do you want a completely random mix of monsters on each level?  Or should levels be a bit thematic, or choose a few kinds of monster to emphasize (lots of orcs on this level, lots of jellies on the next, etc.), with a few wildcards in the mix (there could always be a greater demon around the corner)?

In any scheme, you're probably going to be starting with some metric for how difficult a monster is.  One common way is to specify the "native level" of the monster.  On level 7, you should see lots of level 7 monsters, as well as some level 6/8 monsters, fewer 5/9s, etc. until you hit the point where you feel like it's too unreasonably out of depth.  Let's say you make half your monsters same-depth, and divide the remaining half between deeper and shallower.  For each of those cases, maybe give it an 80% probability of being one level out of depth.  The other 20% of the time, give it an 80% probability to be two levels out of depth, etc.  Exponentiate like that until you hit a limit, and just cut it off there.

So, that's a reasonable way to go, but it doesn't treat monsters any differently.  If that's not what you want, you might think about spawning packs of monsters as a unit or other things like that.

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: Monster generation
« Reply #2 on: January 13, 2014, 04:06:16 AM »
So I always see that people say like there us an 80% chance if spawning how does that actually work? Is each monster just given a percentage to show up but what does a person actually do to figure that out? Do they fill an array? I guess I am more wondering the actual logic then the code. I like the idea of monster difficulty.nyou could almost do it like a level has a budget of monster levels.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Monster generation
« Reply #3 on: January 13, 2014, 06:44:01 AM »
If you've got an array of relative "weights" for each monster to be generated on a given level, you can generate an array of probabilities by dividing each weight by the sum of all monsters' weight. Then you can find the array of cumulative probabilities by getting the cumulative sum of probabilities. That will assign each monster in sequence a number that starts at 0 for the the first monster and goes up to something less than 1 for the last monster.
With the cumulative probabilities calculated, you can just pick a random float from 0 to 1. The monster you generate is the last one whose cumulative probability is less than the random number.
This is more or less what std::discrete_distribution does in c++. You can skip the division step and choose random numbers between 0 and total weight if you want, I only did that so that I could talk in terms of probability. You can use binary search in the last step, but for this application it's not too important.

guest509

  • Guest
Re: Monster generation
« Reply #4 on: January 13, 2014, 08:04:16 PM »
Well Jason I keep it simple myself. My boardgame design background shows through here. For KlingonRL, for example, each system was either:

Friendly (Klingon) (star system 1)
Hostile (Federation) (star systems 21-25)
Neutral (Systems 2-17).
-Special Romulan (system 19)
-Special Neutron Star and Space Whales (system 20)
-Pirate Base (system 18)

In each system I had a sort of table you rolled on. For example the Klingon System always had between 3-6 Klingon cruiser rolling around. So...

If System_Number = 1 then
   Roll Random (3-6)
   Place that number of Klingons, and don't place them on top of each other or on a planet or something dumb.

For Federation systems it was only slight more complex...

If System_Number = 21-25
   Roll Random (4-8) for the number of ships to place.
   Place that number of ships in valid locations, randomly.
   Roll (1-100)
     -1-10 then the ship is a Missile Cruiser
     -11-20 Science Vessel
     -21-30 Battleship
     -31 - 100 Standard Cruiser

So if you do the math, you are going to get AT LEAST 4 ships in a Fed system, and usually at least one of those is going to be a Missile Cruiser/Science Vessel/Battleship with the rest as Standard Cruisers.

To apply this generically I would
1. Decide how many baddies are on that level, can be a random number in a certain range.
2. Do a placement loop for each baddie, and choose from a sort of weighted list.

You'll note that this is pretty much exactly how D&D handles wandering monsters. You check what terrain you are in, or level, and then you roll on that table.

I'm not sure how many levels you have, but you can make a different table for each level, or you can make a different table for each level theme. It's really game specific. You can mix them as well, adding modifiers for the deeper levels.

For example a fire level, deep in the dungeon would have more and harder baddies.

Number_of_Monsters = 4-8 plus Depth/10. That would give you +1 monster every 10 levels.
Now place that many monsters by looping through the Fire Level Table.
   Roll 1-20 (plus Depth)
   -1-9 = Lil Sparky (by depth 9 there are no more of these)
   -10-18 = Lil Flamer (by depth 18 there are no more of these)
   -19-27 = Big Sparky (rare on level 1, getting more common as level's progress, then cut out at level 27)
   -28-36 = Big Flamer
   -37+ = Fire Mini Boss (cannot show up until level 17, 1/20 or 5% chance, by level 36 they are all you get)


Of course how you place your monsters, how many will spawn, and how level affects that, and what types and if the type depends only on depth or if level theme has a say...all that is up to the developer. Note in KlingonRL depth did not matter, the player got weaker over time unless they refueled and repaired and progression was nonlinear, so leveling and increasing in difficulty by level design was not necessary.

When I made Sun Crusher!!!, which was linear, every 3 levels a new type of more difficult baddie showed up, and each level had an increased number of baddies and an increased % chance of a harder baddie showing up. It was only 9 levels though, so I did it by set tables.

Number_of_Baddies = 2-4 plus (level/3) (so level 1 had 2-4 baddies, and level 9 had max 5-7)
Level 1- 3 = place all Easy Baddies.
Level 4 - 6 = alternate 1 easy and 1 medium (so they end up being roughly equal amounts easy and medium)
Level 7 - 9 = alternate placing 1 medium and 1 hard (no more easy baddies)
Boss level 10 = all hard baddies, no more mediums.

Anyway that's how I've done it in the past. The level depth modifies the number of bad guys (sometimes) then run through a table depending on the level theme (and/or depth) and if it makes sense for your game you can add modifiers to your table roll depending on the depth.

guest509

  • Guest
Re: Monster generation
« Reply #5 on: January 13, 2014, 08:36:01 PM »
For my 7DRL coming up this year I'm not doing fully procedural levels, but rather doing preset boards (single screen predesigns) with plenty of spaces that randomize, thematic skinning, etc... there will be spawn points on each board, each spawn point creates one monster. That monster will come from a table according to the theme of the level (castle, crypt, fire, ice, cave, etc...) , there will be 5 monsters associated with each level theme, but you will see the first 1 only on level 1 and as you progress deeper the others will start showing up.

It's not completely set yet how many levels I'll have, but say there are 20 levels. You'll not see the 2nd monster type until level 2 (and then it will be rare), you'll see the 3rd by level 6, etc...with earlier monster types slowly being replaced by later ones.

This is easy to do with a simple table roll plus depth.
 
Example:
Castle_Theme
Roll 1-5 (plus depth) Max Depth = 20
-2-6      = Rat
-7-11    = Squire
-12-16  = Archer
-17- 21 = Guard Dog
-22+     = Knight

Notes by level
-1 Rats only
-2 Squires show up
-6 No more Rats, Squires only
-7 Archers arrive
-11 No more Squires, Archers only
-12 Guard dogs arrive
-16 No more Archers, Guard Dogs only
-17 Knights arrive.

Since it's a 7DRL I might only get one theme done, 5 monsters, 20 levels. Probably the Ice theme...



jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: Monster generation
« Reply #6 on: January 17, 2014, 02:57:20 AM »
man that is a lot of info to absorb.

I like the simplicity of the dice tables from D&D which I had completely forgotten about. I am reworking it a bit to get a better distribution of characters throughout the 10 levels I am trying. currently my table looks like this:

Roll 1-7 (plus depth) Max Depth = 10
-2-5      = Slime
-6-9      = Demon
-10-13  = Fire Elemental
-14- 17 = Wolf

It needs to have a few more monsters and I need to get a bit better distribution so I can have like about 3 different monsters per floor. I think I am going to need to expand out the roll and that should fix it. the hard part now is balancing the enemies to get a good difficulty curve.

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: Monster generation
« Reply #7 on: January 17, 2014, 03:06:53 AM »
Oh also instead of using a d20 for this, you could use 2d10. It would give you a nice bellcurve that would move along the table.

guest509

  • Guest
Re: Monster generation
« Reply #8 on: January 17, 2014, 03:51:10 AM »
So you see:
Slimes on levels 1-4
Demons on levels 1-8
Fire Elementals on levels 3-10
Wolves on 7-10

Level Distribution if you had 7 baddies per level and an even roll distribution (note each 1/7 corresponds to a distribution of 14.3% chance of showing)
1 = 4 slimes and 3 demons
2 = 3 slimes and 4 demons
3 = 2 slimes and 4 demons and 1 Fire Elemental
4 = 1 slimes and 4 demons and 2 Fire Elemental
5 =                   4 Demons and 3 Fire Elementals
6 =                   3 Demons and 4 Fire Elementals
7 =                   2 Demons and 4 Fire Elementals and 1 Wolves
8 =                   1 Demons and 4 Fire Elementals and 2 Wolves
9 =                                        4 Fire Elementals and 3 Wolves
10 =                                      3 Fire Elementals and 4 Wolves

Note sure that helps, but it's interesting to look at. Seems to be a good distribution.

You could always just fill a table by level, like if you are level 5 then roll on a %die table and fill that way, but this spread looks good.

So if you go through each level, beat the whole game, with 7 baddies per level, on average you would see: 10 slimes, 25 demons, 25 fire elementals and 10 wolves.

jasonpickering

  • Rogueliker
  • ***
  • Posts: 274
  • Karma: +0/-0
    • View Profile
    • Email
Re: Monster generation
« Reply #9 on: January 18, 2014, 12:32:16 AM »
One thing I have noticed is its hard to have rare monsters. with the RNG its possible to have a level with all the same enemy, and the different enemies is what my game hinges on. I might have to continue playing with this. Or go back to my original idea of the array with enemies in it I am removing after they are picked.  :-\

guest509

  • Guest
Re: Monster generation
« Reply #10 on: January 18, 2014, 03:22:20 AM »
Well you could always do a sort of max number of the same enemy in the level.

Like keep track of how many of a type have been spawned on a level, and reroll when you hit a max.

For example:
Roll on table to place a monster.
If Slime is rolled then check.
  if Number_of Slimes >= 5 then reroll.

That would assure a variety and also a random number. You could play around with this all day, it need not be super complex.

You could even do a level by level system just as easy.

If Level = 1 then roll and place
   2-4 slimes
   1-2 demons
If Level = 2 then roll and place
   1-3 slimes
   2-3 demons

And so on. You can make sure there are neither too many nor too few on each level. You can even make there be a max on each level like this.

If Level = 2 then roll and place
  1-3 slimes
  5 demons (minus the number of slimes)

Or how about....
If Level = 2 then roll 1d6
   1-3: 4 slimes 1 demon
   4-5: 2 slimes 2 demons
   6: 1 slimes, 1 demon, 1 fire elemental

So 16% of the time you get that rare fire elemental on level 2. I find that 1/6 chance to be a good 'rare' but not 'too rare' % chance. Like when you play a dice game you really really want to roll that 6, it's common enough it might happen but uncommon enough it's awesome when it does and you feel lucky.

For even more rare I find that rolling 12 on a 2D6 just feels freaking epic, but so rare it's sort of a boring roll if you need a 12 because you know you aren't going to get it. Like trying to roll a natural 20, it can happen sometimes but when you know you need to get that 20 it's sort of a deflating roll because it's too rare, you just sort of throw the dice down and shrug. Whereas if you need a 6 on a 6 sided die man you are going to blow on that shit, shake it in your hand, have a lady wish you luck.

The game Yahtzee isn't the most fun, but the fun it has is that the %'s are achievably high, but rare enough to make it awesome when you land something great.

Anyway my magic rare % is 1/6, but that's from boardgames.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Monster generation
« Reply #11 on: January 18, 2014, 07:21:48 AM »
The thing about dice mechanics is that every time you want to tweak it slightly to improve the balance, it becomes more complicated and difficult to work out the probabilities for, and ypu have to change numbers all over the place that aren't related to the thing you actually want to change.

With a simple weight system you just give each monster its own weight, and the computer adds up to get the right number of sides. That means if you want to change the spawn rate of one monster, you just change that monster's weight and everything else is sorted out automatically. Writing a dice table is basically using this algorithm and then doing all the maths by hand with an artificial constraint on the total weight.

You can make the weights dependent on depth by turning them into a function like 5-depth. That way the monster stops spawning at depth 5.

You can solve the problem of not getting enough rare monsters by subtracting from a monster's weight every time you pick that monster. Just think of it as putting tokens in a bag and picking them out at random. You can either keep the token or put it back in. If you keep picking common monsters, their probability will go down and you'll be more likely to pick a rare monster. You can even skew the system by adding extra tokens for a rare monster, then throwing them away when you finally pick one.

It's a very flexible system, appropriate to the task, and more intuitive than dice imo.

guest509

  • Guest
Re: Monster generation
« Reply #12 on: January 18, 2014, 07:30:42 AM »
If you've spent 25 years making dice/card/boardgames and/or playing table top RPG's the dice are 2nd nature. Of course it does seem silly to apply these limitations to making computer games, but I'm hardly a good programmer.

Can you give an example of how one might do this weights thing, I'd be interested in seeing how it works. I think I know...but...

AgingMinotaur

  • Rogueliker
  • ***
  • Posts: 805
  • Karma: +2/-0
  • Original Discriminating Buffalo Man
    • View Profile
    • Land of Strangers
Re: Monster generation
« Reply #13 on: January 18, 2014, 07:36:49 AM »
The game Yahtzee isn't the most fun, but the fun it has is that the %'s are achievably high, but rare enough to make it awesome when you land something great.
Yahtzee is, like, the most awesome game invented after Go :-O (with Mikado a close third, of course.)

As always,
Minotauros
This matir, as laborintus, Dedalus hous, hath many halkes and hurnes ... wyndynges and wrynkelynges.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Monster generation
« Reply #14 on: January 18, 2014, 09:29:11 AM »
Here's a simple example without any depth variables:
Quote
If System_Number = 21-25
   Roll Random (4-8) for the number of ships to place.
   Place that number of ships in valid locations, randomly.
   Roll (1-100)
     -1-10 then the ship is a Missile Cruiser
     -11-20 Science Vessel
     -21-30 Battleship
     -31 - 100 Standard Cruiser
With a weight system this could be something like:
4-8 ships
Missile cruiser: weight 10
Science Vessel: weight 10
Battleship: weight 10
Standard cruiser: weight 70

If you want to tweak the spawn rates for different vessels, you only have to change one number. If you want to limit the number of battleships so that the player doesn't get screwed by bad luck, you can do something like:
4-8 ships
Missile cruiser: weight 2
Science Vessel: weight 2
Battleship: weight 2 minus number of battleships present
Standard cruiser: weight 14

IF you want things to vary with depth, like in
Quote
Number_of_Monsters = 4-8 plus Depth/10. That would give you +1 monster every 10 levels.
Now place that many monsters by looping through the Fire Level Table.
   Roll 1-20 (plus Depth)
   -1-9 = Lil Sparky (by depth 9 there are no more of these)
   -10-18 = Lil Flamer (by depth 18 there are no more of these)
   -19-27 = Big Sparky (rare on level 1, getting more common as level's progress, then cut out at level 27)
   -28-36 = Big Flamer
   -37+ = Fire Mini Boss (cannot show up until level 17, 1/20 or 5% chance, by level 36 they are all you get)
You can do something like this (the probabilities are slightly different here, I just chose something with easier arithmetic):
Lil Sparky: Native_Depth = -5
    weight = 15 - abs(Native_Depth - Depth)
    if weight < 0: weight = 0
    if weight > 10: weight = 10
Lil Flamer: Native_Depth = 5
    weight = 15 - abs(Native_Depth - Depth)
    if weight < 0: weight = 0
    if weight > 10: weight = 10
Big Sparky: Native_Depth = 15
    weight = 15 - abs(Native_Depth - Depth)
    if weight < 0: weight = 0
    if weight > 10: weight = 10
Big Flamer: Native_Depth = 20
    weight = 15 - abs(Native_Depth - Depth)
    if weight < 0: weight = 0
    if weight > 10: weight = 10
Fire Mini Boss:
    weight = Depth - 20
    if weight < 0: weight = 0

I'm using the absolute value function (abs) here; that just gets rid of minus signs, so abs(-5) = 5. You can also use the max and min functions to get rid of those weight<0/weight>10 lines. abs(Native_Depth - Depth) will give you the distance between this depth and the native depth.

Just as a formula in a finished, balanced game, a weights system isn't much easier than the dice system, but if you're tweaking and balancing it's a lot easier to alter one monster's spawn rate without affecting the other monsters, or to add and remove monsters. For instance, if you pointed out that in my version, a Big Sparky can't spawn on level 1, all you do is change its native depth to 14. Everything else gets calculated automatically.

You can also mix in any variables from the game, like details from the spawn tile:
Science Vessel: weight 6 (spawn tile is near a nebula), or 2 (otherwise)
Troll: weight 13 (spawn tile is a bridge), or 3 (otherwise)

If you want a certain monster type to be common in a small range of levels, you can do that easily:
Fire Cultist: Native_Depth = 12
    weight = 3 * (5 - abs(Native_Depth - Depth))
    if weight < 0: weight = 0
    if weight > 10: weight = 10
This monster spawns in a 10-level range, rather than a 30-level range like the rest of them, but the weight still goes up to 10 on levels 11, 12, and 13.