How do I create a deck of cards that generates a dungeon of an average particular size?

Question

I want to create a deck of cards where each card is a room in a dungeon. Each will have between 1-4 doors, one door per side of a card. This will create corners, T intersections, hallways, open rooms with a door on each side, and dead-ends.

How may I go about this (or what sort of math can I do) to show me how many cards of each number of exits to make (or how many of each type of intersection, preferably) so that a dungeon caps off after an average number of draws. Say I wanted a game to last 50 turns, I'd make a 50 card deck and want to know I'd draw at least 45 of them before there are no exits to connect on the board.

It wouldn't need to fit inside a grid, but limiting it's size to fit on a coffee table (instead of generating an overly horizontal or vertical bias) would be preferable. How would the math change if I were to fit it inside a grid, say 5X5 (max 25 cards), 5X9 (max 45 cards) or 10X10 (max 100 cards)? Assuming the edge of the grid would place a cap on an exit.

How do other games go about estimating this ratio?

I say cards, but the concept would be the same using square tiles or something similar.

Answer 1

This game mechanic introduces the problem of trying to establish the expected result of a dynamic series of events that can't be readily repeated. For common terms through out, I'll be using the following to describe the game pieces.

Tile   Doors   Effect
A      1      -1
B      2       0
C      3       1
D      4       2

Additional variables are:

M = Totel Deck Size
t = number of turns taken cards drawn
a, b, c, d = Number of tiles drawn of that type
A, B, C, D = Total Number of that Tile in the Deck

In the Worst Case, if you draw every other tile before you start drawing A's, you would need sufficient A tiles to close the open dungeon. For this:

A >= 3 + C + 2*D

This is because you are starting on the south edge of the map with 3 open doors (west, north, and east). For the tiles you draw, C adds 1 door, D adds two doors, and A subtracts 1 door. If this equation is true for your deck of tiles, than there will be no open doors left.

Not yet addressed is the total number of tiles, needed to provide for an game of t turns, but I'll get there. Crunching the permutations.

Answer 2

I've been working on an Excel sheet, and I think I'm ready to post it now. Here is the link, and you'll need to download it and enable macros.

Here's how to use it:

1. Enter the number of cards in the deck.
2. Enter the ratio of 3 exit to 4 exit cards. In the example image a ratio of 2 means that there are 2 3 exit cards for each 4 exit card. The 1 and 2 exit cards will be auto generated to complete the deck. For each 3 exit card one 1 exit card will be added, and for each 4 exit card two 1 exit cards will be added. Two exit cards are used to fill the rest of the deck.
3. Click the probability generation button (takes a little while to generate it all).

For each row (data in C2:F31) the Macro will generate 300 decks and randomly pull cards until all paths have closed (NOTE: I assume there is already a starting card on the table (not part of the cards in the deck) with 3 exits). The average, min, and max turns will be saved and displayed next to the row of input card counts, as well as graphed. I'll note the theoretical minimum number of turns is always 3, though I haven't had that generated yet.

There are several limitations to this approach. There is no bounding (i.e. a single path could use most of the cards and be very long) and there is no consideration for a loop in a path (this could terminate extra openings without needing a dead end, an example is a 2x2 of 4 opening cards that lose half their openings to each other instead of dead ends).

Playing around with the excel file will hopefully help you determine a ratio of 3 to 4 exit room cards, as well as a total deck size. It will provides several potential deck configurations, and details on 300 limited simulations of games played with them and how many turns the game lasts.

Answer 3

I doubt you can keep your dungeon to a small range of sizes if you are drawing randomly. Even if you start with an entry card with three exits, the next three cards you draw might be dead end rooms and you have a very small dungeon. A real difficulty is that placing a card only uses up one door and unless it is a dead end it adds at least one so the number of open doors wants to grow.

You could think about changing the mechanics. Don't have any dead end cards at all, just ones with 2,3, or 4 doors. Have an outer perimeter beyond which the dungeon cannot grow, but somewhat larger than the dungeon will be, maybe 8 by 12 or so. That will keep it on a reasonable table. Have a way to mark doors as not existing. If a door hits the perimeter it doesn't exist. As you place cards if a door touches the side of a card that doesn't have a door it doesn't exist. After you have placed as many cards as you want your dungeon to have rooms, block any doors that don't connect to anything.

Answer 4

You can't have it totally random, but you can make it random with slight boundaries.

This all depends on the number of doors left in the maze/Labyrinth/dungeon. You start with X on the first tile and every tile afterwards adds (number of doors -2) to the number. So every tile with only one door removes an open door from the maze while a tile with two doors doesn't Change the number.

So the only Thing you have to make sure to Close your dungeon is add at least as much 1 door tiles as you add doors throughout the game. So for example if you start with a 4 door tile (4 open doors) and have another 4 door tile and 5 three door tiles in your pile, you have to include 9 one door tiles to Close up your maze at some Point during the game. If you add more one door tiles, the end lowers, because with even numbers the last one door tile could be drawn on the last Card and statistically speaking in our example it will probably happen in the last ninth of the game. If you add two more one door tiles without adding 3+ door tiles, the game will probably happen in the ninth eleventh of the game (say you have 55 tiles, it would probably happen between tile 41 and 45).

This is only statistics and the most likely, but in rare cases the fourth Card will Close up the dungeon or the third to last Card will Close up the dungeon.

This can be avoided by sorting out some Cards, dividing the deck into stacks of equal sizes and then adding back the sorted out Cards to the parts, shuffling them and then putting part A on part B and so on.

Another Problem would be doors that hit walls on other Cards and it's REALLY tricky to avoid that.

IF you want a really tight control over where the maze should go to, I'd advise starting on the left and only allowing up/down/right expansions, so you can never go back left. If you then make sure that three door tiles come before one door tiles, you can make exactly sure when the maze will Close up.