Labyrinth idea revisited, math problem this time

[Rhoderic]

Here's me again, still going on about my labyrinth idea. I think I've got the pillars thing sorted, but I've changed my original plans somewhat. The current plan is to use bigger and fewer tiles (probably 7 x 7 tiles that are 12cm square), and put several "passages" on each tile. Now my problem is trying to figure out how many possible configurations there are for these tiles. I suppose the math is quite easy really, but everything is relative and I'm relatively crap at math

Basically, the whole tile will have eight possible passages leading out at the sides, and four possible passages leading between the four quarters of the tile. Like so:



(I hope the Prof will forgive me for using my Gallery privileges for uploading these pics, I just need some way to illustrate my plans, and I'll delete them again once this thread has died off)

That tile would basically be an "empty" one with no walls (only a pillar at each corner for show). A more practical one that has some of the passages "closed" (in other words, being blocked off by walls) would be something like this:



So I'd like to know the total number of possible configurations. It's not quite that easy though: I also want to exclude all possible duplicates that could be had by rotating any other tile. For instance, the tile below is obviously the same as the one above, only rotated 90 degrees:



In honesty I don't really "need" to know this in order to proceed with my project, but I want to. I also realize that in the time I've spent writing this message and drawing those pictures, I might have been able to calculate this myself, but math is really not my forte. I was hoping that maybe someone here is really good at math and could calculate this in a minute or two

BTW, I don't suppose that there's some easy way to have my computer visualize all the possible configurations? Something that doesn't involve programming it from scratch? A bit much to expect maybe, but it doesn't hurt to ask.

[Dolmot]

Well, the upper limit should be 2^12 = 4096, because there are 12 sections which may be "on" (open) or "off" (closed). As you have correctly observed, rotations will decrease the number. I can give you the exact count, but first I'd like to check a few things. The foremost question is whether the internal structure of a tile matters or is it only about access from entrance A to B. For example, there are something like 60 different configurations where no passage leads to another. They're all variants of dead ends, internal squiggles and unreachable inner areas. Here's a few which won't let you go anywhere:

Code: [Select]

.......   .......   .......   .......   .......
.     .   . | | .   .   | .   .     .   .   | .
.-+-+ .   .     .   .-    .   .-+-+ .   .     .
. | | .   .     .   .     .   .     .   .     .
. +-+ .   .     .   .     .   . +-+-.   .     .
.     .   . | | .   .   | .   .     .   . +-+ .
.......   .......   .......   .......   .......
Are these equivalent for your game? It surely affects the number greatly. This alone could be either only one tile or ~60 different ones.

[Rhoderic]

If I'm understanding your diagrams correctly, then I'd say that the "dead end" tiles do count. However, the ones with "inner" areas that are completely unreachable do not. Good point, I had missed that completely.

[Dolmot]

To elaborate, what I need to know is whether these four tiles are functionally identical or not.

Code: [Select]

.......   .......   .......   .......
.     .   .     .   .     .   .     .
.-+   .   .-+-+ .   .-+-+ .   .-+-+ .
.     .   .     .   .   | .   . | | .
.     .   .     .   .   + .   . +-+ .
.     .   .     .   .     .   .     .
.......   .......   .......   .......
There's only one entrance, followed by varying amounts of inner area. The tile itself doesn't lead anywhere, but its inner structure can take many forms.

Another example. Are these identical?

Code: [Select]

.......   .......   .......   .......
. |   .   . |   .   . |   .   . |   .
. +   .   . +-+ .   . +-+ .   . +   .
. |   .   .   | .   . | | .   . |   .
. +   .   . +-+ .   . +-+ .   . +-+ .
. |   .   . |   .   . |   .   . |   .
.......   .......   .......   .......
This time you can move through the tile from one edge to another. The difference between these variants is in how many inner sections you can reach. Is it important, or do these all count as the same route from one doorway to another?

[Rhoderic]

Oops, another thing that had eluded me

Presume they'd be identical.

Thanks for helping me out.

[Dolmot]

One more question... (This may be disappointing as you probably wanted answers, not more questions.)

If I remember correctly, in that popular labyrinth game the goal was to reach different tiles. Does it make any difference if a tile has a dead end path from some direction, in contrast to having no entrance at all. Example:

Code: [Select]

.......   .......
.     .   .     .
.-+-+-.   .-+-+-.
.     .   .     .
.     .   . + + .
.     .   . | | .
.......   .......
The lower two quarters may be entirely blocked, or they may have short corridors leading to them from below. The leftmost tile cannot be reached at all from that direction, the rightmost can. It doesn't form a route to anywhere at that point. However, it might become important if you can stay on a tile and it gets moved around later. Do you want these dead end options counted separately from entirely blocked sides?

[Rhoderic]

Don't worry about disappointing me, I'm not in a hurry to get the answer and I realize these calculations might be taking up your valuable time. Given the fact that I don't really "need" the answer, I certainly wouldn't hold it against you if at any point you want to quit. Frankly I didn't expect the problem to have this many conditions

To answer your question, yes the dead end options should be counted separately. As you say, a figure could stay in one of those dead ends and wait for it to connect with some other advantageous tile. Or the figure might get trapped there if another player decides to slide in a tile that blocks the only exit. It's all part of the game. Besides, those dead ends are good spots to place items/clues that the players have to retrieve.

Actually, this illuminates yet another thing that I've missed completely: I don't intend to "block in" any quarter of any tile. So every quarter should have at least one opening (leading either out from the tile, or to an adjacent quarter of the same tile). Does this complicate things too much?

Again, I really am sorry if this is taking up too much time for you.

[Dewbakuk]

It's sad but I'm finding this thread incredibly interesting 

Seems to me that Dolmot is having fun working this out too, besides, he gets to point out how clever he is at the end of it 

[Dolmot]

We have audience. Would this have potential as a TV show? Mathematicians solve your game design issues.

This message would be the annoying cliffhanger then, because I'm leaving early tomorrow for an intensive gaming weekend (both miniature and board). As a side effect, I'll have plenty of idle time during the travel to think about this problem.

To reiterate the rules:

1) There are 12 corridor sections in each tile, either open or closed, as seen in the first illustration.
2) Each crossing point within a tile, also known as "a quarter", should be ultimately accessible via some path from an edge.
3) A corridor does not have to go through a tile. Even a dead end provides space for movement, and access to at least one quarter as well.
4) Rotationally symmetric sets of tiles only count as one.
5) Tiles are also considered redundant if they provide completely identical access to their own quarters and the neighbouring tiles.

And the question is, how many different tiles can be constructed under these rules. Everyone is welcome to submit an answer. We'll check them on Monday (maybe). See you next week.

[Commander Vyper]

Victoria Lamb has already produced a Labyrinth styled games with a resin board with interchangable wall sections, probably worth checking out, it's very nice.



Probably exactly what you're looking for.

The Commander

[Rhoderic]

Actually we already talked about that in the previous labyrinth thread. While I'm really intrigued by the Labyrintus game (and somewhat apprehensive about how much it's going to cost, because I really want to buy it when it's released), it's not quite what I'm looking for, for this project. First, I think the board is too small for my purposes. It seems to be about 12" by 12". Second, the kind of labyrinth I'd like to make uses sliding tiles instead of moveable walls. I just think sliding tiles would make for a more fun game.

Thanks for the suggestion though. Again.

[Dolmot]

Tuesday already...no other answers? Well, I say 537.