Random Dungeon Generator (kind of)

Post your Construct-made creations!

Post » Fri Jul 30, 2010 12:34 pm

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:



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 :D.
B
7
S
2
G
4
Posts: 164
Reputation: 2,418

Post » Fri Jul 30, 2010 9:49 pm

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.
B
46
S
23
G
7
Posts: 459
Reputation: 6,763

Post » Sat Jul 31, 2010 12:14 am

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 :roll:.

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.
B
7
S
2
G
4
Posts: 164
Reputation: 2,418

Post » Sat Jul 31, 2010 4:52 am

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):

[code:3l5u20o5]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 both north and south of it, or both 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.
B
3
S
2
G
2
Posts: 187
Reputation: 1,449

Post » Sat Jul 31, 2010 7:55 am

[quote="Silent Cacophony":1n57v74v]
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().
[/quote:1n57v74v]
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.

[quote="Silent Cacophony":1n57v74v]
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.
[/quote:1n57v74v]
Again, i have no idea how i didn't think of all those excess ground tiles stacking up :oops:.

[quote="Silent Cacophony":1n57v74v]
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):

[code:1n57v74v]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.
[/quote:1n57v74v]
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 :D.

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.
B
7
S
2
G
4
Posts: 164
Reputation: 2,418

Post » Sat Jul 31, 2010 8:38 am

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 :P)
-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:
[code:1ic5pi12]
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.
B
7
S
2
G
4
Posts: 164
Reputation: 2,418

Post » Sat Jul 31, 2010 12:51 pm

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.
B
46
S
23
G
7
Posts: 459
Reputation: 6,763

Post » Sat Jul 31, 2010 3:52 pm

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

[quote="Citnarf":g81ix5ds]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:[/quote:g81ix5ds]

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:

[url:g81ix5ds]http://dl.dropbox.com/u/5868916/DungeonGenV2Modified.cap[/url:g81ix5ds]

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.
B
3
S
2
G
2
Posts: 187
Reputation: 1,449

Post » Sun Aug 01, 2010 4:55 am

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.
[url:2psusb55]http://dl.dropbox.com/u/5426011/examples/mapgen.cap[/url:2psusb55]
req 0.99.91
B
79
S
24
G
52
Posts: 4,725
Reputation: 39,713

Post » Sun Aug 01, 2010 6:10 am

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



:o

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 :D.
http://dl.dropbox.com/u/6660860/mapgenupdated.cap
B
7
S
2
G
4
Posts: 164
Reputation: 2,418

Next

Return to Your Creations

Who is online

Users browsing this forum: No registered users and 1 guest