Random Dungeon Generator (kind of)

This forum is currently in read-only mode.
0 favourites
From the Asset Store
Game with complete Source-Code (Construct 3 / .c3p) + HTML5 Exported.
  • So today i decided to make a random dungeon generator, it didn't really turn out as i would have liked so it actually really just generates large randomly shaped rooms. I had originally planned on it creating rooms all attached to each other with corridors but it was quite complicated and so this is just what i ended up with.

    Here are two "dungeons" i generated with it:

    <img src="http://dl.dropbox.com/u/6660860/Dungeon1.png">

    <img src="http://dl.dropbox.com/u/6660860/Dungeon2.png">

    As you can see, there are some areas that are blocked off, i can't figure out how to fix this.

    And heres the exe:

    http://dl.dropbox.com/u/6660860/DungeonGen.exe

    The No. Of rooms box does not work right now either, which is due to a bug in construct i think, which you will see when i upload the cap later. Also, after the dungeon is done creating itself, it might appear to freeze for a moment, this is where it "hollows" itself out and is checking for ALOT of collisions at once.

    After the dungeon is created you can zoom in and out with your mouse wheel and scroll around the map with WASD

    I will also upload the cap later, after i finish commenting it all .

  • Interesting Citnarf.

    I have played with random generation in the past. I have a folder full of method and ideas. Unforunately my lack of any Maths skills have held me back when trying to port algorithms I have found on the internet.

    My only real success has been a random island generator that used Cellular Automata to produce islands and a basic height map.

    Looking forward to seeing the cap and see if is similar to anything I have tried.

  • Ok, here is the .cap

    http://dl.dropbox.com/u/6660860/DungeonGen.cap

    A few things i should mention, this is my first time using arrays, ever, so i might not have used them perfectly, but hey it works. Also, I'm really bad at explaining things so some of the comments might make no sense .

    And finally, yes i know i could have just used 1 function for the whole thing, but i couldn't be bothered changing it now.

    Also, you should be able to quite easily adapt this to use tiles bigger than 16*16 by simply changing the size of the wall and ground, to 32x32 for example and simply changing the "GridSize" variable to 32. Although i haven't tested this.

  • That's pretty cool. I've played around a bit with some random dungeon generator ideas, and they can get quite complex. I've decided to use Python for such a thing, unless it's pretty simple.

    A couple of notes about this come to mind. I noticed that you had trouble with setting a global variable to the user-input room number, and just set it to a static 99 instead. This can be done by coercing the string value into a numerical value by using the system expression int() or float(). In this case, you'd prefer an integer over a floating point number, so you can do it like so:

    + cmdGenerate: On cmdGenerate clicked

    -> Wall: Destroy

    -> Ground: Destroy

    -> System: Set global variable 'NumRooms' to 0

    -> System: Set global variable 'MaxRooms' to int(txtNumRooms.Text)

    -> Function: Call function "MakeFirstRoom" (and Forget picked objects)

    Also, I noted that a 100-room dungeon ends up creating around 5,200 wall tiles and 15,300 ground tiles, then reduces the number of wall tiles to 400-700 or so after destroying the ones that overlap ground tiles. This leaves a lot of 'stacked' ground tiles that are unnecessary. It also may need two passes to remove all of the extra walls, since it's doing all of that in a single tick, and Construct only updates such changes at the end of the tick.

    I would probably avoid creating all of the extra tiles by using the system condition object overlaps point to test of a tile already exists at the current drawing location. Putting the wall and ground tile objects together into a family (say, 'blue') would simplify things. Then the drawing part could be done something like so (in pseudocode):

    if (wall tile):
        if (family blue does not overlap drawing location):
            draw wall tile
    if (ground tile):
        if (wall tile overlaps drawing location):
            destroy wall tile
        if (family blue does not overlap drawing location):
            draw ground tile[/code:3l5u20o5]
    
    That assumes that the wall tiles will be destroyed instantly, and the next check will not see a 'blue' there afterward. I'm not sure if that's the case, but otherwise one could add another 'draw ground tile' after the 'destroy wall tile', I guess.
    
    Any rooms that are inaccessible at the end could be dealt with by running through all walls with a 'for each wall', and checking for the presence of a ground tile either [i]both[/i] north and south of it, or [i]both[/i] east and west of it, and replacing the wall tile with a ground tile if either is true.
    
    Of course, there are tons of other things that one could do with it, too.  But it starts to become a beast at some point along that road.
  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • A couple of notes about this come to mind. I noticed that you had trouble with setting a global variable to the user-input room number, and just set it to a static 99 instead. This can be done by coercing the string value into a numerical value by using the system expression int() or float().

    Thanks! I feel like an idiot now, i really should have known this as i did do some java in school, and we did exactly this to convert ints to strings, or strings to ints.

    Also, I noted that a 100-room dungeon ends up creating around 5,200 wall tiles and 15,300 ground tiles, then reduces the number of wall tiles to 400-700 or so after destroying the ones that overlap ground tiles. This leaves a lot of 'stacked' ground tiles that are unnecessary. It also may need two passes to remove all of the extra walls, since it's doing all of that in a single tick, and Construct only updates such changes at the end of the tick.

    Again, i have no idea how i didn't think of all those excess ground tiles stacking up .

    I would probably avoid creating all of the extra tiles by using the system condition object overlaps point to test of a tile already exists at the current drawing location. Putting the wall and ground tile objects together into a family (say, 'blue') would simplify things. Then the drawing part could be done something like so (in pseudocode):

    if (wall tile):
        if (family blue does not overlap drawing location):
            draw wall tile
    if (ground tile):
        if (wall tile overlaps drawing location):
            destroy wall tile
        if (family blue does not overlap drawing location):
            draw ground tile[/code:1n57v74v]
    
    That assumes that the wall tiles will be destroyed instantly, and the next check will not see a 'blue' there afterward. I'm not sure if that's the case, but otherwise one could add another 'draw ground tile' after the 'destroy wall tile', I guess.
    
    

    I really like this idea, a lot, but i wonder if it would make the dungeon a lot slower to generate? Since it will be checking for an overlap every time it tries to create an object? I'm probably totally wrong, and I'm going to give this a try right now .

    Also, just for fun i decided to change the second function, instead of setting the room pos to a random wall tile, i set it to a random ground tile and it seems to work much better this way.

  • Okay, heres an updated cap, i implemented your ideas Silent Cacophony, and i have to say its 100x better now.

    -The No. Of Rooms box now works

    -There is no longer a freeze at the end, as it removes all the walls as it goes! (well actually, it just doesn't create them in the first place )

    -There are no more blocked of areas

    http://dl.dropbox.com/u/6660860/DungeonGenV2.cap

    Also i couldn't get your idea of checking to see if the space is occupied before placing the tile to work exactly as you had it written down for some reason, so its slightly different now:

    if (wall tile):
        if (family blue does not overlap drawing location):
            draw wall tile <-- This is the same
    if (ground tile):
        if (ground tile does not overlap drawing location):
            create ground tile
    [/code:1ic5pi12]
    This way it doesn't stack ground tiles, however it still can create a ground tile over a wall tile. I tried to fix this but it started leaving gaping holes in the walls or ground.
    
    A 300 room dungeon uses about 13,000 total tiles now, a bit better than the 15,300 100 room dungeon before.
  • Thanks for the cap Citnarf I'm going to go through it later and pinch some ideas

    I've always wanted to make a proper Roguelike but the map generation has always held me back.

  • Nice. I like the picking of a random ground tile to expand from instead of a wall tile, too.

    Also i couldn't get your idea of checking to see if the space is occupied before placing the tile to work exactly as you had it written down for some reason, so its slightly different now:

    I tried it with the check for a wall tile, and destroying it if so, and it worked as I expected. Here's a modified version of the V2 .cap:

    http://dl.dropbox.com/u/5868916/DungeonGenV2Modified.cap

    Just one event bracketed by red comments added to the MakeRoom function. I tested it in a copy of that, where I counted overlapping tiles at the end, and came up with zero each try, so it should eliminate all overlapping tiles.

  • Citnarf I like your example, very inspirational. I was messing around with dungeon generation after looking at your example and came up with a few ideas.

    For the rooms, box objects would work well to define them. Then to draw the map with walls and floor just sample locations say every 16 pixels over the boxes. If the location overlaps a box then it's a floor, or if the location doesn't overlap a box in any of the 8 directions around it, then it's a wall.

    So all that's left is to do is create a number of boxes, of random size and build onto already placed boxes. I found the "push out of object" actions of the custom movement behavior to be useful in this situation. My Pseudo code for box placement is as follows:

    1. create a new box so that it overlaps existing boxes.

    2. push the new box out of the existing boxes so it isn't overlapping but is next to other boxes.

    3. move new box toward the closest box by a small distance. (this helps eliminate isolated rooms).

    Here is the result of this interesting idea and some free time, enjoy.

    http://dl.dropbox.com/u/5426011/examples/mapgen.cap

    req 0.99.91

  • Wow R0J0hound i LOVE it, the dungeons this creates are amazing.

    <img src="http://dl.dropbox.com/u/6660860/rojodungeon.png">

    The only flaw i could see was that if i tried to create a dungeon with 25 or more rooms, my FPS started to drop quite significantly, this was due to the fact you were destroying all the walls and floor every tick and re-creating them in a loop.

    So i slightly modified it and now it runs at 60fps with 99 rooms .

    http://dl.dropbox.com/u/6660860/mapgenupdated.cap

  • Waou very great thx all

  • Thanks to everyone who has contributed, it has given me some good ideas.

    Here is my work in progress - cap to follow when I iron out a few bugs and add some more features.

    <img src="https://dl.dropbox.com/u/1646976/photos/mapgen1.png">

    Normal map - 10 Rooms

    <img src="https://dl.dropbox.com/u/1646976/photos/mapgen2.png">

    Same map as above showing the rooms as different coloured regions - Should be useful for placing treasure & monsters.

    Just got to sort out the placing of rooms as sometimes you get areas closed off from the other rooms. Add a treasure placement loop, start & exit points, monsters, shaped rooms and make it customizable.

    Thanks again to everyone who has posted here

  • Whoa Minor!

    That's something I'd love to see made into tutorial x]

  • What a great thread!

    R0J0hound nice pice of code.

    .. and I second they I would like to see a finished cap from Minor example, or better a tutorial!

    Things just got interesting here!

  • *subscribes*

    This topic should prove useful if I ever decide to design a Diablo-esque dungeon-crawler--very exciting!

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)