#160 improved pick_random_monster

open
nobody
None
5
2008-10-09
2008-10-09
Anonymous
No

I've tried to understand monster generation and believe the attached patch creates a functionally equivalent (minus the MONS_PROGRAM_BUG's) implementation of monplace.cc:pick_random_monster.

This should be a lot more efficient than the current version, though it's still quite suboptimal, traversing all monster types twice. The same change could be applied to abyss monster generation, and possibly elsewhere. In that case, the "algorithm" should probably be factored out into stuff.cc (some general "chose one among many with varying weights").

I'm pretty sure the current behaviour is to some extent accidental, but I guess it works well enough. Probably best to make the code clearer first and adapt afterwards.

Discussion

  • Nobody/Anonymous

    This is a broken out patch that just simplifies a little and doesn't really touch the algorithm:

    Index: monplace.cc

    --- monplace.cc (revision 7200)
    +++ monplace.cc (working copy)
    @@ -262,6 +262,28 @@
    // No monsters in the Labyrinth, or the Ecumenical Temple, or in Bazaars.
    }

    +// modify rarity based on level difference
    +// compared to random2avg(100,2)
    +int _mons_chance(monster_type mon_type, level_id place, int lev_mons)
    +{
    + int diff, diffsq, level, rar;
    +
    + level = mons_level(mon_type, place);
    + rar = mons_rarity(mon_type, place);
    + diff = level - lev_mons;
    + diffsq = diff*diff;
    +
    + // zero rarity means it can't occur, while zero rar-diff*diff is just unlikely
    + if (diffsq > 25 || rar == 0)
    + {
    + return -1;
    + }
    + else
    + {
    + return rar - diffsq;
    + }
    +}
    +
    monster_type pick_random_monster(const level_id &place, int power,
    int &lev_mons)
    {
    @@ -327,8 +349,6 @@
    }
    else
    {
    - int level, diff, chance;
    -
    lev_mons = std::min(30, lev_mons);

    int i;
    @@ -346,15 +366,8 @@
    if (count == 2000)
    return (MONS_PROGRAM_BUG);

    - level = mons_level(mon_type, place);
    - diff = level - lev_mons;
    - chance = mons_rarity(mon_type, place) - (diff * diff);
    -
    - if ((lev_mons >= level - 5 && lev_mons <= level + 5)
    - && random2avg(100, 2) <= chance)
    - {
    + if (random2avg(100, 2) <= _mons_chance(mon_type, place, lev_mons))
    break;
    - }
    }

    if (i == 10000)

     
  • Nobody/Anonymous

    I should note that the patch compiles for me and seems to provide the normal distribution from one play through to D:8 or so. Unfortunately, I haven't been able to compile wizard mode.

     
  • Nobody/Anonymous

    Ugh, _chance_to_prob needs some bounds checking:

    if (chance < 0)
    return 0;
    else if (chance > 99)
    return 10100;

     

Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks