The dungeon should not be a fully connected grid

[kmamal]

Current Behavior:

The dungeon is a grid. All rooms are connected with their neighbors in the 4 cardinal directions. It is impossible to choose a wrong path, or encounter a dead-end.

Desired behavior:

The dungeon should look more like an actual maze. Desired features include:

1. The position of the Entrance Room and Boss Room should be randomized.
2. Not all neighboring rooms should be accessible from one another.
3. Dead-ends should be possible
4. [advanced] Mazes that can't be solved by application of the left-hand rule should be possible.

[kmamal]

I am going to use ASCII graphics to visualize dungeons. This is the current state of dungeons:

E--#--#--#
|  |  |  |
#--#--#--#
|  |  |  |
#--#--#--#
|  |  |  |
#--#--B--#

E = Entrance B = Boss # = Room | and -- = Corridors

Right now the entrance is always at 0,0 and the boss room in the third place of the last row.

[kmamal]

A simple algorithm

As a first step we should implement a simple maze algorithm:

Step 1: Randomize Entrance and Boss

Any room in the first row can be the Entrance. Any room in the last row can be the Boss. Some examples:

#--#--E--#        #--#--#--E
|  |  |  |        |  |  |  |
#--#--#--#        #--#--#--#
|  |  |  |        |  |  |  |
#--#--#--#        #--#--#--#
|  |  |  |        |  |  |  |
#--#--#--B        B--#--#--#

Step 2 : Use corridors

In the current implementation all neighboring rooms are connected with one another by default. It should be the other way around: No room connects to any other room, unless there is a corridor between them. This is what such a dungeon would look like:

#  #  E  #

#  #  #  #

#  #  #  #

#  #  #  B

Use whatever data structure you prefer to store corridors. As an initial exercise, try to reconnect all neighboring rooms with each other using corridors, so you have the initial fully connected grid.

Step 3: Turn the corridors into a maze

This is the most difficult step. Most maze generation algorithms require knowledge of Graph Algorithms which we have not dealt with yet. Here is an initial simple algorithm:

1. Start with the entrance.

   
     v
   #  #  E  #

B

2. Select a random room in the second row (marked X):

  v

E

X # # #

B

3. Connect rooms in the first row until you are directly above the room of the second row:

v

--#--E

X # # #

B

4. Connect the two rooms vertically:

--#--E

|

X # # #

B

5. Repeat until you have reached the last row:

--#--E

|

--#--#--

     |

--#--

|

X # B

^

6. If the room that was randomly selected for the last row isn't the boss room, connect it with the boss room:

--#--E

|

--#--#--

     |

--#--

|

--#--B

     ^

This should be enough for a start.