Penrose Tile Maker - OpenProcessing

mySketch
xxxxxxxxxx
 
function penroseTileMaker(p) {
  const scale = 50;
  let tiles = [];
  
  let pendingTile;
  
  // Track the closest edge for the current mouse location
  let adjacentTile;
  let adjacentTileEdge;
  
  p.setup = function() {
    p.createCanvas(1112, 834);
    p.angleMode(p.DEGREES);
    p.mouseX = 1112/2;
    p.mouseY = 835/2; 
    p.mouseMoved();
    p.noLoop();
  }
​
  p.draw = function() {
    p.background('white');
    
    for (const tile of tiles) {
      tile.drawTile(255);
    }
    
    if (pendingTile) {
      pendingTile.drawTile(128);
    }
  }
  
  p.keyPressed =
  p.keyReleased =
  p.mouseMoved = function () {
    if (p.keyIsPressed && p.key === 'Meta') {
      pendingTile = undefined;
      p.redraw();
      return;
    }
    
    const [type, alternate] = p.keyIsPressed && p.key === 'Shift' ? ['Thin', 'Thick'] : ['Thick', 'Thin'];
    if (tiles.length === 0) {
      // Simple case
      const xOffset = scale * p.cos(Rhombs[type].Angles[0] / 2);
      pendingTile = new Tile(
        type,
        { x: p.mouseX - xOffset, y: p.mouseY },
        0
      );
    } else {
      // Find the nearest edge
      //   Find the closest vertice.
      //   Of the tiles touching that vertice, find the closest adjacent vertice
      //   If there are two tiles sharing that edge, fuggedaboutit
      
      let matches;
      // TODO: instead of O(N) search we could probably do something more efficient
      // by arranging the vertices in a quadtree. However I need to think more
      // about how such an implementation would work.
      for (let ix = 0; ix < tiles.length; ix++) {
        let closest;
        // Find the closes vertex for the current rhomb
        for (let vx = 0; vx < 4; vx++) {
          let v = tiles[ix].vertices[vx];
          let dx = p.mouseX - v.x;
          let dy = p.mouseY - v.y;
          let sqdist = dx * dx + dy * dy;
          if (!closest || sqdist < closest.sqdist) {
            closest = { sqdist, vx };
          }
        }
        
        if (!matches) {
          matches = {
            sqdist: closest.sqdist,
            vertex: tiles[ix].vertices[closest.vx],
            tileVertices: [{ ix, vx: closest.vx }]
          }
        } else {
          let v = tiles[ix].vertices[closest.vx];
          // see if this is same vertex (accounting for floating point errors)
          // This assumes that scale >= 1
          if (vertexMatch(v, matches.vertex)) {
            matches.tileVertices.push({ ix, vx: closest.vx });
          } else if (closest.sqdist < matches.sqdist) {
            matches = {
              sqdist: closest.sqdist,
              vertex: tiles[ix].vertices[closest.vx],
              tileVertices: [{ ix, vx: closest.vx }]
            }
          }
        }
      }
    
      let edges;
      for (const tileVertex of matches.tileVertices) {
        for (const adjIx of [(tileVertex.vx + 1) % 4, (tileVertex.vx + 3) % 4]) {
          let v = tiles[tileVertex.ix].vertices[adjIx];
          let dx = p.mouseX - v.x;
          let dy = p.mouseY - v.y;
          let sqdist = dx * dx + dy * dy;
          if (!edges) {
            edges = {
              sqdist,
              start: matches.vertex,
              end: v,
              tileEdges: [{ ix: tileVertex.ix, startVx: tileVertex.vx, endVx: adjIx }]
            };
          } else if (vertexMatch(v, edges.end)) {
            // This is another tile with the same edge
            edges.tileEdges.push({
              ix: tileVertex.ix,
              startVx: tileVertex.vx,
              endVx: adjIx
            });
          } else if (sqdist < edges.sqdist) {
            // This condition has to come after checking if the alternate edge is
            // identical to avoid floating point error issues
            edges = {
              sqdist,
              start: matches.vertex,
              end: v,
              tileEdges: [{ ix: tileVertex.ix, startVx: tileVertex.vx, endVx: adjIx }]
            };
          }
        }
      }
      
      if (edges.tileEdges.length > 1) {
        // This edge already has two touching tiles. We're pau
        pendingTile = undefined;
      } else {
        let vx = Math.min(edges.tileEdges[0].startVx, edges.tileEdges[0].endVx);
        let otherVx = Math.max(edges.tileEdges[0].startVx, edges.tileEdges[0].endVx);
        if (vx === 0 && otherVx == 3) {
          // The edge index corresponds to the "starting" vertex index. Normally that
          // is the lesser index (i.e. 0-1, 1-2, 2-3), but not for the 3-0 edge.
          var temp = vx;
          vx = otherVx;
          otherVx = vx;
        }
        
        let existingTile = tiles[edges.tileEdges[0].ix];
        
        if (!pendingTile ||
            existingTile != adjacentTile ||
            vx != adjacentTileEdge) {
          
          adjacentTile = existingTile;
          adjacentTileEdge = vx;
​
          let edgeType = existingTile.edgeTypes[vx];
          let matchingEdgeType = edgeType[0] + (edgeType[1] === '+' ? '-' : '+');
          // There is an anomoly with the B edges of thin Rhombs. Thick Rhomb B+ edges
          // can connect to either Thick or Thin Rhomb B-, however Thin Rhomb B+ edges
          // can *only* connect to the *Thick* Rhomb B- edges.
          //
          // By stripping the ? off when looking for a match for a Thin Rhomb edge,
          // and adding the ? when looking for a Thick Rhomb edge, and then using
          // startsWith rather than === below, we are able to enforce this rule.
          if (existingTile.type === 'Thick' && matchingEdgeType[0] === 'R') {
            matchingEdgeType += '?';
          }
​
          // determine the tile orientation that will fit next to this edge.
          let requiredAngle = existingTile.orientation + existingTile.angles[0] / 2;
          for (let i = 1; i <= vx; i++) {
            requiredAngle -= (180 - existingTile.angles[i % 2]);
          }
​
          requiredAngle = (requiredAngle + 180) % 360;
​
          for (const newTileType of [type, alternate]) {
            let angles = Rhombs[newTileType].Angles;
            let edgeTypes = Rhombs[newTileType].Edges;
            let naturalAngle = angles[0] / 2;
            let mx;
            for (let i = 0; i < 4; i++) {
              if (matchingEdgeType.startsWith(edgeTypes[i])) {
                mx = i;
                break;
              }
​
              naturalAngle -= (180 - angles[(i + 1) % 2]);
            }
​
            if (mx !== undefined) {
              // Check if this tile is compatible with the neighbors around both vertices.
​
              // Check the counter clockwise corner of the current edge
              let vxPlusCorners = [`${Rhombs[newTileType].Prefix}${mx}`];
              let next = { tile: existingTile, edge: vx };
              while (next) {
                let nextEdgeIx = (next.edge + 1) % 4;
                vxPlusCorners.push(`${Rhombs[next.tile.type].Prefix}${nextEdgeIx}`);
                next = next.tile.adjacent[nextEdgeIx];
              }
              // This walk is clockwise around the vertex, so we need to reverse it
              vxPlusCorners.reverse();
​
              let vxPlusShapes = getValidShapes(vxPlusCorners);
              if (vxPlusShapes.length == 0) {
                pendingTile = undefined;
              } else {
                // Check the clockwise corner of the current edge;
                let vxMinusCorners = [`${Rhombs[newTileType].Prefix}${(mx + 1) % 4}`];
                let next = { tile: existingTile, edge: vx };
                while (next) {
                  let nextEdgeIx = (next.edge + 3) % 4;
                  vxMinusCorners.push(`${Rhombs[next.tile.type].Prefix}${next.edge}`);
                  next = next.tile.adjacent[nextEdgeIx];
                }
​
                let vxMinusShapes = getValidShapes(vxMinusCorners);
                if (vxMinusShapes.length === 0) {
                  pendingTile = undefined;
                } else {
                  // Moar checks:
                  //  * does this tile have other adjacent tiles? if so we need to check those corners as well
                  //  * are any of our valid shapes singular (only one possible shape)?
                  //      * if so, we can check the other new tiles additional adjacencies for validity
                  //      * also, we can go ahead and add the entire star
                  
                  let orientation = requiredAngle - naturalAngle;
                  let offsetPos = existingTile.vertices[vx];
                  let position;
                  switch ((mx + 1) % 4) {
                    case 0:
                      position = offsetPos;
                      break;
                    case 1:
                      position = {
                        x: offsetPos.x - scale * p.cos(orientation + angles[0] / 2),
                        y: offsetPos.y - scale * p.sin(orientation + angles[0] / 2)
                      };
                      break;
                    case 2:
                      position = {
                        x: offsetPos.x - scale * Rhombs[newTileType].Length * p.cos(orientation),
                        y: offsetPos.y - scale * Rhombs[newTileType].Length * p.sin(orientation)
                      };
                      break;
                    case 3:
                      position = {
                        x: offsetPos.x - scale * p.cos(orientation - angles[0] / 2),
                        y: offsetPos.y - scale * p.sin(orientation - angles[0] / 2)
                      };
                      break;
                  }
​
                  pendingTile = new Tile(
                    newTileType,
                    position,
                    orientation
                  );
​
                  pendingTile.adjacent[mx] = { tile: existingTile, edge: vx };
                  break;
                }
              }
            }
          }
        }
      }
      
      // TODO identify and prevent conflicts/overlaps
    }
    
    p.redraw();
  }
  
  p.mouseClicked = function() {
    if (pendingTile) {
      // Check for other tile adjacencies
      for (const adjacency of getAdjacentTiles(pendingTile, true)) {
        // The reverse adjacency will get set up below
        pendingTile.adjacent[adjacency.index] = adjacency;
      }
      
      // Add pending tile to tiles
      tiles.push(pendingTile);
      for (const edgeIx of Object.keys(pendingTile.adjacent).map(k => Number(k))) {
        let adjacentInfo = pendingTile.adjacent[edgeIx];
        if (adjacentInfo.tile.adjacent[adjacentInfo.edge]) {
          console.log(`Replacing tile adjacent to edge ${adjacentInfo.edge} with ${pendingTile}`);
        }
        
        adjacentInfo.tile.adjacent[adjacentInfo.edge] = {
          tile: pendingTile,
          edge: edgeIx
        };
      }
    }
    
    pendingTile = undefined;
  }
  
  function* getAdjacentTiles(existingTile, skipExisting) {
    if (!skipExisting) {
      for (const index of Object.keys(existingTile.adjacent).map(k => Number(k))) {
        yield { ...existingTile.adjacent[index], index };
      }
    }
    
    // Search all tiles again (another optimization opportunity).
    for (const tile of tiles) {
      let err = vertexError(existingTile.position, tile.position);
      // Only full process tiles that are within a range where they could
      // theoretically share an edge
      if (err < scale * Rhombs.Thin.Length * 2) {
        // Note, since we're checking for a matching edge, once we get to vertex
        // 3 with no match we are done.
        for (let vx = 0; vx < 3; vx++) {
          if (existingTile.adjacent[vx]) {
            // If we already have an adjacency we can skip this edge
            continue;
          }
​
          let mx;
          for (mx = 0; mx < 4; mx++) {
            if (vertexMatch(existingTile.vertices[vx], tile.vertices[mx])) {
              break;
            }
          }
          if (mx < 4) {
            // vx matches mx, if vx + 1 matches mx - 1 then these tiles share an edge
            mx = (mx + 3) % 4;
            if (vertexMatch(existingTile.vertices[vx + 1], tile.vertices[mx])) {
              yield { index: vx, tile, edge: mx };
              // The reverse adjacency will get set up below
            }
​
            // Once we've found one matching vertex we can stop checking this tile
            break;
          }
        }
      }
    }
  }
  
  function vertexError(v1, v2) {
    return Math.max(Math.abs(v1.x - v2.x), Math.abs(v1.y - v2.y))
  }
  
  function vertexMatch(v1, v2) {
    return vertexError(v1, v2) < 0.01;
  }
  
  const Rhombs = {
    Thin: {
      Prefix: 't',
      Angles: [36, 144],
      Edges: ['R+?', 'R-?', 'B+', 'B-'],
      Fill: p.color('LightCoral'),
      Length: 1.90211303259 // 2 * cos(36 / 2)
    },
    Thick: {
      Prefix: 'T',
      Angles: [72, 108],
      Edges: ['R+', 'B+', 'B-', 'R-'],
      Fill: p.color('LightSkyBlue'),
      Length: 1.61803398875 // 2 * cos(72 / 2)
    }
  };
  
  // The 7+ valid P3 tile combinations
  // Corners are labeled with 'T' for thick, and 't' thin, 0 corresponds to the
  // first narrow angle, and corners are labeled on counter clockwise order.
  const Shapes = [
    ['T3', 'T1', 't1'],
    ['T2', 't3', 't3'],
    ['T2', 'T2', 'T2', 't3'],
    ['T0', 'T0', 'T0', 'T0', 'T0'],
    ['T2', 'T2', 'T2', 'T2', 'T2'],
    ['T1', 'T3', 't2', 'T0', 't0'],
    ['T0', 'T0', 'T0', 'T0', 't0', 't2'],
    ['T0', 'T0', 't0', 't2', 'T0', 't0', 't2'],
  ];
  
  function isValidShape(corners) {
    return getValidShapes(corners).length > 0;
  }
  
  function getValidShapes(corners) {
    // in order for corners to represent part of a valid shape it must be a subset
    // of one of the valid Shapes, however it may need to be shifted to properly
    // line up, since we could have started listing corners at any point in the
    // shape.
    let validShapes = [];
    
    for (const shape of Shapes) {
      for (let off = 0; off < shape.length; off++) {
        let matching = true;
        for (let i = 0; i < corners.length && matching; i++) {
          matching = (shape[(off + i) % shape.length] === corners[i]);
        }
        if (matching) {
          validShapes.push(shape.slice(off).concat(shape.slice(0, off)));
        }
      }
    }
    
    return validShapes;
  }
  
  class Tile {
    constructor(type, position, orientation) {
      this.type = type;
      this.position = position;
      this.orientation = orientation;
      this.adjacent = [];
      this.vertices = [];
      this.edges = [];
      
      this.angles = Rhombs[this.type].Angles;
      this.edgeTypes = Rhombs[this.type].Edges;
      
      let angle = this.orientation + this.angles[0] / 2;
      this.vertices.push(position);
      let x = position.x;
      let y = position.y;
      
      for (let i = 1; i < 4; i++) {
        x += scale * p.cos(angle);
        y += scale * p.sin(angle);
        this.vertices.push({ x, y });
        this.edges.push({ start: i - 1, end: i, type: this.edgeTypes[i - 1] });
        angle -= (180 - this.angles[i % 2]);
      }
      
      this.edges.push({ start: 3, end: 0, type: this.edgeTypes[3] });
    }
    
    toString() {
      // Don't try to serialize adjacent tiles because this is a bi-directional cyclic graph
      return JSON.stringify({ ...this, adjacent: this.adjacent.length });
    }
    
    drawTile(alpha) {
      const spikeEdge = Math.sqrt(0.02);
      
      let fill = Rhombs[this.type].Fill;
      p.fill(p.red(fill), p.green(fill), p.blue(fill), alpha);
      
      p.beginShape();
      let x = this.position.x;
      let y = this.position.y;
      let angle = this.orientation + this.angles[0] / 2;
      p.vertex(x, y);
      
      let scaledSpikeEdge = Math.sqrt(2 * Math.pow(0.1 * scale, 2));
      for (let i = 0; i < 4; i++) {
        x += scale * 0.4 * p.cos(angle);
        y += scale * 0.4 * p.sin(angle);
        p.vertex(x, y);
        
        // Draw edge marker
        switch (this.edgeTypes[i].substring(0, 2)) {
          case 'B+':
            x += scaledSpikeEdge * p.cos(angle + 45);
            y += scaledSpikeEdge * p.sin(angle + 45);
            p.vertex(x, y);
            x += scaledSpikeEdge * p.cos(angle - 45);
            y += scaledSpikeEdge * p.sin(angle - 45);
            p.vertex(x, y);
            break;
          case 'B-':
            x += scaledSpikeEdge * p.cos(angle - 45);
            y += scaledSpikeEdge * p.sin(angle - 45);
            p.vertex(x, y);
            x += scaledSpikeEdge * p.cos(angle + 45);
            y += scaledSpikeEdge * p.sin(angle + 45);
            p.vertex(x, y);
            break;
          case 'R+':
            x += scale * 0.1 * p.cos(angle + 90);
            y += scale * 0.1 * p.sin(angle + 90);
            p.vertex(x, y);
            x += scale * 0.2 * p.cos(angle);
            y += scale * 0.2 * p.sin(angle);
            p.vertex(x, y);
            x += scale * 0.1 * p.cos(angle - 90);
            y += scale * 0.1 * p.sin(angle - 90);
            p.vertex(x, y);
            break;
          case 'R-':
            x += scale * 0.1 * p.cos(angle - 90);
            y += scale * 0.1 * p.sin(angle - 90);
            p.vertex(x, y);
            x += scale * 0.2 * p.cos(angle);
            y += scale * 0.2 * p.sin(angle);
            p.vertex(x, y);
            x += scale * 0.1 * p.cos(angle + 90);
            y += scale * 0.1 * p.sin(angle + 90);
            p.vertex(x, y);
            break;
        }
        
        if (i < 3) {
          // The final vertex can be skipped since it is the same as the first
          x += scale * 0.4 * p.cos(angle);
          y += scale * 0.4 * p.sin(angle);
          p.vertex(x, y);
          angle -= (180 - this.angles[(i + 1) % 2]);
        }
      }
      
      p.endShape(p.CLOSE);
      
      /* debugging
      p.push();
      p.strokeWeight(4);
      p.stroke('green');
      p.point(this.vertices[0].x, this.vertices[0].y);
      p.stroke('red');
      p.point(this.vertices[2].x, this.vertices[2].y);
      p.stroke('blue');
      p.point(this.vertices[1].x, this.vertices[1].y);
      p.point(this.vertices[3].x, this.vertices[3].y);
      p.pop();
      //*/
    }
  }
}
​
var currentSketch = new p5(penroseTileMaker);