Skip to content

Instantly share code, notes, and snippets.

@pjt33
Last active August 29, 2015 14:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save pjt33/becd56784480ddd751bf to your computer and use it in GitHub Desktop.
Save pjt33/becd56784480ddd751bf to your computer and use it in GitHub Desktop.
GenericLife
import java.awt.Point;
import java.util.*;
public abstract class AbstractLattice implements Tiling<AbstractLattice.LatticeCell> {
// Use the idea of expansion and vertex mapping from my earlier aperiod tiling implementation.
private Map<Point, Set<LatticeCell>> vertexNeighbourhood = new HashMap<Point, Set<LatticeCell>>();
private int scale = -1;
// Geometry
private final int dx0, dy0, dx1, dy1;
private final int[][] xs;
private final int[][] ys;
protected AbstractLattice(int dx0, int dy0, int dx1, int dy1, int[][] xs, int[][] ys) {
this.dx0 = dx0;
this.dy0 = dy0;
this.dx1 = dx1;
this.dy1 = dy1;
// Assume sensible subclasses, so no need to clone the arrays to prevent modification.
this.xs = xs;
this.ys = ys;
}
private void expand() {
scale++;
// We want to enumerate all lattice cells whose extreme coordinate is +/- scale.
// Corners:
insertLatticeNeighbourhood(-scale, -scale);
insertLatticeNeighbourhood(-scale, scale);
insertLatticeNeighbourhood(scale, -scale);
insertLatticeNeighbourhood(scale, scale);
// Edges:
for (int i = -scale + 1; i < scale; i++) {
insertLatticeNeighbourhood(-scale, i);
insertLatticeNeighbourhood(scale, i);
insertLatticeNeighbourhood(i, -scale);
insertLatticeNeighbourhood(i, scale);
}
}
private void insertLatticeNeighbourhood(int x, int y) {
for (int sub = 0; sub < xs.length; sub++) {
LatticeCell cell = new LatticeCell(x, y, sub);
int[][] bounds = bounds(cell);
for (int i = 0; i < bounds[0].length; i++) {
Point p = new Point(bounds[0][i], bounds[1][i]);
Set<LatticeCell> adj = vertexNeighbourhood.get(p);
if (adj == null) vertexNeighbourhood.put(p, adj = new HashSet<LatticeCell>());
adj.add(cell);
}
}
}
public Set<LatticeCell> neighbours(LatticeCell cell) {
Set<LatticeCell> rv = new HashSet<LatticeCell>();
// +1 because we will border cells from the next scale.
int requiredScale = Math.max(Math.abs(cell.x), Math.abs(cell.y)) + 1;
while (scale < requiredScale) expand();
int[][] bounds = bounds(cell);
for (int i = 0; i < bounds[0].length; i++) {
Point p = new Point(bounds[0][i], bounds[1][i]);
Set<LatticeCell> adj = vertexNeighbourhood.get(p);
rv.addAll(adj);
}
rv.remove(cell);
return rv;
}
public int[][] bounds(LatticeCell cell) {
int[][] bounds = new int[2][];
bounds[0] = xs[cell.sub].clone();
bounds[1] = ys[cell.sub].clone();
for (int i = 0; i < bounds[0].length; i++) {
bounds[0][i] += cell.x * dx0 + cell.y * dx1;
bounds[1][i] += cell.x * dy0 + cell.y * dy1;
}
return bounds;
}
public LatticeCell initialCell() {
return new LatticeCell(0, 0, 0);
}
public abstract boolean isInterestingOscillationPeriod(int period);
public Set<LatticeCell> parseCells(String[] data) {
Set<LatticeCell> rv = new HashSet<LatticeCell>();
if (data.length % 3 != 0) throw new IllegalArgumentException("Data should come in triples");
for (int i = 0; i < data.length; i += 3) {
if (data[i + 2].length() != 1) throw new IllegalArgumentException("Third data item should be a single letter");
rv.add(new LatticeCell(Integer.parseInt(data[i]), Integer.parseInt(data[i + 1]), data[i + 2].charAt(0) - 'A'));
}
return rv;
}
public String format(Set<LatticeCell> cells) {
StringBuilder sb = new StringBuilder();
for (LatticeCell cell : cells) {
if (sb.length() > 0) sb.append(' ');
sb.append(cell.x).append(' ').append(cell.y).append(' ').append((char)(cell.sub + 'A'));
}
return sb.toString();
}
static class LatticeCell {
public final int x, y, sub;
LatticeCell(int x, int y, int sub) {
this.x = x;
this.y = y;
this.sub = sub;
}
@Override
public int hashCode() {
return (x * 0x100025) + (y * 0x959) + sub;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof LatticeCell)) return false;
LatticeCell other = (LatticeCell)obj;
return x == other.x && y == other.y && sub == other.sub;
}
@Override
public String toString() {
return x + " " + y + " " + (char)('A' + sub);
}
}
}
import java.awt.Point;
import java.util.*;
/**
* http://en.wikipedia.org/wiki/Cairo_pentagonal_tiling
*/
class CairoTiling implements Tiling<Point> {
private static final int[][] SHAPES_X = new int[][] {
{ 0, 4, 11, 11, 4 },
{ 11, 4, 8, 14, 18 },
{ 11, 18, 14, 8, 4 },
{ 22, 18, 11, 11, 18 }
};
private static final int[][] SHAPES_Y = new int[][] {
{ 0, 7, 3, -3, -7 },
{ 3, 7, 14, 14, 7 },
{ -3, -7, -14, -14, -7 },
{ 0, -7, -3, 3, 7 }
};
public Set<Point> neighbours(Point cell) {
Set<Point> neighbours = new HashSet<Point>();
int exclx = (cell.y & 1) == 0 ? -1 : 1;
int excly = (cell.x & 1) == 0 ? -1 : 1;
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx == 0 && dy == 0) continue;
if (dx == exclx && dy == excly) continue;
neighbours.add(new Point(cell.x + dx, cell.y + dy));
}
}
return neighbours;
}
public int[][] bounds(Point cell) {
int x = cell.x, y = cell.y;
int[] xs = SHAPES_X[(x & 1) + 2 * (y & 1)].clone();
int[] ys = SHAPES_Y[(x & 1) + 2 * (y & 1)].clone();
int xoff = 7 * (x & ~1) + 7 * (y & ~1);
int yoff = 7 * (x & ~1) - 7 * (y & ~1);
for (int i = 0; i < 5; i++) {
xs[i] += xoff;
ys[i] += yoff;
}
return new int[][] { xs, ys };
}
public Point initialCell() { return new Point(0, 0); }
public boolean isInterestingOscillationPeriod(int period) {
return period != 2 && period != 6;
}
public Set<Point> parseCells(String[] data) {
if ((data.length & 1) == 1) throw new IllegalArgumentException("Expect pairs of integers");
Set<Point> cells = new HashSet<Point>();
for (int i = 0; i < data.length; i += 2) {
cells.add(new Point(Integer.parseInt(data[i]), Integer.parseInt(data[i + 1])));
}
return cells;
}
public String format(Set<Point> cells) {
StringBuilder sb = new StringBuilder();
for (Point cell : cells) {
if (sb.length() > 0) sb.append(' ');
sb.append(cell.x).append(' ').append(cell.y);
}
return sb.toString();
}
}
public class DeltoidTrihexagonal extends AbstractLattice {
public DeltoidTrihexagonal() {
super(32, 0, 16, 28, new int[][] {
{0, 8, 16, 16},
{8, 16, 24, 16},
{16, 24, 32, 16},
{16, 32, 32, 24},
{32, 48, 40, 32},
{32, 40, 32, 24}
}, new int[][] {
{0, 14, 9, 0},
{14, 28, 14, 9},
{9, 14, 0, 0},
{28, 28, 19, 14},
{28, 28, 14, 19},
{19, 14, 0, 14}
});
}
@Override
public boolean isInterestingOscillationPeriod(int period) {
if (period % 2 == 0) period /= 2;
if (period % 2 == 0) period /= 2;
if (period % 3 == 0) period /= 3;
if (period % 5 == 0) period /= 5;
return period > 1;
}
}
public class FloretPentagonal extends AbstractLattice {
public FloretPentagonal() {
super(35, -12, 28, 24, new int[][] {
{0, 0, 7, 14, 14},
{0, 14, 21, 21, 14},
{0, 14, 14, 7, 0},
{0, 0, -7, -14, -14},
{0, -14, -21, -21, -14},
{0, -14, -14, -7, 0}
}, new int[][] {
{0, 16, 20, 16, 8},
{0, 8, 4, -4, -8},
{0, -8, -16, -20, -16},
{0, -16, -20, -16, -8},
{0, -8, -4, 4, 8},
{0, 8, 16, 20, 16}
});
}
@Override
public boolean isInterestingOscillationPeriod(int period) {
return period > 3;
}
}
import java.awt.*;
import java.awt.image.*;
import java.io.*;
import java.util.*;
import java.util.List;
import javax.imageio.*;
import javax.imageio.metadata.*;
import javax.imageio.stream.*;
import org.w3c.dom.Node;
/**
* Implements a Life-like cellular automaton on a generic grid.
* http://codegolf.stackexchange.com/q/35827/194
*
* TODOs:
* - Allow a special output format for gliders which moves the bounds at an appropriate speed and doesn't extend the last frame
* - Allow option to control number of generations
*/
public class GenericLife {
private static final Color GRIDCOL = new Color(0x808080);
private static final Color DEADCOL = new Color(0xffffff);
private static final Color LIVECOL = new Color(0x0000ff);
private static final int MARGIN = 15;
private static void usage() {
System.out.println("Usage: java GenericLife <tiling> [<output.gif> <cell-data>]");
System.out.println("For CairoTiling, cell data is pairs of integers");
System.out.println("For random search, supply just the tiling name");
System.exit(1);
}
// Unchecked warnings due to using reflection to instantation tiling over unknown cell type
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
if (args.length == 0 || args[0].equals("--help")) usage();
Tiling tiling = (Tiling)Class.forName(args[0]).newInstance();
if (args.length > 1) {
String[] cellData = new String[args.length - 2];
System.arraycopy(args, 2, cellData, 0, cellData.length);
Set alive;
try { alive = tiling.parseCells(cellData); }
catch (Exception ex) { usage(); return; }
createAnimatedGif(args[1], tiling, evolve(tiling, alive, 133));
}
else search(tiling);
}
private static <Cell> void search(Tiling<Cell> tiling) throws IOException {
while (true) {
// Build a starting generation within a certain radius of the initial cell.
// This is a good place to tweak.
Set<Cell> alive = new HashSet<Cell>();
double density = Math.random();
Set<Cell> visited = new HashSet<Cell>();
Set<Cell> boundary = new HashSet<Cell>();
boundary.add(tiling.initialCell());
for (int r = 0; r < 10; r++) {
visited.addAll(boundary);
Set<Cell> nextBoundary = new HashSet<Cell>();
for (Cell cell : boundary) {
if (Math.random() < density) alive.add(cell);
for (Cell neighbour : tiling.neighbours(cell)) {
if (!visited.contains(neighbour)) nextBoundary.add(neighbour);
}
}
boundary = nextBoundary;
}
final int MAX = 1000;
List<Set<Cell>> gens = evolve(tiling, alive, MAX);
// Long-lived starting conditions might mean a glider, so are interesting.
boolean interesting = gens.size() == MAX;
String desc = "gens-" + MAX;
if (!interesting) {
// We hit some oscillator - but was it an interesting one?
int lastGen = gens.size() - 1;
gens = evolve(tiling, gens.get(lastGen), gens.size());
if (gens.size() > 1) {
int period = gens.size() - 1;
desc = "oscillator-" + period;
interesting = tiling.isInterestingOscillationPeriod(period);
System.out.println("Oscillation of period " + period);
}
else {
String result = gens.get(0).isEmpty() ? "Extinction" : "Still life";
System.out.println(result + " at gen " + lastGen);
}
}
if (interesting) {
String filename = System.getProperty("java.io.tmpdir") + "/" + tiling.getClass().getSimpleName() + "-" + System.nanoTime() + "-" + desc + ".gif";
createAnimatedGif(filename, tiling, gens);
System.out.println("Wrote " + gens.size() + " generations to " + filename);
}
}
}
private static <Cell> List<Set<Cell>> evolve(Tiling<Cell> tiling, Set<Cell> gen0, int numGens) {
Map<Set<Cell>, Integer> firstSeen = new HashMap<Set<Cell>, Integer>();
List<Set<Cell>> gens = new ArrayList<Set<Cell>>();
gens.add(gen0);
firstSeen.put(gen0, 0);
Set<Cell> alive = gen0;
for (int gen = 1; gen < numGens; gen++) {
if (alive.size() == 0) break;
Set<Cell> nextGen = nextGeneration(tiling, alive);
Integer prevSeen = firstSeen.get(nextGen);
if (prevSeen != null) {
if (gen - prevSeen > 1) gens.add(nextGen); // Finish the loop.
break;
}
alive = nextGen;
gens.add(alive);
firstSeen.put(alive, gen);
}
return gens;
}
private static <Cell> void createAnimatedGif(String filename, Tiling<Cell> tiling, List<Set<Cell>> gens) throws IOException {
OutputStream out = new FileOutputStream(filename);
ImageWriter imgWriter = ImageIO.getImageWritersByFormatName("gif").next();
ImageOutputStream imgOut = ImageIO.createImageOutputStream(out);
imgWriter.setOutput(imgOut);
imgWriter.prepareWriteSequence(null);
Rectangle bounds = bbox(tiling, gens);
Set<Cell> gen0 = gens.get(0);
int numGens = gens.size();
for (int gen = 0; gen < numGens; gen++) {
Set<Cell> alive = gens.get(gen);
// If we have an oscillator which loops cleanly back to the start, skip the last frame.
if (gen > 0 && alive.equals(gen0)) break;
writeGifFrame(imgWriter, render(tiling, bounds, alive), gen == 0, gen == numGens - 1);
}
imgWriter.endWriteSequence();
imgOut.close();
out.close();
}
private static <Cell> Rectangle bbox(Tiling<Cell> tiling, Collection<? extends Collection<Cell>> gens) {
Rectangle bounds = new Rectangle(-1, -1);
Set<Cell> allGens = new HashSet<Cell>();
for (Collection<Cell> gen : gens) allGens.addAll(gen);
for (Cell cell : allGens) {
int[][] cellBounds = tiling.bounds(cell);
int[] xs = cellBounds[0], ys = cellBounds[1];
for (int i = 0; i < xs.length; i++) bounds.add(xs[i], ys[i]);
}
bounds.grow(MARGIN, MARGIN);
return bounds;
}
private static void writeGifFrame(ImageWriter imgWriter, BufferedImage img, boolean isFirstFrame, boolean isLastFrame) throws IOException {
IIOMetadata metadata = imgWriter.getDefaultImageMetadata(new ImageTypeSpecifier(img), null);
String metaFormat = metadata.getNativeMetadataFormatName();
Node root = metadata.getAsTree(metaFormat);
IIOMetadataNode grCtlExt = findOrCreateNode(root, "GraphicControlExtension");
grCtlExt.setAttribute("delayTime", isLastFrame ? "1000" : "30"); // Extra delay for last frame
grCtlExt.setAttribute("disposalMethod", "doNotDispose");
if (isFirstFrame) {
// Configure infinite looping.
IIOMetadataNode appExts = findOrCreateNode(root, "ApplicationExtensions");
IIOMetadataNode appExt = findOrCreateNode(appExts, "ApplicationExtension");
appExt.setAttribute("applicationID", "NETSCAPE");
appExt.setAttribute("authenticationCode", "2.0");
appExt.setUserObject(new byte[] { 1, 0, 0 });
}
metadata.setFromTree(metaFormat, root);
imgWriter.writeToSequence(new IIOImage(img, null, metadata), null);
}
private static IIOMetadataNode findOrCreateNode(Node parent, String nodeName) {
for (Node child = parent.getFirstChild(); child != null; child = child.getNextSibling()) {
if (child.getNodeName().equals(nodeName)) return (IIOMetadataNode)child;
}
IIOMetadataNode node = new IIOMetadataNode(nodeName);
parent.appendChild(node);
return node ;
}
public static <Cell> Set<Cell> nextGeneration(Tiling<Cell> tiling, Set<Cell> gen) {
Map<Cell, Integer> neighbourCount = new HashMap<Cell, Integer>();
for (Cell cell : gen) {
for (Cell neighbour : tiling.neighbours(cell)) {
Integer curr = neighbourCount.get(neighbour);
neighbourCount.put(neighbour, 1 + (curr == null ? 0 : curr.intValue()));
}
}
Set<Cell> nextGen = new HashSet<Cell>();
for (Map.Entry<Cell, Integer> e : neighbourCount.entrySet()) {
if (e.getValue() == 3 || (e.getValue() == 2 && gen.contains(e.getKey()))) {
nextGen.add(e.getKey());
}
}
return nextGen;
}
public static <Cell> BufferedImage render(Tiling<Cell> tiling, Rectangle bounds, Collection<Cell> alive) {
// Create a suitable paletted image
int width = bounds.width;
int height = bounds.height;
byte[] data = new byte[width * height];
int[] pal = new int[]{ GRIDCOL.getRGB(), DEADCOL.getRGB(), LIVECOL.getRGB() };
ColorModel colourModel = new IndexColorModel(8, pal.length, pal, 0, false, -1, DataBuffer.TYPE_BYTE);
DataBufferByte dbb = new DataBufferByte(data, width * height);
WritableRaster raster = Raster.createPackedRaster(dbb, width, height, width, new int[]{0xff}, new Point(0, 0));
BufferedImage img = new BufferedImage(colourModel, raster, true, null);
Graphics g = img.createGraphics();
// Render the tiling.
// We assume that either one of the live cells or the "initial cell" is in bounds.
Set<Cell> visited = new HashSet<Cell>();
Set<Cell> unvisited = new HashSet<Cell>(alive);
unvisited.add(tiling.initialCell());
while (!unvisited.isEmpty()) {
Iterator<Cell> it = unvisited.iterator();
Cell current = it.next();
it.remove();
visited.add(current);
Rectangle cellBounds = new Rectangle(-1, -1);
int[][] cellVertices = tiling.bounds(current);
int[] xs = cellVertices[0], ys = cellVertices[1];
for (int i = 0; i < xs.length; i++) {
cellBounds.add(xs[i], ys[i]);
xs[i] -= bounds.x;
ys[i] -= bounds.y;
}
if (!bounds.intersects(cellBounds)) continue;
g.setColor(alive.contains(current) ? LIVECOL : DEADCOL);
g.fillPolygon(xs, ys, xs.length);
g.setColor(GRIDCOL);
g.drawPolygon(xs, ys, xs.length);
for (Cell neighbour : tiling.neighbours(current)) {
if (!visited.contains(neighbour)) unvisited.add(neighbour);
}
}
g.dispose();
return img;
}
}
import java.awt.*;
import java.awt.event.*;
import java.awt.image.BufferedImage;
import java.util.*;
import java.util.List;
import javax.swing.*;
public class GenericLifeGui<Cell> extends JComponent {
private static final Color GRIDCOL = new Color(0x808080);
private static final Color DEADCOL = new Color(0xffffff);
private static final Color LIVECOL = new Color(0x0000ff);
private static final Color PENDING_DEADCOL = new Color(0x2244ff);
private static final Color PENDING_LIVECOL = new Color(0xccbbff);
private final Tiling<Cell> tiling;
private Set<Cell> alive = new HashSet<Cell>();
private Set<Cell> nextGeneration = new HashSet<Cell>();
private Point centre = new Point(0, 0);
private List<Cell> bufferIndex;
private BufferedImage pBuffer;
private static void usage() {
System.out.println("Usage: java GenericLifeGui <tiling>");
System.exit(1);
}
// Unchecked warnings due to using reflection to instantation tiling over unknown cell type
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
if (args.length == 0 || args[0].equals("--help")) usage();
Tiling tiling = (Tiling)Class.forName(args[0]).newInstance();
GenericLifeGui gui = new GenericLifeGui(tiling);
gui.launch();
}
private GenericLifeGui(Tiling<Cell> tiling) {
this.tiling = tiling;
}
private void launch() {
SwingUtilities.invokeLater(new Runnable() {
public void run() {
final JFrame frame = new JFrame(tiling.getClass().getSimpleName());
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.getContentPane().setLayout(new BorderLayout());
frame.getContentPane().add(GenericLifeGui.this, BorderLayout.CENTER);
GenericLifeGui.this.addMouseListener(
new MouseAdapter() {
@Override
public void mouseClicked(MouseEvent evt) {
if (pBuffer == null) return;
int x = evt.getX(), y = evt.getY();
if (x < 0 || x >= pBuffer.getWidth() || y < 0 || y >= pBuffer.getHeight()) return;
int idx = pBuffer.getRGB(x, y) & 0xffffff;
if (idx > 0 && idx < bufferIndex.size()) {
Cell cell = bufferIndex.get(idx);
if (!alive.add(cell)) alive.remove(cell);
nextGeneration = GenericLife.nextGeneration(tiling, alive);
repaint();
}
}
});
JPanel toolbar = new JPanel();
toolbar.setLayout(new FlowLayout());
frame.getContentPane().add(toolbar, BorderLayout.NORTH);
toolbar.add(new JButton(
new AbstractAction("Step") {
@Override
public void actionPerformed(ActionEvent evt) {
alive = nextGeneration;
nextGeneration = GenericLife.nextGeneration(tiling, alive);
repaint();
}
}));
toolbar.add(new JButton(
new AbstractAction("Text") {
@Override
public void actionPerformed(ActionEvent evt) {
JDialog textDialog = new JDialog(frame, "Text", Dialog.ModalityType.APPLICATION_MODAL);
textDialog.getContentPane().setLayout(new BorderLayout());
JTextPane textPane = new JTextPane();
textDialog.getContentPane().add(textPane, BorderLayout.CENTER);
textPane.setText(tiling.format(alive));
//textDialog.pack();
textDialog.setBounds(frame.getBounds());
textDialog.setVisible(true);
}
}));
toolbar.add(new JButton(
new AbstractAction("Clear") {
@Override
public void actionPerformed(ActionEvent evt) {
alive.clear();
nextGeneration.clear();
repaint();
}
}));
frame.setSize(450, 450);
frame.setVisible(true);
}
});
}
@Override
public void paintComponent(Graphics g) {
super.paintComponent(g);
Rectangle bounds = new Rectangle(getSize());
bounds.x = centre.x - (bounds.width >> 1);
bounds.y = centre.y - (bounds.height >> 1);
// Render the tiling to the front buffer and a lookup table to the back buffer.
// We assume that either one of the live cells or the "initial cell" is in bounds.
// TODO Remove that assumption.
Set<Cell> visited = new HashSet<Cell>();
Set<Cell> unvisited = new HashSet<Cell>(alive);
bufferIndex = new ArrayList<Cell>();
bufferIndex.add(null);
if (pBuffer == null || pBuffer.getWidth() != bounds.width || pBuffer.getHeight() != bounds.height) {
pBuffer = new BufferedImage(bounds.width, bounds.height, BufferedImage.TYPE_INT_ARGB);
}
Graphics g2 = pBuffer.createGraphics();
unvisited.add(tiling.initialCell());
while (!unvisited.isEmpty()) {
Iterator<Cell> it = unvisited.iterator();
Cell current = it.next();
it.remove();
visited.add(current);
Rectangle cellBounds = new Rectangle(-1, -1);
int[][] cellVertices = tiling.bounds(current);
int[] xs = cellVertices[0], ys = cellVertices[1];
for (int i = 0; i < xs.length; i++) {
cellBounds.add(xs[i], ys[i]);
xs[i] -= bounds.x;
ys[i] -= bounds.y;
}
if (!bounds.intersects(cellBounds)) continue;
boolean isAlive = alive.contains(current);
boolean isChanging = nextGeneration.contains(current) != isAlive;
g.setColor(isChanging ? (isAlive ? PENDING_DEADCOL : PENDING_LIVECOL) : (isAlive ? LIVECOL : DEADCOL));
g.fillPolygon(xs, ys, xs.length);
g.setColor(GRIDCOL);
g.drawPolygon(xs, ys, xs.length);
bufferIndex.add(current);
g2.setColor(new Color(bufferIndex.size() - 1));
g2.fillPolygon(xs, ys, xs.length);
g2.setColor(Color.BLACK);
g2.drawPolygon(xs, ys, xs.length);
for (Cell neighbour : tiling.neighbours(current)) {
if (!visited.contains(neighbour)) unvisited.add(neighbour);
}
}
g2.dispose();
}
}
import java.awt.Point;
import java.util.*;
public class LabyrinthTiling implements Tiling<String> {
private Map<Point, Point> internedPoints = new HashMap<Point, Point>();
private Map<String, Set<Point>> vertices = new HashMap<String, Set<Point>>();
private Map<Point, Set<String>> tris = new HashMap<Point, Set<String>>();
private int level = 0;
// 3^level
private int scale = 1;
public LabyrinthTiling() {
linkSymmetric("", new Point(-8, 0));
linkSymmetric("", new Point(8, 0));
linkSymmetric("", new Point(0, 14));
}
private void linkSymmetric(String suffix, Point p) {
int ay = Math.abs(p.y);
link("+" + suffix, new Point(p.x, ay));
link("-" + suffix, new Point(p.x, -ay));
}
private void link(String tri, Point p) {
Point p2 = internedPoints.get(p);
if (p2 == null) internedPoints.put(p, p);
else p = p2;
Set<Point> ps = vertices.get(tri);
if (ps == null) vertices.put(tri, ps = new HashSet<Point>());
Set<String> ts = tris.get(p);
if (ts == null) tris.put(p, ts = new HashSet<String>());
ps.add(p);
ts.add(tri);
}
private void expand() {
level++;
scale *= 3;
subdivideEq("", new Point(-8 * scale, 0), new Point(8 * scale, 0), new Point(0, 14 * scale), level, true);
}
private static Point avg(Point p0, Point p1, Point p2) {
return new Point((p0.x + p1.x + p2.x) / 3, (p0.y + p1.y + p2.y) / 3);
}
private void subdivideEq(String suffix, Point p0, Point p1, Point p2, int level, boolean skip0) {
if (level == 0) {
linkSymmetric(suffix, p0);
linkSymmetric(suffix, p1);
linkSymmetric(suffix, p2);
return;
}
Point p01 = avg(p0, p0, p1), p10 = avg(p0, p1, p1);
Point p02 = avg(p0, p0, p2), p20 = avg(p0, p2, p2);
Point p12 = avg(p1, p1, p2), p21 = avg(p1, p2, p2);
Point c = avg(p0, p1, p2);
level--;
if (!skip0) subdivideEq(suffix + "0", p01, p10, c, level, false);
subdivideIso(suffix + "1", p0, c, p01, level);
subdivideIso(suffix + "2", p0, c, p02, level);
subdivideEq(suffix + "3", p02, c, p20, level, false);
subdivideIso(suffix + "4", p2, c, p20, level);
subdivideIso(suffix + "5", p2, c, p21, level);
subdivideEq(suffix + "6", c, p12, p21, level, false);
subdivideIso(suffix + "7", p1, c, p12, level);
subdivideIso(suffix + "8", p1, c, p10, level);
}
private void subdivideIso(String suffix, Point p0, Point p1, Point p2, int level) {
if (level == 0) {
linkSymmetric(suffix, p0);
linkSymmetric(suffix, p1);
linkSymmetric(suffix, p2);
return;
}
Point p01 = avg(p0, p0, p1), p10 = avg(p0, p1, p1);
Point p02 = avg(p0, p0, p2), p20 = avg(p0, p2, p2);
Point p12 = avg(p1, p1, p2), p21 = avg(p1, p2, p2);
Point c = avg(p0, p1, p2);
level--;
subdivideIso(suffix + "0", p0, p01, p02, level);
subdivideEq(suffix + "1", p01, p02, p20, level, false);
subdivideIso(suffix + "2", p01, p2, p20, level);
subdivideIso(suffix + "3", p01, p2, c, level);
subdivideIso(suffix + "4", p01, p10, c, level);
subdivideIso(suffix + "5", p10, p2, c, level);
subdivideIso(suffix + "6", p10, p2, p21, level);
subdivideEq(suffix + "7", p10, p12, p21, level, false);
subdivideIso(suffix + "8", p1, p10, p12, level);
}
public Set<String> neighbours(String cell) {
Set<String> rv = new HashSet<String>();
Set<Point> cellVertices;
while ((cellVertices = vertices.get(cell)) == null) expand();
for (Point p : cellVertices) {
// If the point is on the edge of the current level, we need to expand once more.
if (Math.abs(p.x) / 8 + Math.abs(p.y) / 14 == scale) expand();
Set<String> adj = tris.get(p);
rv.addAll(adj);
}
rv.remove(cell);
return rv;
}
public int[][] bounds(String cell) {
Set<Point> cellVertices;
while ((cellVertices = vertices.get(cell)) == null) expand();
int[][] bounds = new int[2][3];
int off = 0;
for (Point p : cellVertices) {
bounds[0][off] = p.x;
bounds[1][off] = p.y;
off++;
}
return bounds;
}
public String initialCell() {
return "+";
}
public boolean isInterestingOscillationPeriod(int period) {
return period != 4;
}
public Set<String> parseCells(String[] data) {
Set<String> rv = new HashSet<String>();
for (String cell : data) rv.add(cell);
return rv;
}
public String format(Set<String> cells) {
StringBuilder sb = new StringBuilder();
for (String cell : cells) {
if (sb.length() > 0) sb.append(' ');
sb.append(cell);
}
return sb.toString();
}
}
public class Rhombille extends AbstractLattice {
public Rhombille() {
super(14, 0, 7, 12, new int[][] {
{0, 7, 14, 7},
{0, 7, 7, 0},
{7, 14, 14, 7}
}, new int[][] {
{0, 4, 0, -4},
{0, -4, -12, -8},
{-4, 0, -8, -12}
});
}
@Override
public boolean isInterestingOscillationPeriod(int period) {
return true;
}
}
public class Rhombitrihexagonal extends AbstractLattice {
public Rhombitrihexagonal() {
super(22, 0, 11, 19, new int[][] {
{-7, 0, 7, 7, 0, -7},
{0, 4, 11, 7},
{7, 11, 15},
{7, 15, 15, 7},
{7, 15, 11},
{7, 11, 4, 0},
}, new int[][] {
{4, 8, 4, -4, -8, -4},
{8, 15, 11, 4},
{4, 11, 4},
{4, 4, -4, -4},
{-4, -4, -11},
{-4, -11, -15, -8},
});
}
@Override
public boolean isInterestingOscillationPeriod(int period) {
return period != 2 && period != 4 && period != 5 && period != 6 && period != 10 && period != 12 && period != 15 && period != 30;
}
}
import java.util.Set;
interface Tiling<Cell> {
/** Calculates the neighbourhood, which should not include the cell itself. */
public Set<Cell> neighbours(Cell cell);
/** Gets an array {xs, ys} of polygon vertices. */
public int[][] bounds(Cell cell);
/** Starting cell for random generation. This doesn't need to be consistent. */
public Cell initialCell();
/** Allows exclusion of common oscillations in random generation. */
public boolean isInterestingOscillationPeriod(int period);
/** Parse command-line input. */
public Set<Cell> parseCells(String[] data);
/** Inverse of the parse. */
public String format(Set<Cell> cells);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment