how do you do a 'random dungeon room connectivity check'?

[wolph42]

The cryptic title says it all. But let me clarify.

The dungeon builder 2 (link in sig) can create a random dungeon by piecing together 6x6 (grid) tiles (effectively 3x3 path tiles). The *only* thing the generator checks however is whether an open space is connected to an open space, dit for 'closed' space and ofcourse the edges, this to prevent having a pathway ending in a wall. This works nicely and renders nice looking dungeons, however there is no certainty that all 'rooms' are accessible and there is also no way to tell how to get from one end of the dungeon to the other end (nor whether there is a connection between those two ends at all).

My question: how can you determine
1. whether all open spaces can be accessed from each room
2. how to determine whether 2 ends of the dungeon are connected (this question is redundant though as soon as 1 is solved).

So how does it work?
The dungeon is first 'virtually' rendered simply in a list with rows and columns where each cell is a representation of a dungeon tile e.g a 2x2 tile dungeon would virtually look like:
Undecided dungeon:
tX00000XX, t0000XXX0
tXXX00000, t00XXX000
is turned into a 'random' dungeon:
t00000010, t00000000
t10100000, t0000100

Here is 0=Wall; 1=Path and X=Either wall or Path

So What does "t10100000" mean? Each (binary) number represents the edge of the tile so if we label those postions: t12345678
then you can read it as:
1=East edge
2=North East corner
3=North edge
4=North West corner
5=West edge
6=South West corner
7=South edge
8=South East corner.
Have a look at tile way bottom right of this picture, here you can see the positions

picture

Now this leaves the centre undecided. I've already solved this issue by storing whether the tile centre is open or closed by a property on the tile.

Given this however you thus have a dungeon which looks like this:

Code: Select all

t00000010, t00000000 
t10100000, t0000100

now how do I determine whether there is a path between the South edge of tile 1 and the West edge of tile 4?
The above configuration looks like this:

Code: Select all

X=WALL ; O=PATH/OPEN ; ?=UNKNOWN (known when the actual tile is chosen, which is also random)
XXX XXX
X?X X?X
XOX XXX

XOX XXX
X?O O?X
XXX XXX
where
XXX
XXX
XXX
is one tile consisting out of 9 areas that can either be open or closed (path or wall)

The centres are 'known' as soon as the tile that matches e.g. t00000010 is chosen (which usually are several different tiles, some with an open centre and some not). As soon as this is done you can simply retrieve the property.

Any comments, questions, suggestions?

[aliasmask]

Rather than tiles, unless you're building a maze I would focus on rooms and setting paths to the rooms. Here's an image for some ideas.

Rooms were randomly placed on 5x5 grid but spaced to fit a 9x9 grid for paths. Then I randomly determined exits. I then noted where a room was next to another room with red dots. I then put green dots when surrounded by red dots. I connect any green - red - green combos. Put yellow dots when 2 or more red dots near. Put a blue dot when room and yellow dot is near. Connect all rooms going through red dot but not passing through green line. Rooms that don't connect go to closet room and/or exit (randomly determined if multiples).

This gives you a basic pathing system. As for the transitions, the rooms can connect directly or though a hall. Green lines can potentially hold secret doors. Just some random thoughts.

[wolph42]

What your basically saying is that i first randomly generate a dungeon and then replace the result with the tiles.

Let me elaborate. The tiles I have are 9x9 grid size but you could use them as 3x3 type tiles. When you random generate a dungeon according to your method you could hack the result in 3x3 pieces, see where wall and path is and apply the correct tile 3x3 to that part.

This however will immensely limit the choice of dungeon types because:
1. i dont have ALL permutations of tiles if you include the centre (open or closed). I only have all permutations for the edges and corners.
2. i have quite a few 'cardinal sets' which means that only the edges (so N,W,E,S) can be paths and the rest is wall. This means that you can't apply that set to a fully random generated dungeon.
In short: i don't have the tiles to do it through that method.

Actually I have one set that has ALL permutations, which i created to have a fully available photoshop template and method to import them into MT. This one set however is incredibly boring as i only used 2 textures (road and pavement).