1
\$\begingroup\$

I'm planing to write a game based on octagon tiles. Currently I'm wondering how many images I really need. That is something about graph theory, I know that, but not only.

I want to connect each side of the eight sides, but in some cases I also want to connect all eight sides or just two so the complexity grows immense. If I'm not totally confused that ends in 88 which is 2048. Well of cause there are already many dublicated e.g. left to right is equal with right to left. When I'm very tricky I can rotate the image of left to right which I rotate by 90° to get top to buttom. I'm sure there are quiet more things like like mirroring.

My question is now how many images do I really need?

enter image description here

Here is my basic idea as image, of cause it still has some problems, as you can see on my image too but I think it should not be too hard to find a simple solution for such cases.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ You know that octagons don't tile without adding little squares, or are you planning on leaving the gaps open? historichouseparts.com/pdshop/images/FXLMOWWT.jpg \$\endgroup\$ – Patrick Hughes Oct 26 '14 at 16:49
  • \$\begingroup\$ Since the tiles should been an overlay for the background this does not matter for me \$\endgroup\$ – rekire Oct 26 '14 at 17:04
  • 1
    \$\begingroup\$ @rekire It's really hard to imagine how this is supposed to work. An image would really help to visualize the problem. Could you maybe post a screenshot or when you aren't that far at least a mockup of how you plan to place your tiles in relation to each other? \$\endgroup\$ – Philipp Oct 26 '14 at 17:38
  • \$\begingroup\$ I really hate persons who downvote without an explanation. I'm just talking about math... No reason for downvotes IMHO, @Philipp wants an image for understanding my idea so find I added that resouce. \$\endgroup\$ – rekire Oct 26 '14 at 19:23
  • 1
    \$\begingroup\$ @rekire Thank you for the image. It is now a lot clearer what you are trying to do. \$\endgroup\$ – Philipp Oct 26 '14 at 19:28
3
\$\begingroup\$

If you write a 1 for a connection and 0 for lack of connection, and have 8 sides, then you can write out the configuration of an octagon as a bit string. I'll order them as east, northeast, north, northwest, west, southwest, south, southeast. If north and west are connected to neighbors and other directions are not, this would be written 0 0 1 0 1 0 0 0.

First question is, how many possibilities are there? There are 8 numbers, each with 2 possibilities, so that's 2^8 = 256 possibilities.

However, rotation and mirroring mean we can reuse some of them. I'm not 100% sure this code is correct, but I found that there were no mirrors to remove after removing rotations:

def all_sequences(n):
    if n == 1: return [(0,), (1,)]
    rest = all_sequences(n-1)
    return [x + (0,) for x in rest] + [x + (1,) for x in rest]

def rotations_of(seq):
    return [seq[i:] + seq[:i] for i in range(len(seq))]

unique = set()
for seq in all_sequences(8):
    for rot in rotations_of(seq):
        if rot in unique:
            break
    else:
        unique.add(seq)

print(len(unique))

It prints 36 different octagon neighbor patterns. Is there a mathematical way to compute this? Probably, but I don't know what it is. I found this entry in The On-Line Encyclopedia of Integer Sequences, if you want to read more.

There might be more ways to reduce the number of sprites, but I think 36 is the upper bound.

\$\endgroup\$
2
  • \$\begingroup\$ That is really interesting, after thinking about a while I guess you are right that mirrow operations can been replaced with rotations in my case. +1 so far I need to think a little more abut it than I will accept one of the answers. \$\endgroup\$ – rekire Oct 27 '14 at 11:04
  • \$\begingroup\$ While looking for something else unrelated, I found this page that has a visualization of the patterns: jasondavies.com/necklaces ; it shows that once mirrors are taken into account, the number drops from 36 to 30. \$\endgroup\$ – amitp Oct 30 '14 at 20:39
1
\$\begingroup\$

Unless you want to allow octagons to overlap (when you would, you would be in quite a lot more trouble), it is impossible for two adjacent edges (a diagonal and an orthogonal) to be both connected to another tile. This makes stuff a lot easier.

Separate each of your octagons into 9 tiles like this:

enter image description here

You need one set of tiles where the diagonals are connected and the orthogonals are not:

enter image description here

And one set where the orthogonals are connected but the diagonals aren't:

enter image description here

The center tile is identical in all cases. Also, the connected edge-tiles opposite of each other are identical in both of above images, but the unconnected edge-tiles aren't. So you need a total of 1+2+4+2+4 = 13 images.

\$\endgroup\$
1
  • \$\begingroup\$ I like your pagmatic answer (+1), it does not answer my question directly in scope of my question, it is much better ;) I'm thinking about if my octagon tile idea good or not, I'll ask another question about it... Maybe I'll accept your answer, I need to think a little about it. \$\endgroup\$ – rekire Oct 27 '14 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.