beware 1642

[PowerDiver]

I've been hit by a bug in cave generation in r1642. I don't know how far back it was introduced. The level is occasionally generated with a single boring room, so no corridors, so an infinite loop looking for a place to put rubble.

If you are playing the nightlies, save before stairs or anything else that creates a level. If it fails, you can nuke the process, restart, and do something to change the seed before you try the stairs again.

[takkaria]

I've been hit by a bug in cave generation in r1642. I don't know how far back it was introduced. The level is occasionally generated with a single boring room, so no corridors, so an infinite loop looking for a place to put rubble.

If you are playing the nightlies, save before stairs or anything else that creates a level. If it fails, you can nuke the process, restart, and do something to change the seed before you try the stairs again.

The game should already autosave before a new level, but maybe it doesn't...

[PowerDiver]

The game should already autosave before a new level, but maybe it doesn't...

It autosaves *after* level generation. IMO it would be better to save before.

[d_m]

This should be fixed in HEAD.

[PowerDiver]

This should be fixed in HEAD.

Did you revert to old generation, or just tune down the constant on the level sizes?

It's not enough just to avoid the rubble problem. There are implicit assumptions about level size throughout the code. E.g. Portal will infinite loop in the 1-room scenario.

This really needs some in-depth discussion. Even the occasional 4-room levels mean I will probably have to give up on playing with disconnected stairs. It is a huge deal. At least until all balance issues are worked out, it should probably be a challenge level difficulty option [i.e. birth option like ironman] to have this random-sized level generation.

[d_m]

I toned it down a bit and also fixed that loop. Based on the change, it tries to create at least 25 rooms in at least 1/4 of the total dungeon size (50% x 50%) so I'm pretty sure it should work better than the last version.

This was a feature that Andi had on a list of plans for 3.1.2. It would be great to get input on it but it seemed like a good idea to get something checked in to get some testing.

I'm currently working on splitting the assumptions about all levels being DUNGEON_WID by DUNGEON_HGT--once that is done I think it will be easier to guarantee that the various loops/spells work properly.

[PowerDiver]

I toned it down a bit and also fixed that loop. Based on the change, it tries to create at least 25 rooms in at least 1/4 of the total dungeon size (50% x 50%) so I'm pretty sure it should work better than the last version.

I noticed some stuff while I was debugging. There is a clear error where number of rooms is multiplied by a percentage but not divided by 100. Then that number is used as a number of attempts, not a number of rooms. Adjust * 3 / 100 would be more than enough tries.

Is it possible that a greater vault could be the first room, placed in a way so that no other room could also be placed in the 50% x 50% [or even larger] area? It seems possible to me. I wonder what would happen if you descend to a level which is entirely composed of 1 greater vault. What will happen if you phase? If I understand your scheme, this is sure to happen to someone eventually.

The whole generation scheme seems backwards to me. It would make more sense to me to generate a distribution on the rooms first and then see how much space they use, instead of limiting the space and then seeing what happens.

[d_m]

I noticed some stuff while I was debugging. There is a clear error where number of rooms is multiplied by a percentage but not divided by 100. Then that number is used as a number of attempts, not a number of rooms. Adjust * 3 / 100 would be more than enough tries.

That fix was included in the other fix.

Is it possible that a greater vault could be the first room, placed in a way so that no other room could also be placed in the 50% x 50% [or even larger] area? It seems possible to me. I wonder what would happen if you descend to a level which is entirely composed of 1 greater vault. What will happen if you phase? If I understand your scheme, this is sure to happen to someone eventually.

From what I can tell, there is no vault that makes it impossible to place another room in 50% x 50% (that is height 33, width 99). "Mazer" would use up all the available height but still leave around 2/3 of the width open. "The reward is worth it" would leave about 40% of the width free as well as about 2/3 of the height.

I do agree that the random walk inside the bounds approach of generate.c isn't great. Initially I used a strategy to reduce the number of rooms but that tended to create large sparse levels which had very different properties.

Believe it or not, I'm actually more nervous about making deeper changes due to the inherent differences in monster placement, item placement, etc. That's my next plan but I thought it would be worth trying this out.

[PowerDiver]

From what I can tell, there is no vault that makes it impossible to place another room in 50% x 50% (that is height 33, width 99). "Mazer" would use up all the available height but still leave around 2/3 of the width open. "The reward is worth it" would leave about 40% of the width free as well as about 2/3 of the height.

You may be right, but I am not convinced. The tricky part is the way spaces for the rooms are marked. As I read the code, for blocking purposes the dungeon is 6x18. Half by half of that is 3x9. If the minimum sized room blocks 1x3 [as I think it does in my current confused state], then a vault of size greater than 2.01x3.01 [where 1 unit is about 11 square lengths] that was perfectly centered would block any other rooms. Now everything is integers, and I'm sure I do not understand centering or rounding or anything else, but even 60% width free from a half width map may not be enough.

Or I could just be completely confused. That's always a strong possibility.

We need to figure out what are the requirements to easily *guarantee* enough rooms, and write an init function that asserts checks on the room structures for everything that is needed. I suppose we could add a test for #rooms and regenerate if some condition is not met, but solving the problems created by one while(TRUE) loop by adding another while(TRUE) loop seems counterproductive. OTOH it does seem easy. The temptation may be irresistable.

[d_m]

I'm pretty sure block-allocation takes into account the most size that room could take up. So in the 3x9 example, the biggest vault you'll get is a lesser vault (whose max block size is 2x3) since the greater vault requires at least 4x6. Since it keeps trying to build a room down to the smallest kind, it should always try a 1x3 at the end. If the dungeon were 4x12 (the smallest size with height 4) then the greater vault could fit, but that would still leave a 3x4 region on each side of it.

Of course, if it picks "bad" block coords to try for each of the rooms it tries to build, you could end up with only one room. This was possible in the original code and is still the modified code, although obviously the smaller the level the more likely this is (since there are fewer block coords to try). It still seems very unlikely. One fix would be to keep track of which blocks have been tried, and not let the room creation routine exit until it has created N rooms or tried every block (thus guaranteeing N rooms).

I could also imagine an assertion like you suggest that restarts dungeon creation if it fails to meet some basic criteria. Obviously this code could theoretically loop infinitely if one got really unlucky, for some large value of really.

[Atarlost]

Why not look at the ToME dungeon generation code. It can construct dungeon levels one room without difficulty. It must either have some failsafe code to avoid endless loops on small levels or use a different algorith that produces superficialy similar dungeons at least for some room settings.

[d_m]

Why not look at the ToME dungeon generation code. It can construct dungeon levels one room without difficulty. It must either have some failsafe code to avoid endless loops on small levels or use a different algorith that produces superficialy similar dungeons at least for some room settings.

I think the concern isn't that the current code can't produce one room dungeons, but rather that the rest of the Angband code assumes that there will be N rooms (where N is probably at least 4). It's easy to make the generation code create only one room if that's what is desired.

[Atarlost]

I thought the problem was the corridor generation looping when there was only one room. I guess I misread something.

[PowerDiver]

I thought the problem was the corridor generation looping when there was only one room. I guess I misread something.

That's the infinite loop problem for generation. There are other infinite loops for things like Portal [failed my test after I fixed the rubble bug] and who knows what else.

What if all open space is inside vaults, because the level is just 1 vault? Aren't you guaranteed not to start in a vault? Isn't phase guaranteed to take you out? Who knows what would happen.

Also, tiny levels make telSelf and telOther not be escapes. That's a fundamental change to how the game is played. IMO this deserves more discussion than symmetric LOS or item generation.

I continue my 1642 game, and have survived a couple small levels just through luck. I guess I should post a dump.

[takkaria]

The dungeon used to be variably-sized; Ben took it out when he refactored the code. I don't think it's a massive fundamental game change.