Language: 
To browser these website, it's necessary to store cookies on your computer.
The cookies contain no personal information, they are required for program control.
  the storage of cookies while browsing this website, on Login and Register.

Author Topic:  Procedurally-generated dungeons  (Read 12511 times)

0 Members and 1 Guest are viewing this topic.

_people_

« on: 23, September 2020, 14:42:51 »
I've long desired for procedurally-generated dungeons in Daimonin. I know there was at one point some code in the SVN which would enable such a feature but I think it has been removed for quite a long time.

I've made a basic proof of concept over the last few days which IMO shows a lot of potential when combined with my future plans. As I work on it, a simulator is run which provides ample debug info such that I can ensure that no maps are generated that will be impassible or potentially buggy.

Please let me know any thoughts you guys have on the matter, or if you have any questions about implementation details. :)

There are a few big drawbacks to procedurally/randomly-generated dungeons which I hope to address:
  • Heavy stress on server resources
  • Lore
  • It's all just the same map but rearranged
  • Technical constraints

1. Server stress

My plan to get around the server stress is simple. Rather than generating maps when needed, pre-generate a buffer of a handful of dungeons (for argument's sake we'll pick N=5 variations of each dungeon). And do this by an external script which is controlled by the reboot bash scripts.

To create a new RDG, create a .lua script in a specific folder of daiserv/maps. At server start, an external Lua program will use that Lua script, which determines generation parameters, to create N copies of that dungeon. It will then save them in /maps/rdg/<specific_dungeon_name>/<seed>/<mapname_xxyy>. For each specific_dungeon_name it will add a global DataStore entry listing (a) what seeds are available and (b) whether or not each seed of each dungeon has been used. <seed> will just be a unique Unix time (from os.time())

So now we have:
(a) N variations of mapset "caverns_of_evil"
(b) For each variation, a DataStore flag denoting which have already been used.

The RDG program will detect that 1 copy has been used and will subsequently generate 1 more variation of that mapset.

2. Lore

So player talks to Bob (hypothetical NPC name) and Bob offers pl information about the "shattered planes". Based on past discussion of the SP the intention is for maps which do not belong elsewhere to be standalone maps in the SP. I think it still makes sense to have random dungeons to be in the SP as well.

Bob should inform player that while player is in this instance, Bob will "keep a magical lock" on pl's location so he can pull pl back if he starts to lose that lock (player logs out, dies, etc.). But Bob will no longer be able to TP player to that instance (instance here having no correlation with "instanced maps" - these maps will be the default multiplayer maps).

We can either use pl:GetGroup() (or whatever it actually is) or use a specific tile and iterate through player objects on that tile to teleport them to the dungeon. As stated before, as any individual player dies or logs out, they are no longer able to access the dungeon.

3. It's all just the same map but rearranged

Based on my initial experimentation, the layout can be different enough that there will always be a decent amount of exploration to be done.

I'd like to have a unique-ish boss at the end of each RDG. These will likely have to be mostly static, but with small deviations. In the Halloween event maps, the Tarrasque has Lua scripts which give him extra abilities - healing, summoning minions, becoming temporarily invincible to certain attack types, etc. If I can come up with enough interesting "special abilities" and static mobs to use those abilities, I think I can make the boss fight fun enough.

As for rewards/loot for completing these dungeons... That's pretty difficult to make balanced items with random stats. Again it will likely have to be mostly-static items but with some variations, at least for HLP's. For LLP's or MLP's, boss rewards can probably just be a "pretty good" piece of equipment slightly better than what comes in a standard treasurelist.

4. Technical constraints

The server will have minimal excess load on it, because all of this is offloaded to a separate program running on a different thread. Obviously some of the server machine's resources will be allocated, but the gameserver is lightweight enough that I don't anticipate any issues here.

Some ground-rules must be established to prevent any unexpected behaviour. Anything I can think of is covered by aforementioned constraints preventing the player from ever attempting to load a map which no longer exists. This will require some tweaks to event_login.lua to remove the player from any RDG they may be on. I think the best way to do this is to have a table of "hooks" which is executed during event_logout.lua, and when the pl is teleported to a map add a hook to that table to teleport them back to Bob.
-- _people_ :)

_people_

« Reply #1 on: 23, September 2020, 14:46:27 »
I've been talking with Yoll a bit about this and he PM'ed me the following as I was typing this:

Quote
well I think its not just the randomness of the dungeon, but keys can be drops from random generated spawn mobs, so it makes difficult to put all keys together. At the end a boss can drop as well a key to a treasure room, where one can pick from different boxes, all boxes have one piece of random set of armour, or only one piece of the armour is found within the boxes but only one box can box opened. As well an instance can be created within the dungeon, so there are 2 parts of a story to be fulfilled, in this case the first part can require keys, those keys are found by random spawn mob in a random generated dungeon, thus making it necessary to team up with a partner to succeed. I think if the rewards are such that allow the unique potential to enter a new realm of the game, then you can lift the regulations for drop frequency of the other armours, if there is a problem with  people camping the grounds maybe such armours and weapons can be set to degrade over time and vanish. Also I feel the ultimate lvl of achievement should be increased so there is more of a progressive situation within dungeons, and also the fact that books should be specific on guiding players to locations, even a random book to go dig a unique treasure somewhere... Easter eggs a always fun to hide and to seek. Remember that there could be a new gate that after completing the entire game, highest lvl and having all quests finished, then it could be plugged to a net hack engine for those players willing to sacrifice most for the dare of entering such portal... that can bring a little game into a different dimension...

This has given me a bit to think about as I work on this project.
-- _people_ :)

smacky

« Reply #2 on: 23, September 2020, 15:33:36 »
Well, yes. The old random maps code (from 1990s CF) was borked -- IDR how -- and remove ~B4 (2007ish). I think Gecko did some work in Ruby for some reason and aomehow TPK generated 10(0)(0)s of maps and then spent months working on them. IDR seeing anything come from either.

BTW bosses are a part of my entity concept, so just assume it'll happen.

Shroud

« Reply #3 on: 23, September 2020, 19:11:34 »
Well if I was trying to implement it from scratch I think I would build it around small squares and then have connection points so they kind of fit together like 3d lego blocks. I would suggest all "blocks" connect at same points and then blocks can connect in 1 to 4 directions. Maybe best way to do it is to get the layout first in terms of blocks and then for each block randomly load a corresponding one that has connections in right amount of directions. A boss room at the end can be specially made if required.

I would assume decor and mobs could be set to random so that floors, walls etc can follow themes as well as mobs. Maybe easiest is to have default schemes for decor so that for example in a swamp an impassible obstacle is a marsh, in grasslands it's a river, in a volcano it is lava etc

As far as drops go it's a balancing issue with usual problem that if drops aren't good enough no one does them and if it's too good then no one does anything else. If you want an interesting idea you could put a time limit on it saying planar gateway is unstable so Bob can only hold the portal open for 1 hour and then he yanks you back. Then you can have it so that drops get better deeper into the dungeon so idea is that player is under pressure to take risks to get deeper into the dungeon faster. I would also suggest that Bob could charge a hefty fee to open a portal. Potentially when he opens the portal you could choose the difficulty with drops increasing proportionately. Another thought is that cost rises proportionally to drops. Just to give an example you could pay Bob 10 silver to get to a goblin's lair where you'll be able to got a goblin's loincloth or you might pay 1 mithril to get to a dragon's lair and try to get all it's hoarded over it's lifetime.

Another suggestion could be a bounty system where Bob gives a quest to hunt as many mobs as possible and/or find a certain quest item. When completed you return to Bob and he gives you a certain amount of quest reward points. These points can then be traded for items desired. Note that a player could trade several missions worth of points for a really good item or get several items from a mission's worth of points depending on how quality vs quantity.
Doesn't matter, you'd die anyway. ;D Shroud's a hacker. After many hours of deep thought I have came to that conclusion.

Yoll

« Reply #4 on: 23, September 2020, 20:46:17 »
Shroud .- "drops go it's a balancing issue with usual problem that if drops aren't good enough no one does them and if it's too good then no one does anything else". such is true, yet my thought was inclined towards "keys" instead of loot, so if you need keys just to enter a different realm or an instance, then the reward is something desirable, but just to enter such dungeon would require from a player to have finished the entire game already, and entering such instance would risk all the player's achievements, so the problem of balance in use/value of&for all treasure is cancelled, allowing the game to lift the drop rate restriction there is for so many items at the moment. Economically speaking, I would consider deregulating those drops, thinking that instead of balancing in favour of holders of valuable items for a market,  there are ways to increase value by adding to the players experience, such experience in the end translates into greater curiosity to reach such instance, so there is a natural need to camp for all treasure, finish all quests and reach highest lvl, since such instance would require all this components, based on experience, difficulty and having proper equips and team to succeed.
« Last Edit: 23, September 2020, 20:49:42 by Yoll »

_people_

« Reply #5 on: 23, September 2020, 22:08:47 »
Well if I was trying to implement it from scratch I think I would build it around small squares and then have connection points so they kind of fit together like 3d lego blocks. I would suggest all "blocks" connect at same points and then blocks can connect in 1 to 4 directions. Maybe best way to do it is to get the layout first in terms of blocks and then for each block randomly load a corresponding one that has connections in right amount of directions. A boss room at the end can be specially made if required.

Yep, turns out there are some cool algorithms that can help us there.
(click to show/hide)

In the above image, we start by generating N rectangular "rooms" with varying width/height. That's the blue rectangles.
Next we plot a pre-defined shape around the center of that room. Apply Perlin noise to get irregular shapes. That will determine the walls of the room (seen in red).

I've used Delaunay triangulation (green lines) and a minimum spanning tree algorithm (cyan lines) to establish the links between rooms. I will later add a probability to create loops between nodes and some more Perlin noise to make the corridors twisty and irregular.

The green circles are supposed to be the points at which a room connects to another but the math isn't playing nicely.

I'll also have to figure out or look up an algorithm to determine the 2 furthest nodes from each other to define as the starting room and the end/boss room.

I would assume decor and mobs could be set to random so that floors, walls etc can follow themes as well as mobs. Maybe easiest is to have default schemes for decor so that for example in a swamp an impassible obstacle is a marsh, in grasslands it's a river, in a volcano it is lava etc

Yep, each dungeon has a definition file which determines which walls to use, what decorations make sense to use here (no ice sculptures in as volcano), etc. The definition file also specifies randomization parameters such as room shape (castles should have mostly perfectly rectangular rooms, and will either have straight/90-degree corridors or no corridors (just doors connecting 2 rooms).

As far as drops go it's a balancing issue with usual problem that if drops aren't good enough no one does them and if it's too good then no one does anything else. If you want an interesting idea you could put a time limit on it saying planar gateway is unstable so Bob can only hold the portal open for 1 hour and then he yanks you back. Then you can have it so that drops get better deeper into the dungeon so idea is that player is under pressure to take risks to get deeper into the dungeon faster.

I definitely agree, good point.

I would also suggest that Bob could charge a hefty fee to open a portal. Potentially when he opens the portal you could choose the difficulty with drops increasing proportionately. Another thought is that cost rises proportionally to drops. Just to give an example you could pay Bob 10 silver to get to a goblin's lair where you'll be able to got a goblin's loincloth or you might pay 1 mithril to get to a dragon's lair and try to get all it's hoarded over it's lifetime.

Shroud .- "drops go it's a balancing issue with usual problem that if drops aren't good enough no one does them and if it's too good then no one does anything else". such is true, yet my thought was inclined towards "keys" instead of loot, so if you need keys just to enter a different realm or an instance, then the reward is something desirable, but just to enter such dungeon would require from a player to have finished the entire game already, and entering such instance would risk all the player's achievements, so the problem of balance in use/value of&for all treasure is cancelled, allowing the game to lift the drop rate restriction there is for so many items at the moment. Economically speaking, I would consider deregulating those drops, thinking that instead of balancing in favour of holders of valuable items for a market,  there are ways to increase value by adding to the players experience, such experience in the end translates into greater curiosity to reach such instance, so there is a natural need to camp for all treasure, finish all quests and reach highest lvl, since such instance would require all this components, based on experience, difficulty and having proper equips and team to succeed.

I'm not quite sure what exactly you're wanting to be implemented Yoll. Are you saying that entry into a RDG instance should be free, but that the "value" of an expedition should come from the difficulty itself? Something like: boss drops a "key" to a more difficult instance as well as a decent item, and then the player runs through the more difficult instance and gets a slightly better prize at the end as well as another key, etc.?
-- _people_ :)

smacky

« Reply #6 on: 23, September 2020, 23:12:19 »
Will irregular shaped rooms and funny angled passages work? Roguelikes mostly stick to rectangular rooms and nesw passages [with the occasional prefab vault] 

 We're not that diff [esp with non-smooth move] -- syill a coarse grid system.

_people_

« Reply #7 on: 23, September 2020, 23:39:02 »
Yep, irregularly shaped rooms will work. Currently I have only definitions for circular, ellipsoid, and rectangular rooms. Circular/ellipsoid rooms have noise applied to make the edges either jagged, or if the noise is weighted very low then it will just be "slightly not a perfect circle".

For irregular paths, I think the plan is to add extra random nodes outside of any room which can be connected to in between rooms. I think if I can get the right weight to these extra nodes, we can even have something as irregular as an S-shaped corridor (top of upper room connects to the bottom of lower). I'll try to get a proof of concept today or tomorrow.
-- _people_ :)

Yoll

« Reply #8 on: 23, September 2020, 23:56:04 »
I start from questioning the economic balance, because I understand now drop rates of certain items is reduced to sustain market value, so I made a comment, that I rather have an increase to player's experience value instead of regulating drop rates which caps the market instead. But then the question is how; so I said make a new instance, which is random generated dungeon and as well random mob spawn, and make the reward of such instance the entrance to a new realm, which could be then plugged into a Nethack like engine. So for the new instance, make it such that it requires from a player to have achieved all of the game's goals, Quests, Highest lvl, Full set of higher equipment, and a Team, all this in order to have a chance to finish the instance's quest, included in the rewards whichever they are, is to be able to pass to that new realm, passing that quest and entering such plug-in or bridge, would then risk all of the players achievements if he was to fall or gain the highest wealth and riches. I consider that such would end the need to regulate drop rates, increase the game play need to camp and do all quests and achieve highest lvl, because there would be a great need for those those items; but as well there would be a place where constantly players would be loosing them, thus having a free market would make sense, and more and better drops from bosses and random mobs through out the game could be implemented, the game would benefit as well, since opening a gateway to an entire Nethack base engine would double the world, like an expansion. I don't believe adapting that code would be so complex, Nethack, Zangband and others have entirely opensource engines. (its just an opinion).

Shroud

« Reply #9 on: 24, September 2020, 18:38:59 »
Looking at the algorithm would I be correct in saying that longest path would generally be a corner to the opposite corner. In addition while there are a lot of rooms optimal path to boss room assuming corner to corner model is around 5 rooms. In addition if you start in a corner where you can only go right or up then it's logical to assume boss room is in top right corner so it shouldn't be too hard to reach quickly. On the other hand if you start in the middle it is a lot harder to navigate and there is possibility you could be going in the wrong direction. As for a general principle for an algorithm I would suggest generating the rectangles and then making the centre one the start point. Then I would suggest going outwards in a spiral or increasingly large circles and last rectangle it touches becomes the boss room. You can do a 90, 180 or 270 degree rotation if algorithm produces a bias in a certain direction to truly randomise it. While I hadn't considered it before it's also possible to have a tower style map with staircases linking each floor so it could be large horizontally and vertically.

I think Yoll's suggestion was that instead of getting a reward from completing a dungeon you wager your previous haul to get a potentially bigger haul in the next dungeon. I'll note that I'm a bit wary of the word key since I'm carrying several kilograms of keys. Using game theory poker equivalent would be double or nothing.
Doesn't matter, you'd die anyway. ;D Shroud's a hacker. After many hours of deep thought I have came to that conclusion.

Yoll

« Reply #10 on: 24, September 2020, 19:59:20 »
I meant flag or a token...(key), something that would allow entrance into an expansion of the game's world. Such instance can be huge and I believe that the Nethack engine has an algorithm already, there are a few engines for nethack which translate the simple code into dimensional graphics, so I think such can be adapted here. being that nethack is quite large instance with many different quests and some engines have infinite levels... it could be mod into daimonim

_people_

« Reply #11 on: 25, September 2020, 13:36:59 »
@Yoll: Is Shroud's interpretation of your suggestion correct? If so, I'm not sure if there's a pragmatic way to delete any items (between player's apartment and inventory) which were generated by a RGD. Even if we were to, say, add an additional flag to items correlating it with RGD, what's stopping the player from dropping it in the wilderness while he runs a dungeon and reclaiming it later (after he dies or completes the dungeon)?

For the developer types, I've just thought of a concern that I hadn't addressed yet. What happens if the server crashes while a player is in a random dungeon? The dungeon won't exist on server restart so they'll be placed in the emergency map (which should in theory be benign, but still undesirable).

I suppose we could add event_login.lua and supporting server code (which may be useful in the future - for example, if a player has mail in the post office they could be notified) but I don't know if I like the idea of executing event_login.lua prior to placing them on a map.

Made a bit of progress on connecting rooms:

(click to show/hide)

As previously, blue represents floor, red represents wall, green represents corridors which will eventually be expanded to contain floors and walls of their own. Every pixel on the image represents a tile.

I've added extra nodes outside of rooms which create some irregularity in corridors. My next step will be to add some Perlin noise to corridors which will allow them to bend smoothly rather than being at sharp angles.
« Last Edit: 25, September 2020, 13:45:20 by _people_ »
-- _people_ :)

Yoll

« Reply #12 on: 25, September 2020, 16:20:58 »
there are several things to take into account. if you enter an instance which is random generated, there are two options, one is that only the stage you are in gets recorded, and thus if you are to step back you either step back into the world map or you walk back "B=)a"(a=Ba) into a random generated stage until the number of stages takes you out of the instance or it is that going back any stage takes you out of the instance. Second option is a progression, where the later stage has not been recorded and the previous stage has {"B=)a"="A=)b)"}="b=B", thus you either step back into the world map or you go back into a recorded stage of the instance. Delete or not of items within the map is not an issue since either the instance itself is not recorded and if it is recorded then {as=)"if"} where "if" can hold an array of dims as long as the instance is active. Stepping out of the instance (or in case of a crash) imports no items from environment, but specific values, which once the character returns to Bob from the instance, Bob rewards accordingly. This means that if there is a crash, the character will go back in any case to Bob, and no value of achievement will be valid, but one can begin the process again, just as in nethack, when one dies "value=reset", or the reward from Bob is based on recorded value. ( is this what you mean?) ...btw, instead of passages, it can be portals that connect rooms; you solve a puzzle, you kill a boss, portal activates.
« Last Edit: 25, September 2020, 16:27:02 by Yoll »

smacky

« Reply #13 on: 25, September 2020, 17:06:08 »
@Yoll: Is Shroud's interpretation of your suggestion correct? If so, I'm not sure if there's a pragmatic way to delete any items (between player's apartment and inventory) which were generated by a RGD. Even if we were to, say, add an additional flag to items correlating it with RGD, what's stopping the player from dropping it in the wilderness while he runs a dungeon and reclaiming it later (after he dies or completes the dungeon)?

For the developer types, I've just thought of a concern that I hadn't addressed yet. What happens if the server crashes while a player is in a random dungeon? The dungeon won't exist on server restart so they'll be placed in the emergency map (which should in theory be benign, but still undesirable).

i think both issues are solvablewith a small extn to egoitems. Im coimcidentally workimg on something not 1m miles away right now [but its a secret ;)].

Quote

I suppose we could add event_login.lua and supporting server code (which may be useful in the future - for example, if a player has mail in the post office they could be notified) but I don't know if I like the idea of executing event_login.lua prior to placing them on a map.

stresms/PA.

Quote
Made a bit of progress on connecting rooms:


Minor point but imo at 1pix/msp this mapset is way too big.

Related: the non-play area:play area and passage:room ratios are too high.  Also can u add to the algo a chance to merge 2+ nearby rooms (not nec completely so we get topographically interesting shapes.

Shroud

« Reply #14 on: 25, September 2020, 18:11:24 »
Well as far as the server crash scenario could following work?

Let's say that default map is PlayerNameProcDungeon with let's say 0101 to 2525. This map would exist in same way that Panaim Redoubt has an instanced version for each player. I would suggest every square has a teleporter to the entrance of shattered plane. Now when Bob sends the player to the shattered plane the map is overwritten with a the procedurally generated dungeon with the exact same name. When it expires it reverts to default version. If there is a server crash then player's location would be saved in a location that is valid for both the default and generated map. As generated map no longer exists player would be placed in default map and then teleported to exit.

Would this be a workable solution?

Another possibility is that if the mapname has the seed used to generate it then assuming that procedural map generator uses the same seed it should be able to generate exactly the same dungeon. So if the player is on a map that doesn't currently exist it could be possible for the server to create the map as per player location. As a random number is just a finite very long list of numbers as long as you start in the same place you can reproduce the same random numbers.
Doesn't matter, you'd die anyway. ;D Shroud's a hacker. After many hours of deep thought I have came to that conclusion.

Tags:
 

Related Topics

  Subject / Started by Replies Last post
9 Replies
1260 Views
Last post 16, October 2005, 07:09:58
by Carleto
16 Replies
6032 Views
Last post 21, July 2008, 13:07:56
by grommit
0 Replies
2061 Views
Last post 21, February 2009, 05:51:25
by angry
24 Replies
1322 Views
Last post 13, February 2022, 20:46:47
by _people_
5 Replies
185 Views
Last post 02, June 2022, 14:42:22
by Shroud