title: Procedurally generating dungeons using some rooms from a given collection
body: <p>Most attempts at procedurally generating dungeons I have stumbled upon do space out areas that will be rooms and connect them will corridors and hallways but what about instances where you have a collection of possible rooms in various dimensions and want to generate a dungeon that uses some of these specific rooms without those corridors and connections? To answer this question I found <a href="https://youtu.be/GcM9Ynfzll0?t=5m19s" rel="nofollow noreferrer">this particular video on the topic of generating levels in Path of Exile</a> (~5:20 - ~7:20 about the dungeon part I am referring to) which left questions open on how to technically implement the algorithm described.</p>
  
  <p>In general I understand the idea but I am struggling to figure out how this would be translated into code (most efficiently) and therefore here are a few questions:</p>
  
  <ol>
  <li>When he shows how the entire level is sliced up I could not come up with a graph that would allow to represent this structure. My naive approach would be to have the entire level consist of <code>1x1</code> rooms and arbitrarily merge nodes in the graph to form rooms of valid dimensions (valid = there is a predefined room that can be inserted there later on). Or is it better to work with a two-dimensional array and fitting rooms of specific dimensions and then building a graph out of it?</li>
  <li>Coloring the rooms should be just assigning random distances (in a given interval) to edges of connected nodes and just applying Dijkstra to find the sequence of rooms from start to finish I presume?</li>
  <li>When he adds branching rooms I noticed that they do not allow another alternative path to the exit (which could be random of course) but how would one implement the branching? Just a recursive traversal with diminishing chances of continuing deeper into the graph?</li>
  </ol>
  
  <h3>Remark</h3>
  
  <p>Please notice that the collection exceeds the number of slices in the level and that it is <strong>not</strong> intended to define the number of rooms in the level beforehand. The number of slices should be arbitrary and the rooms randomly placed into the slices.</p>
  
  <hr>
  
  <h1>Description of the algorithm in the video</h1>
  
  <p><strong>Step 1.</strong> Place a start and end room arbitrarily into the level (presumably with a given minimum distance to prevent degenerate layouts):</p>
  
  <p><a href="https://i.stack.imgur.com/PEVvw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/PEVvw.png" alt="enter image description here"></a></p>
  
  <p><strong>Step 2.</strong> Slice the entire level into an <strong>arbitrary</strong> number of areas that have exactly the sizes of your predefined rooms from the collection:</p>
  
  <p><a href="https://i.stack.imgur.com/QlK5t.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/QlK5t.png" alt="enter image description here"></a></p>
  
  <p><strong>Step 3.</strong> Assign each room a random weighting/distance which is depicted with colors in this example:</p>
  
  <p><a href="https://i.stack.imgur.com/H0rxd.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/H0rxd.png" alt="enter image description here"></a></p>
  
  <p><strong>Step 4.</strong> Find a shortest path to get a nonlinear path from start to end:</p>
  
  <p><a href="https://i.stack.imgur.com/OBQXz.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/OBQXz.png" alt="enter image description here"></a></p>
  
  <p><strong>Step 5.</strong> You have your basic layout with a single successful path in which you can place random rooms of corresponding dimensions that have to be connected with appropriate doors:</p>
  
  <p><a href="https://i.stack.imgur.com/dkjTq.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/dkjTq.png" alt="enter image description here"></a></p>
  
  <p><strong>Step 6.</strong> Finally, add some branching rooms:</p>
  
  <p><a href="https://i.stack.imgur.com/vU1Z9.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/vU1Z9.png" alt="enter image description here"></a></p>