Hi,

I am looking for ways to generate a random tile map out of prebuild pieces, much like diablo 2 and Dungeons of Dredmore do. I have prebuild sets of 8x8 for corridors and small rooms, and for larger rooms i need 16x16, 24x24 and perhaps 32x32 sets. Some rooms will hold quest pieces like bosses or artifacts, most probably i will do this with color values on images. The picture below shows just entrances in pink and passable area in black.

I have been looking into mazes and translate these mazes to these prefab pieces. So if i generate a 16x16 maze it will give me a 128x128 map. Each maze tile will translate to a corresponding prefabricated piece.

Some characteristics:

- I do not want to many dead ends since this might frustrate the player.

- The mazes i looked for are "dense", every tile is used. This is ok for some maps but some need to be less dense.

- I need some maps to have the entrances/exits at the edge and some within the map but some distance appart.

- I need to insert special rooms that hold treasure, quest items, bosses, etc.

Basically what i am looking for now is a partially braid maze algorithm that let's me pick the entrance and exit area's, insert some larger rooms and generates some larger rooms occasionally. I could also just pop in my entrance, exit, special room and multiple larger rooms then run a braid maze algorithm and restrict it on those area's but taking there entrances into account to connect properly.

How would you take on a problem like this? I would love to read some ideas so i can look at this from another angle since i am stuck on this for days.

I used to have a website bookmarked that explained exactly what i am looking for, unfortunately i lost that bookmark. It used much smaller "connection" rooms but i think i can easily translate this into bigger ones i have. So if anyone has this i bookmark i would already be very happy.

One approach I've seen is to first generate the rooms without any doors or corridors between them. Then you go through a second pass adding doors to each room to connect them all to each other. Larger rooms could be allowed more doors, and you could easily verify how many dead ends you have by looking at rooms with only one connecting door.

I can't find the link right now, but I recall seeing a presentation on Path of Exile's random dungeon generation, where they place a Start room, an end Room and then a room in the very middle of the map. Then they randomly add rooms and doors using a similar technique I mentioned above, but ensuring that there's a path from the start room to the middle room, and then the middle room to the end room. This ensures the overall network of rooms is linear, which is better for guiding the player.

Another interesting technique is described here: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/

That might be more complex than you're after, but it could give you some ideas.

One approach I've seen is to first generate the rooms without any doors or corridors between them. Then you go through a second pass adding doors to each room to connect them all to each other. Larger rooms could be allowed more doors, and you could easily verify how many dead ends you have by looking at rooms with only one connecting door.

I can't find the link right now, but I recall seeing a presentation on Path of Exile's random dungeon generation, where they place a Start room, an end Room and then a room in the very middle of the map. Then they randomly add rooms and doors using a similar technique I mentioned above, but ensuring that there's a path from the start room to the middle room, and then the middle room to the end room. This ensures the overall network of rooms is linear, which is better for guiding the player.

Another interesting technique is described here: http://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/

That might be more complex than you're after, but it could give you some ideas.

I already have my rooms and corridors as fixed templates. Like i said i need an algorithm that binds them together in a convincing way, with just some dead ends and mostly loops. So what i am thinking of now is for every 8x8 on the map grid i need a single tile of a maze grid that has open/close flags on each side, then pop in my corridors and rooms. A long dead end could hold a large "side" treasure. I am not looking for a complete random map since that does not look convincing for buildings most of the time. If you look at Diablo 2, they only use fixed pieces. I believe Diablo 2 uses a simple maze as the basis for there maps. I Cannot find a good braid maze algorithm, i am still experimenting with it and i want to add the mentioned characteristics in it.