Jump to content
  • Advertisement
  • 08/28/19 12:26 PM

    A Labyrinth Generation Algorithm

    General and Gameplay Programming

    GameDev.net

    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 or sign in to comment

    You need to be a member in order to leave a comment

    Create an account

    Sign up for a new account in our community. It's easy!

    Register a new account

    Sign in

    Already have an account? Sign in here.

    Sign In Now

  • Advertisement
  • Game Developer Survey

    completed-task.png

    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!

    Take me to the survey!

  • Advertisement
  • Latest Featured Articles

  • Featured Blogs

  • Advertisement
  • Popular Now

  • Similar Content

    • By RoKabium Games
      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
       
    • By HDR Games
      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.
      It takes a minute to download and you won't regret it. Please let me know what you think in the comments.
      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!
      3. Improve your best score to beat your friends'!
      4. Complete 100 quests to win rewards!
      5. Enter every day to receive daily rewards!
      6. Enjoy the sea, and Fish The Fun.
      Link to HDRGames website: http://hdrgames.sytes.net
      Link to HDRGames Instagram: https://www.instagram.com/hdr.games
      Watch the trailer: 
       



    • By COUNTING DEMON STUDIOS
      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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!