Tiling Algorithm/Data Structures?

Question

I'm thinking of creating a program to let me play or solve slitherlink puzzles, like on krazydad.com. It consists of tiles of 4, 5, 6, 7 and 8 sides. All but the seven sided tiles seem to have sides with the same length, with the sides between two seven sided tiles (and therefore connecting five-sided tiles to 4 sided tiles) having sides of approximately 70% of the normal length. As you can see in the picture below, octagons are surrounded by alternating pentagons and hexagons. These are attached to others a by the far sides of the hexagons. Attached to the tips of the pentagons are smaller lines connecting to squares connecting to other groups. Around the squares are then formed seven-sided figures with two short sides. I think the outer edge is defined by just omitting tiles that are too far away from the center.

For a data structure I think I need a graph connecting all nodes. I can let the user click to place a solid line on the closest link, and I can check for loops or too many lines entering a node fairly easily. I'll also need to create tiles and associate lines to them, with inner lines being assigned to both tiles, but treated as one line.

As for setting it up, I am thinking of manually figuring out the points and defining the minimal set of repeated tiles (1 8, 4 5, 4 6, 4 7 and 1 4), then placing them next to each other. When placing, I would check for existing close points to each one I'm placing and combine them if found. Then I would need to check for duplicate lines and merge them as well.

Is there an easier or cleaner way to A) generate the tiling or B) merge the nodes and links when doing my tiling?

Answer 1

some observations that might help:

• if you join the centres of neighbouring polygons you have a delaunay triangulation (1).

• the dual (2) of the delaunay triangulation is the graph above (with slightly different edge lengths, but you can adjust that if necessary)

• there's a discussion here (3) of how to generate graphs from delaunay triangulations

so, putting that together, you could:

• generate the centres of the tiles (see below)

• construct the delaunay triangulation from the tile centres (by joining neigbours).

• find the dual to get the graph you want (the process of finding the dual should be supported by a good graph library)

to generate the pattern of tile centres, take the minimal set and start with the centre 8. for each 90 degree rotation about there, add the (rotated) minimal set (plus an 8 in addition to the one you're rotating around), removing duplicates. then do the same on the 8s that you have added (either recurse or use a stack).

once you have the centres, i'm not sure what the best way to connect neighbours would be - you want some efficient way of generating a set of candidates. but it's not a hard problem, just fiddly (a "fancy" solution would be quadtree or spatial hashes, but just a crude binning would probably be enough).