Diffusing domino tilings: thinking about sets all time
Draft of 2017.11.07
May include: games ↗ graphics ↖ combinatorics ↙ Clojure ↘ domino tiling ↗ &c.
The other day,^{1} I was sitting in Brighton with Ron and showing him the little animations of dominoflipping systems I’ve been showing you here (see also A, B, C, D and E), and we did a bit of codetalk. I mentioned along the way that I hadn’t used a rectangular array of “pixels” in my implementation, except in a very indirect kind of way, and he looked at me funny in that way he does, and made noises that eventually formed themselves into a question about why I would do that and why I’m so weird about making more work for myself.
Both are very valid things to wonder. Let me review where I am, and where I might be going with this project shortly… not so much to make my case, as to frame things as part of a flowing context.
review of sorts
I started, way back, wondering what “kinds” of “patterns” (whatever those words mean) one can build out of the various tilings of a checkerboard with dominoes, if each domino has one blue and one orange square on it. I cast this proposed question as a “benchmark” for classifiers, the sort my genetic programming work over the years has focused on:
If I show you (or your computer program) a “picture” of a portion of square lattice, colored with orange and blue squares, can you (or it) tell me whether that particular pattern could have been made out of
blue:orange
dominoes alone?
See, there’s a bunch of pretty fancy combinatorics and constrainthandling tucked into that question. First, there might be more than one way to tile a particular region of lattice with dominoes—actually, there are loads probably, although as I discussed last time there are certain regions where only one tiling pattern is possible.
Then there’s the additional layer of whether, given all the ways to plop dominoes onto a region, any of those permit the blue and orange ends of dominoes to form particular patterns. I talked a bit about how a given tiling might be colored in an even earlier chunk of this exploration.
This makes me suspect that for your “algorithm” to be able to say whether a given arrangement of blue and orange squares could be the result of a tiling of blue:orange
dominoes, it needs to be able to coordinate two different suites of constraints, both kinda complicated and graphytheoreticalish: the constraints imposed by the possible set of domino tilings of the region in question, and also the ways colors can be applied to those tilings.
Over the last few stages of this exploration, though, you might have noticed that I haven’t even drawn a single blue:orange
domino. Not once. I have these nice rainbowcolored animated thingies, but what relation do these have to the question at hand?
Well, think of it all as “proof of concept”. Or maybe “skepticism in action”. “Something something ergodic systems or probability theory,” maybe?
This little hiatus has been an exploration, for me, of whether (and how) I might be able to visit a lot of different domino tilings. I needed to see—in the visceral, makingitmyself and watching the longterm dynamics kind of way of “seeing”—that it’s true, what we’re told about these little twosnugdominoesrotating “moves” being sufficient to visit every possible tiling of a region.
One wants to look and see.
So what can we see here?
The animation above starts with an Aztec Diamond region of a square lattice, initially tiled with dominoes in a boring kind of brick pattern. In every “tick”, we
 pick a random domino, with uniform probability over all of them present in the tiling;
 look at all the dominoes that share at least one square’s worth of edge with the target I picked in (1);
 if any of those neighbors is “snug”—shares a “long edge”, in any orientation—then I pick one of those “snug” neighbors with uniform probability, and rotate the target domino and that neighbor 90° clockwise or counterclockwise (again, with equal probability). If there are no “snug” neighbors, the domino doesn’t move at all.
It’s important, at least to me, to reemphasize that I’m very aware that so far these aren’t my blue:orange
dominoes… but they’re close. I’ve colored the two squares in each domino the same color, and I’ve made each domino’s squares different from all the rest. “Really”—which is to say, “in the bigger scheme of things”, or maybe “in keeping with the academic literature that treats these systems”—I should probably have all the dominoes look exactly the same as the others, except for their location and orientation.
But instead, I made them all look different so I could see them diffuse (or not), depending on the shape of the region they’re tiling. I like it. It gives me a sense of progress to see them moving around.
Talk normal
OK, fair warning: this will be about implementation details and software development methodologies and habits and assumptions and worldviews. You know, objectoriented and functional programming and such.
I think I know at least two reasons why Ron made questionlike noises about the way I implemented these animations.
First, because I said in passing that I was using “sets” to model the system, and he has a long and storied history with set theory. More on that another time.
But more likely he was thinking about “portion of a checkerboard” as being a sort of obvious cue to model domino tilings with twodimensional matrices of some sort. That’s what I would do, if we had started in Ruby and this was somebody else’s project. It’s more… “familiar” maybe? Is that the right word?
Let me sketch—though I won’t implement it explicitly here (leaving it as an exercise for the curious and overenthused student)—something like what I suspect he and I would have done, if we’d been working together on this from the start. Some counterfactual code as it were….
Like I said, “portion of a checkerboard” makes me reach for a twodimensional array. Maybe an array of bits or pixels, like you know an image or something close to one. There are loads of convenient graphics libraries built into our all of computers and the languages we’re using, and those libraries do a lot of the stuff we might want to do here.
Except if we started down that road, I would immediately have emphasized that I didn’t want to just stick to rectangular regions of pixels here: I have meant all along that we should be exploring the behavior of dominoes on regions like the Aztec Diamond—and more exotic and arbitrary ones—from the getgo.
So one of the core features our implementation would want to handle would be “chunks” of square lattice. Like this square one, which we might model as an 8x8
image? bitmap? pixelmap? something like that:
My first impulse for handling nonrectangular regions in this paradigm would be, probably, to create a rectangular region and then apply some kind of “mask” which restricts the pixels we’re actually using.
The left block is the region, but the right block indicates which of those are “masked cells”. Or something like that. While in this case I’ve drawn an 8x8
square region of cells, the mask means I’m really talking about an Aztec diamond of order 4.
The presence of a colored pixel in the “mask” layer would tell us we’re not allowed to use a given pixel in the array—that it “doesn’t exist” for our dominoes’ purposes. Pixels that are left white or “empty” can be occupied by one end of a domino, and the other ones aren’t “really” part of the region we’re talking about. When we get around to writing code, we’ll just have to try to remember not to ever place a domino on one of those maskedout pixels. Or maybe the other way around: Maybe a colored masklayer pixel means we can count a given pixel as part of the region, and only the plain white ones are allowed.
Whatevs.
OK, so if we have a masked region of pixels, we should start putting down some dominoes. For the sake of getting this counterfactual code “working”, maybe we go back to a square or rectangular region. We’ll probably start by making one domino, and it’ll probably be an object with some attributes like which pixel coordinates it’s sitting on top of. Something like (if we’re using Ruby):
class Domino attr_accessor :pixels def initialize(pixels) @pixels = pixels end end
But then we’ll want to make a particular Domino
instance in a test, and we’ll have to pass in something reasonableseeming for pixels
. Those are coordinates in the plane, so we might use an Array
or maybe a Struct
like {:x => 3, :y => 3}
for the Pixel
located at coordinates \((3,3)\), and something like [Pixel.new(3,3), Pixel.new(3,4)]
to produce the array of Pixel
values to pass into our Domino
constructor.
That seems OK. I think we’re good; we can do this.
Imagination is a wonderful thing, ain’t it?
So let’s implement that sketch I made up there of my algorithm for diffusing dominoes: There’s probably an Array
of Domino
objects. Picking a random item from a collection isn’t complicated, so let’s work out how to pick out which ones are the neighbors of a domino we’ve targeted.
Hmm. It turns out that the Domino
instances contain all the information about where they’re sitting, so we’ll need to ask them who’s where. Maybe the model would be more amenable to this sort of query if we used the twodimensional array of pixels to record where each Domino
object was. That is, if one particular Domino
instance occupies coordinates \((3,3)\) and \((3,4)\), we could record that in its @pixels
attribute, but also have it “publish” to our region, writing something to those entries in a 2d array to “claim” those pixels. Maybe its object_id
or something; some kind of unique identifier.
That might work pretty well, actually. Though we’ll also have to factor in the mask
part, since no Domino
should ever try to sit astraddle a pixel that’s unavailable. And having this matrix of “claimed” pixels then gives us the opportunity to more efficiently “ask” which Domino
instance is occupying to the north, south, east and west pixels, relative to some given pixel.
By that route, I can definitely intuit a path towards a function that will return all the neighbors of a given Domino
. Metaphorically speaking, I can treat this array of masked cells and Domino
ID values as a kind of “whiteboard” sort of thing that records occupants and availability of every pixel.
And I can also intuit a path towards a function that, given a pair of Domino
instances, determines whether they’re “snug neighbors or not. And if I had those two functions, I could ask for all the neighbors of an arbitrary Domino
, and filter out all but the ones that are “snug”, and then pick one of those at random.
And then, given that information, I could totally see how to rotate the two “snug” dominoes: just exchange some of the pixels they’re standing on.
Yeah, well. That’s not what I did.
And I have to agree with Ron: this arraybased representation’s the “obvious” way to proceed. It’s interesting for me to wonder why—and there are several “whys” here, I think—I chose the weird setbased representation that I did. Something about Clojure (and ClojureScript), maybe. Something about behaviordriven habits. And definitely something about extending the stuff I implement to more general cases, which through the years I have come to think of as “overthinking”.
This time, though, “overthinking” did the trick. Almost certainly blind luck, but then again maybe there’s a little bit of decadesold experience wrapped up in the ball there, the same way the pillow cases end up tucked into the corners of the fitted sheets when I take them out of the clothes dryer: as a sort of inevitable emergent thing that nobody wants, but which everybody should expect.
An other way
Let me walk through my actual, working code now—or at least the version of my code which I have on hand at the moment. Here’s a dump (jump to the other end unless you’re a Clojure nerd):
(ns dominotilings.core (:require [quil.core :as q :includemacros true] [quil.middleware :as m] [clojure.math.combinatorics :as combo] [clojure.set :as set] )) (def config "global stuff for setting up" {:cellsize 20 :latticeside 20 :proportionofmonominoes 0.0 :saveinterval 100} ) (defn rectangularregionofcells "returns a Clojure set containing 2d position index vectors; yes, this is weird" [width height] (into #{} (for [i (range width) j (range height)] [i j])) ) (defn aztecdiamondofcells "returns a set containing cells that fill an Aztec diamond of the given size" [edgesize] (let [all (rectangularregionofcells edgesize edgesize) corner (/ edgesize 2) oppositecorner (+ edgesize edgesize ( corner))] (>> all (filter #(<= (dec corner) (apply + %)) ,) ; (filter #(> oppositecorner (apply + %)) ,) ; (filter #(< (dec corner) (+ (first %) ( edgesize (second %)))) ,) (filter #(>= oppositecorner (+ (first %) ( edgesize (second %)))) ,) ))) (defn adjacentcells? "given two cells (2d index vectors), returns `true` if they are Von Neumann neighbors of one another" [cell1 cell2] (let [[i1 j1] cell1 [i2 j2] cell2] (or (and (= i1 i2) (= 1 (Math/abs ( j1 j2)))) (and (= j1 j2) (= 1 (Math/abs ( i1 i2)))) ))) (defn neighboringcells "given a cell and a set of cells, returns all neighbors of the former" [cell setofcells] (filter #(adjacentcells? cell %) setofcells)) (defn allneighbors "produces a set of all pairs of Von Neumann neighbors (as sets) from a given set of cells" [setofcells] (set (map set (filter #(apply adjacentcells? %) (combo/combinations setofcells 2) )))) (defn drawcell "draw a square, with a 1pixel border on the right and bottom" [cell size hue saturation brightness] (q/fill hue saturation brightness) (q/rect (* size (first cell)) (* size (second cell)) (dec size) (dec size)) ) (defrecord Polyomino [cells color opportunities turns]) (defn domino? "given a polyomino, return `true` if it's a domino" [polyomino] (= 2 (count (:cells polyomino))) ) (defn monomino? "given a polyomino, return `true` if it's a monomino" [polyomino] (= 1 (count (:cells polyomino))) ) (defn initialrectangledominoes "given a rectangular region/collection of cells, construct nonoverlapping dominoes covering the region, in vertical alignment; assign them various colors as well, just to be a bit fancy" [width height] (let [scale (:latticeside config) deltah (/ 256 scale)] (for [i (range width) j (range 0 height 2)] (>Polyomino #{[i j] [i (inc j)]} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation (+ (* deltah i) j 150) :brightness (+ (* deltah j) i 100)} 0 0 )))) (defn monominoeseverywhere "returns a set of new monominoes where each cell is an individual Polyomino containing just that cell; sets some pretty colors too" [cells] (let [scale (:latticeside config) deltah (/ 256 scale)] (for [c cells] (let [i (first c) j (second c)] (>Polyomino #{c} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation (+ (* deltah i) j 150) :brightness (+ (* deltah j) i 100)} 0 0 ))))) (defn allpolyominocellsvalid? "given a polyomino and a set of cells, returns true if every coordinate in the polyomino is a member of the set of cells" [polyomino cells] (let [c (set (:cells polyomino))] (every? (set cells) c) )) (defn rightlatticeneighbor [cell] [(inc (first cell)) (second cell)] ) (defn aztecdiamonddominoes [edgesize cells] (loop [unusedcells (sort cells) newdominoes []] (if (empty? unusedcells) newdominoes (let [nextcell (first unusedcells) neighbor (rightlatticeneighbor nextcell) i (first nextcell) j (second nextcell) deltah (/ 256 edgesize)] (recur (remove #{nextcell neighbor} unusedcells) (conj newdominoes (>Polyomino #{nextcell neighbor} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation (+ (* deltah i) j 150) :brightness (+ (* deltah j) i 100)} 0 0) )))))) (defn aztecdiamondmostly [edgesize cells proportionofmonominoes] (loop [unusedcells (sort cells) newdominoes []] (if (empty? unusedcells) newdominoes (let [nextcell (first unusedcells) neighbor (rightlatticeneighbor nextcell) i (first nextcell) j (second nextcell) deltah (/ 256 edgesize)] (recur (remove #{nextcell neighbor} unusedcells) (if (<= (rand) proportionofmonominoes) (into newdominoes [(>Polyomino #{nextcell} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation 0; (+ (* deltah i) j 10) :brightness 0; (+ (* deltah j) i 100) } 0 0) (>Polyomino #{neighbor} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation 0 ; (+ (* deltah i) j 10) :brightness 255 ; (+ (* deltah j) i 100) } 0 0)] ) (conj newdominoes (>Polyomino #{nextcell neighbor} {:hue (mod (+ (* deltah i) (* deltah j)) 256) :saturation (+ (* deltah i) j 150) :brightness (+ (* deltah j) i 100)} 0 0)) )))))) (defn drawpolyomino "given a polyomino of any size and shape, place it on the canvas in the appropriate position, size and color" ([polyomino size hue saturation brightness] (let [cells (:cells polyomino)] (q/fill hue saturation brightness) (doall (for [c cells] (let [i (first c) j (second c)] (q/rect (* size i) (* size j) size size) ))))) ([polyomino size] (let [color (:color polyomino) h (:hue color) s (:saturation color) b (:brightness color)] (drawpolyomino polyomino size h s b)))) (defn neighboringcellsofcell "given a cell, return a set of all the other cells that are its neighbors, accoring to the neighborhood lattice provided" [cell neighborlattice] (apply set/union (filter #(contains? % cell) neighborlattice))) (defn neighboringcellsofpolyomino "given a polyomino, return a set of all cells that are neighbors of any of the polyomino's cells (and not part of the polyomino)" [polyomino neighborlattice] (let [insides (:cells polyomino)] (set/difference (apply set/union (map #(neighboringcellsofcell % neighborlattice) insides)) insides ))) (defn polyominooncell "return the polyomino that occupies a given cell" [cell polyominoes] (first (filter #(contains? (:cells %) cell) polyominoes))) (defn setoverlap? "return `true` if the intersection of two sets is nonempty" [set1 set2] (not (empty? (set/intersection set1 set2)))) (defn neighboringpolyominoesofpolyomino "given a polyomino, return all other polyominoes that contain cells adjacent to that polyomino's cells" [polyomino polyominoes neighborlattice] (let [surroundings (neighboringcellsofpolyomino polyomino neighborlattice)] (into #{} (map #(polyominooncell % polyominoes) surroundings)) )) (defn snugneighborsofpolyomino "given a polyomino, return all neighboring polyominoes where _every cell_ of the polyomino is a neighbor of the given polyomino; these are the 'snug' neighbors" [polyomino polyominoes neighborlattice] (let [surroundings (neighboringcellsofpolyomino polyomino neighborlattice)] (filter #(set/subset? (:cells %) surroundings) (neighboringpolyominoesofpolyomino polyomino polyominoes neighborlattice)) )) (defn monominoneighborsofpolyomino "given a polyomino, return all neighboring polyominoes which contain only one cell" [polyomino polyominoes neighborlattice] (let [surroundings (neighboringcellsofpolyomino polyomino neighborlattice)] (filter #(and (monomino? %) (set/subset? (:cells %) surroundings)) (neighboringpolyominoesofpolyomino polyomino polyominoes neighborlattice)) )) (defn highlightcell "draw a black dot on a cell" [cell size] (let [halfsquare (/ size 2)] (q/translate halfsquare halfsquare) (q/fill 10 10 10) (q/ellipse (* size (first cell)) (* size (second cell)) halfsquare halfsquare) (q/translate ( halfsquare) ( halfsquare)) )) (defn rotateddominopair "given two snug dominoes, return the pair of rotated dominoes, with equal probability of clockwise or counterclockwise rotation" [domino1 domino2] (let [c1 (sort (:cells domino1)) c2 (sort (:cells domino2))] (if (< (rand) 0.5) (vector (assoc domino1 :cells #{(first c1) (first c2)}) (assoc domino2 :cells #{(second c1) (second c2)})) (vector (assoc domino1 :cells #{(second c1) (second c2)}) (assoc domino2 :cells #{(first c1) (first c2)})) ))) (defn swappedmonominopair "given two monominoes, returns them with their positions swapped" [monomino1 monomino2] (vector (assoc monomino1 :cells (:cells monomino2)) (assoc monomino2 :cells (:cells monomino1)) )) (defn swappeddominoandmonomino "given a domino and (adjacent!) monomino, returns the domino shifted to the other position in the triple of cells" [domino monomino] (let [mcells (:cells monomino) dcells (:cells domino) mneighbor (neighboringcells (first mcells) dcells) mnonneighbor (set/difference dcells mneighbor) ] (vector (assoc domino :cells (set/union mcells mneighbor)) (assoc monomino :cells mnonneighbor)) )) (defn setup [] "build the Quil state" (let [s (:latticeside config) allpositions (aztecdiamondofcells s) cellneighbors (allneighbors allpositions) initialpolyominoes (aztecdiamondmostly s allpositions (:proportionofmonominoes config)) ] (q/framerate 60) (q/colormode :hsb) {:cells allpositions :lattice cellneighbors :polyominoes initialpolyominoes :changedpolyominoes [] :stepcounter 0} )) (defn swapinpair "replace a pair of 'old' polyominoes with a pair of 'new' ones (probably because you rotated a snug pair, but maybe for some other reason)" [[old1 old2] [new1 new2] polyominoes] (into (set (remove #{old1 old2} polyominoes)) #{new1 new2}) ) (defn updatestate [state] "pick a random polyomino; if it's a monomino, find all its domino and monomino neighbors, pick one uniformly, and swap those polyominoes; if it's a domino, find all its monomino and _snug_ domino neighbors, pick one uniformly, and swap those polyonominoes; otherwise, change nothing" (let [cells (:cells state) polyominoes (:polyominoes state) lattice (:lattice state) focuspolyomino (randnth (vec polyominoes)) neighbors (neighboringpolyominoesofpolyomino focuspolyomino polyominoes lattice) snugneighbors (snugneighborsofpolyomino focuspolyomino (:polyominoes state) (:lattice state)) ] {:cells cells :lattice lattice :polyominoes (cond (and (domino? focuspolyomino) (seq snugneighbors)) (let [partner (randnth (into [] snugneighbors))] (swapinpair [focuspolyomino partner] (if (monomino? partner) [focuspolyomino partner];(swappeddominoandmonomino focuspolyomino partner) (rotateddominopair focuspolyomino partner)) polyominoes)) (and (monomino? focuspolyomino) (seq neighbors)) (let [partner (randnth (into [] neighbors))] (swapinpair [focuspolyomino partner] (if (domino? partner) (swappeddominoandmonomino partner focuspolyomino) (swappedmonominopair focuspolyomino partner)) polyominoes)) :else polyominoes) :changedpolyominoes [] :stepcounter (inc (:stepcounter state))} )) (defn drawstate [state] "clear the background, draw all the cells and domino polyominoes, and highlight any that want highlighting" (let [s (:cellsize config)] (q/background 240) (q/nostroke) (doall (map #(drawcell % s 0 0 200) (:cells state))) (doall (map #(drawpolyomino % s) (:polyominoes state))) (q/fill 0 255 0) (q/text (:stepcounter state) 20 20) ; (if (zero? (mod (:stepcounter state) 100)) ; (do (q/saveframe "./foo####.png") ; (q/text "saving" 20 50))) )) (q/defsketch dominotilings :host "dominotilings" :size [400 400] :setup setup :update updatestate :draw drawstate :middleware [m/funmode])
overview
This program is a Quil sketch, meaning that (like Processing or Codea sketches) it’s structured in a very formal way. There’s some setup
, which sets up some parameters and constructs a persistent state
variable, and then there are two crucial functions called drawstate
and update
which together produce an “infinite loop” of frames of animation. As with all these animationloop frameworks, the update
draw
loop is the key.
Let me broadly sketch the overall approach I took, to contrast with the 2d pixel array thing I described in the previous section. I’ll also give some of the motivating ideas, but be aware these may not be smart ideas… and indeed I know I’m probably prematurely focused on relatively “distant” features.
But at the same time, remember that it’s all about looking to see.
“region of square lattice”
Here’s the part where I build my initial state
:
(defn setup [] "build the Quil state" (let [s (:latticeside config) allpositions (aztecdiamondofcells s) cellneighbors (allneighbors allpositions) initialpolyominoes (aztecdiamondmostly s allpositions (:proportionofmonominoes config)) ] (q/framerate 60) (q/colormode :hsb) {:cells allpositions :lattice cellneighbors :polyominoes initialpolyominoes :changedpolyominoes [] :stepcounter 0} ))
There’s a bunch of stuff there you don’t really need to know about, which involves the graphics you see animated in those little compiled animations: the size of squares in the lattice, the nominal framerate of the program as it runs in your browser, counters and so forth.
The crucial things being used to model “dominoes diffusing in a region” are up there at the top, really: allpositions
and cellneighbors
and initialpolyominoes
.
First, because I’m concerned with the prospect of nonsquare lattices (and possibly even arbitrary graphs), I’m modeling the “region of square lattice” as a collection of cells, each of which is only an [i j]
coordinate pair. In my ClojureScript code, this is stored in an immutable state
value called allpositions
, and is a set
of simple coordinates exactly like [4 2]
or [1 8]
.
Cells don’t “know” who their neighbors are. They’re simple ordered pairs of coordinates, and that’s it.
Instead, the idea of “neighbors”—which features so strongly in the threestep update cycle I described above (pick a domino, find its neighbors, pick a snug neighbor)—is split out into a separate collection of sets
called cellneighbors
. Because I wanted to see what would happen computationally, I did not set this up as a keyvalue map organized by cells as keys, but simply as a “set of sets”.
Each set
in cellneighbors
is simply the pair of items from allpositions
that happen to be adjacent to one another.
Indeed, that’s exactly how it’s constructed: For every item in allpositions
, we call the function allneighbors
. The idea of “next to” is in some sense “buried” in a predicate function called adjacentcells?
, which I admit in this implementation is kind of a “cheat”, because it explicitly depends on the square lattice being present. But “in future”, for instance if I wanted to move to a hexagonal lattice, or higher dimensions, or even an arbitrary graph, then the only thing that needs to be changed to construct a different arrangement of cells is this predicate, not anything else.
(defn adjacentcells? "given two cells (2d index vectors), returns `true` if they are Von Neumann neighbors of one another" [cell1 cell2] (let [[i1 j1] cell1 [i2 j2] cell2] (or (and (= i1 i2) (= 1 (Math/abs ( j1 j2)))) (and (= j1 j2) (= 1 (Math/abs ( i1 i2)))) ))) (defn neighboringcells "given a cell and a set of cells, returns all neighbors of the former" [cell setofcells] (filter #(adjacentcells? cell %) setofcells)) (defn allneighbors "produces a set of all pairs of Von Neumann neighbors (as sets) from a given set of cells" [setofcells] (set (map set (filter #(apply adjacentcells? %) (combo/combinations setofcells 2) ))))
For example, suppose I am building a square region from a “bag” of 100 cells in allpositions
, set out in a 10x10
lattice. I accumulate allneighbors
by taking every possible pair of cells in turn, and asking whether the two cells in question are adjacentcells?
or not. If there are 100 cells, then we examine every possible one of the 495 possible pairs and keep only the ones that are next to one another.
The result is a collection, cellneighbors
, of collections containing pairs of adjacent cell
items. Nothing else, no repeats (because they’re set
s of cell values), just the entire universe of positive relationships we’d call “neighbors”. The cell in position [0 0]
, a corner, will only have two neighboring cells, so it will only appear in two collections in cellneighbors
; the cell in [2 0]
has three neighbors, and it will only appear in three, and so on.
If and when I want to draw a nonrectangular region, like the Aztec diamond, I can start by making the rectangular region first as a temporary allpositions
, and then delete all the items in that that don’t belong in the Aztec diamond itself. Throw the corner cells away, and keep the ones in the diamond itself. Then when we build cellneighbors
, there’s no need to pay any attention to who’s on an edge or in the middle.
And that’s the first “lovely thing” I saw drop out of this approach. I don’t have to think about masks or any other data structures to do the “bookkeeping” regarding the outlines of my region of square cells. If I want to set up a region that’s a rectangle with a chunk taken out of it, I can make a rectangularregionofcells
and then subtract another rectangularregionofcells
from it, before starting to build the allneighbors
structure.
It’s not that cells are “marked unavailable”, it’s that they’re not even present in allpositions
to begin with!
drawing
To draw my region of cells, I’m again relying on the possible “cheat” that every location or cell is simply a pair of [i j]
coordinates. For the time being, I have drawn them just as you would expect: placing a square at the (scaled) coordinate in my drawing. Here again, if I were to change the layout to be hexagonal or random Poissonsampled points, I imagine that I’d still be able to place those other shapes in the drawing at the correct location(s), and would probably only have to change the adjacentcells?
function and maybe the shape they’re drawn with.
They’re abstracted quite a bit farther than a pixel, in other words.
“dominoes”
Now there’s the question of a “domino”.
If you’re the sort of masochist who took the time to scroll through my whole codebase, above, you might have noticed that I mention both domino
and monomino
in it.
This is another of those places where I’ve gone with a more general representation than my initial musings might have implied. Though I admit I started with only Domino
records originally, and only recently have added the potential of working with othershaped polyominoes.
But it’s not complicated. Here’s what a Polyomino
record looks like:
(defrecord Polyomino [cells color opportunities turns])
Each Polyomino
record is a collection of only four attributes, three of which you really don’t need to worry about. The one called :cells
is, once again, a collection of [i j]
coordinates. Exactly the same values we have in allpositions
and cellneighbors
. As for the other three, :color
is exactly what you’d expect, and :opportunities
and :turns
are there to count stuff that happens in the course of animated diffusion simulation (how many times a polyomino is picked to try to turn, and how many times it actually manages to do so).
So once again, a Polyomino
is essentially a set
of cells. They don’t even have to be contiguous.
This leads to the following helper functions for finding a particular polyomino’s neighbors:
(defn neighboringcellsofcell "given a cell, return a set of all the other cells that are its neighbors, according to the neighborhood lattice provided" [cell neighborlattice] (apply set/union (filter #(contains? % cell) neighborlattice))) (defn neighboringcellsofpolyomino "given a polyomino, return a set of all cells that are neighbors of any of the polyomino's cells (and not part of the polyomino)" [polyomino neighborlattice] (let [insides (:cells polyomino)] (set/difference (apply set/union (map #(neighboringcellsofcell % neighborlattice) insides)) insides )))
The function neighboringcellsofcell
does the heavy lifting, and it could probably be refactored, simplified, and/or optimized quite a bit. Here’s how it works, though: It takes the bag cellneighbors
, and it throws all of them away that don’t contain the target cell as an item. Then it returns the set union of the remaining subsets of cells. In other words, it depends on the commutativity of the “neighbor” relationship: If somebody is my neighbor, I am their neighbor as well.
The function neighboringcellsofpolyomino
takes this up a notch, calling it for each cell that is an element of the Polyomino
. So, as an intermediate step, we get the set of cells that are either in the Polyomino
or next to one of those cells. Then we apply set/difference
to subtract away the cells inside the Polyomino
, and end up with just the adjacent cells around it on all sides.
And from there, we can reach neighboringpolyominoesofpolyomino
:
(defn polyominooncell "return the polyomino that occupies a given cell" [cell polyominoes] (first (filter #(contains? (:cells %) cell) polyominoes))) (defn neighboringpolyominoesofpolyomino "given a polyomino, return all other polyominoes that contain cells adjacent to that polyomino's cells" [polyomino polyominoes neighborlattice] (let [surroundings (neighboringcellsofpolyomino polyomino neighborlattice)] (into #{} (map #(polyominooncell % polyominoes) surroundings)) ))
The function polyominooncell
is a sort of inverse or lookup function for the collection of Polyomino
items: given a cell and a collection of Polyomino
items—which you’ll recall each contain a set
of cells they occupy—it returns the Polyomino
that’s occupying that cell.
And that brings us to neighboringpolyominoesofpolyomino
.
So to review, here’s the algorithm’s flow:
 given a polyomino (which is mainly a set of cells), and a collection of neighbor relations, determine which cells that are its neighbors
 for each of those neighboring cells, determine which
Polyomino
occupies that cell  return that as a set (important because one
Polyomino
can occupy two or more neighboring cells)
Is that roundabout? Absolutely. But by way of “justification” (if after the fact), let me point out that it works just the same way for a domino as it does for a monomino or an Ltromino or an Rpentomino, if you have those items in hand.
Which is the thing I enjoyed most about writing it this way.
“snug neighbors”
Next, at least for the “domino flipping” thing I’ve been describing so far, there’s this question of finding the subset of a domino’s neighbors that are “snug”.
Now you’ll recall that I defined “snugness” as “sharing a long side.” But hey, here’s a cunning trick I stumbled across along the way: When two dominoes “share a long side”, that is equivalent to saying that every cell occupied by one domino is one of its neighboringcellsofpolyomino
. If the two dominoes are endtoend, then one of each domino’s cells isn’t an immediate neighbor of the other domino. And if they’re offset, same thing (since we only define “neighboring” as occupying the four cardinal Von Neumann directions).
So the “snug neighbors” of a domino (or any polyomino) are the subset of the neighboringpolyominoesofpolyomino
for which every cell is also present in neighboringcellsofpolyomino
.
(defn snugneighborsofpolyomino "given a polyomino, return all neighboring polyominoes where _every cell_ of the polyomino is a neighbor of the given polyomino; these are the 'snug' neighbors" [polyomino polyominoes neighborlattice] (let [surroundings (neighboringcellsofpolyomino polyomino neighborlattice)] (filter #(set/subset? (:cells %) surroundings) (neighboringpolyominoesofpolyomino polyomino polyominoes neighborlattice)) ))
flipping pairs
Finally, once a “snug pair” has been identified, there’s the question of changing where those two dominoes are sitting.
(defn rotateddominopair "given two snug dominoes, return the pair of rotated dominoes, with equal probability of clockwise or counterclockwise rotation" [domino1 domino2] (let [c1 (sort (:cells domino1)) c2 (sort (:cells domino2))] (if (< (rand) 0.5) (vector (assoc domino1 :cells #{(first c1) (first c2)}) (assoc domino2 :cells #{(second c1) (second c2)})) (vector (assoc domino1 :cells #{(second c1) (second c2)}) (assoc domino2 :cells #{(first c1) (first c2)})) )))
This is pretty brute force, but it works well enough. And the overarching dynamics are simple as well: Start from the set of dominoes, and if you identify a “snug pair”, remove them from the set and replace them with the rotateddominopair
. Flip a coin to determine whether you rotate the pair clockwise or anticlockwise.
That’s literally it. That’s the dynamics running the animation in the top of this piece.
Summing up, and some observations
So that’s the way my code ended up using a “setbased” model to describe its dynamics. In describing it here, I’ve noticed some pretty nasty inefficiencies (like the fact that allneighbors
calls (combo/combinations setofcells 2)
for every cell, and that’s just dumb).
And to be honest I’m still not 100% sure I’ve correctly implemented, called or explained the neighboringcellsofcell
function and the structures that feed into it. And I know there are plenty of places where a vector
or list
would do, even though I’ve used a set
.
But on the other hand, this has been an interesting exploration, and fruitful in its way. For instance, as I mentioned above, it was easy to extend it to handle the case of a monomino tile without constructing much new stuff, just by extending the dynamics of dominoflipping.
Now a monomino, in this context at least, is a Polyomino
with only one cell in its :cells
field, instead of two. We know (from the literature) that in the case where the entire region is tiled with dominoes, the “snug flip” move suffices to eventually move every domino to every other place. But it’s not going to handle neighboring monominoes “flipping” with each other, or monomino–domino neighbors shifting around.
Or at least that was what I thought. Interestingly, a “snug flip” for monominoes is more or less already done. Any two monominoes are “snug neighbors” in every case where they’re neighbors at all (because every cell in one monomino is one of the neighboringcellsofcell
of a cell in the other monomino), and therefore exchanging their positions is simply a matter of swapping the :cells
they contain.
The “swap” of a domino with a neighboring monomino is a bit more complicated… but not by much. It’s easiest to visualize when they form a row or stack on one another; this “swap” is pretty obvious. If I can skip making a drawing for once and just use a typographic diagram, imagine we have three cells A
and B
and C
arranged in a row and covered by a domino and monomino like this (A B)(C)
. A “flip” of the two polyominoes would produce (A)(B C)
.
In the case where the monomino is “next to” the domino (forming an L
shape), we can make exactly the same sort of swap, if a little more carefully, “around the corner”. We shift the monomino to the cell farthest from it in the domino, and we swap that cell out of the domino and replace it with the original position of the monomino. The only trick here is to be sure to swap the “farthest” position, not the close one, or we end up “chopping up” our domino into two nonadjacent cells.
That, as they say, would be bad.
the code is coming from inside the house
I have an offbalance feeling about this paradigm, at least right at the moment.
Why did I consider but then choose to ignore the “obvious” arraybased solution, and go for a weird graph/subset based one? One doesn’t want to be a creative coder, at least without reason. And frankly, I’ve been trained long enough by my own mistakes to know that I shouldn’t ever make big leaps without working incrementally from a more stable place to stand.
So there’s a feeling of risk.
But as I’ve said, at least part of the reason I chose this path was because I already knew I eventually wanted to do stuff with more general types of tiles and regions of cells. And also because I wanted to explore whether this kind of moremathematical approach was even feasible in something as “playful” feeling as ClojureScript.
Yes to that, by the way. I am liking ClojureScript more all the time.
Mainly because, you know… it seems to work.
But that said, I still fell like I did a bad thing: There are no tests. I did some REPLbased testing, but to be frank nowhere near as much as I thought I should. And I think the code I’m seeing, now that I take the time to extract a little bit and write about it in public, isn’t as good as I’d like it to be. For some definition of “good” that involves trustworthiness and scalability and robustness.
And to date I haven’t actually changed the square lattice to some other kind. I mean, I believe (and the literature suggests) that the “snug neighbor” swap move will work just as well for a hexagonal lattice as it does for a square lattice… but I haven’t worked out yet how to draw a hexagonal lattice tiled with dominoes yet.
Are they going to be oblongs, or pairs of hexes, or what? We’ll see. And what does all this look like with Ltrominoes?
That may be trickier.
State of the shuffler
As you might imagine, from all this talk about monominoes and stuff, things have changed somewhat since the last time I showed you one of these diffusion simulations. The one in the diagram at the top of this article, for example, is doing things very differently from the code I presented.
Here’s that code actually running, using a setup I’ve been playing with for a little sideproject—more about that in a subsequent essay.
As always, if you want to restart the simulation, reload the page and it will reset to the (random) starting state.
You will notice a few things:
 The initial arrangement is kind of a “partial Aztec diamond”, with a staggered arrangement of “stretcher bricks” in the top part, but a collection of verticallystacked columns of bricks in the lower part.
 I’ve added a handful of monominoes at random, by splitting up some dominoes into two tiles each, which are colored white and black for each pair; you can see them floating around. Because they’re literally made by splitting a domino, they always start next to one another.
 If you don’t see any monominoes, just reload again. They’re placed probabilistically, and sometimes there may be none.
 The little number in the upper left shows the number of ticks of the clock (or
:opportunities
, as they’re called in thePolyomino
record structure I discussed above), in which a random polyomino is chosen with uniform probability, and if it has any “swappable” neighboring tiles then it is swapped with one of those (also chosen with uniform probability).
If you want to know where I’m going with this “houseshaped” layout, or why I find it so interesting, take some time to watch what happens over longish periods of time. Remember that every polyomino has an equal chance of being chosen as a target, and also that every “snug” neighbor of the target has an equal chance of being chosen to flip.
Yet something is very different in the top vs the bottom sections of the diagram, and also something is very different in the areas of the top where a monomino or two have wandered through, as opposed to the parts where the bricks are still stacked.
What is it about the top that makes it so much more static than the bottom part? I mean, we both know it’s something to do with how the dominoes are arranged. But what does that mean?
More on that next time. And also, I think it would be interesting to finally make these blue and orange, don’t you?

“The other day” in this case should be taken quite literally, since it’s been several weeks. A few interruptions have cropped up, things being what they are. But it was not this day, and therefore it was an other…. ↩