• # A Labyrinth Generation Algorithm

General and Gameplay Programming

This was for a Dungeon Explorer home project I was working on. When researching labyrinth, maze, or dungeon generation algorithms I found many that would create hub or tree-style dungeons, but none that would 'loop back' on themselves.

I created this algorithm with the intention of designers or artists still having full control over the look and contents of rooms and corridors. As long as certain rules are followed (e.g. attachpoints are assigned to rooms and snapped to a grid, rooms have a 'footprint' object that bounds their size) rooms and corridors can be any size or shape desired.

This video demonstrates the process, which is also outlined below:

I did go on to make a small game using this algorithm and bar some silly behaviour (like making corridors to from a room to itself), it's worked great!

A short excerpt about the algorithm, for those that might like to re-create it!

Steps

1. Randomly Place rooms within the defined area
2. Attempt to connect all rooms together in a large 'chain'
3. Starting with random rooms, make smaller 'chains' of rooms within the network
4. Prune room connections from rooms that have more connections than attach points
5. Go through all room connections and connect actual attach points
6. Use A* pathing to create corridors between the attach points
7. Mark all of the corridors onto the grid
8. Actually place straight, corner, T-Junction, and crossroad corridors oriented in the correct way

There's a whole bunch more complexity in each of these steps, but that's the basic breakdown!

The objects you see in the gif are 3d rooms complete with art and stuff inside them, but the camera is top down and lighting set to make the gif easier to see!

Each room is a prefab game object. They have their own scripts that manage the stuff contained within them, in this case flickering torches, furnaces, and other puzzles.

Each room has attach points that are defined by me (in this case acting as the designer), and the dungeon generator is given a list of all rooms it should use to generate, again defined by the designer.

The rooms provide information like their size, shape, available attach points etc that the generator uses to position and connect them.

There are different corridor types, straight, t junction, crossroad, and corners. Each has a different setup of walls. The algorithm places them just after the steps seen in the gif, choosing which to place base on what's adjacent to each grid position and orients them. Again these are prefab game objects with other things in them (e.g. Torches).

I've just used debug lines to draw out the connections for the purpose of showing it in gif format, the original version doesn't do this at all!

Another example but with 200 rooms rather than 50, at increased speed:

And another 200 room demo, with no speed increase:

Note: This article was originally shared via Reddit, and is recreated here with the kind permission of the author.

Report Article

## User Feedback

There are no comments to display.

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 2
• 0
• 0
• 3
• 0

• 10
• 15
• 22
• 17
• 46
• ### Similar Content

• For #screenshotsaturday, the song of Fire and Ice can be experienced in SAMA if you bring your Pyroblaster into the cold depths of Aura.
• By thomedy
Okay i am building a super market game...

and im developing the ai for my npc...

i am thinking about the way that customers walk around a super market and it kinda has a fluid motion feel to it.... like they way they way in between aisles..
im very seriously considering writing a vector field for my  my path where the customer (npc) can  sense pivot points (end of aisle) and transition

another thought i had was just an intuitive.. if you went right last time... go left this time walking the entirety of the supermarket and starting over

i amg oing back and forth on this idea... what is the most realistic path and most efficient use of my memory

• Yesterday I've published my new game to google play!
I'm 16 years old and I will be very happy if you check my game and tell me what you think about it.
Best android game of the year! https://play.google.com/store/apps/details?id=com.HDRGames.FishTheFun
Swim into the depths of the sea! Jump the highest and reach the sky. Beware of enemy fish, birds and obstacles.
1. Discover fish as you play!
2. Buy fish to be able to play with them!
4. Complete 100 quests to win rewards!
5. Enter every day to receive daily rewards!
6. Enjoy the sea, and Fish The Fun.
Watch the trailer:

• Devlog #4 showing the most recent updates to the game I've been working on in my spare time for about 2 years now.

Any comments or suggestions are much appreciated!

• By asmit10
Read this first to not waste time
Hey everyone! I'm basically brand new to game dev, specifically programming which is what I care to specialize in. Currently i'm working on a 3D Tile-based tower defense game in Unity. The plan is to plan for primary monetization on mobile, but it will come to PC too. I probably lack the most skills in the art department, primarily graphics work, but it's not like my modeling is great either. That being said, my main focus is programming so if you read further below and find yourself interested in the project and have a different interest, please let me know!

Game Info
TD Game ala Bloons TD
Differences
Towers are based on tiles pre-placed on a grid (plan to add ability to buy tiles, so that tile scarcity can be more of a part of level design)
No Russian dolling of enemies, different enemies following a difficulty gradient
flying enemies that normally follow a different path
Misc
Branching, occasionally choice making upgrade branches for each distinctly unique tower. (thinking something like 15 unique upgrades per turret, though that would be tough to come up with)
Initially planning for 10 distinct level layouts not including an endless survival 'leaderboard' mode
Seems like it would be silly to not include easy / medium / hard difficulties, just need to think of a way to reward the player for doing so
Planning to have some long-term progression system. Maybe related to # of kills with a tower. Every 500 kills = 1% fire rate or something like that.
All current art and models are place holders, screenshots of the project can be provided if you show interest
×