Designing the logic for randomized dungeons...

So... I have been playing around the last months with lots of ideas I had for a dungeon crawler. The maps are grid-like, and now I'm working on proper randomized dungeon generation. To add longevity and re-playability to the game. I started out whith Pre-defined grid info for the dungeons, then experimented with random maze generation. And now I wanted to move on to proper randomized dungeons, but am having trouble thinking up how to do the logic. I am not asking for any code, just for ideas you guys come up with for me to program myself.
Anyone that wants to participate and give ideas/suggestions (no matter what programming experience you have) is welcome, this discussion isnt about code, its more about designing/planning the logic behind it!


I am trying to come up with a new random generator that will create something more dungeon-like and something that will actually be fun to play:

Elements/Concepts:
-all of this is just a simple 2d array, off of this grid I build the floor/walls/doors/etc depending of the value in the array. Don't go crazy thinking of complex 3d stuff, I'm keeping this hobby project simple but fun.
-Of course rooms, what is a dungeon withought random rooms to explore!
-Corridors to connect the rooms and limit the order the player can access the rooms
-Keys! Have you ever played old shooters like doom? Well I want to include something similar, a random set of rooms and corridors, in one of the rooms a red key to unlock the red door and gain access to the random set of rooms in that area, where there is the blue key, yellow, etc, etc...
-Later on I might include puzzles and stuff, but for now lets keep the ideas simple.


Why start a thread on this?:

I am having trouble with comming up with the logic to create this, Creating random rooms is easy. Creating them one by one with simple linear corridors is also easy but I don't want it to be so linear-progression! Creating a maze was wierd, but i got the grasp of it also... Combining both ideas? Now that is the hard part! Also... what if the red key is placed somewhere behind the red door? Or even worse behind the next areas (blue/yellow/etc)! Rendering the whole random dungeon in-completeable! Any ideas would be great.


Exaclty how simple is "simple":

int map[128][128];
0= represents space not used yet by randomizer / available
1= walkable floor
2-3 not used yet / reserved for future floor types, mabe water, destructable wall for secret rooms, I don't know yet...
4= simple door / no key required
5-9= locked door types / colors
10-15= key types / colors
16= not passable / wall

Dosn't get more simple than that, does it? Now how to generate the values in the map array... The tough part is coming up with the logic that will randomly create an array like this:

(PS: forgot one thing, brownish ones are walls)

I am all ears for ideas and feedback!
Meanwhile feel free to watch one of my Random Maze Generators in action creating several different mazes:
http://www.youtube.com/watch?v=4nFvObjOqSQ

Ideas I have already played around with:

-I have already created a random maze generator. Uses a concept I found somewhere (sorry I don't remeber the link) for something the author called "the perfect maze". Basically I create a maze, where if you choose any starting and ending point there is only one possible path to solve it. While it was fun creating it... Sadly I think it is of no use to me since it dosn't take into account rooms and such...

-Line of sight / field of view: only creates floor and walls that are in field of view distance and line of sight. It is periodically updated and works on the grid view. (though the player has free movement and is not limited to the grid, the line of sight works like in rogue-like style) I transform the free postition of the player to the cell he is standing on, and then calculate what walls/floors are visible on the grid, and then translate that back to a 3D coordinates to create the 3d elements.

-The camera style is a third person view, with right-click rotation and mouse wheel zoom, this is why I made the line-of-sight algorithm, so the player cannot cheat and see inside rooms or across walls taking advantage of his semi-isometric perspective. I also incorporated a dual stick shooter aproach to movement and attack but that is off-topic.

-I have made a random room generator that, while it was fun to play around with, is not usefull to me. Created rectangular rooms of varying width and height and randomly places them on the grid taking into account not to overlap exsisting rooms. This generator has no halways or anything to limit room-connections or similar limits...


So now that I have had alot of fun with random things and feel quite comfortable with these concepts, I want to take this little hobby-project a step further and make something that will actually be fun for me and my friends to play, something that will look and feel a little more like a real game.


What I don't want:

-Code! This is not a "I don't know how to program and want someone to build me a game" type thread. What I want are ideas, concepts, mabe after discussing some logic pseudo-code helps transmit a complex idea across. But remeber this is my hobby, I do this for fun in my leasure time, I am not asking for this to be done for me.
-Examples on how to transform the array info into 3d world objects/coordinates. I have already done this alot of times and have several different methods already programmed I can use from previous games. I would prefer this discussion to be more about a random generator of simple info for the array, with the objective of producing data for a random dungeon generator, and then mabe any game design ideas to include / expand upon.

hehh a but chaotic and long description... but if you already have the rooms, corridors and open doors, it is not a big thing to create a solvable lock-key system:
place all the locks;
floodfill from start tile defining locks as impassable tiles;
while filling note if a lock was examined as neighbouring tile;
when floodfill ends check which locks were touched;
place randomly these keys in any floodfilled tile;
define these touched locks as passable;
continue floodfill and repeat key placing...
finally transfer money to me

Idea for a dynamic generator:

Lets say you want a generator for making a specific adventure.
that you can define by script:

AreaA
-leave AreaA a though a door
-there is a another locked door #1
AreaB
-find a weapon
-find a helmet
AreaC
-fight a rat
-find a healthpack
AreaD
-find Key #1 for a Door #1 in Area A
AreaA
unlock Door -> passage to Area E
AreaE
fight 3 goblins

now what you can do already is generating a string of rooms and passages.
Lets assume all rooms have the same size, and lead from left to right.

Room AreaE is special, and is placed below AreaA

The generated Dungeon looks like this:

[A] [B] [C] [D]
[E]

And each room contains items as defined

Now this looks boring, but already represents your dungenon logically.

*********

Next Step:
randomly alter/adjust the rooms, passages and positions ,
as long as none of the conditions above is invalidated.

This could be done by moving / scaling / relatively rotating the rooms randomly, updating the passages between them.
Any change that makes them (or the passages) intersect will be rolled back (invalid) and the next random change is tried.

lets say the dungeon looks like this (ok ASCII is not really usefull here)
[BBBBBB] [C CCCCC]
[AAAAAAA] [DDDD]
[EEE]

You basically bend and twist the vector-grid of the generated room layout to make it look more random.
-> like Origami or making a baloon dog

It should work well for maps where you dont need to seuqeeze everything into small space (where other methods make more sense)
The advantage is that you can precisely define the flow of the level, and balance it quite well.

I have in here a random generator dll for download, and I am currently finishing a new one that does not use the dll and works more with a tile system that I will be putting up here soon.

@sivan:
Thanks for the feedback, yes I re-read the post and it did seem a little chaotic. Too many ideas at the same time and it looked like my brain exploded on the screen hahahaha. I tidied it up a little and changed the order around a bit.
The thing is, I don't have the cooridors and rooms. The picture is just an example of the style of dungeon I want to create, but there is no random generator to create something like that yet. The floodfill idea is good for the keys and stuff, but there is nothing to floodfill yet. Any ideas for the logic behind a random generator that would produce something like the example is welcome.

@Damocles:
Looks like a good concept to start on, thanks! At a first glance it feels like the progression of such a system would be too linear for what I want, but I might be wrong. I will give it some thought and plan it out to see how it would work. Seems like a good starting point for the generator!

@lostzac:
While that might be usefull, I really want to create this myself. I would prefer if you talked about the logic behind your generator than just giving it to me. Don't get me wrong, I'm not ungratefull, I just like doing this for fun as a hobby and withought work there is no fun or gratification if I just jump to the result. Its kind of like playing basketball as a hobby, imagine you get to the court and are handed a paper with the result "you won 67-15" and are told to go back home, you never got to play the game, you didnt have fun, and the lack of effort gives you no satisfaction from the win.
Still I am very gratefull for your offer, and will probably take it, but not look at it till I finish my own, or fail to create a decent generator. If I finish it will be great to compare it to another and see if there are some extra features I like or better ways of doing things, and if I fail it will be a great consolation prize! Thanks!
And I am all ears if you wish to discuss the logic your generator is based on. Share your wisdom, I would love to hear your approach and opinions on random dungeon generators.

For the one I am working on now it is rather simple.... the workflow goes something like this

Using a grid based system (I use 25x25 in my test), each grid is 2560 x 2560 units large. (Primarily as each tile is use is 256x256), anyways....

I star by generating the amount of rooms I would like to have, the generator randomly chooses width and length of each room and randomly chooses one grid section to place a single room on, can be anywhere with in that grid section.

Hallways are generated next, I tried severely ideas but the one I found out that worked the best for me...was to have each grid with a room on it draw a path from the door to the center edge of the map section it was on...

ie a north door would first draw a line from the door to the center edge along the top, ect ect ect...then a second pass to add bends and branches (that would end into a dead end), on sections that did not have a room in it, i would randomly draw hallways from the center of each edge that met in the middle and then again add the branches and bends on it afterwards. This assures that each room is connected.

Again it is rather simple in design right now, oh and I did not mean hey why program it when I have one on here, I meant it more as here is how I am doing it on this point, take a look at it, and maybe you could add some input on how I can make it better....as i said its rather simple

I like the idea, so if I understood correctly... each "section" is connected to neighboring sections by the middle of each edge like this?


Lets see if I got it right:
-1 random room in a section (only one room per section)
-2 hallway to connect the room to the closest section (in the middle of an edge, like marcked in the picture)
-3 random hallways branching from the first hallway

Did I understand you correctly? Seems very simple and at the same time functional.
Great idea! No need to over-complicate myself (I was thinking of a rather complex system with linked lists that memorized door positions and hallways etc, then some sort of pathfinding algorithm to connect those positions, after that a modified version of my "perfect maze" algorithm to add random hallways, and at the end some sort of floodfill algorithm to place keys, locked doors and cut off halways that connect to zones they shouldnt). Why complicate myself so much when a simple appraoch gives good results also! I think I'm going to program a simple version of your idea tomorrow and check how it works out!

Only one question though... If you only have one room per "section" why do you have 256*256 sized sections? Do you use huge rooms? Tons of hallways per section? Or is it due to your scale or something?

Yes you got the idea....


well if you figure each room can be from 3x3 to 8x8 in my area so that's at the smallest 768x768 to 2048x2048 on the largest room it leaves room for two tile hall to the next section in any direction on the smallest a 7 tile hall without bends....at the most at the most a hallway is usually with the bends 14-18 tiles long which really is not that big....I am finishing up some touch ups on the hallways and then I will be placing this up (most likely some time tonight) for download to anyone who wants to take a look at it

The next feature I am planning on inter-grading

Room Types to spawn different tile pieces
Vertex placement of props lights and items

You are correct with a smaller dungeon say 15-40 rooms on the hallways

I am working on a function that first draws hallways from room sections to room sections..

ie scans for unconnected rooms and then connects them to the nearest hallway piece or room. Then a second scan to cap off any hallways that have no ending piece. This should cut down on the amount of hallways generated...

another idea would be to have the amount of grids dependent on how many rooms the user wanted to generate...

so lets say i wanted 30 rooms in this dungeon... You could divide the dungeon by a third to get the grid size. so a dungeon with 30 rooms would be placed on a 10x 10 grid..I used a third so you had empty spots to generate longer hallways that lead to nowhere.(I will have to try this on the next version as I have this one almost done)

//UPDATE:

Could not get the idea out of my head was not as hard to implement it as I thought it may be....

So Generation Map size depends on the amount of rooms you want
The current formula will generate 9-625 rooms....on map sizes (dependent on how many rooms you want) 3x3 to 25x25..

Example I generated a 15 room map
the map size was 5x5 (15/3) for a total of 25 squares... only leaving a possibility of 10 blank sections, cutting down the chance of exceeding long hallways.

9 rooms is the min as that makes a 3x3 map making a room in each section. Anything less would not fit the current equation

You should look at "Legend of Grimrock" it's agreat indie dungeon example game

http://www.youtube.com/watch?v=emM4J6BxKJ0

all of this is extremely interesting to me ,if someone nails it
and decide to upload it on the forums i would love checking it out

even games in thiere simplest form can be complicated hey!

i was thinking having rooms with certain tiles with values that qualify
as connection points ,these connection points being for generating
pathways between rooms and some rooms having more than one connection
doors are then obviously where the connection tiles are located,
so the rooms are then generated at their random positions/orientations/sizes
then pathfinding connects them from connection to connection generating tiles bla bla..

layer/array 1:
--------------
lets say walls=0
and paths=1

now the paths that connect the rooms
are generated on this layer/array which makes tiles of value 1's
also some random connection point's are placed throughout the grid
which also generated paths to other (already placed) random connection points
which will basicly make some useless corridors that lead no where

a invert function then inverts all 1's to 0's efectively creating walls around
the paths which is basicly corrodors rite

now theres another layer/array where the rooms are placed on which have also a
value like 2's for walls and 3's for open area inside room, then this
layer/array gets passed over the layer/array 1 overwriting all the walls with
this layer/array's data which places the rooms and paths/walls into one layer

but im just rambling anyway.
haha holy crap i just realised the garbage that came from my mind here

It's been a while since I had time to check the forums, thankyou everyone for your input! Oh, and Legend of Grimrock did catch my eye on launch and I had a look at it. Lots of great ideas there!

Still working on mine, and I do intend to upload it when I am done for the community. I was optimizing hallways to give them more a random shape, and working on a multi-texture shader (Idea to give levels more randomness, select random textures from a group and place them...this way a sewer tileset could have dirty, clean, ect ect looks to it without having to have a whole new tileset for each look)

I stuck to the approach of dividing it by "sections" and creating each section randomly like you suggested, but took a different approach on the hallway generation and how sections connect to eachother.

I declare two small arrays I use for creation purposes besides the big array containing the actual map.



"map" is to store my final map, and has two levels. One for floor tile info and one for objects/walls above the floor.

"macromap" is used to decide how secctions connect to eachother

"micromap" is not necessary but it makes creating each section easier and faster

-First I use a modified version of my maze generator to fill in "macromap" that will control what sections connect to which and in what order.

-"micromap" will be reused alot (each time I generate a new section). I place a room randomly in micromap, create a random door on one of the four walls of the room, and then create hallways filling up the rest of "micromap" using a different modified version of my maze generator (starting from the room door). Then I place all that section information in the cuadrant it belongs in the big map and re-use micromap for another section.

-Last I connect the different sections (independant room & maze hallway sectors) acording to the information in "macromap".

Feel free to take a look at my old "maze generator" video in my first post. Note that macromap and micromap are generated with different modified versions of my old "perfect maze" algorithm. It is called perfect maze because if you choose any two points in the maze there is one (and only one) path to get there. If you are interested in how it works the concept is quite simple and I will be happy to explain.

Also, my big map is not actually an array of simple integers, it is an array of a custom struct that contains different tile information along with visibility, transparency, and passability flags for my other algorithms I am working on (custom tile sets, line of sight and pathfinding).