Pyrel dungeon generation
Collapse
X
-
d_m suggested perlin noise. And that's probably what I'll go with. It seems to produce exactly the behavior type we want.Leave a comment:
-
It could (I think) if the kind of noise used is very patchy rather than randomly per tile. I don't know what kind of noise function would make that though, maybe picking seeds of +1/-1 cost and growing them outward randomly for some amount.That seems like it might work, as it's an improved version of what I was trying to code. We can make twistiness by creating a noise function on the granite floors with various granite walls taking higher costs to traverse them. It won't create the illogical twistiness that we currently have,Leave a comment:
-
That seems like it might work, as it's an improved version of what I was trying to code. We can make twistiness by creating a noise function on the granite floors with various granite walls taking higher costs to traverse them. It won't create the illogical twistiness that we currently have, but some of those (especially paths that leave and return) are ornaments that can be added on later.Is there any particular reason you wouldn't just use A* for all your tunnel-planning needs? Granted, it can be slow at times, but it's guaranteed to find a solution (if one exists) and by tweaking the cost function it's really quite flexible. Once I started using it in my own variants I've never encountered a feature that it couldn't handle.
Unless, of course, you want extremely twisty, totally illogical tunnels that bend back on themselves and reenter rooms... sortof like what Angband has
thanks.Last edited by fizzix; December 6, 2012, 15:22.Leave a comment:
-
Is there any particular reason you wouldn't just use A* for all your tunnel-planning needs? Granted, it can be slow at times, but it's guaranteed to find a solution (if one exists) and by tweaking the cost function it's really quite flexible. Once I started using it in my own variants I've never encountered a feature that it couldn't handle.
Unless, of course, you want extremely twisty, totally illogical tunnels that bend back on themselves and reenter rooms... sortof like what Angband has
Leave a comment:
-
That fails when you have two separate obstacles. (see the second choice). There you want to break away even though there's an obstacle in the line.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.
My current plan is to try to implement the breadth-first search as d_m described it and then use whichever works better as the main connection option and save the other as an alternate.
Mikko: I hope that stuff like this will be trivial to support in pyrel. The nice thing about the archetype + priority system is that you can add any feature you want and have a very good grasp on how often it will show up.Leave a comment:
-
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.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.)
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.Leave a comment:
-
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.You're both close. The situation that currently will break is the following.
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.Code:................... .B.#############... ...#############... ...##>.-.-.-.v##... ...##|.......*##... ...##^<-A.....##... ...##.........##... ...##.............. ...##.............. ..####............. ..more obstacles...
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.Leave a comment:
-
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.Leave a comment:
-
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.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.
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.Leave a comment:
-
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.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.Code:###### ####....#### ............ ####....#### #....# #....# #....# ######
Leave a comment:
-
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.Leave a comment:
-
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.Leave a comment:
-
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.)Leave a comment:
-
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.Last edited by fizzix; December 4, 2012, 15:23.Leave a comment:
Leave a comment: