2b:null 2c:["$","title",null,{"children":"Wang tiles | Adam Sasine | Observable"}] 31:T175d,class Grid { constructor(tilesGroup, tileSize, tileSet) { this.tilesGroup = tilesGroup; this.tileSize = tileSize; this.tileSet = tileSet; this._columns = Math.floor(width / this.tileSize); this._rows = Math.floor(height / this.tileSize); } drawTiles(indices2d) { this.tilesGroup .classed("tiles", true) .attr("transform", `translate(${this.tileSize / 2}, ${this.tileSize / 2}) scale(${this.tileSize})`); const allRows = this.tilesGroup .selectAll("g.row") .data(indices2d) .join("g") .classed("row", true) .attr("transform", (_, i) => `translate(0, ${i})`); const allTileGroups = allRows .selectAll("g.tile") .data(row => row) .join("g") .classed("tile", true) .attr("transform", (_, i) => `translate(${i}, 0) rotate(180)`); const allWangTiles = allTileGroups .selectAll("path.side") .data(tileIndex => this.tileSet.getTile(tileIndex)) .join("path") .classed("side", true) .attr("d", "M 0,0 l 0.5,0.5 h -1 Z") .attr("fill", this.tileSet.colorScale) .attr("stroke", borders ? "black" : "none") .attr("vector-effect", "non-scaling-stroke") .attr("transform", (_, i) => `rotate(${90 * i})`); } *getRandomTileIndicesWithWalls() { const indices2d = new Array(this._rows); for (let row = 0; row < this._rows; row++) { indices2d[row] = new Array(this._columns); for (let col = 0; col < this._columns; col++) { indices2d[row][col] = null; } } // fill in initial constraints // top and bottom walls const lastRow = this._rows - 1; for (let col = 0; col < this._columns; col++) { indices2d[0][col] = 0; indices2d[lastRow][col] = 0; } // left and right walls const lastColumn = this._columns - 1; for (let row = 0; row < this._columns; row++) { indices2d[row][0] = 0; indices2d[row][lastColumn] = 0; } // yield indices2d[0]; // the center of the tiling is a random choice at every node from the set of possible tiles // each possible tile must satisfy the constraint given by tile.allowedBy(top, right, bottom, left) const root = new Tree(null); let current = root; const start = 0; const endRows = this._rows; const endColumns = this._columns; let row = start; while (row < endRows) { let col = start; while (col < endColumns) { // clear current tile indices2d[row][col] = null; let possibleTiles; if (current.hasChildren()) { // we have visited here before and already removed bad nodes, try again with another node possibleTiles = current.children.map(child => child.data); } else { // first time here, add all possible tiles for this location possibleTiles = Array.from(this.getPossibleTileIndices(indices2d, row, col)); } // if no possible tiles, go back to parent, clear subtree, and retry if (possibleTiles.length === 0) { if (col === start) { // reached beginning of row, go back to end of previous row if (row === start) { // reached first tile, no possible tiling return; } col = endColumns - 1; row--; } else { col--; } current = current.parent; current.clearChildren(); } else { // add them to the tree possibleTiles.map(tile => new Tree(tile, current)).forEach(child => current.addChild(child)); // pop a random one and set it in the grid const possibleTile = current.popRandomChild(); if (possibleTile === undefined) { console.log("current grid:", indices2d); console.log("current tree:", current); console.log("current possibilities:", possibleTiles); console.log(`(row, col): (${row}, ${col})`); } indices2d[row][col] = possibleTile.data; // try next cell current = possibleTile; col++; } } row++; } for (let row = 0; row < this._rows; row++) { yield indices2d[row]; } // for (let row = 1; row < this._rows - 1; row++) { // for (let col = 1; col < this._columns - 1; col++) { // const possibleTiles = Array.from(this.getPossibleTileIndices(indices2d, row, col)); // if (possibleTiles.length === 0) { // // TODO: walk back up tree of random choices and try another // return; // } // indices2d[row][col] = chooseRandom(possibleTiles); // } // // yield the entire row instead of individual tiles // // therefore this generator yields a 2D grid // yield indices2d[row]; // } // yield indices2d[this._rows - 1]; } *getPossibleTileIndices(grid, row, column) { // generate an iterable of possible tiles for a given coordinate // the possible tiles should satisfy all neighboring tiles' constraints const top = row > 0 ? this.tileSet.getTile(grid[row - 1][column]) : null; const right = column < this._columns - 1 ? this.tileSet.getTile(grid[row][column + 1]) : null; const bottom = row < this._rows - 1 ? this.tileSet.getTile(grid[row + 1][column]) : null; const left = column > 0 ? this.tileSet.getTile(grid[row][column - 1]) : null; for (let i = 0; i < this.tileSet.tiles.length; i++) { const tile = this.tileSet.getTile(i); if (tile.allowedBy(top, right, bottom, left)) { yield i; } } } indexToRowColumn(index) { const row = Math.floor(index / this._columns); const column = Math.floor(index % this._columns); return [row, column]; } }32:[] 2f:{"id":"6b7d8f5376633365","slug":"wang-tiles","title":"Wang tiles","thumbnail":"f2da45603acbc67c32f0452906c3df0ec3a9e0106c65b5d7c9096b4140938769","access_level":"public","create_time":"$D2020-12-04T12:18:49.364Z","update_time":"$D2021-08-22T02:18:12.089Z","view_time":null,"first_public_time":"$D2020-12-04T15:37:04.103Z","fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"88f46a18608f4703","login":"asasine","name":"Adam Sasine","avatar_url":"https://avatars-next.observableusercontent.com/76eb676b927ff768da6863d7e51e0611b99c7324be9cb323a367d577a8ee5923","tier":"starter_2024"},"version":950,"publish_version":950,"role":null,"authored":false,"authors":[{"type":"individual","id":"ce5642080d938bd5","login":"asasine","name":"Adam Sasine","avatar_url":"https://avatars-next.observableusercontent.com/76eb676b927ff768da6863d7e51e0611b99c7324be9cb323a367d577a8ee5923","tier":null}],"members":[{"type":"individual","id":"ce5642080d938bd5","login":"asasine","name":"Adam Sasine","avatar_url":"https://avatars-next.observableusercontent.com/76eb676b927ff768da6863d7e51e0611b99c7324be9cb323a367d577a8ee5923","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"title":"Wang tiles","cells":[{"id":0,"value":"md`# Wang tiles\nFrom the Wikipedia article on [Wang tiles](https://en.wikipedia.org/wiki/Wang_tile):\n\n> **Wang tiles** (or **Wang dominoes**), first proposed by mathematician, logician, and philosopher [Hao Wang](https://en.wikipedia.org/wiki/Hao_Wang_(academic)) in 1961, are a class of [formal systems](https://en.wikipedia.org/wiki/Formal_system). They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, _without_ rotating or reflecting them.\n\nThe tiling below follows the proper rules for Wang tiles, but it uses a simple tile set of only two colors. Hit the **Reset** button to generate a new arrangement.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":376,"value":"viewof resetButton = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":86,"value":"{\n resetButton;\n \n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", height);\n \n const tilesGroup = svg.append(\"g\");\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n \n const maxTilesPerRow = Math.floor(width / tileSize);\n const maxTilesPerColumn = Math.floor(height / tileSize);\n const tileIndices = grid.getRandomTileIndicesWithWalls(maxTilesPerRow, maxTilesPerColumn);\n \n grid.drawTiles(tileIndices);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":400,"value":"md`To make a Wang tiling, we first start with a predetermined set of _tiles_. The complete set of tiles is called the _tile set_. Each tile consists of four _sides_, denoted by a specific color.\n\nHere are all of the tiles in the current tile set.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":414,"value":"{\n const h = Math.ceil(tileSet.tiles.length * tileSize / width) * tileSize;\n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", h);\n \n const tilesGroup = svg.append(\"g\")\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[...tileSet.tiles.keys()]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":287,"value":"md`The below tile is tile **${tileViewerIndex}** from the current tile set. Check out a different tile by adjusting the slider below.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":265,"value":"{\n const scale = 4;\n const svg = d3.create(\"svg\")\n .attr(\"width\", tileSize * scale)\n .attr(\"height\", tileSize * scale);\n \n const tilesGroup = svg.append(\"g\")\n .attr(\"transform\", `scale(${scale})`)\n .append(\"g\");\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[tileViewerIndex]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":276,"value":"viewof tileViewerIndex = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":7,"value":"md`# Appendix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":788,"value":"md`## Tests`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":566,"value":"md`## Tile sets`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":919,"value":"colors = [\"#f00\", \"#0f0\", \"#00f\", \"#e8e8e8\"];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":431,"value":"tileSet = new TileSet(colors, wallTileSet.concat(simpleTileSet));","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":931,"value":"{\n const h = Math.ceil(tileSet.tiles.length * tileSize / width) * tileSize;\n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", h);\n \n const tilesGroup = svg.append(\"g\")\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[...tileSet.tiles.keys()]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":281,"value":"wikipediaTileSet = [\n new Tile(0, 0, 0, 1),\n new Tile(2, 0, 2, 1),\n new Tile(0, 1, 1, 1),\n new Tile(3, 2, 0, 2),\n new Tile(2, 2, 3, 2),\n new Tile(3, 3, 0, 3),\n new Tile(0, 1, 2, 3),\n new Tile(2, 3, 2, 0),\n new Tile(2, 0, 3, 0),\n new Tile(1, 1, 2, 0),\n new Tile(0, 3, 0, 1),\n];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":916,"value":"{\n const tileSet = new TileSet(colors, wikipediaTileSet);\n \n const h = Math.ceil(tileSet.tiles.length * tileSize / width) * tileSize;\n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", h);\n \n const tilesGroup = svg.append(\"g\")\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[...tileSet.tiles.keys()]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":861,"value":"simpleTileSet = [\n new Tile(0, 3, 3, 3),\n new Tile(3, 0, 3, 3),\n new Tile(3, 3, 0, 3),\n new Tile(3, 3, 3, 0),\n \n new Tile(0, 0, 3, 3),\n new Tile(3, 0, 0, 3),\n new Tile(3, 3, 0, 0),\n new Tile(0, 3, 3, 0),\n \n new Tile(0, 0, 0, 3),\n new Tile(3, 0, 0, 0),\n new Tile(0, 3, 0, 0),\n new Tile(0, 0, 3, 0),\n \n new Tile(3, 0, 3, 0),\n new Tile(0, 3, 0, 3),\n \n new Tile(0, 0, 0, 0),\n\n];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":927,"value":"{\n const tileSet = new TileSet(colors, simpleTileSet);\n \n const h = Math.ceil(tileSet.tiles.length * tileSize / width) * tileSize;\n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", h);\n \n const tilesGroup = svg.append(\"g\")\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[...tileSet.tiles.keys()]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":571,"value":"wallTileSet = [\n new Tile(3, 3, 3, 3),\n];","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":934,"value":"{\n const tileSet = new TileSet(colors, wallTileSet);\n \n const h = Math.ceil(tileSet.tiles.length * tileSize / width) * tileSize;\n const svg = d3.create(\"svg\")\n .attr(\"width\", width) \n .attr(\"height\", h);\n \n const tilesGroup = svg.append(\"g\")\n \n const grid = new Grid(tilesGroup, tileSize, tileSet);\n grid.drawTiles([[...tileSet.tiles.keys()]]);\n \n yield svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":465,"value":"md`## Settings`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":459,"value":"md`Toggle this to enable or disable borders around the tiles`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":445,"value":"viewof borders = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":9,"value":"height = 512;","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":177,"value":"width = {\n // to avoid problems with window width resizing, we are fixing the width value instead of using the stdlib value\n // TODO: adjust tile scaling to allow for arbitrary width and fixed number of tiles per row\n return height;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":185,"value":"tileSize = 32; // each tile is square and this many pixels per side","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":621,"value":"md`## Helper classes`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":676,"value":"class Tile {\n constructor(topColor, rightColor, bottomColor, leftColor) {\n this.topColor = topColor;\n this.rightColor = rightColor;\n this.bottomColor = bottomColor;\n this.leftColor = leftColor;\n }\n \n allowedBy(top, right, bottom, left) {\n return (top === null || this.topColor === top.bottomColor)\n && (right === null || this.rightColor === right.leftColor)\n && (bottom === null || this.bottomColor === bottom.topColor)\n && (left === null || this.leftColor === left.rightColor);\n }\n \n *[Symbol.iterator]() {\n yield this.topColor;\n yield this.rightColor;\n yield this.bottomColor;\n yield this.leftColor;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":684,"value":"class TileSet {\n constructor(colors, tiles) {\n this.colors = colors;\n this.tiles = tiles;\n \n this.colorScale = d3.scaleOrdinal([...colors.keys()], colors);\n }\n \n getTile(index) {\n if (index === null) {\n return null;\n } else {\n return this.tiles[index];\n }\n }\n \n getRandomTileIndex(min = 0, max = this.tiles.length) {\n return getRandomInt(min, max)\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":624,"value":"$31","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":877,"value":"class Tree {\n constructor(data, parent) {\n this.data = data;\n this.children = [];\n this.parent = parent;\n }\n \n hasChildren() {\n return this.children.length > 0;\n }\n \n addChild(child) {\n this.children.push(child);\n }\n \n popRandomChild() {\n const index = getRandomInt(0, this.children.length);\n const child = this.children.splice(index, 1);\n return child[0];\n }\n \n clearChildren() {\n this.children = [];\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":463,"value":"md`## Helper functions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":834,"value":"function chooseRandom(arr) {\n const index = getRandomInt(0, arr.length);\n return arr[index];\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":835,"value":"function getRandomInt(min, max) {\n return Math.floor(Math.random() * (max - min) + min);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":469,"value":"md`## Imports`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":272,"value":"import {View} from \"@mbostock/synchronized-views\";","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"},{"id":87,"value":"d3 = require(\"d3@6\");","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined"}],"files":"$W32","stdlib":"1","titling":"auto"}} 30:"$2f:body"