[WGEN] The Dungeonator - A Procedural Dungeon Crawl Generator [v0.0.3 Preview Now Available!]

Discussion in 'WIP and Development Status' started by Timberjaw, Feb 26, 2011.

Thread Status:
Not open for further replies.
  1. Offline

    M1sT3rM4n

    Will be watching this thread closely!
     
  2. Offline

    Raphfrk

    Ahh, that method was specifically put in for Dynmap, so that it could read without killing the server. It is also thread safe.
    --- merged: Mar 1, 2011 10:10 PM ---
    Anyway, I added a pull that extends getBlockTypeIdAt() to 2 set methods, dunno about thread safety though.
     
  3. Offline

    Gutter

    True, that's probably why it helped me, I could just scan and change a few blocks, not the whole thing like you. How large do you want your dungeons to be anyway? You want "Dungeon World" (That'd be amazing) or just dungeons for the normal map? Why not use the existing map, surely those prefabs can be added to generated chunks?
     
  4. Offline

    Timberjaw

    Dungeon World.

    Long-term, the dungeons will end up having vertical elements as well. For now, they're on 1 level, so I could conceivably just replace a layer of 5-6 blocks in each chunk and leave the rest untouched, but it feels like a sloppy method to me (I can foresee some issues related to mob spawning in particular, and it seems like a waste of space to be storing all that unused chunk data). When the generator branch is finished, these performance issues should disappear instantly. In the meantime, I'm abstracting my generation system to give identical results, but at reduced performance.
    --- merged: Mar 2, 2011 6:42 AM ---
    What effect (if any) does that have on the cache for existing chunk instances referring to the same chunk? Won't their cache suddenly be incorrect?
     
  5. Offline

    Raphfrk

    I don't think it's really a cache exactly. It is like a block object reference store. When you access a block for the first time, a CraftBlock is created.

    This CraftBlock acts as interface to the actual block. It stores things like the x/y/z of the block for fast readback and also has references to the CraftChunk. This means that you don't need to keep looking up the chunk every time.
     
  6. Offline

    Timberjaw

    Just realized: getting the block type id at a position without hitting the block cache is useful to me even if I need to modify blocks, because then I can skip AIR blocks (currently I don't bother, because with getBlockAt() you get the cache hit regardless of whether you manipulate it).
    --- merged: Mar 2, 2011 4:09 PM ---
    Something seems to have changed with the generation/chunk load process in recent builds. I'm getting some pretty wild results.

    [​IMG]
    --- merged: Mar 2, 2011 4:14 PM ---
    Bizarrely, this appears to be related to switching from bottom-up to top-down. I have no idea why that would make a difference. Changing for(y = 0; y < 128; y++) to for(y = 127; y >= 0; y--) goes from nice flatland to apocalyptic landscape.
    --- merged: Mar 2, 2011 4:55 PM ---
    Took care of the top-down issue. Turned out to be related to some bad world.getBlockTypeIdAt coordinates.

    That seemed to take care of the item drop issue (I assume chest items are just falling below the world as it generates and eventually getting removed). Performance is better when I skip the air blocks via getBlockTypeIdAt, but it still lags significantly while generating. It can't keep up with a walking player.

    I wonder if lighting calculations are slowing it down, since lighting proceeds from top-down, and I have the bedrock layer at 0.
    --- merged: Mar 2, 2011 6:32 PM ---
    To anyone who's interested in chatting about Dungeonator progress, I've also registered #dungeonator on esper.net and will be in there any time I'm on #bukkit. Nothing really going on in there yet, but I figured I should secure the channel.
     
    M1sT3rM4n likes this.
  7. Offline

    tension69

    We'd have to call in Lara Croft to navigate that dungeon [​IMG]ROFL

    Good luck with the endeavour though[​IMG]
     
  8. Offline

    Raphfrk

    I submitted a pull request.

    This allows a plugin to override the normal chunk generation (and decoration) events.

    Decoration occurs once per chunk and it is guaranteed that the (x+1,z), (x+1,z+1) and the (x,z+1) chunks will be loaded. This gives a 2x2 square of chunks. It is designed so that thinks like ore "seams" don't have to end at chunk boundaries.

    Also, I submitted another pull that has a regenerate chunk method for the world class.

    The 2 pulls would allow plugins to take over world generation.

    The process would be something like
    - server starts with no world
    - server generates world
    - plugin enabled
    -- plugin hooks to generate and decorate chunk events
    -- plugin regenerates all loaded chunks
    - plugin records that the spawn area is updated, so it doesn't do it again.

    In fact, there could be a command for admins. They would login to the new world and hit /regen to regen all loaded chunks. This might be safer than having the plugin auto-detect. If it goes wrong, the whole spawn area is wiped.

    Having said that, I don't know how likely it is that the pulls will be accepted, since there is a generation branch. These events would be useful for a plugin which wants to generate random dungeons spread out over the world but doesn't want to take over world generation.
     
  9. Offline

    Timberjaw

    @Raphfrk Good stuff. [​IMG] Unfortunately when I spoke to the devs they didn't think the pulls would be accepted (because of the generation branch like you said). If it has uses other than total generation override though, maybe the devs would be more open to the idea.
     
  10. Offline

    Raphfrk

    I was talking to one of the devs and he said maybe, but that it might go against the plans for the generation branch, which he wasn't sure about (which is pretty similar to the message you got).

    He also said that there may be other features being added to the generation branch so that chunks can be sent to specific players, which is certainly interesting.

    The events could be used for a plugin which does dungeon generation, but doesn't want to override the the entire map.

    For example, a plugin like yours could have a setting that creates random dungeons spread out over the map, but mostly is the standard world.

    Also, the refresh/regenerate methods have uses other than related to world generation. For example, the regenerate method could be used for an area that is an infinite mine.

    The refresh method could be used for fixing missing chunk bugs.

    Maybe I should have pitched them in that context.
     
  11. Offline

    Timberjaw

    @Raphfrk Yeah, my plugin is definitely the type of thing the Generator branch is designed for, so I don't want to give the developers too much flak wrt workarounds. I'm excited to see what they eventually release, but I'm making as much progress as I can in the meantime (and having all sorts of fun with crazy generation quirks, as you can see in the gallery).

    Re: regenerate + refresh: yeah, being able to fix a corrupted chunk on the fly or let players reload a chunk without reconnecting would be nice. You'd save a lot of bandwidth too, because the player would be reloading 1 chunk instead of 441.

    I've actually sorted out most of the performance issues for generation at this point (though it would certainly be much better without the server doing its own generation first), but I've hit some weird lockup issues. Basically, my current code can generate the 400+ spawn chunks in anywhere from 2 to 20 seconds depending on which method I'm using (the long time is for the most reliable method; the others give lighting errors until chunk reload). So call that 20 chunks per second. So if a player is walking in a cardinal direction, it should be generating ~20 chunks every 16 blocks, for a total of 1 second spent generating. And that actually does appear to be the case...for the first 5-10 rows. You can see it generating the chunks (in console) at turbo speed, and loading (in-game) at a nice normal pace.

    After that it starts to choke, though RAM usage doesn't spike (the chunk generation memory is being neatly released). CPU will spike to ~50% and hang out there for a while. I assume it's some kind of I/O issue related to unloading and immediately re-loading a lot of chunks. Possibly a deadlock of some kind (well, not really a deadlock; it comes out of it eventually) either on I/O or on a thread-safe chunk of code somewhere.
     
  12. Offline

    Raphfrk

    How are you checking memory usage? Maybe the heap is filling even though the total memory (according to the OS) is not rising.

    I was looking at some of the old commits and it looks like unloading a chunk doesn't actually cause the block cache to be dumped.
     
  13. Offline

    Timberjaw

    I've been watching it in the task manager. I haven't tried via Crafty to track used vs allocated.

    It's definitely releasing memory on unload though. The heap overflows very quickly if I don't unload the chunks. With unloading, it never runs out of memory, but it gets stuck somewhere at 50% cpu for a while after generating a couple hundred chunks. While generating each row, CPU doesn't spike beyond 10-20%.

    I haven't done much with the GC other than call it periodically during the initial generate process (spawn chunks).

    I should really fire up FileMon or something similar and watch the disk I/O.
     
  14. Offline

    Taurondir

  15. Offline

    Timberjaw

    I came across this page a while back; I had forgotten about it though. Cool stuff! The supertrees in particular are awesome; the procedural castles/roads are a bit more bland.
     
  16. Offline

    Gutter

    It also doesn't make anything "asynchronously", which is a must for MC maps IMHO.

    Have you though about how to produce your dungeons yet? I have been following the thread, trying to come up with a way to create floors and rooms from a heightmap (eg : A perlin noise function). I can come up with ways to create some of it, but not connect any of them together so far. It might be enough for Minecraft though, as the player could make his own connections.
     
  17. Offline

    Timberjaw

    I'm planning on using a combination of tiles (prebuilt chunks) and procedural generator (initially following a preset set of possibilities). Each chunk will be tagged with meta data specifying chunk type, doorway locations, and internal pathing. It will certainly be a less random experience than regular Minecraft, but that's by design in order to produce something that feels 'made'. Down the line, I may try to rough up the generation (Realistic Battle Damage!(tm) ), but the early versions will be very clean-cut. Lots of simple cuboid operations.

    Even that level of random generation produces a surprisingly large set of possibilities. If each chunk can have 1-12 doorways, that gives you 4095 combinations right off the bat. Ignoring pathing restrictions, 1-12 internal connector possibilities gives you several million possible 'passage' chunks. In practice, that number will be reduced somewhat by a weighting mechanism intended to reduce/control the likelihood of dead-end passages.

    If I end up using Perlin noise in the generation, it will mainly be in an attempt to achieve reliable seed generation (so you can share your dungeon with your friends via the seed), rather than as a random terrain generator per se.

    Since I'm building this primarily as a dungeon crawler rather than a typical Minecraft experience, pathing is very important. Players shouldn't have to dig through walls to progress (and I may take steps to prevent them from doing so, actually). This is a significant challenge of its own, however. It's simple enough to ensure that a pair of adjacent chunks are connected, but ensuring a path between arbitrary chunks is likely impossible. I will be experimenting with various edge weighting methods to produce sparser or denser pathing graphs. Denser graphs should result in less dead-ends and less closed regions.

    Where this kind of unbounded random generation is involved, however, it's inevitable that some seeds will produce inescapable starting regions. Nothing a bit of TNT can't solve though...
     
  18. Offline

    Gutter

    That seems like a sensible middle ground. In fact, it is very close to how maps in Spelunky are created.

    Post some screens when you have some!
     
  19. Offline

    Timberjaw

    Of course! I've been uploading screenshots to an imgur album as I take them: http://timberjaw.imgur.com/dungeonator_wip

    I'll be posting some of the more interesting ones in this thread as I go.
     
  20. Offline

    phondeux

    How's it been going? :)

    I've been watching this thread but there hasn't been an update in a week, are you still working on this Timberjaw?
     
  21. Offline

    Timberjaw

    Still working on it, but things are crazy at work. [​IMG]

    I got a basic Perlin noise setup going, and I'm doing the tile editor and tile load/save now. As soon as that's done, basic maze generation will also be done.
     
  22. Offline

    OvermindDL1

    I had actually thought of something kind of like this before, but instead of it replacing the map I had thought of just doing 'larger' corridored dungeons at bedrock level (if bedrock is layer 0, this would be layers like 1-3/4/5), and just instead of a perlin function, an altered one that creates linked 'ridges', and using the high values of that to generate long crawling dungeons with a few splits and things like that, with a few entrances as well. In 'rooms' along the corridors have chests with fancy crap (initially just thinking of taking whatever the dungeon 'displaces', diamonds and the like, and put it in the chest, but could put in more as well), have it be completely dark so the players have to light it up and it should hopefully be full of critters that want to eat the adventurers internal organs. Doing it that way would be very low server usage as it works on a small amount of stuff in only 'some' chunks and it would be deterministic, always generating the same dungeons for the same map.
     
  23. Offline

    feverdream

    The "generation" branch sounds to me like instancing is a goal.. is that something you also want to do?
     
  24. Offline

    Timberjaw

    Instancing of what, exactly?
     
  25. Offline

    lokiman72

    I love this idea!!!
     
  26. Offline

    dak393

    I know I've been watching this thread for a while now can't wait till its done
     
  27. Offline

    feverdream

    Instancing of worlds. Like in WoW.
     
  28. Offline

    Timberjaw

    You'll have to break it down for me; I'm not an MMO guy. Instancing of worlds = multiple copies of the same world, right? I'm not grasping how that would work in the Dungeonator.

    April 27th Status Report

    Flatland Progress
    Made some progress on the Flatland generation today. Wrote my own ChunkProvider and attached it to the world's ChunkProviderServer. This doesn't help with the pre-generated chunks, but significantly improved performance in generating all subsequent chunks. This marks the first time I've been able to just walk indefinitely and have it generate+load new chunks. The big performance boost occurs because it's no longer waiting for CB to generate the chunks and then replace them; it bypasses the first generation entirely.

    Lighting
    Still trying to sort out lighting. I force lighting recalculation in the new chunks by adding and then removing a block via the API. This doesn't seem to work correctly for the spawn chunks (20x20 chunks around the spawn location) though.

    Spawn Chunks
    For the spawn chunks, I've been experimenting a bit with chunk deletion. I waited for the startup generation to complete, then replaced the initial .mcr files with zero-filled dummies before connecting to the server. This turned out better than expected, with my ChunkProvider taking over for the spawn chunks. This workaround isn't acceptable as a real solution, but it also marked the first time I got a Dungeonator-only map at reasonable performance. For now, I'm setting aside the basic generation tasks and moving on to the Editor.

    Next Up: Labyrinth (Maze Generation, Chunk Editor)
    I'm still working on incorporating the JNBT library into Dungeonator to get the Editor working. With Flatland mostly taken care of, I'm moving full steam ahead into the second step on the roadmap: Labyrinth.

    The Editor is an in-game chunk designer for building DungeonChunks (NBT format template chunks with additional Dungeonator-specific metadata). Entering edit mode will flatten the current chunk and mark exit locations in the adjacent chunks for easy design. This allows the designer to build a dungeon section (hallway, L-section, room, what-have-you) using the regular Minecraft interface, then export to a template marked with proper exit information for later matching during random generation.

    The Editor will eventually be extended to Widgets and multi-chunk regions as well.

    EDIT by Moderator: merged posts, please use the edit button instead of double posting.
     
    Last edited by a moderator: May 10, 2016
  29. Offline

    feverdream

    When I say "instance" I mean the following:

    Dungeons, keeps, and other confined areas can have sub-areas called instances (aka instance dungeons). These instances are special areas in the World of Warcraft and other MMO's where your group or raid party is able to interact with a dungeon privately; that is, without interference from other parties or raids. A private world. It is also a respite from the global PvP environment on a PvP server. The term instance has been often conflated and interchanged with the term dungeon.

    Instance dungeons tend to feature the most difficult and rewarding unique content, both in terms of enemies and items, but also in terms of level design. Instances feature boss(es), usually with special abilities and immunities. Getting through an instance normally requires a well-trained and well-balanced group of players who are of an appropriate level for the challenge in most games.

    The defining aspect of a instance is that the world area inside of it is loaded from a template and is temporary. A copy is created from a base template, loaded for the user to use as that instance is "assigned" to them, , and once the goal or defining quest of the world is done and the player exists the instance, the instance is unloaded and deleted with all the changes the plater made inside of it reverted.. leaving the template for the world untouched so that the next group/person can use it. In fact, another big part of instancing is that multiple people can play their private copy of it at the same time.
     
  30. Offline

    M1sT3rM4n

    Now fill the bottom with lava. We just created a parkour game type! Whoever reaches the end first wins 2 diamonds.
     
Thread Status:
Not open for further replies.

Share This Page