GenericLife

AbstractLattice.java

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);
		}
	}
}

CairoTiling.java

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();
	}
}

DeltoidTrihexagonal.java

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;
    }
}

FloretPentagonal.java

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;
    }
}

GenericLife.java

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;
	}
}

GenericLifeGui.java

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();
	}
}

LabyrinthTiling.java

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();
	}
}

Rhombille.java

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;
    }
}

Rhombitrihexagonal.java

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;
	}
}

Tiling.java

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);
}