A Labyrinth Generation Algorithm 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: giphy.mp4 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 Randomly Place rooms within the defined area Attempt to connect all rooms together in a large 'chain' Starting with random rooms, make smaller 'chains' of rooms within the network Prune room connections from rooms that have more connections than attach points Go through all room connections and connect actual attach points Use A* pathing to create corridors between the attach points Mark all of the corridors onto the grid 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: giphy2.mp4 And another 200 room demo, with no speed increase: giphy3.mp4 Note: This article was originally shared via Reddit, and is recreated here with the kind permission of the author. https://ift.tt/eA8V8J

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: giphy.mp4 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 Randomly Place rooms within the defined area Attempt to connect all rooms together in a large 'chain' Starting with random rooms, make smaller 'chains' of rooms within the network Prune room connections from rooms that have more connections than attach points Go through all room connections and connect actual attach points Use A* pathing to create corridors between the attach points Mark all of the corridors onto the grid 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: giphy2.mp4 And another 200 room demo, with no speed increase: giphy3.mp4 Note: This article was originally shared via Reddit, and is recreated here with the kind permission of the author.

from GameDev.net https://ift.tt/2U9jbcx