tmewett / BrogueCE

Brogue: Community Edition - a community-lead fork of the much-loved minimalist roguelike game
https://sites.google.com/site/broguegame/
GNU Affero General Public License v3.0
990 stars 107 forks source link

Bog monster generated inside a statue #15

Open tmewett opened 4 years ago

tmewett commented 4 years ago

Seed 739002545, depth 11. The bog monster is fully visible and shows on the sidebar as hunting.

Bog monster inside statue

Any monster that spawns in a statue should be dormant and activated when the player is near. I'm fairly sure it's impossible for a creature to coincidentally be generated inside an inert statue, but this needs to be checked. Perhaps this is an edge case of a creature statue being generated in a bog.

tmewett commented 4 years ago

I think the issue arises from Architect.c:796, in the function spawnHorde, which makes the call

randomMatchingLocation(&(loc[0]), &(loc[1]), FLOOR, NOTHING, (hordeCatalog[hordeID].spawnsIn ? hordeCatalog[hordeID].spawnsIn : -1)

This function is defined at Architect.c:3732:

// fills (*x, *y) with the coordinates of a random cell with
// no creatures, items or stairs and with either a matching liquid and dungeon type
// or at least one layer of type terrainType.
// A dungeon, liquid type of -1 will match anything.
boolean randomMatchingLocation(short *x, short *y, short dungeonType, short liquidType, short terrainType) {

Because the bog monster horde definition has a spawnsIn entry of MUD, randomMatchingLocation only looks for a cell with MUD on one of its layers; it disregards the condition that dungeon layer should be FLOOR, which would be used if spawnsIn were 0. This means the marble statue is a matching location as it has MUD on the liquid layer, despite it having STATUE_INERT on the dungeon layer.

Adding an extra condition that monsters cannot spawn on obstructing tiles wouldn't work, as turrets are specified to spawn in WALL, dormant monster spawn in STATUE_DORMANT, etc.

withinwheels commented 3 years ago

Your theory looks right to me. Additionally all uses of randomMatchingLocation except the offending line seem to pass terrainType == -1.

$ fgrep -n randomMatchingLocation src/brogue/*.c
src/brogue/Architect.c:1129:                    randomMatchingLocation(&originX, &originY, FLOOR, NOTHING, -1);
src/brogue/Architect.c:1760:                if (randomMatchingLocation(&x, &y, gen->requiredDungeonFoundationType, gen->requiredLiquidFoundationType, -1)) {
src/brogue/Architect.c:3755:boolean randomMatchingLocation(short *x, short *y, short dungeonType, short liquidType, short terrainType) {
src/brogue/Items.c:363:        randomMatchingLocation(&(loc[0]), &(loc[1]), FLOOR, NOTHING, -1);
src/brogue/Items.c:646:                randomMatchingLocation(&x, &y, FLOOR, NOTHING, -1); // Food and gain strength don't follow the heat map.
src/brogue/Monsters.c:798:            while (!randomMatchingLocation(&(loc[0]), &(loc[1]), FLOOR, NOTHING, (hordeCatalog[hordeID].spawnsIn ? hordeCatalog[hordeID].spawnsIn : -1))

..which means we're free to change the meaning of a non--1 terrainType without affecting other call sites.

randomMatchingLocation strikes me as a function that is trying to do too many things at once. In particular it runs a boolean formula over sampled locations, and the formula looks large and weird. A solution may involve breaking it up into multiple functions, or equivalently trying to extract and parameterize the boolean formula as an explicit argument of some kind.

Another part of the solution seems to include either making the spawnsIn formula (if we choose to see it as a boolean formula) more expressive, or altering the terrain generator to relieve the need for spawnsIn to be more expressive. In the first choice, the spawnsIn for a bog monster might grow to express (in pseudo) FLOOR && MUD while that for turrets could exclude floor but include WALL.

In the second, we could ask ourselves how important it is to us for MUD to be only on FLOOR, and perhaps forbid it appearing elsewhere.

withinwheels commented 3 years ago

As a concrete realization of those ideas, it is tempting to change spawnsIn from a tileType to a terrain flags mask (or perhaps two, flags required and forbidden.) However mud doesn't offer a lot of flags to key off of. So augmenting hordeType with some terrain flags might be more realistic.

Then of course bog monster would request MUD that forbids T_OBSTRUCTS_PASSABILITY. Turrets could additionally require it, if we're worried about the existence of passable walls.

To act on these flags randomMatchingLocation would probably be split into two. One would drop the terrainFlag argument and cater to the other call sites. The new one would be specifically for horde placement, and perhaps also inline the passable arc count check in spawnHorde.

withinwheels commented 3 years ago

There might be a simpler way. I'm looking at the spawnsIn column and I'm seeing most entries (besides NOTHING) are seemingly dungeon- or liquid-layer anyway. That is, spawnsIn could become spawnsInDungeonType and spawnsInLiquidType, with -1 wildcards filling in the off columns.

Then, the terrainType argument to randomMatchingLocation goes away, and the two new struct fields get fed into the first two arguments instead of the hard-wired FLOOR, NOTHING.

That idea rests on the spawnsIn terrain types being restricted to the dungeon and liquid layers, which I need to double check.

To help with that check, here are the spawnsIn tile types with counts of how many times they appear in the horde catalog.

      9 DEEP_WATER
      1 LAVA
      2 MACHINE_MUD_DORMANT
     25 MONSTER_CAGE_CLOSED
      2 MUD
    112 NOTHING
      8 STATUE_DORMANT
     10 STATUE_INSTACRACK
      4 TURRET_DORMANT
      4 WALL
withinwheels commented 3 years ago

I scanned all floors of the first 300 seeds and counted which layers the above tile types appear in. For speed I omitted WALL and NOTHING. WALL seems to appear only in DUNGEON while NOTHING appears in any layer but DUNGEON.

The others all had hits in the chosen seeds, and each seems to be restricted to exactly one of DUNGEON or LIQUID. I think my proposal will therefore work.

1056800 DEEP_WATER LIQUID
 785232 LAVA LIQUID
    500 MACHINE_MUD_DORMANT LIQUID
    522 MONSTER_CAGE_CLOSED DUNGEON
 338515 MUD LIQUID
   1733 STATUE_DORMANT DUNGEON
    329 STATUE_INSTACRACK DUNGEON
   1457 TURRET_DORMANT DUNGEON
withinwheels commented 3 years ago

..with this patch

$ git diff
diff --git a/src/brogue/Monsters.c b/src/brogue/Monsters.c
index 430324e..f0f15a3 100644
--- a/src/brogue/Monsters.c
+++ b/src/brogue/Monsters.c
@@ -814,6 +814,13 @@ creature *spawnHorde(short hordeID, short x, short y, unsigned long forbiddenFla
             y = loc[1];
             i++;

+            if (hordeCatalog[hordeID].spawnsIn == MACHINE_MUD_DORMANT
+                || hordeCatalog[hordeID].spawnsIn == MUD) {
+              if (pmap[x][y].layers[DUNGEON] == STATUE_INERT) {
+                printf("GOT A WINNER s = %lu d = %d x = %d y = %d\n", rogue.seed, rogue.depthLevel, x, y);
+              }
+            }
+
             // This "while" condition should contain IN_FIELD_OF_VIEW, since that is specifically
             // calculated from the entry stairs when the level is generated, and will prevent monsters
             // from spawning within FOV of the entry stairs.

we can run the repro seed catalog to see a match:

$ ./brogue --print-seed-catalog 739002545 1 11 | grep 'GOT A WINNER'
Scanning seed 739002545...
GOT A WINNER s = 739002545 d = 11 x = 56 y = 11

However, if we then run the first 1000 seeds, we get no hits :sad:. This is therefore pretty rare. I will scan the first 20k soon.

withinwheels commented 3 years ago

I thought I could do 150K overnight, but it's only to 93K. Within those, I see 56 hits, for a ~0.06% repro rate:

GOT A WINNER s = 5323 d = 14 x = 70 y = 21
GOT A WINNER s = 6876 d = 11 x = 56 y = 15
GOT A WINNER s = 7025 d = 14 x = 68 y = 5
GOT A WINNER s = 17014 d = 14 x = 63 y = 25
GOT A WINNER s = 17262 d = 12 x = 29 y = 5
GOT A WINNER s = 17654 d = 10 x = 37 y = 18
GOT A WINNER s = 19381 d = 13 x = 45 y = 20
GOT A WINNER s = 20335 d = 11 x = 17 y = 21
GOT A WINNER s = 20570 d = 11 x = 60 y = 20
GOT A WINNER s = 21926 d = 11 x = 50 y = 21
GOT A WINNER s = 21988 d = 14 x = 6 y = 27
GOT A WINNER s = 21989 d = 11 x = 69 y = 21
GOT A WINNER s = 22626 d = 12 x = 22 y = 10
GOT A WINNER s = 22672 d = 11 x = 59 y = 13
GOT A WINNER s = 23483 d = 10 x = 48 y = 14
GOT A WINNER s = 23712 d = 11 x = 13 y = 23
GOT A WINNER s = 23783 d = 10 x = 12 y = 13
GOT A WINNER s = 23861 d = 12 x = 10 y = 14
GOT A WINNER s = 25629 d = 13 x = 14 y = 21
GOT A WINNER s = 28573 d = 11 x = 20 y = 8
GOT A WINNER s = 29044 d = 12 x = 15 y = 23
GOT A WINNER s = 30056 d = 11 x = 62 y = 2
GOT A WINNER s = 31268 d = 11 x = 24 y = 18
GOT A WINNER s = 33902 d = 13 x = 15 y = 17
GOT A WINNER s = 35986 d = 14 x = 63 y = 14
GOT A WINNER s = 36250 d = 11 x = 52 y = 14
GOT A WINNER s = 37382 d = 13 x = 14 y = 7
GOT A WINNER s = 39472 d = 13 x = 41 y = 21
GOT A WINNER s = 42636 d = 14 x = 43 y = 5
GOT A WINNER s = 42636 d = 14 x = 39 y = 3
GOT A WINNER s = 44127 d = 13 x = 31 y = 20
GOT A WINNER s = 44844 d = 12 x = 34 y = 12
GOT A WINNER s = 44963 d = 12 x = 6 y = 7
GOT A WINNER s = 46520 d = 10 x = 45 y = 6
GOT A WINNER s = 47870 d = 14 x = 36 y = 24
GOT A WINNER s = 50283 d = 14 x = 31 y = 16
GOT A WINNER s = 53474 d = 12 x = 32 y = 10
GOT A WINNER s = 55408 d = 14 x = 33 y = 21
GOT A WINNER s = 64132 d = 11 x = 34 y = 22
GOT A WINNER s = 64132 d = 11 x = 30 y = 21
GOT A WINNER s = 64227 d = 12 x = 62 y = 14
GOT A WINNER s = 66348 d = 12 x = 35 y = 17
GOT A WINNER s = 66539 d = 14 x = 38 y = 17
GOT A WINNER s = 68566 d = 12 x = 58 y = 4
GOT A WINNER s = 69929 d = 13 x = 9 y = 11
GOT A WINNER s = 69991 d = 13 x = 21 y = 6
GOT A WINNER s = 72386 d = 11 x = 12 y = 5
GOT A WINNER s = 73025 d = 10 x = 61 y = 24
GOT A WINNER s = 73141 d = 10 x = 62 y = 18
GOT A WINNER s = 74716 d = 12 x = 42 y = 21
GOT A WINNER s = 79271 d = 10 x = 16 y = 18
GOT A WINNER s = 82417 d = 13 x = 31 y = 17
GOT A WINNER s = 82437 d = 11 x = 19 y = 12
GOT A WINNER s = 86289 d = 14 x = 23 y = 11
GOT A WINNER s = 92838 d = 12 x = 47 y = 22
GOT A WINNER s = 92856 d = 10 x = 47 y = 20

Will inspect these for validity shortly.

SanatMishra commented 3 years ago

Alright, I think #254 will fix this. Try running your brute force tests on top of it.

Sorry for mixing posts in between threads, but I just wanted to say that my previous testing was with the normal statue autogenerator, which comes before the swamp and prevents mud from spawning within the statue. There's an autogenerator after it ("remnant area," carpet with statues) that comes after the swamp, which is how this bug actually happened and why I couldn't recreate it.

Tested it with the remnant, with and without the changed monster generation, it seems to work: https://imgur.com/a/FMHMYSP

In the upper left there's some burned carpet next to the bog, and bog monsters that have all dodged the statues

withinwheels commented 3 years ago

Alright, I think #254 will fix this. Try running your brute force tests on top of it.

No worries. When your branch is in a good state, I'll run the brute check again too against it. It seems 100K seeds is enough to get a trust-worthy signal.

withinwheels commented 3 years ago

The catalog for the first 14 depths of 150K seeds rendered in 14 hours 45 min on one of these 1.8 GHz laptop cores (the process is single-threaded right now.)

There were 82 hits, for a final repro rate of 0.055%

$ grep 'GOT A WINNER' seed-catalog.txt 
GOT A WINNER s = 5323 d = 14 x = 70 y = 21
GOT A WINNER s = 6876 d = 11 x = 56 y = 15
GOT A WINNER s = 7025 d = 14 x = 68 y = 5
GOT A WINNER s = 17014 d = 14 x = 63 y = 25
GOT A WINNER s = 17262 d = 12 x = 29 y = 5
GOT A WINNER s = 17654 d = 10 x = 37 y = 18
GOT A WINNER s = 19381 d = 13 x = 45 y = 20
GOT A WINNER s = 20335 d = 11 x = 17 y = 21
GOT A WINNER s = 20570 d = 11 x = 60 y = 20
GOT A WINNER s = 21926 d = 11 x = 50 y = 21
GOT A WINNER s = 21988 d = 14 x = 6 y = 27
GOT A WINNER s = 21989 d = 11 x = 69 y = 21
GOT A WINNER s = 22626 d = 12 x = 22 y = 10
GOT A WINNER s = 22672 d = 11 x = 59 y = 13
GOT A WINNER s = 23483 d = 10 x = 48 y = 14
GOT A WINNER s = 23712 d = 11 x = 13 y = 23
GOT A WINNER s = 23783 d = 10 x = 12 y = 13
GOT A WINNER s = 23861 d = 12 x = 10 y = 14
GOT A WINNER s = 25629 d = 13 x = 14 y = 21
GOT A WINNER s = 28573 d = 11 x = 20 y = 8
GOT A WINNER s = 29044 d = 12 x = 15 y = 23
GOT A WINNER s = 30056 d = 11 x = 62 y = 2
GOT A WINNER s = 31268 d = 11 x = 24 y = 18
GOT A WINNER s = 33902 d = 13 x = 15 y = 17
GOT A WINNER s = 35986 d = 14 x = 63 y = 14
GOT A WINNER s = 36250 d = 11 x = 52 y = 14
GOT A WINNER s = 37382 d = 13 x = 14 y = 7
GOT A WINNER s = 39472 d = 13 x = 41 y = 21
GOT A WINNER s = 42636 d = 14 x = 43 y = 5
GOT A WINNER s = 42636 d = 14 x = 39 y = 3
GOT A WINNER s = 44127 d = 13 x = 31 y = 20
GOT A WINNER s = 44844 d = 12 x = 34 y = 12
GOT A WINNER s = 44963 d = 12 x = 6 y = 7
GOT A WINNER s = 46520 d = 10 x = 45 y = 6
GOT A WINNER s = 47870 d = 14 x = 36 y = 24
GOT A WINNER s = 50283 d = 14 x = 31 y = 16
GOT A WINNER s = 53474 d = 12 x = 32 y = 10
GOT A WINNER s = 55408 d = 14 x = 33 y = 21
GOT A WINNER s = 64132 d = 11 x = 34 y = 22
GOT A WINNER s = 64132 d = 11 x = 30 y = 21
GOT A WINNER s = 64227 d = 12 x = 62 y = 14
GOT A WINNER s = 66348 d = 12 x = 35 y = 17
GOT A WINNER s = 66539 d = 14 x = 38 y = 17
GOT A WINNER s = 68566 d = 12 x = 58 y = 4
GOT A WINNER s = 69929 d = 13 x = 9 y = 11
GOT A WINNER s = 69991 d = 13 x = 21 y = 6
GOT A WINNER s = 72386 d = 11 x = 12 y = 5
GOT A WINNER s = 73025 d = 10 x = 61 y = 24
GOT A WINNER s = 73141 d = 10 x = 62 y = 18
GOT A WINNER s = 74716 d = 12 x = 42 y = 21
GOT A WINNER s = 79271 d = 10 x = 16 y = 18
GOT A WINNER s = 82417 d = 13 x = 31 y = 17
GOT A WINNER s = 82437 d = 11 x = 19 y = 12
GOT A WINNER s = 86289 d = 14 x = 23 y = 11
GOT A WINNER s = 92838 d = 12 x = 47 y = 22
GOT A WINNER s = 92856 d = 10 x = 47 y = 20
GOT A WINNER s = 93409 d = 12 x = 54 y = 21
GOT A WINNER s = 94929 d = 14 x = 15 y = 16
GOT A WINNER s = 97799 d = 14 x = 9 y = 16
GOT A WINNER s = 98316 d = 13 x = 3 y = 16
GOT A WINNER s = 102350 d = 11 x = 73 y = 21
GOT A WINNER s = 104394 d = 13 x = 25 y = 21
GOT A WINNER s = 106739 d = 13 x = 64 y = 23
GOT A WINNER s = 108817 d = 13 x = 65 y = 13
GOT A WINNER s = 111691 d = 14 x = 32 y = 4
GOT A WINNER s = 112455 d = 12 x = 21 y = 7
GOT A WINNER s = 113780 d = 13 x = 40 y = 25
GOT A WINNER s = 114177 d = 12 x = 63 y = 16
GOT A WINNER s = 114308 d = 12 x = 6 y = 25
GOT A WINNER s = 115688 d = 12 x = 27 y = 10
GOT A WINNER s = 118261 d = 12 x = 60 y = 23
GOT A WINNER s = 121379 d = 14 x = 8 y = 2
GOT A WINNER s = 124809 d = 11 x = 25 y = 18
GOT A WINNER s = 125340 d = 13 x = 49 y = 26
GOT A WINNER s = 127299 d = 10 x = 13 y = 16
GOT A WINNER s = 131124 d = 13 x = 30 y = 10
GOT A WINNER s = 131124 d = 13 x = 33 y = 6
GOT A WINNER s = 139902 d = 13 x = 33 y = 17
GOT A WINNER s = 142297 d = 13 x = 51 y = 23
GOT A WINNER s = 143507 d = 12 x = 14 y = 11
GOT A WINNER s = 145494 d = 14 x = 27 y = 12
GOT A WINNER s = 146196 d = 13 x = 12 y = 10

I'd attach the file, but after gzip compression it's still 54 MiB :shrug: