A "Spectre" is a new shape.
Yes, I did say new shape! It is pretty incredible that there can be any such things as new shape, I mean, how do we not know all the shapes already? Also, to be fair, it is a reasonable bet that the ancient Greek's knew of this and forgot to write anything down. But certainly in my life time - this is indeed a new shape. Discovered in 2023!
So what makes it special? There is, of course, a whole wikipedia article on what is called The Einstein Problem, but I'll try and explain it simply.
This shape tessellates. Basically that means you can tile your bathroom wall with it - the shape fits together with itself to cover a surface with no gaps. Lots of shapes do this, squares, triangles, hexagons, and so on. You can rotate the tiles if needed (e.g. for triangle you have to). There are many that do not, such as pentagons, and circles, etc. You cannot tile a wall with circles without leaving gaps.
So what? Well, most tessellating shapes create a repeating pattern. Hexagons make a familiar honeycomb pattern for example. But with the Spectre you can make a pattern that does not repeat. In fact, you cannot make a repeating pattern with it at all, no matter how hard you try. Yes, some groups of tiles may appear the same in other places but even then these do not form a regular pattern, at any level.
There is some debate over the rules - this was, it seems, a competition. The rules allowed you to turn a tile over. The researchers created a shape called the "Hat" which worked but some of the tiles had to be turned over. People, quite reasonably, said "If I want to tile my bathroom wall I have to buy two sets of tiles". So the researchers came out with the "Spectre" a year later, and that works without turning over tiles. In fact if you can turn over titles, you can make a repeating pattern with it.
But basically, until this was discovered, nobody even knew if a forced aperiodic tessellating monotile shape even existed. That is what makes it a new shape.
You can now tile your bathroom wall with one type of tile and it is a non repeating pattern.
But how?
Well, you could just try placing randomly where they fit, but you quickly end up with gaps that are not Spectre shaped, and have to back track and try again.
However, there is an agorithm, published by Simon Tatham, here. I'd like to thank him for his work, but I have a word of caution if you want to use his paper. I also appreciate, as a coder, the counting from 0 all the way through.
It just so happens I had an idea how to use this shape, for reasons which will become apparent later this year I hope. So I wanted to code generating a surface covered with these tiles. Long story short - here it is, open source on Codeberg.
But this took me a couple of days, which is a long time for me, so let me explain the issues.
The principle is simple, a recursive set of meta tiles are groups of tiles in a pattern (represented has hexagons in the paper).
You can start at the top, pick a meta tile from a set of 9 different types, and that tells you how to place 7 or 8 subtitles in a honeycomb pattern, and their types (from the set of 9) and orientation. You repeat as far as you want and the last level you actually have Spectre tiles not hexagons.
You can also start at the bottom with a Spectre, and decide which of the meta tile types it shall be at random. You can then find a meta tile which includes that type, and it tells you the neighbouring Spectre tiles to place. This is then a meta tile which you can again decide is part of a higher level meta tile randomly, and that tells you what meta tiles to place for its neighbours and work down to Spectre tiles below. So you have one upward process in a loop, and at each point have a recursive downward process placing 6 or 7 neighbours at each level down. This is the approach I took.
If I started at the top I would pick one of 9 meta tiles, and maybe one of 12 orientations, and that would be it, the Spectres under that are determined by the algorithm and not any more random. By starting at the bottom, I pick one of 12 orientations and place the first tile, and pick one of 9 meta tiles, but at each level as I go up I get to pick which higher meta tile it is in, and in some cases which of two sub tiles it is. This is random at each level and makes for a much more randomised final output.
So what was confusing me?
The distraction that took me most of the time trying to get this working is the rather excellent graphic representations in Simon's paper. They show a hexagon meta tile substituted with 7 or 8 joined hexagon meta tiles, and shows a hexagon meta tile substituted with a Spectre tile. These diagrams have specific orientation, and rotation, so one is lulled in to a sense of simplicity that you are literally replacing one hexagon with a set of them, each with specific orientation.
Looks pretty, and simple, but this is NOT the case!
The diagrams are actually simply a mapping, a look up table for what gets joined to what and what side. The hexagon has 6 sides, basically at the lowest level each Spectre is joined to exactly 6 other Spectre tiles (there is a special case for that G meta tile where it is two Spectre tiles, the others are all one, just to add to the fun). So you have each Spectre tiles as having 6 connection sets of edges - but these are not simple, as each of the 9 types of meta tile is a Spectre with a specific set of edges for each of the 6 sides.
The numbering is the key - on the yellow tile there is a side 0, which is actually the three edges 8, 7, and 6 (marked 0.0, 1.0, and 2.0). On the purple, there is a side 4, which is edges 13, 12, and 11 (marked 0.4, 1.4, and 2.4). But side 4 on the yellow tile is only sides 12 and 11 (marked 0.4 and 1.4). But you a see yellow side 0 and purple side 4 would fit together. Some of these 6 sides are one edge (see purple side 3), but can be as many as 6 edges in some cases. Each of the 9 meta tiles has a specific set of edges making up the 6 joint points to other tiles. Each similarly has a set of edges on the hexagon pattern, which is different for each type.
So in practice you connect the defined edges, and they end up nothing like hexagonal tiles. In fact they twist and distort all over the place. The graphical representations are really not helpful in my view, sorry. Also, I would have numbered side.subedge so 1.0, 1.1, 1.2, not 0.1, 1.1, 2.1, personally.
Once I grasped that logic, the code became simple. As I say, you start with one Spectre, and connect neighbours. You only need to know the specific 6 sets of edges for that tile. Then when you use the meta tile rules you know which set of edges that connects to on the neighbouring Spectre. It is pretty simple to then align the new Spectre connected on that edge. Having placed the 7 or 8 Spectres to make a meta tile, you then just need to know the 6 joining points on that meta tile, which are themselves 6 sets of specific Spectre tile edges within the meta tile.
One issues is these connecting sides are several edges, so I actually picked one end, e.g. for yellow it would be 8, 5, 2, 0, 13, 12, 10, and for purple it would be 8, 5, 3, 0, 13, 10 as the 6 outgoing edges. These are the first edge of each side (numbered 0.x). When placing a Spectre next to one of these, you pick the other ends, so 6, 3, 1, 13, 11, 9 for yellow and 6, 4, 1, 0, 11, 9 for purple, the last edge for each side.
So connecting yellow side 0 to purple side 4 you connect yellow edge 8 to purple edge 11. The 11 being the incoming edge. This means you don't have to think of the sets of edges, just one edge on one Spectre tile for each of the 6 outgoings sides of your meta tile, at any level. This is quite a small amount of data to hold in a simple recursive algorithm
Another thing I got wrong is I stored a list of tiles, and referenced them as the 6 sides. Each tile with a starting point and rotation so I could plot it, and align new attached tiles. But this really is not necessary, and ends up using memory. I can plot the tiles (output a path to SVG) as I go, and I just need the 6 sides of a meta tile to be the 6 sets of position, rotation, and outgoing edge number. The only memory usage is a small set of data for the level of recursion. You quickly cover a very large number of tiles in each level (multiple by 8 or 9 each time), so need very few levels of recursion.
Co-ordinates
One issue is coordinates. Ultimately the output uses pixels or millimetres to several decimal places, and indeed I allow a final output rotation. But internally all lines on the Sprectre tiles are at multiples of 30 degrees. Even so you do not want to use floating point - rounding errors will accumulate as you recurse and lead to tiles not quite aligning, and also it is not possible to test two points are the same (why you need this is explained below). So the solution is to use coordinates that are integers! How do you do that with 30 degree angles, well simple - each distances is an integer multiple of sin60 plus an integer multiple of cos60 - at the final stage you multiple out and add these. You can also make a simple table of one unit distance integers for each 30 degree angle. And a table of the relative integer offsets for each point on a Spectre at each angle. This means no floating point maths, nor sin/cos, until you actually output to SVG.
Finishing
One problem which I don't think Simon's paper covers, and was unexpected, is knowing when to stop! I am trying to cover a rectangular area. How do I know I have got there?! I could just set a maximum level, but using random choices for meta tiles at each level one can find the whole things quickly gets to way bigger than the area but ends up one sided leaving gaps in your rectangle. If I had gone top down, or always picked the current tile being in the middle of the meta tile, I could maybe work out a max level, but that is not what I am doing.
After a bit of head scratching I finally worked out a way. I wanted to make a grout line on top of the final tile output so I decided to keep track of all the edges I placed. A simple start/end for each unit length edge in a list. This can be made as I go along, and the integers mean I can always match to an existing edge to plot the grout efficiently as a series of lines.
This also meant I could actually keep two lists - one a list of first use of an edge, and then moving over to another list of second use of an edge, when a tile is attached the other side.
I could also check each edge I added to a list to see if it falls (even one end) within my target rectangle, and so only keep edges I need.
But this has the side effect that as soon as my list of single used edges, within rectangle, is empty, I must have 100% covered the rectangle, as no edges that don't have a tile on one side are in the target area. I can then immediately abort the whole placement process at every level just by checking the list of single use edges is now empty.
Cropping
The final challenge was the edge of rectangle. Firstly the SVG has a viewBox, and so I can simply plot tiles that fall even slightly within the rectangle, and the same for grout lines. These go off the edge, but you cannot see when looking at the final SVG.
This has a problem, if you want to use the SVG in another design, as I did, the embedding does not inherently crop the edges. But SVG has an answer for this, clipPath. It allows me to clip an object to a path, a rectangle in this case. Perfect.
The snag is support of clipPath is not that good. I don't know why, but lots of things mess up, ignoring it, or barfing in some other way. One was my resin printer, which simply ignored the whole block of tiles if it has a clipPath.
So I ended up making a whole path generation set of functions which understood cropping the path to the edge of the rectangle. I could not sleep, and ended up coding this at 2am.
The final result is I can now make an SVG of a randomised set of tessellating aperiodic Spectre monotiles, with loads of options. I even added a sort of bevel edge to the tiles with a lighting based shade.
This is shaded per level, showing how the tiles actually join up at a meta level.
