GenTruchet, 2024
Processing, Ink, Paper
Plotter artwork visualizing solutions to a Truchet Tile problem
Truchet tiles are tiles sets marked so that laying them out at random still produces a cohesive design. The traditional set is tiny, one or two designs placed in a few rotations, so every pattern is built from the same handful of shapes repeating. GenTruchet throws out the fixed set and generates each tile instead: every tile in a drawing is generated independently of all the others, so no two are ever alike.
Losing the shared set of shapes makes the pattern hard to hold together. A tile is drawn knowing nothing about its neighbors, so whatever coherence the image has must come from guarantees that each tile can make on its own. The first version of this project has two such guarentees: a line always crosses from one tile into the next without a kink at the border, and every line is a part of one closed shape. A later version adds a third guarentee, that no two lines in a drawing ever intersect. Creating mono-tile algorithms that afford these inter-tile guarentees is the core of this project.
The drawings are made for a pen plotter, which informs the patterns I generated. The sketch writes each drawing straight to SVG as pure line work - exactly what a pen is best at. Every shape closes, so each is a single continuous path instead of a pile of separate strokes. No line turns a sharp corner, so the pen never has to stop and reverse. With no two lines crossing, no point on the paper is ever inked twice.
Truchet tiles were first described in 1704 by Sébastien Truchet, a French priest, in a memoir titled Mémoire sur les combinaisons. His tiles were squares split along the diagonal into two triangles of contrasting colors. Each tile can be placed in four orientations; Truchet studied the patterns that come out of arranging them in different combinations. In 1987, Cyril Stanley Smith popularized a variant that replaces the triangles with two quarter circles joining the midpoints of neighboring sides. That version has only two orientations. Because its quarter circles always meet at the middle of an edge, a grid of randomly rotated tiles still forms continuous, winding lines.
Truchet’s original tile, Smith’s quarter-circle tile in its two orientations, and a grid of Smith’s tiles placed at random.
That is the core idea of Truchet tiles: each tile is chosen independently, without looking at its neighbors, but the pattern still reads as one continuous whole. The catch is that in Smith’s version every tile is the same design, so the patterns are built out of the same few shapes over and over. I wanted every tile to be different. In GenTruchet, each tile is generated randomly and independently of the others, while still guaranteeing three things:
1.Every line closes into a shape.
2.Lines join smoothly from one tile to the next.
3.No line ever makes a true sharp corner.
Intersection of tiles and scribbles
The sketch starts with a random scribble: hundreds or thousands of randomly selected points on the canvas, joined in the order they are generated by straight lines, with the last joined back to the first so that the scribble closes into a (very likely self-intersecting) loop. Over that scribble, I lay a grid that will later define the borders of the tiles I generate. The sketch then finds every place where the closed loop scribble crosses one of the grid lines.
Those intersections are the only thing the rest of the algorithm ever uses. Once they are found, the grid and the scribble are deleted. From here on I call them points. Every point sits on the shared edge of two adjacent tiles, 'belonging' to both tiles.
A short scribble, then the same scribble with a 3 x 3 grid over it. The number written in each tile is how many points it has across its four edges.
Because the scribble is a closed loop, every time it enters a tile it has to leave that tile again, so each tile ends up with an even number of points spread across its four edges. This even guarantee across all tiles is key to the next steps of the algorithm.
Pairing up the points
Each tile is filled in completely independently. First the tile puts its points in order around its four edges. Then it splits them into pairs, each pair to be joined by a single line drawn inside the tile. The pairing works like this:
1.Pick a random point, then pair it with a random partner that has an even number of points between them.
2.That pair splits the points still unpaired into two groups, one on each side of it. Both groups hold an even number of points.
3.Repeat inside each group until every point has a partner.
Every group always holds an even number of points, so the process never strands a point with nothing to pair it with.
In the diagrams a straight line between two paired points shows which point went with which. I call that straight line a link. A link is not what actually ends up being drawn in a tile but simply a good way to keep track of what points are paired, such as the links drawn in the diagram below.
Pairing the six points on the center tile of the grid above. The straight links show only which point went with which, not the curve that ends up being drawn.
Drawing the connections
Each pair is joined by a curve whose shape is determined by which sides of the tile it is connecting. There are only three cases, and these are the names I use for them from here on:
Side. Both points on the same edge. A half circle from one to the other.
Corner. The two points on edges that meet at one of the tile’s four corners. A quarter of an ellipse centered on that tile corner. The two distances from the tile corner out to each point are the pair’s legs.
Crosser. The two points on opposite edges. Two quarter ellipses meeting halfway across the tile, forming an S curve.
The dashed circles and ellipses are the shapes each curve is cut from, and the gray dots are their centers. The small squares mark right angles.
The same three pairings from before, first as links, then as the curves they actually draw.
All three shapes meet the tile edge at a right angle, which is what holds the pattern together. A point on an edge belongs to the tiles on both sides of that edge, so two curves arrive at it, one from each tile, both perpendicular to their shared edge and therefore parallel to each other. They line up and continue as a single smooth line, though neither tile knows anything about the line created in the other tile. Curves may get very tight when two points sit close together, but they never kink, so every transition between tiles is smooth.
Why every shape closes
Every point sits on an edge shared by two tiles, and is the end point of one curve on each of its two tiles. So every point ends up with two curves attached to it, one on each side of its edge. Follow a line up to a point and there is always a curve waiting on the far side to continue onto, which means a line can never stop partway. There are only so many points to pass through, which means the line eventually arrives back where it started, closing the shape. No line is ever left hanging at the border of the canvas either. The scribble is built from positions inside the canvas, so it never crosses out of it, and every point therefore lands on an interior grid line with a tile on each side of it.
The finished example. Each point (gray dot) has one curve from each of its two tiles, so both shapes close.
These three versions use exactly the same points as the example above, with each tile pairing them differently. The shapes change completely, from one large shape to several smaller ones, but they are always closed. Closedness never depends on which pairing a tile happens to pick, or on what its neighbors did. So long as every point gets one curve from each of its two tiles, which every tile guarantees on its own, the lines have nowhere to end. That is how GenTruchet keeps the defining property of Truchet tiles, a continuous pattern built from tiles made independently, while no two of its tiles are ever the same.
At full size
Here is the same algorithm on an 8 x 8 grid, once with a 200 position scribble and once with a 1000 position scribble. The longer the scribble, the more intersections are generated, and the more points each tile gets. The sketch saves each pattern as an SVG.
Lines that never intersect
Those three guarantees say nothing about a fourth question: whether two lines run through each other. Nothing stops them, and the patterns above are full of places where one curve cuts straight across another. I wanted a version where that never happens, so that a finished drawing is a set of separate closed curves that never touch.
The pairing already rules out one kind of trouble. The points go in order around the tile’s four edges, and partners are chosen so that no two links ever intersect. But a link is not what gets drawn. A curve is rigid: choose its two points and its shape is settled, which can mean bulging a long way into the tile. So a pairing whose links all miss each other can still draw curves that run straight through one another.
The same four points, paired two ways. On the left the links miss each other, but the curves that pairing draws intersect twice. Pairing those four points the other way is fine.
The links, then, are no guide at all to whether a pairing is safe. Only the curves it draws can settle that. Some pairings work and some do not, with nothing in the order of the points around the edges to separate them. Finding a way to land on a safe pairing every time took me two attempts.
A first attempt: one curve at a time
My first working solution got there by trial and error. It throws out the random closed scribble and its intersections, and builds the design one curve at a time, along a random walk through the grid tiles. From wherever the walk currently sits, it steps into a random neighboring tile, picks a random position on the edge those two tiles share, then draws the curve joining where it was to where it has landed. Before that curve is kept, it is compared against every curve already sitting in that tile. If it intersects any of them, it is thrown out and the whole step is taken again from scratch: a fresh neighboring tile, and a fresh position on the edge between the current tile and the neighboring one.
Every candidate curve is checked against everything already in the tile. The first two run into it; the third is kept.
Sometimes there are almost no valid positions. Once a tile holds a few curves, there can be only extraordinarily narrow margins for valid curves, and trying more positions will not help, because the obstacle is not the curve being added but the curves that are already there. The tile has become a dead end.
So after five failed tries in a row the sketch stops trying to add to that tile and rebuilds it instead. It deletes every pair in the tile and pools their points together with the position the walk is stuck on. That pool holds an odd number of points, so one of them is set aside at random to become the walk’s new starting position, which leaves an even number to pair up. The sketch then generates a fresh pairing and a fresh set of curves. If any two of them clash, it generates another pairing, and keeps going until it finds one that fits. Because the tile is rebuilt from nothing, the curves that were blocking the walk are likely somewhere else entirely.
Every way out of the starting point is blocked. Pairing that tile’s points again from scratch rearranges everything inside it, and the walk carries on from one of the points picked at random.
It works, but it is slow. Every part of it is random guessing followed by checking. The position is a guess. Comparing the resulting curve against every curve in the tile, each comparison sampling both curves at more than a thousand places, is the check. When that fails five times, the replacement pairing is another guess, all of its curves get built, every pair of them gets checked, and a single clash sends it back to guess again. The only thing keeping it out of a loop is a record of the pairings it has already rejected, so that it never tries the same one twice. Beyond a few hundred steps in the walk, things seriously slow down and creating a dense output like in the original is completely impractical.
Worse, it breaks the closed shapes. The first version’s scribble was a closed loop, but the walk is not a loop. It has a first position and a last one, each of which gets a single curve rather than two, so the lines running through those two positions have nothing to continue onto. Plenty of closed shapes do still appear, because every rebuild cuts the walk and rejoins it somewhere else, which can seal a loop off behind it. What is gone is the guarantee: the first version closed every shape it drew, while this one closes most of them and leaves two ends hanging.
The walk itself (black) starts and ends somewhere, and those two points are the only ones with a single curve. Re-pairing a stuck tile closes off loops (gray) as it goes.
Solving a whole tile at once
The final version returns to the same manner of pregenerating an even number of points on each tile. What is new is how I pair up the points within a tile. The first version created non-intersecting links that could still generate intersections in the resulting curves. The second built one curve at a time and threw away anything that clashed. In this version, I finally figured out a tile-wise algorithm that guarantees that curves, not just links, will never intersect, and does so without any need for guess and check.
Going back to the scribble also buys back everything the walk had given up. The scribble is a closed loop, so every point once again sits on an edge shared by two tiles and collects one curve from each. Every line has somewhere to continue, every shape closes, and the two loose ends are gone. And because all of the points exist before a single curve is drawn, no tile ever waits on another or has anything to undo: each one is handed its points and solves itself. Importantly to me, this returned the project to its Truchet roots, where each tile’s appearance is independent of all others yet they still produce a cohesive overall form. It is also what makes this version fast. The walk bogged down after a few hundred curves, while this one fills a dense grid in a single pass, which puts outputs as dense as the original back within reach.
The algorithm is two steps:
1.Connect the smallest corner available, then repeat until the tile has no corner left. Smallest means the least average of a corner’s two legs.
2.Connect whatever points remain exactly the way the first version did: pick one of them, pair it with a partner that has an even number of points between them, then repeat inside each of the two groups that splits the rest into.
Run on a single tile, from a full set of points down to none, it goes like this.
The four corners on offer, with each one’s two legs added together. The smallest goes first. Two of them end up sharing the top left tile corner, the top right never gets one at all, and the six survivors are paired last.
Step 1 is very cheap. The smallest corner must be made of the two points closest to that corner, so only four candidates ever need checking, one per tile corner. Points therefore only ever get used up from one end or the other of an edge, never from the middle of it.
Why it works
First, a caveat: I never managed to turn the argument below into a formal proof, and I am not aware of one for any other method of pairing the points that is not simply guessing and checking. My algorithm seems to always work. I've tested it on upwards of 100,000 tiles and have never seen it fail, and the explanation I write out below makes sense, but my every attempt to prove it has shattered into tens of tiny cases, subcases, subsubcases, and subsubsubcases.
Below you can find a formal description of the problem. If you have an idea on how to solve it, please reach out, this still bugs me to this day!
Download the PDFProblem statement.
A counterexample to the reasoning below would be just as welcome as a proof of it. What follows is the reasoning I have.
The key property of the smallest corner is that nothing can be inside it.
Suppose some other point sat inside the region that the smallest corner’s curve encloses. Points only ever sit on tile edges, so this one would have to be on one of the two edges that corner uses, nearer the shared tile corner than that corner’s own point on the same edge. It could then pair with the point on the other edge to form a corner whose legs add up to less, which contradicts the first corner being the smallest one available.
If p were inside, p and the point on the other edge would form a corner of t plus b, where t is less than a. So the smallest corner has nothing inside it.
That rules out another point sitting in the region. It does not yet rule out a curve drawn later reaching through it with both of its ends outside, which is again that difference between links and curves.
Every later pair is a side, a corner, or a crosser, so there are three cases. Put the closed corner at the top left of the tile and measure out from that tile corner: a is its leg along the top edge, b is its leg down the left edge, and a tile is L across. Every point still unused on the top edge lies further out than a, and every one still unused on the left edge further out than b, which is what the result above gives us.
A side is a half circle standing on the stretch of edge between its own two points, and it never reaches outside that stretch. Both of those points lie beyond a, so the whole half circle does too, while the region lies inside a.
A later corner at the same tile corner has to use the nearest unused point on each of the two edges, so both of its legs are longer. Its quarter ellipse is the same shape stretched outward, nesting strictly around the closed one. Corners at the other three tile corners are nowhere near it.
A crosser is the case that takes real work.
Nothing drawn after the smallest corner can reach into it. A side stays between its own two points, a later corner nests outside, and the half of a crosser leaving the same edge is further out at every height.
A crosser joins a point on the top edge to a point on the bottom edge, drawn as two quarter ellipses that meet halfway down. Only the half leaving the top edge can get anywhere near the corner, because the other half never leaves the bottom half of the tile. And if that half leans away from the corner on its way down there is nothing to check at all, so take the case where it leans toward it.
Call the crosser’s point on the top edge p and its point on the bottom edge q. At a height y below the top edge, the two curves sit at:
The crosser. x = (p + q) / 2 + ((p - q) / 2) * sqrt(1 - 4y^2 / L^2)
The corner. x = a * sqrt(1 - y^2 / b^2)
Both have the same three parts: where the curve starts out, how far sideways it has to travel in total, and a square root that falls from 1 to 0 and says how much of that travel is still ahead of it. The corner starts at a and has used up its whole width by the time it reaches a depth of b. The crosser starts at p and finishes halfway between p and q, at a depth of half a tile.
While b is at most half a tile. The crosser spreads its square root over a drop of L/2 and the corner spreads its own over a drop of b. With b the smaller of the two, the crosser’s square root is the larger one at every depth, which is to say the crosser has always used up a smaller share of its sideways travel than the corner has of its own. It also started further out, since p is a point still unused on the top edge and so lies beyond a. Starting further out and giving up its width more slowly, it stays outside the corner the whole way down, and the two never meet. Written out in full, the comparison comes down to p + q being at least zero, which holds because both are distances.
Once b is more than half a tile the region reaches past the halfway line, the crosser’s second half comes into play, and the comparison above no longer covers it. Being the smallest corner is what rescues the case. For a crosser to exist at all the bottom edge has to hold a point, which means that back when the smallest corner was picked there was also a corner going spare between the bottom edge and the left edge. Its two legs run from the bottom left tile corner out to the nearest point on each of those edges. Call the first of them d. The left edge already holds the closed corner’s own point at depth b, so the second leg is at most L - b, and the top left corner being no larger than that one gives:
a + b is at most d + (L - b), which rearranges to d being at least a + 2b - L.
With b past half a tile, that puts d beyond a. Every point on the bottom edge is at least as far out as d is, so both halves of the crosser stay beyond a while the region stays inside it. The same bound covers a half circle standing on the bottom edge, which is the only other curve that could have reached back across the halfway line. Turned on its side, the whole argument covers a crosser running between the left edge and the right edge.
So closing the smallest corner uses up space that no other curve could have needed, and that is what lets the argument repeat. Delete the corner’s two points and what is left is a smaller tile, still holding an even number of points, where the same reasoning applies to whatever its smallest corner is now. Each round removes two points, so the process runs out with the tile empty. A valid answer always exists.
The same fact settles the ordering. Walking around the tile’s four edges you meet the smallest corner’s two points one after the other with nothing in between, because the two stretches of edge running from their shared tile corner out to each of them are exactly what the argument above emptied. So step 1 never produces a pair whose link crosses another, and the points it leaves behind are still in order for step 2.
Step 1 stops when no corner is on offer, which means no two edges that still hold points meet at a tile corner. A tile is a square, so its four edges come as two facing pairs, and that leaves only two ways for the survivors to sit: all on one edge, or split between two edges that face each other. Either way a corner is out of the question, because a corner needs two edges that meet. Only sides and crossers are left.
Once no two occupied edges meet at a tile corner, everything left sits on a facing pair of edges, where the only pairs possible are sides and crossers.
That is a much smaller problem than the one step 1 started with. A side is a half circle hanging under its own edge, never straying outside the stretch between its own two points. A crosser runs straight across to the edge facing it. So long as the links are kept clear of one another, the sides along an edge nest one inside the next, the crossers run alongside one another in order, and a side and a crosser never end up in each other’s way. The case that would cause trouble is two crossers leaning opposite ways, and building one of those needs points on two edges that meet at a tile corner, which step 1 has already used up.
The leftover points can be paired any number of ways, and every one of them is safe.
That is why step 2 can be left free. Once step 1 has finished, any pairing of the leftover points whose links do not intersect will be safe, so the sketch picks one at random, with every such pairing equally likely.
Put together, those pieces are why I believe the rule can never draw an intersection: every curve a tile adds after the smallest corner stays out of it, the same then holds for the next smallest, and once the corners run out only sides and crossers are left. The places it stops being airtight are the last few, which rest on cases I have checked rather than cases I have proved.
So I checked them hard. The rule and the curve geometry were ported to a separate script and run on 100,000 random tiles holding anywhere from two to twenty-four points, testing every curve against every corner already closed, and every pair of curves against each other. Nothing ever turned up in the wrong place. That is evidence rather than proof, which is why the problem above still seems worth someone’s time.
Two colors
Ruling out intersections opens up something neither earlier version could do. A finished drawing is now a set of separate closed curves, none of them touching, which means the regions they cut the page into can be filled using only two colors. Which color a region gets depends solely on whether the number of curves you have to cross to reach it is odd or even. Outside every curve the count is zero, so white. Step across one line and the count is one, so black. Step across another and it is two, so white again. The first version cannot be colored this way at all, because where two curves run through each other there is no consistent inside and outside left to count.
A ray fired out of a region meets one curve for every curve containing that region. Odd means inside, so black. Even means outside, so white.
Turning that into a picture takes three passes over the drawing.
1.Collect each closed curve. Every point has exactly one curve from each of the two tiles sharing its edge, so at the end of any curve there is always exactly one other curve to step onto. Keep stepping and you arrive back where you started, having walked that whole curve and nothing else. It is the same fact that closes the shapes in the first place, used here to gather each curve into a list of its own.
2.Work out each curve’s color. Take a spot just inside the curve, fire a ray out of it in any direction, and count how many curves that ray meets before it leaves the drawing. An odd count means the spot sits inside an odd number of curves, so the curve is filled black. An even count means white.
3.Fill them in, largest first. Curves never touch, so a curve that contains another is always the larger of the two. Sorting them by area and painting in that order therefore paints every curve before anything inside it, and each smaller curve then paints its own interior over the top in the opposite color.
Filling runs from the largest curve down, so each curve repaints the inside of whichever curve contains it.
The colored version is written out as filled polygons rather than as curves, which makes for a much heavier file and means it is not what you would send to a plotter or a cutter. How close two lines are allowed to run is handled separately, by a rule that thins out points landing too near each other along a grid line. This can have an effect on how visually clear it is that shapes and lines never intersect, but nothing about the algorithm is fundamentally different.
Turning the grid size and the scribble length up and down changes the result completely, from a handful of large shapes to a dense field of nested rings.
The source code for all three versions is on GitHub, and the current version runs live on OpenProcessing.