How to make sure every tile connects.

[Ex]

I keep hearing about people who are having problems with their dungeon generator not connecting a bunch of rooms. So, here's an easy way to make sure that everything connects. First, you'll need an array of integers the size of the dungeon. Fill this array with the number -1 to start. Number every tile the player can walk on sequentially using the array, such that every tile that the player can walk on has a different number in the array.

Then loop over the array repeatedly. Any location in the array where one number is next to a different number, change the location's number to the different number. Further, change all places in the array that contain the location's old number to the new number. Don't change any numbers to -1 under any circumstances, ever.

Once that's done, find any two different numbers on the map, and connect those two locations. Then change every tile that contains the first number to the second number. Do this until there are no different numbers on the map. If you want a really good map, I suggest always picking the two closest different numbers, instead of picking two at random. Again, never pick any tile that has a -1.

Congratulations, every tile on your map is now guaranteed to connect. Here's a small example of how this goes:

Code: [Select]

Starting with:

#...#
#.###
#.#.#
###.#

First we number all the empty tiles, and place -1 anywhere we can't walk (On all the #s in this case). To make things look nice, I'm going to leave those as # instead of -1. Here's what we have after:

#123#
#4###
#5#6#
###7#

Now anywhere where a number is next to a different number the old number is changed to the new one. Here's an example in a number of steps:

#123#
#4###
#5#6#
###7#

#113#
#4###
#4#7#
###7#

#111#
#4###
#4#7#
###7#

#444#
#4###
#4#7#
###7#

Now we chose any two different numbers and connect them with some kind of hall, anything will work as long as those two spots are guaranteed to be connected.

#444#
#4#.#
#4#4#
###4#

And viola! All parts of the map are connected :)


[Vanguard]

That's not a bad idea.

[Darren Grey]

I must say I much prefer the simplicity of the traditional floodfill algorithm.  It is likely faster too (since you tend to use boolean checks rather than integer calculations).  The process:

Step 1: Choose an initial passable tile to work with - say the down stairs, or a random floor tile.
Step 2: Mark square as "connected" (a specific boolean flag for this purpose).
Step 3. For every square surrounding the last square, IF it's a passable tile AND IF it's not already marked as connected THEN repeat step 2.
(conditions are important to make sure the recursion eventually stops)

That's all there is to it - simple, elegant and quick.  If you want all of your dungeons to have no diagonal connections (so you can always use the arrow keys to move) then have step 3 only check the squares in the 4 cardinal directions instead of all 8 adjacent squares.

[Ex]

I must say I much prefer the simplicity of the traditional floodfill algorithm.  It is likely faster too (since you tend to use boolean checks rather than integer calculations).  The process:

Step 1: Choose an initial passable tile to work with - say the down stairs, or a random floor tile.
Step 2: Mark square as "connected" (a specific boolean flag for this purpose).
Step 3. For every square surrounding the last square, IF it's a passable tile AND IF it's not already marked as connected THEN repeat step 2.
(conditions are important to make sure the recursion eventually stops)

That's all there is to it - simple, elegant and quick.  If you want all of your dungeons to have no diagonal connections (so you can always use the arrow keys to move) then have step 3 only check the squares in the 4 cardinal directions instead of all 8 adjacent squares.

This doesn't ensure that connections are made between all areas of the dungeon, however The main point of my algorithm is to ensure that every tile that the player should be able to reach, he can reach through connecting unconnected parts of the dungeon.

Also, a flood fill is significantly slower than my algorithm since it requires more loops over the dungeon map.

[stu]

This doesn't ensure that connections are made between all areas of the dungeon, however The main point of my algorithm is to ensure that every tile that the player should be able to reach, he can reach through connecting unconnected parts of the dungeon.

Also, a flood fill is significantly slower than my algorithm since it requires more loops over the dungeon map.

actually your routine sounds really slow with many loops over the dungeon map. I'm also not fond of connecting disconnected pieces of the dungeon, mostly because I'd rather rely an algo that builds it all connected in the first place. Connecting random disconnected dots all over the place may not make very interesting dungeons (I could see lots of open space etc but I guess it depends on how you do it overall)...

[rdc]

A flood-fill would be faster since you are only visiting a tile once, not multiple times. As Darren has suggested, simply flood-fill the map with some value (TRUE, 1, whatever) and then scan the map after the flood-fill. Any passable tile that does not have flag set means an unconnected map. Simple and fast.

The way I build my maps is to place rooms and then connect. This gives you the option to change the look and feel of the dungeon by changing the connection algorithm. To ensure connected maps, you use a "pick list" for the rooms. As each room is built, add it to the pick list. Once all the rooms are added, select two rooms and connect them. Mark the first room connected; you are done with it. Pick a new room. Connect the new room to the second room in the previous pick. Mark the previous second room as connected. Continue through the list until all rooms have been connected. You have a connected map.