[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

    Timberjaw

    [​IMG]
    Latest Download: V0.0.3 PREVIEW + JNBT Library
    Overview
    The Dungeonator is, as the title indicates, a procedural dungeon crawl generator. When completed, it will override the native world generation code entirely, producing an infinite expanse of mines, tunnels, caves, and more, packed with mobs, traps and treasures.

    Potential future additions include: biomes (lava, ice, forest, aquatic), classes, NPCs, quests, an automated DM (Dungeonator Master), procedural or prefab puzzles, ...

    Technical Details
    • I plan on using a combination of pure procedural generation and tile-based prefabs to assemble the dungeon. This allows for a great deal of flexibility and variety, as I can seamlessly drop nice hand-made tiles or sets of tiles into the sea of procedural content.
    • Underground biomes are also a possibility.
    • Prefab 'widgets' can be used to decorate tile-based chunks. They can also be used to dynamically populate procedural chunks based on dimensions and tags.
    Roadmap

    Obviously this information is laughably preliminary and subject to significant change. This rough road map comprises the earliest phase of this project. At the end of this phase, the Dungeonator will be generating an infinite (a little birdy told me it was 8 times the size of the Earth) labyrinth of very uninteresting rooms and passages. After that, the real fun can begin.
    • 0.0.1 “Flatland” - Flat, featureless terrain generation with stone base.
      [Done]
    • 0.0.2 “Labyrinth” - Simple NESW tile-based generation and edge/entry matching. Effectively an infinite random maze. Experiment with storage and import mechanisms for tiles. Build basic Chunk Editor.
      [Done]
    • 0.0.3 “Compass Rose” – 12-exit tile-based generation and matching. More complex pathways can emerge. Experiment with exit weighting to vary likelihood of loops and overall difficulty of traversal. Experiment with procedural generation for passage chunks.
      [Done]
    • 0.0.4 “Great Hall” – Experiment with room types, e.g.: storage/cell (1-exit), wide passage (2-exit), hub (3+ exit). Experiment with room weighting vs. passage weighting in overall generation scheme. Multi-chunk rooms. Candidate selection based on exit and wall compatibility. Experiment with size weighting and need for chunk pre-reservation. Widget support.
      [In Progress - 25%]
    • 0.1.0 – Revisit design and formulate further goals
      [Not started]
    Feedback & Notes

    I'm looking for feedback on any and all aspects of the Dungeonator concept and design. I'm taking the design very seriously: I want this project to be totally awesome, cleanly-coded, and as future-proof as I can make it. I'm heavily abstracting data and chunk access, among other things.

    Please share your thoughts, feature suggestions, concerns, criticisms, or random musings.
     
  2. Offline

    Edward Hand

    Wow. This looks really brilliant! Kudos on a fantastic idea.

    Just a quick thought:
    If you want to generate things that look smoothly random, Perlin Noise is the best way to do it. Every aspect of minecraft's normal map generation is done with that. You could probably hook into the servers noise-generation classes and utilise them (to save yourself the hassle of making your own multi-octave 4D vector dot-product interpolation algorithms). Might be worth a look.
     
  3. Offline

    Timberjaw

    Thanks for the tip. Just like using Terragen. ;)

    Early on, the procedural generation will be mainly things that are supposed to look man-made, so simple cuboid operations will be common. Later on, more natural formations like underground biomes will certainly benefit from some Perlin noise or other mathemagics.
     
  4. Offline

    darknesschaos

    This seems so amazing, if you pull this off, notch could buy this from you XD
     
  5. Offline

    phondeux

    This sounds great! I want to do the same and have even sketched out some of the terrain and some algorithms for generating it but I have no idea where to even start coding. [​IMG]
     
  6. Offline

    Gutter

    Wow! I actually wrote "Perlin Noise Dungeon" in Google in order to find idea on how to create dungeons that are like true perlin noise (ie : that you can get the value of any point in the dungeon without calculating the whole dungeon) because *I wanted to make a plugin like this for Bukkit*.

    4 post down, I click this one...
     
  7. Offline

    Timberjaw

    @Gutter I've been looking through some Perlin noise, but that level of predictability won't actually work entirely with the way Dungeonator needs to generate maps. Specifically, certain chunks will be built from 'tiles' (prefab, manually constructed chunks), and some will be parts of prefab 'chunk sets' (a non-random multi-chunk region).

    Additionally, even with a universal random seed, the chunk generation may not be entirely deterministic, as the order in which chunks are generated will affect certain factors, like available doorways to/from each chunk. When a chunk is being added, its existing neighbors are queried for adjacent doorways, which are put into a candidate doorway list. Each dungeon chunk MUST have at least 1 doorway joining an adjacent doorway, but is currently free to do whatever it 'wants' with any sides that don't yet have a neighbor. In practice, almost every chunk generated will have at least one side without a neighbor.

    Basically, in its current form, the generation algorithm will produce different results depending on where the players walk, because it will cause chunks to be generated in different orders.

    There are some methods I'm considering (like Perlin noise) to bring things back into a fully deterministic manner, but I'm not sure right now if it will happen. Being able to recreate a world from a simple seed is definitely cool and I'll support it if I can, but it's not my primary goal.
     
  8. Offline

    Zeroth

    I was thinking about something like this a few days ago! :D The whole idea really reminds me of the game Spelunky. Download it and play a few minutes to get an idea.

    I was also thinking about game play objectives, cause face it, no one will play the plugin for more than 30 minutes if theres no goal or way of keeping track of progress. A few things I was thinking of...

    I'd play the game mostly as a survival game, trying to see how far some friends and I could get without dying. The game would need to keep track of how long I've been alive, how many monsters I've defeated, and how many rooms I've been through. I also like the idea of not being able to craft anything. This sounds like a horrible idea until you add in randomly spawned shops where you can purchase armor/weapons/food/abilities(?).

    And good luck in your adventures ;) If you need any help, I may be interested.
     
  9. Offline

    Timberjaw

    @Zeroth Having a goal is definitely one of my goals. ;) Quests are certainly within the realm of possibility, as are NPCs. Bosses may be impossible (or prohibitively difficult) at this stage without a client mod, but I haven't investigated that much.

    How tightly controlled the resources are is ultimately up to the server admin, but I'm thinking that by default, the players' ability to modify the world will be heavily restricted (somewhat like the "no breaking blocks" rule many adventure maps have).

    I love the stats idea.

    I've also been thinking about special 'waypoint' rooms that act as a party checkpoint.
    --- merged: Feb 27, 2011 4:44 PM ---
    Some early experimental screenshots for the Flatland build:
    http://timberjaw.imgur.com/dungeonator_wip

    [​IMG]

    [​IMG]
     
  10. Offline

    Zeroth

  11. Offline

    phondeux

    There's so little information on how bukkit handles chunks, how are you even starting this? What do you use as reference?
     
  12. Offline

    Timberjaw

    You can learn a lot by tracing execution paths in Bukkit. It's tedious and sometimes brain-melting, but the information is there for anyone willing to put in the time necessary to understand it.

    That said, chunk handling in the Minecraft server is pretty ugly. Generation occurs in multiple places, as does loading, so it's difficult to override that functionality thoroughly. Case in point, CHUNK_LOADED does not trigger for chunks loaded when the player joins. It does trigger when the player moves around, and it triggers if they die and respawn (though for some reason it's missing certain player information at that point).

    There's currently a Bukkit branch called 'Generator' that is intended to greatly simplify this process by overriding the world generator in a more plugin-friendly way, but it's pretty far out of date right now and I haven't yet had much success updating it to the latest CB to try it out (too many file conflicts). That will definitely be the preferred method in the future.

    The nonsense I'm doing right now with CHUNK_LOADED is an inefficient partial workaround; to get it working under reasonable CPU and memory restrictions, I had to tap into the server internals (bad!) rather than using the native API methods. Using the API, each block change is cached in the chunk, and after processing a few hundred chunks, the heap overflows. Right now I'm getting a handle to the base chunk and overwriting its raw data (a byte array), which is very fast, but has some unfortunate side effects (seen in the later screenshots).

    As always, if someone is reading this and thinking "no, dummy, just do X", feel free to share your wisdom. :)
     
  13. Offline

    xCrap

    Nice!

    Are you able to give an estimation on when this is going to be released? :)
     
  14. Offline

    Timberjaw

    Nope. [​IMG]

    When I get a stable build for 0.0.2 or 0.0.3 (in the roadmap), I may start releasing builds for feedback. I'm a little hesitant to do an early public release though; I don't want to deal with a bunch of "I put this on my live server and it deleted my world wtf??" reports. [​IMG]
     
  15. Offline

    xCrap

    Oh sure, understood. [​IMG]

    I'm really looking forward to this, best of luck! :)
     
  16. Offline

    phondeux

    I appreciate the response; I've read hints and half-discussions about the generator branch but can't even find it [​IMG]

    It's probably beyond my skill right now; I can work out equations to generate terrain but hacking into something that's not far past abstraction will have to wait.
     
  17. Offline

    Raphfrk

    On the chunk thing, have you tried unloading the chunk. I think the cache is linked to the chunk, so, unloading the chunk and then reloading it should wipe the cache.

    FYI, the key file is called ChunkProviderGenerate.java

    This has 2 method:

    public Chunk b(int i, int j)

    and

    public void a(IChunkProvider ichunkprovider, int i, int j) {

    The first one does basic generating and is called when a new chunk is first accessed. However, this only generates a basic chunk. The last time I looked, it created a chunk made up of bedrock, stone, sand, sandstone and (stationary) water.

    The 2nd one does the more complex stuff, but it is only called if the chunk has neighbours. This is used to "decorate" the chunk and adds stuff like lakes, ores, trees and so on.

    I was thinking about adding ON_GENERATED and ON_DECORATED events as a pull request but then Dinnerbone created the generation branch on git and I figured he was planning to do it.

    Anyway, probably the easiest way to fix things might be just to add a "clearBlockCache()" method to the chunk API.
    --- merged: Feb 28, 2011 2:47 PM ---
    Also, the game searches for sand in order to create the initial spawn point. This means that if you generate a map with no sand, it will cause an exception for the spawn search algorithm.
     
  18. Offline

    Timberjaw

    @Raphfrk I'm not sure it's a cache issue, at least not directly. After I do my generation, I can stop the server, restart, and the bizarro flatland-with-ores is maintained. I'll look into your unload/reload suggestion though; maybe I can simply put the chunks in a queue the first time CHUNK_LOADED fires; wait a moment, unload and reload, and do my generation on the second CHUNK_LOADED event.

    I do wish that CHUNK_LOADED didn't fire until after the decoration phase, but this is all horrible abuse of the event anyway. As Dinnerbone has told me, it would be more sensible to wait for the generator branch to be finished. [​IMG]

    Thanks for the sand tip. I'm not actually overriding the spawn area yet (it doesn't seem to fire a CHUNK_LOADED event when the server starts or the player joins), so I'll have to address that more directly.
     
  19. Offline

    Raphfrk

    @Timberjaw

    Yeah, when starting an initial world, it generates the spawn area before loading any of the plugins.

    I thought you were having a problem with memory. This is likely caused by the block cache.

    However, from what I can see, the generator branch only lets you assign generators to worlds you create with the createWorld() and so you can't generate the main world.

    I don't know how you are doing the generation. Are you using loadChunk? I think that fires for the initial chunk load.

    This means that it fires after the generate stage, but before the decorate stage.

    Normally, the game leaves the outermost chunks undecorated. It is only when a chunk is surrounded by generated chunks that the decorate step is applied.

    Are you intending to have 1 "room" per chunk? Also, would the maze be multi-leveled? In theory, you could have tiles that have a stairs the links level 1 with level 2 of the maze.

    Also, you could add bedrock into the centre of the walls so people can't tunnel. Maybe even have secret passages where the bedrock is missing.
    --- merged: Feb 28, 2011 3:26 PM ---
    What you could do is

    onEnable()
    - use the getLoadedChunks() method
    - check these chunks against your list of already processed chunks
    - process any of them which haven't been processed already

    onLoadChunk()
    - check if the chunk has already been initialised
    - process it if required
     
  20. Offline

    Timberjaw

    That makes sense.

    Oh, yeah, I was. That was using the previous method, which used the getBlockAt() method on the world and replaced each one. Block cache was my guess as well. I didn't understand by your last post that that was what you were referring to. I'll give unload/reload a try; the getBlockAt() method produced clean results, so it would be completely usable if I can get it to not eat up 1.5gb of memory in 2 minutes.

    Yeah, I think that was to avoid the server startup silliness. I think Dinnerbone is not satisfied with the current generator, so it will probably see some changes before it gets merged.

    Yeah, that's what I've intuited. getBlockAt() will be better if I can get it to not crash horribly.

    After I get some of these initial kinks worked out I'll post my full design spec (about 12 pages currently). Basically, I have the current chunk types: passage, room (single-chunk), room (multi-chunk), set chunk, and biome.

    Passage: procedurally generated single chunk with up to 12 external-facing exits and 12 internal connectors.
    Room (single-chunk): procedurally generated or tile-based single-chunk room.
    Room (multi-chunk): procedurally generated or tile-based multi-chunk room. Multi-chunk room chunks have at least one wall facing an adjacent multi-chunk room chunk entirely removed.
    Set Chunk: these are unique (prefab) chunks tied together in a specific arrangement.
    Biome: procedurally generated underground biome chunks (ice/fire/forest/aquatic)

    I've also been spec'ing out prefab 'widgets' that can be used to dynamically populate both procedural and prefab room chunks with furniture/etc.

    I'm considering it. My initial chunk schematic doesn't have thick enough walls to allow this (I wanted wider NESW passages). It's definitely on the table though.

    I really like this idea. I just need to sort out the onLoadChunk issue with generate vs. decorate.
     
  21. Offline

    Raphfrk

    With server port, I did a "gridload" method.

    This was where I loaded a 3x3 grid of chunks instead of just the target chunk.

    Prior to that, the portal would sometimes appear snow covered.

    I think the reason is that the 3x3 grid meant that the central chunk would be decorated.
     
  22. Offline

    Timberjaw

    Iterating through getLoadedChunks() seems to work, provided you null each entry as you go. Otherwise the chunk array you're working with causes the same heap overflow error. I ended up running a loop basically like so on startup:

    For i in chunks[]:
    1. For x,y,z in chunks: do generation magic
    2. Unload chunk at chunks.getX(),chunks.getZ()
    3. chunks = null
    4. System.gc()

    This slowed the startup time for the server considerably, but it never got above ~200mb of memory and loaded up just fine. I haven't tested yet to see if I can ditch the .gc() call. I'm running it every 10 chunks during the startup processing since I'm allocating and then clearing large amounts of memory.

    All in all, that's working pretty well.

    Still some kinks to work out. The big one right now: "More than 1000000 updates. Aborting light updates." This causes some crazy lighting issues until something forces the server to recalculate lighting.
    --- merged: Feb 28, 2011 6:23 PM ---
    I also need to forcibly remove entities during the initial load. I found a bunch of ink laying around (sorry squid!).
    --- merged: Feb 28, 2011 6:58 PM ---
    Unload and reload in onChunkLoad takes care of memory issues. Lighting issue turned out to be something else, and is also taken care of.

    Downside: significantly increased chunk loading lag. You can walk faster than it can process chunks with this method. Being able to clear the block cache would probably eliminate the need for a reload.

    Entities don't appear to be a problem for chunks flattened after the initial load.
    --- merged: Feb 28, 2011 7:02 PM ---
    Very exciting.
    [​IMG]
     
  23. Offline

    Gutter

    Did you try to use chunk.world.getBlockAt() to read the blocks? I ran into something similar while trying to read all the blocks on a nether map and seed it with wood to be able to play a netherworld only game. I was doing it exactly like Raphfrk is describing (so it works :) )

    Using chunk.getBlock() creates memory problems, chunk.world.getBlockAt() doesn't. I could scan the whole 600 startup chunks in about 7 seconds. Of course, I don't do much beside reading the blocks and setting some to wood, but still, no memory problems.
     
  24. Offline

    Timberjaw

    I'll give that a try. Strange that one would hit the block cache and the other wouldn't.

    I think I should also change processing from bottom-up to top-down. That would probably eliminate the flowers/mushrooms/etc I keep finding everywhere.
     
  25. Offline

    Gutter

    I don't get it. Why don't you just check for them and remove them? Or you mean to say that removing a block with those on them causes problems?
     
  26. Offline

    jwideman

    Years ago, I bought a book (I still have it even) for pen-and-paper RPGs that is basically step-by-step random dungeon generation. It includes everything from corridors to the different types of rooms, and creates a layout that is logical. It is ideal for this sort of thing. It's called "Central Casting: Dungeons" and is available on Amazon, used for <$25.
     
  27. Offline

    Timberjaw

    If you remove the blocks from the bottom up, you will cause flowers/mushrooms/etc to turn into entities instead of blocks, because the pop when the block below them is removed. Thus they don't get removed. Removing chest blocks also causes their contents to get dropped instead of deleted.
     
  28. Offline

    Raphfrk

    This is the getBlockAt() method:

    Code:
        public Block getBlockAt(int x, int y, int z) {
            return getChunkAt(x >> 4, z >> 4).getBlock(x & 0xF, y & 0x7F, z & 0xF);
        }
    
    It looks like it gets the chunk and then calls getBlock, so they should be the same.

    One possibility is that it throws away the resulting CraftChunk object returned by getChunk object and so the cache is eliminated. However, it might not work so well.

    Also, that having to set chunks = null is one of the big risks of using getLoadedChunks .... if you don't set chunk to null, you have a reference to all loaded chunks.
     
  29. Offline

    Gutter

    Arg.... I meant "world.getBlockTypeIdAt()"
     
  30. Offline

    Timberjaw

    Unfortunately, getting the type id isn't of much use to me, since I'm going to overwrite everything anway. Though if it doesn't hit the block cache in each chunk, it would save a bit of memory by skipping air blocks.
     
Thread Status:
Not open for further replies.

Share This Page