Pyrel dungeon generation

[half]

It would be somewhat expensive to calculate effects of sound propagation through different materials.

Actually, it is very easy and relatively cheap. If your base code already has the monster flow code, you just add a new flow which represents noise. In Sil, this is just like the normal flow for monsters that can open doors, but it adds and extra +5 points of distance when going through a closed door. Making it go through granite and adding +10 squares of distance each time (or whatever) should just be a few lines of code.

I personally didn't see any advantage of having sound go through solid rock, but the move to having it use the base flow code was a big boost to enjoyable stealth gameplay, and having closed doors help is also really neat. If you also give a stealth penalty when in LOS, you have suddenly got a decent stealth system for very little work.

[fizzix]

I figure I'd post a high level overview of what I've done in pyrel, and maybe get some feedback about some difficulties with dungeon connection I've run into.

Right now the game keeps the following info during generation
a set of all the room centers that need to be connected
a set of all the junctions (for door placement)
some general information about the dungeon (width, height)
a grid that contains some information for each grid cell. the information is
- the priority of the cell
- whether or not its a room
- whether or not its a tunnel
- whether or not its "pierceable"

When attempting to place a feature, the game checks the priority rating of the cells around it to see if it can fit. If the feature you're placing is higher priority it will overwrite what's already there. I've described this before, and I'm sticking with this design as I think it will work.

Pierceable cells is used to describe wall cells that a tunnel can overwrite regardless of priority. It's used to specify what places are entrances, and to keep track of what's intersecting what (to place junctions and doors).

Right now, I'm working on connection as how well I can connect all the rooms will dictate how general a structure we can have. I'll list some dungeon rooms that are possible from easiest to deal with to hardest.

1 rectangular rooms surrounded by pierceable walls
2 arbitrarily shaped rooms surrounded by pierceable walls
3 rectangular obstacles
4 unenterable obstacles
5 rectangular rooms with only specific entrance locations
6 convex rooms with only specific entrance locations
7 arbitrarily shaped rooms with only specific entrance locations.

V can handle up to 3 only. It can sort of handle 5 but it doesn't do it very well at all. Right now, I have an algorithm that can deal up to 6. However, there's a caveat. Things get difficult if you have a bunch of randomly placed rooms all with only one or two entrance locations. I can probably handle it, but the tunnels will take a while to find them.

The problem with 7 is figuring out when you can stop following the perimeter of an obstacle and peel off in the target direction. Right now I just check if the target is in the opposite direction from the obstacle. If it's not, continue following. This fails if the obstacle is convex. I don't have any plans for supporting 7 anytime soon, but I'll start thinking about it later, after the rest of the connection algorithm works.

Is support for 7 necessary? What about dungeons filled solely with templated rooms with few entrance locations?

[Patashu]

The problem with 7 is figuring out when you can stop following the perimeter of an obstacle and peel off in the target direction. Right now I just check if the target is in the opposite direction from the obstacle. If it's not, continue following. This fails if the obstacle is convex. I don't have any plans for supporting 7 anytime soon, but I'll start thinking about it later, after the rest of the connection algorithm works.

Is support for 7 necessary? What about dungeons filled solely with templated rooms with few entrance locations?

I assume you mean 'this fails if the obstacle is concave'? e.g. a tunneler is running around a jigsaw piece shaped room's perimeter trying to get to the target like so:

     /---\
  ###|###|
  # #V# #\--<--<--<
### ### ###
T         #
### ### ###
  # # # #
  ### ###

Since it is following the left wall, now behind it relative to the target, it would like to peel off and beeline but cannot as more walls are in the way.

One way that comes to mind:
-If I'd like to peel off
-Run an algorithm like A* that tries to go towards the target, and gives up if it has to stray substantially (e.g. more than a few tiles) off the best possible course
-If that works, peel off, if it doesn't, continue following and don't try to peel off again for X number of tiles

Lots of potential for optimization there of course

[Derakon]

I think what fizzix is talking about is this situation (start at A, want to get to B):

     ##########
     #        #
A---+# ###### #     
    |# #    # #
    |###    # #
    +---*--?# #    B
            # #
            ###

At *, the algorithm discovers that it can break away from following the wall to head straight to B, but then it encounters another obstacle -- which is secretly the obstacle it encountered before; it just doesn't know that. Ideally we'd just start following the wall again in the same direction (counterclockwise in this case), but you need some way to know what room a given wall is bordering to find that out. Which of course isn't impossible, but it does make the code more complex.

[fizzix]

You're both close. The situation that currently will break is the following.

...................
.B.#############...
...#############...
...##>.-.-.-.v##...
...##|.......*##...
...##^<-A.....##...
...##.........##...
...##..............
...##..............
..####.............
..more obstacles...

At * the code checks and finds that B is in an appropriate exit direction, so it leaves the obstacle, only to run into the opposite side and the tunnel it already created. In the current code this would create a repeated failure and will cause dungeon generation to fail.

Basically we need to distinguish the situation at * from the following case where peeling off is the desired behavior.

...................
.B.##.........##...
...##.........##...
...##.....A>-v##...
...##........*##...
...##.........##...
...##.........##...
...##..............
...##..............

There are a couple ways around this.

1) If you always choose a different target and a different starting point, it may be that you make enough other tunnels that already reach the desired target. Or, that you find a better path. Arguably, we should be doing this anyway. It still will not solve a good sized fraction of the cases.

2) The only foolproof way to path to B is to construct a flow map that finds the shortest path to B and then head there with some optional deviations thrown in. This is costly and slow and it's harder to recreate the "natural" meandering tunnels.

My current plan is to install 1 and see how far it gets us to solving the problems. Then if I find that the connection algorithm fails on a lot of dungeon archetypes we can code up 2 and have it be an alternate connection option that gets selected in the archetype.

[Magnate]

My current plan is to install 1 and see how far it gets us to solving the problems. Then if I find that the connection algorithm fails on a lot of dungeon archetypes we can code up 2 and have it be an alternate connection option that gets selected in the archetype.

Would it need selection at archetype stage? If you wanted to use #1 as much as possible (if it leads to more natural-looking dungeons), could you invoke #2 after a certain number of tries, or something?

[fizzix]

Would it need selection at archetype stage? If you wanted to use #1 as much as possible (if it leads to more natural-looking dungeons), could you invoke #2 after a certain number of tries, or something?

That's certainly a possibility, but as usual there's a catch. Let N be the number of areas that need to be connected. then N-1 is the minimum number of contiguous tunnels that need to be created. You'll probably want some slop to account for tunnel attempts that turn around and connect on themselves. So let's say the number of tries looks something like 3(N - 1)/2. Typical numbers for N are probably between 20 and 30, so we're talking about 30-40 attempts total.

Roughly 10-15 attempts are likely to wind up stuck (after all the good tunnels are connected, it will keep on trying to connect up that last point and running into problems). This means taking 10-15 tunnels from the same few starting points, and taking slightly different paths to the target and losing each time. The result is a gigantic hollow section of the tunnel near the obstacle, which completely defeats the purpose of having an arbitrarily shaped obstacle in the first places (just inscribe it in a hollow rectangle first!).

edit: It occurs to me now that we could put off actually making the tunnel until the path is completed. Saving everything in a set of tunnel points (and tunnel wall points) and only clearing them out after a completed tunnel is made.

[Magnate]

edit: It occurs to me now that we could put off actually making the tunnel until the path is completed. Saving everything in a set of tunnel points (and tunnel wall points) and only clearing them out after a completed tunnel is made.

I'm so glad you said that. I hadn't understood the problem at all until I realised you were talking about implementing unproven tunnels!

(That said, I think genuine dead-ends would be a nice feature. In V you just KNOW there's a secret door.)

[fizzix]

I'm so glad you said that. I hadn't understood the problem at all until I realised you were talking about implementing unproven tunnels!

(That said, I think genuine dead-ends would be a nice feature. In V you just KNOW there's a secret door.)

V has genuine dead ends. The reason that V corridors are predictable is:
* V distinguishes between tunnel junctions and room junctions.
* Something like 95% of tunnel junction squares have a door.
* Tunnel junctions therefore are almost always surrounded by 3 doors (and sometimes 4).

Some solutions are pretty easy and can be implemented in V even without any difficulty. Here are some suggestions.
* Place some doors in corridors
* Reduce door placement in tunnel junctions to 60 or less.
* Allow doors to appear before (after) tunnel turns. This one is the hardest to implement.


The reason it's not worth worrying about this in V is because of the prevalence of detect doors which makes any interesting features irrelevant.

[buzzkill]

Completely off topic of the current discussion, just dungeon generation in general. What if you drew a over zealous network of tunnels to begin with, and then tried to place rooms (some randomly, some centered on intersections), and then cleaned up what would be considered excessive tunnels.

[Derakon]

Completely off topic of the current discussion, just dungeon generation in general. What if you drew a over zealous network of tunnels to begin with, and then tried to place rooms (some randomly, some centered on intersections), and then cleaned up what would be considered excessive tunnels.

That could certainly work, but I think it'd end up feeling artificial. IMO most tunnels should go somewhere. You also would probably end up with lots of tunnels that "enter" and "exit" a room at the same X or Y coordinate, e.g.

   ######
####....####
............
####....####
   #....#   
   #....#   
   #....#   
   ######

[fizzix]

Completely off topic of the current discussion, just dungeon generation in general. What if you drew a over zealous network of tunnels to begin with, and then tried to place rooms (some randomly, some centered on intersections), and then cleaned up what would be considered excessive tunnels.

Actually pyrel generation as I plan to design it will allow for just that. The main motivation is allowing rooms to be places on top of a cavern level. Basically you can start generation by making a network of tunnels that start and end at random points. Then you can place rooms (possibly on the random points, but anywhere else in the tunnel network will work.) Then, if you want, you can call the connection algorithm which will exit immediately since all rooms are connected.

Placing special rooms is harder because they can cause discontinuities in the tunnel structure.

Whether the dungeon looks strange as Derakon suggests I think is wholly dependent on the parameters you choose for both rooms and tunnels. For super-twisty tunnels or large rooms, it should look exactly the same.

[Patashu]

Well, one thing you could do is make the tunnel planner backtracking. E.g.
1) in the case where you decide to peel off,
2) and on the way you run into an obstacle that circumnavigating isn't immediately obvious, 2) And on the way, circumnavigating another obstacle, you enter a tile that you've already pathed, thus potentially being in an infinite loop,
3) shrug and say 'well, I won't do that then,' jump back to before you peeled off and set a 'don't peel out for this many steps' counter to e.g. 3 or 5.

And that way you only generate the first tunnel that doesn't run into itself.

[Derakon]

You're both close. The situation that currently will break is the following.

...................
.B.#############...
...#############...
...##>.-.-.-.v##...
...##|.......*##...
...##^<-A.....##...
...##.........##...
...##..............
...##..............
..####.............
..more obstacles...

At * the code checks and finds that B is in an appropriate exit direction, so it leaves the obstacle, only to run into the opposite side and the tunnel it already created. In the current code this would create a repeated failure and will cause dungeon generation to fail.

It just occurred to me -- you can readily detect this situation by examining the tiles on a line between * and B. If any of those tiles are already a part of the tunnel, then breaking away from the wall will not be profitable.

Sorry if you've already gotten past this problem; I haven't managed to follow most of the IRC conversations you've been having with d_m about all this.

[Mikko Lehtinen]

Actually pyrel generation as I plan to design it will allow for just that. The main motivation is allowing rooms to be places on top of a cavern level. Basically you can start generation by making a network of tunnels that start and end at random points. Then you can place rooms (possibly on the random points, but anywhere else in the tunnel network will work.)

Cool! Halls of Mist does something like this with tiny treasure rooms and shortcut tunnels. These are placed after the rest of the level has been generated. My motivation was to allow locked doors that are hard to open, while still making sure that the player can reach all the staircases. Only skilled or lucky characters can loot locked and teleport-proof treasure rooms or to use locked shortcut tunnels for escaping.

You can lock the door after you, and monsters will have real trouble to break through. Locking monsters in treasure rooms and Phase Dooring away is also an option.