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