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]

Originally Posted by 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.

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

[PowerDiver]

Originally Posted by takkaria

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]

Originally Posted by d_m

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]

Originally Posted by 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.

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]

Originally Posted by PowerDiver

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.

Originally Posted by PowerDiver

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]

Originally Posted by d_m

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.