A dungeon is connected if there is a way to get from every room to every other room. We always want to generate a connected dungeon.
What we're going to do here is make a Set of Sets. Suppose there are n rooms. Before you start digging tunnels, make a new Set([ new Set([0]), ... new Set([n-1]) ]). This kind of set is called a partition, because we've taken the set [0, 1, 2, 3, 4... ] and split it up into smaller sets that have the same elements in total.
Now, every time you successfully dig a tunnel, modify the list of sets. Suppose there are 5 rooms, so we start with
[ [0], [1], [2], [3], [4] ]
and you successfully dig a tunnel from room 2 to room 4. Find the sets that contain 2 and 4. If they're already in the same set, then we already knew that room 2 was reachable from room 4. If they're not, then now every room that is reachable from room 2 is also reachable from room 4, so add all the members of the set that contains 4 to the set that contains 2, and then delete() the set that contains 4 from the outer set. We'd end up with sets:
[ [0], [1], [2, 4], [3] ]
Now suppose we successfully connect 1 and 3. Merge the sets containing 1 and 3, and delete one of them:
Now suppose we connect 2 and 3. Merge the sets and delete one of them:
And finally once we connect 0 with anything, we end up with
Once the outermost set contains only one element, every room is connected to every other room, and we can stop digging tunnels. (We don't have to stop digging tunnels, but we can choose to.)
It is possible for the randomly generated dungeon to end up in a situation where one room cannot be connected to any other room with either a straight or one-bend path. Modify the tunnel digging algorithm to give up and start over completely with all new rooms if you don't attain a fully connected dungeon after, say, a hundred tries.
A dungeon is connected if there is a way to get from every room to every other room. We always want to generate a connected dungeon.
What we're going to do here is make a
SetofSets. Suppose there are n rooms. Before you start digging tunnels, make anew Set([ new Set([0]), ... new Set([n-1]) ]). This kind of set is called a partition, because we've taken the set[0, 1, 2, 3, 4... ]and split it up into smaller sets that have the same elements in total.Now, every time you successfully dig a tunnel, modify the list of sets. Suppose there are 5 rooms, so we start with
and you successfully dig a tunnel from room 2 to room 4. Find the sets that contain 2 and 4. If they're already in the same set, then we already knew that room 2 was reachable from room 4. If they're not, then now every room that is reachable from room 2 is also reachable from room 4, so add all the members of the set that contains 4 to the set that contains 2, and then
delete()the set that contains 4 from the outer set. We'd end up with sets:Now suppose we successfully connect 1 and 3. Merge the sets containing 1 and 3, and delete one of them:
Now suppose we connect 2 and 3. Merge the sets and delete one of them:
And finally once we connect 0 with anything, we end up with
Once the outermost set contains only one element, every room is connected to every other room, and we can stop digging tunnels. (We don't have to stop digging tunnels, but we can choose to.)
It is possible for the randomly generated dungeon to end up in a situation where one room cannot be connected to any other room with either a straight or one-bend path. Modify the tunnel digging algorithm to give up and start over completely with all new rooms if you don't attain a fully connected dungeon after, say, a hundred tries.