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 domino-flipping systems I’ve been showing you here (see also A, B, C, D and E), and we did a bit of code-talk. 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:orangedominoes alone?
See, there’s a bunch of pretty fancy combinatorics and constraint-handling 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 graphy-theoreticalish: 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 rainbow-colored 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, making-it-myself and watching the long-term dynamics kind of way of “seeing”—that it’s true, what we’re told about these little two-snug-dominoes-rotating “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 counter-clockwise (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 re-emphasize 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, object-oriented and functional programming and such.
I think I know at least two reasons why Ron made question-like 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 two-dimensional 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 over-enthused 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 two-dimensional 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 get-go.
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 non-rectangular 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 masked-out pixels. Or maybe the other way around: Maybe a colored mask-layer 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 reasonable-seeming 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 two-dimensional 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 2-d 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 array-based 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 set-based representation that I did. Something about Clojure (and ClojureScript), maybe. Something about behavior-driven 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 decades-old 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 domino-tilings.core (:require [quil.core :as q :include-macros true] [quil.middleware :as m] [clojure.math.combinatorics :as combo] [clojure.set :as set] )) (def config "global stuff for setting up" {:cell-size 20 :lattice-side 20 :proportion-of-monominoes 0.0 :save-interval 100} ) (defn rectangular-region-of-cells "returns a Clojure set containing 2-d position index vectors; yes, this is weird" [width height] (into #{} (for [i (range width) j (range height)] [i j])) ) (defn aztec-diamond-of-cells "returns a set containing cells that fill an Aztec diamond of the given size" [edge-size] (let [all (rectangular-region-of-cells edge-size edge-size) corner (/ edge-size 2) opposite-corner (+ edge-size edge-size (- corner))] (->> all (filter #(<= (dec corner) (apply + %)) ,) ; (filter #(> opposite-corner (apply + %)) ,) ; (filter #(< (dec corner) (+ (first %) (- edge-size (second %)))) ,) (filter #(>= opposite-corner (+ (first %) (- edge-size (second %)))) ,) ))) (defn adjacent-cells? "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 neighboring-cells "given a cell and a set of cells, returns all neighbors of the former" [cell set-of-cells] (filter #(adjacent-cells? cell %) set-of-cells)) (defn all-neighbors "produces a set of all pairs of Von Neumann neighbors (as sets) from a given set of cells" [set-of-cells] (set (map set (filter #(apply adjacent-cells? %) (combo/combinations set-of-cells 2) )))) (defn draw-cell "draw a square, with a 1-pixel 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 initial-rectangle-dominoes "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 (:lattice-side config) delta-h (/ 256 scale)] (for [i (range width) j (range 0 height 2)] (->Polyomino #{[i j] [i (inc j)]} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation (+ (* delta-h i) j 150) :brightness (+ (* delta-h j) i 100)} 0 0 )))) (defn monominoes-everywhere "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 (:lattice-side config) delta-h (/ 256 scale)] (for [c cells] (let [i (first c) j (second c)] (->Polyomino #{c} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation (+ (* delta-h i) j 150) :brightness (+ (* delta-h j) i 100)} 0 0 ))))) (defn all-polyomino-cells-valid? "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 right-lattice-neighbor [cell] [(inc (first cell)) (second cell)] ) (defn aztec-diamond-dominoes [edge-size cells] (loop [unused-cells (sort cells) new-dominoes []] (if (empty? unused-cells) new-dominoes (let [next-cell (first unused-cells) neighbor (right-lattice-neighbor next-cell) i (first next-cell) j (second next-cell) delta-h (/ 256 edge-size)] (recur (remove #{next-cell neighbor} unused-cells) (conj new-dominoes (->Polyomino #{next-cell neighbor} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation (+ (* delta-h i) j 150) :brightness (+ (* delta-h j) i 100)} 0 0) )))))) (defn aztec-diamond-mostly [edge-size cells proportion-of-monominoes] (loop [unused-cells (sort cells) new-dominoes []] (if (empty? unused-cells) new-dominoes (let [next-cell (first unused-cells) neighbor (right-lattice-neighbor next-cell) i (first next-cell) j (second next-cell) delta-h (/ 256 edge-size)] (recur (remove #{next-cell neighbor} unused-cells) (if (<= (rand) proportion-of-monominoes) (into new-dominoes [(->Polyomino #{next-cell} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation 0; (+ (* delta-h i) j 10) :brightness 0; (+ (* delta-h j) i 100) } 0 0) (->Polyomino #{neighbor} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation 0 ; (+ (* delta-h i) j 10) :brightness 255 ; (+ (* delta-h j) i 100) } 0 0)] ) (conj new-dominoes (->Polyomino #{next-cell neighbor} {:hue (mod (+ (* delta-h i) (* delta-h j)) 256) :saturation (+ (* delta-h i) j 150) :brightness (+ (* delta-h j) i 100)} 0 0)) )))))) (defn draw-polyomino "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)] (draw-polyomino polyomino size h s b)))) (defn neighboring-cells-of-cell "given a cell, return a set of all the other cells that are its neighbors, accoring to the neighborhood lattice provided" [cell neighbor-lattice] (apply set/union (filter #(contains? % cell) neighbor-lattice))) (defn neighboring-cells-of-polyomino "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 neighbor-lattice] (let [insides (:cells polyomino)] (set/difference (apply set/union (map #(neighboring-cells-of-cell % neighbor-lattice) insides)) insides ))) (defn polyomino-on-cell "return the polyomino that occupies a given cell" [cell polyominoes] (first (filter #(contains? (:cells %) cell) polyominoes))) (defn set-overlap? "return `true` if the intersection of two sets is nonempty" [set1 set2] (not (empty? (set/intersection set1 set2)))) (defn neighboring-polyominoes-of-polyomino "given a polyomino, return all other polyominoes that contain cells adjacent to that polyomino's cells" [polyomino polyominoes neighbor-lattice] (let [surroundings (neighboring-cells-of-polyomino polyomino neighbor-lattice)] (into #{} (map #(polyomino-on-cell % polyominoes) surroundings)) )) (defn snug-neighbors-of-polyomino "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 neighbor-lattice] (let [surroundings (neighboring-cells-of-polyomino polyomino neighbor-lattice)] (filter #(set/subset? (:cells %) surroundings) (neighboring-polyominoes-of-polyomino polyomino polyominoes neighbor-lattice)) )) (defn monomino-neighbors-of-polyomino "given a polyomino, return all neighboring polyominoes which contain only one cell" [polyomino polyominoes neighbor-lattice] (let [surroundings (neighboring-cells-of-polyomino polyomino neighbor-lattice)] (filter #(and (monomino? %) (set/subset? (:cells %) surroundings)) (neighboring-polyominoes-of-polyomino polyomino polyominoes neighbor-lattice)) )) (defn highlight-cell "draw a black dot on a cell" [cell size] (let [half-square (/ size 2)] (q/translate half-square half-square) (q/fill 10 10 10) (q/ellipse (* size (first cell)) (* size (second cell)) half-square half-square) (q/translate (- half-square) (- half-square)) )) (defn rotated-domino-pair "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 swapped-monomino-pair "given two monominoes, returns them with their positions swapped" [monomino1 monomino2] (vector (assoc monomino1 :cells (:cells monomino2)) (assoc monomino2 :cells (:cells monomino1)) )) (defn swapped-domino-and-monomino "given a domino and (adjacent!) monomino, returns the domino shifted to the other position in the triple of cells" [domino monomino] (let [m-cells (:cells monomino) d-cells (:cells domino) m-neighbor (neighboring-cells (first m-cells) d-cells) m-nonneighbor (set/difference d-cells m-neighbor) ] (vector (assoc domino :cells (set/union m-cells m-neighbor)) (assoc monomino :cells m-nonneighbor)) )) (defn setup [] "build the Quil state" (let [s (:lattice-side config) all-positions (aztec-diamond-of-cells s) cell-neighbors (all-neighbors all-positions) initial-polyominoes (aztec-diamond-mostly s all-positions (:proportion-of-monominoes config)) ] (q/frame-rate 60) (q/color-mode :hsb) {:cells all-positions :lattice cell-neighbors :polyominoes initial-polyominoes :changed-polyominoes [] :step-counter 0} )) (defn swap-in-pair "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 update-state [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) focus-polyomino (rand-nth (vec polyominoes)) neighbors (neighboring-polyominoes-of-polyomino focus-polyomino polyominoes lattice) snug-neighbors (snug-neighbors-of-polyomino focus-polyomino (:polyominoes state) (:lattice state)) ] {:cells cells :lattice lattice :polyominoes (cond (and (domino? focus-polyomino) (seq snug-neighbors)) (let [partner (rand-nth (into [] snug-neighbors))] (swap-in-pair [focus-polyomino partner] (if (monomino? partner) [focus-polyomino partner];(swapped-domino-and-monomino focus-polyomino partner) (rotated-domino-pair focus-polyomino partner)) polyominoes)) (and (monomino? focus-polyomino) (seq neighbors)) (let [partner (rand-nth (into [] neighbors))] (swap-in-pair [focus-polyomino partner] (if (domino? partner) (swapped-domino-and-monomino partner focus-polyomino) (swapped-monomino-pair focus-polyomino partner)) polyominoes)) :else polyominoes) :changed-polyominoes [] :step-counter (inc (:step-counter state))} )) (defn draw-state [state] "clear the background, draw all the cells and domino polyominoes, and highlight any that want highlighting" (let [s (:cell-size config)] (q/background 240) (q/no-stroke) (doall (map #(draw-cell % s 0 0 200) (:cells state))) (doall (map #(draw-polyomino % s) (:polyominoes state))) (q/fill 0 255 0) (q/text (:step-counter state) 20 20) ; (if (zero? (mod (:step-counter state) 100)) ; (do (q/save-frame "./foo-####.png") ; (q/text "saving" 20 50))) )) (q/defsketch domino-tilings :host "domino-tilings" :size [400 400] :setup setup :update update-state :draw draw-state :middleware [m/fun-mode])
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 draw-state and update which together produce an “infinite loop” of frames of animation. As with all these animation-loop frameworks, the update-draw loop is the key.
Let me broadly sketch the overall approach I took, to contrast with the 2-d 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 (:lattice-side config) all-positions (aztec-diamond-of-cells s) cell-neighbors (all-neighbors all-positions) initial-polyominoes (aztec-diamond-mostly s all-positions (:proportion-of-monominoes config)) ] (q/frame-rate 60) (q/color-mode :hsb) {:cells all-positions :lattice cell-neighbors :polyominoes initial-polyominoes :changed-polyominoes [] :step-counter 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 frame-rate 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: all-positions and cell-neighbors and initial-polyominoes.
First, because I’m concerned with the prospect of non-square 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 all-positions, 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 three-step 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 cell-neighbors. Because I wanted to see what would happen computationally, I did not set this up as a key-value map organized by cells as keys, but simply as a “set of sets”.
Each set in cell-neighbors is simply the pair of items from all-positions that happen to be adjacent to one another.
Indeed, that’s exactly how it’s constructed: For every item in all-positions, we call the function all-neighbors. The idea of “next to” is in some sense “buried” in a predicate function called adjacent-cells?, 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 adjacent-cells? "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 neighboring-cells "given a cell and a set of cells, returns all neighbors of the former" [cell set-of-cells] (filter #(adjacent-cells? cell %) set-of-cells)) (defn all-neighbors "produces a set of all pairs of Von Neumann neighbors (as sets) from a given set of cells" [set-of-cells] (set (map set (filter #(apply adjacent-cells? %) (combo/combinations set-of-cells 2) ))))
For example, suppose I am building a square region from a “bag” of 100 cells in all-positions, set out in a 10x10 lattice. I accumulate all-neighbors by taking every possible pair of cells in turn, and asking whether the two cells in question are adjacent-cells? 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, cell-neighbors, of collections containing pairs of adjacent cell items. Nothing else, no repeats (because they’re sets 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 cell-neighbors; 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 non-rectangular region, like the Aztec diamond, I can start by making the rectangular region first as a temporary all-positions, 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 cell-neighbors, 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 rectangular-region-of-cells and then subtract another rectangular-region-of-cells from it, before starting to build the all-neighbors structure.
It’s not that cells are “marked unavailable”, it’s that they’re not even present in all-positions 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 Poisson-sampled 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 adjacent-cells? 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 other-shaped 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 all-positions and cell-neighbors. 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 neighboring-cells-of-cell "given a cell, return a set of all the other cells that are its neighbors, according to the neighborhood lattice provided" [cell neighbor-lattice] (apply set/union (filter #(contains? % cell) neighbor-lattice))) (defn neighboring-cells-of-polyomino "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 neighbor-lattice] (let [insides (:cells polyomino)] (set/difference (apply set/union (map #(neighboring-cells-of-cell % neighbor-lattice) insides)) insides )))
The function neighboring-cells-of-cell 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 cell-neighbors, 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 neighboring-cells-of-polyomino 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 neighboring-polyominoes-of-polyomino:
(defn polyomino-on-cell "return the polyomino that occupies a given cell" [cell polyominoes] (first (filter #(contains? (:cells %) cell) polyominoes))) (defn neighboring-polyominoes-of-polyomino "given a polyomino, return all other polyominoes that contain cells adjacent to that polyomino's cells" [polyomino polyominoes neighbor-lattice] (let [surroundings (neighboring-cells-of-polyomino polyomino neighbor-lattice)] (into #{} (map #(polyomino-on-cell % polyominoes) surroundings)) ))
The function polyomino-on-cell 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 neighboring-polyominoes-of-polyomino.
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
Polyominooccupies that cell - return that as a set (important because one
Polyominocan 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 L-tromino or an R-pentomino, 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 neighboring-cells-of-polyomino. If the two dominoes are end-to-end, 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 neighboring-polyominoes-of-polyomino for which every cell is also present in neighboring-cells-of-polyomino.
(defn snug-neighbors-of-polyomino "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 neighbor-lattice] (let [surroundings (neighboring-cells-of-polyomino polyomino neighbor-lattice)] (filter #(set/subset? (:cells %) surroundings) (neighboring-polyominoes-of-polyomino polyomino polyominoes neighbor-lattice)) ))
flipping pairs
Finally, once a “snug pair” has been identified, there’s the question of changing where those two dominoes are sitting.
(defn rotated-domino-pair "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 rotated-domino-pair. 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 “set-based” model to describe its dynamics. In describing it here, I’ve noticed some pretty nasty inefficiencies (like the fact that all-neighbors calls (combo/combinations set-of-cells 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 neighboring-cells-of-cell 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 domino-flipping.
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 neighboring-cells-of-cell 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 non-adjacent cells.
That, as they say, would be bad.
the code is coming from inside the house
I have an off-balance feeling about this paradigm, at least right at the moment.
Why did I consider but then choose to ignore the “obvious” array-based 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 more-mathematical 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 REPL-based 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 L-trominoes?
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 side-project—more about that in a subsequent essay.
As always, if you want to re-start the simulation, re-load 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 vertically-stacked 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 re-load 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 thePolyominorecord 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 “house-shaped” layout, or why I find it so interesting, take some time to watch what happens over long-ish 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…. ↩