Published
Edited
Dec 9, 2020
2 stars
height = 512;
width = {
// to avoid problems with window width resizing, we are fixing the width value instead of using the stdlib value
// TODO: adjust tile scaling to allow for arbitrary width and fixed number of tiles per row
return height;
}
tileSize = 32; // each tile is square and this many pixels per side
class Tile {
constructor(topColor, rightColor, bottomColor, leftColor) {
this.topColor = topColor;
this.rightColor = rightColor;
this.bottomColor = bottomColor;
this.leftColor = leftColor;
}
allowedBy(top, right, bottom, left) {
return (top === null || this.topColor === top.bottomColor)
&& (right === null || this.rightColor === right.leftColor)
&& (bottom === null || this.bottomColor === bottom.topColor)
&& (left === null || this.leftColor === left.rightColor);
}
*[Symbol.iterator]() {
yield this.topColor;
yield this.rightColor;
yield this.bottomColor;
yield this.leftColor;
}
}
class TileSet {
constructor(colors, tiles) {
this.colors = colors;
this.tiles = tiles;
this.colorScale = d3.scaleOrdinal([...colors.keys()], colors);
}
getTile(index) {
if (index === null) {
return null;
} else {
return this.tiles[index];
}
}
getRandomTileIndex(min = 0, max = this.tiles.length) {
return getRandomInt(min, max)
}
}
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];
}
}
class Tree {
constructor(data, parent) {
this.data = data;
this.children = [];
this.parent = parent;
}
hasChildren() {
return this.children.length > 0;
}
addChild(child) {
this.children.push(child);
}
popRandomChild() {
const index = getRandomInt(0, this.children.length);
const child = this.children.splice(index, 1);
return child[0];
}
clearChildren() {
this.children = [];
}
}
function chooseRandom(arr) {
const index = getRandomInt(0, arr.length);
return arr[index];
}
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min) + min);
}
import {View} from "@mbostock/synchronized-views";
d3 = require("d3@6");
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
