1. zetro
  2. Square Dino

Commits

zetro  committed 11c1bed

Refactored Game of Life code as an implementation of an abstract cellular automaton class. Both BoardImpl/Automaton and QuadBoard/HashAutomaton can use it.

  • Participants
  • Parent commits 69cc055
  • Branches default

Comments (0)

Files changed (6)

File src/org/bitbucket/zetro/squaredino/backend/AbstractAutomaton.java

View file
 
 import java.util.ArrayList;
 import java.util.Collection;
+import org.bitbucket.zetro.squaredino.backend.experimental.CellularAutomaton;
+import org.bitbucket.zetro.squaredino.backend.experimental.GameOfLife;
 
 /**
- * An abstract Cellular Automaton class for implementing Conway's Game of Life.
+ * An abstract automaton class for updating cell boards.
  */
 public abstract class AbstractAutomaton {
 	/**
 	 * Rules.
 	 */
 	protected Collection<Integer> born, survive;
+	/**
+	 * Cellular automaton.
+	 */
+	protected CellularAutomaton automaton;
 	private int vEdgeType, hEdgeType;
 
 	/**
 		parseRule(rule);
 	}
 
+	private void initCellularAutomaton() {
+		automaton = new GameOfLife(born, survive);
+	}
+
 	/**
 	 * Sets the vertical and horizontal edge types.
 	 *
 
 		this.born = parseRulePart(bornPart);
 		this.survive = parseRulePart(survivePart);
+		
+		initCellularAutomaton();
 	}
 
 	private Collection<Integer> parseRulePart(String part) throws IllegalArgumentException {

File src/org/bitbucket/zetro/squaredino/backend/Automaton.java

View file
 package org.bitbucket.zetro.squaredino.backend;
 
 import java.util.Collection;
+import java.util.HashMap;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.LinkedList;
 import org.bitbucket.zetro.squaredino.misc.Point;
 
 /**
- * Cellular Automaton class implementing Conway's Game of Life.
+ * Automaton implementation for BoardImpl.
  */
 public class Automaton extends AbstractAutomaton {
 	/**
 			Point point = queue.poll();
 
 			// Count neighbours and add edge points
-			int neighbours = 0;
+			HashMap<Cell, Integer> neighbours = new HashMap<Cell, Integer>();
 			for (int x = -1; x <= 1; x++) {
 				for (int y = -1; y <= 1; y++) {
 					if (x == 0 && y == 0) { // Current cell, ignore
 						continue;
 					}
 
-					if (getCell(board, point.x + x, point.y + y) != null) {
-						neighbours++;
+					Cell cell = getCell(board, point.x + x, point.y + y);
+					if (cell != null) {
+						Integer i = neighbours.get(cell);
+						if (i != null) {
+							neighbours.put(cell, i + 1);
+						} else {
+							neighbours.put(cell, 1);
+						}
 					} else if (addEdges) { // Add dead cell as edge point
 						edgePoints.add(verifyPoint(new Point(point.x + x, point.y + y)));
 					}
 			}
 
 			// Update cell state
-			// TODO: Implement edge handling
 			Cell currentCell = board.getCell(point.x, point.y);
-			if (currentCell == null) { // Dead cell
-				if (born.contains(neighbours)) { // Change state to alive
-					Cell cell = new Cell();
-					successor.addCell(cell, point.x, point.y);
-				}
-			} else if (survive.contains(neighbours)) { // Keep state (alive)
-				successor.addCell(currentCell, point.x, point.y);
-			} // else die
+			Cell newState = automaton.getNextState(currentCell, neighbours);
+			if (newState != null) {
+				successor.addCell(newState, point.x, point.y);
+			}
 
 			// Check if first pass is finished
 			if (queue.isEmpty() && addEdges) {

File src/org/bitbucket/zetro/squaredino/backend/experimental/CellularAutomaton.java

View file
+package org.bitbucket.zetro.squaredino.backend.experimental;
+
+import java.util.HashMap;
+import org.bitbucket.zetro.squaredino.backend.Cell;
+
+/**
+ * An abstract class for implementing diffrent cellular automatons that updates
+ * depending on the amount of neighbours.
+ */
+public abstract class CellularAutomaton {
+	/**
+	 * Returns the next state of a given cell.
+	 *
+	 * @param cell the given cell
+	 * @param neighbours neighbour map
+	 * @return the next state of the given cell
+	 */
+	public abstract Cell getNextState(Cell cell, HashMap<Cell, Integer> neighbours);
+
+	/**
+	 * Returns the amount of neighbours of a specific cell type (state).
+	 *
+	 * @param neighbours neighbour map
+	 * @param cell cell type (state)
+	 * @return the amount of neighbours of a specific cell type (state)
+	 */
+	public static int getCount(HashMap<Cell, Integer> neighbours, Cell cell) {
+		return neighbours.containsKey(cell) ? neighbours.get(cell) : 0;
+	}
+}

File src/org/bitbucket/zetro/squaredino/backend/experimental/GameOfLife.java

View file
+package org.bitbucket.zetro.squaredino.backend.experimental;
+
+import java.util.Collection;
+import java.util.HashMap;
+import org.bitbucket.zetro.squaredino.backend.Cell;
+
+/**
+ * Implementation of (Conway's) Game of Life.
+ */
+public class GameOfLife extends CellularAutomaton {
+	/**
+	 * States.
+	 */
+	public static final Cell ALIVE = new Cell(), DEAD = null;
+	private Collection<Integer> born, survive;
+
+	/**
+	 * GameOfLife constructor.
+	 *
+	 * @param born list of neighbour counts that gives living cells
+	 * @param survive list of neighbour counts keeps the state of a cell
+	 */
+	public GameOfLife(Collection<Integer> born, Collection<Integer> survive) {
+		this.born = born;
+		this.survive = survive;
+	}
+
+	@Override
+	public Cell getNextState(Cell cell, HashMap<Cell, Integer> neighbours) {
+		if (cell == DEAD && born.contains(getCount(neighbours, ALIVE))) {
+			return ALIVE;
+		} else if (survive.contains(getCount(neighbours, ALIVE))) {
+			return cell;
+		}
+		return DEAD;
+	}
+}

File src/org/bitbucket/zetro/squaredino/backend/experimental/HashAutomaton.java

View file
 package org.bitbucket.zetro.squaredino.backend.experimental;
 
+import java.util.HashMap;
+import java.util.Map;
 import org.bitbucket.zetro.squaredino.backend.AbstractAutomaton;
 import org.bitbucket.zetro.squaredino.backend.Cell;
 
 /**
- * HashAutomaton class. Only implements the standard 3/23 rule.
+ * Automaton implementation that uses the Hashlife algorithm.
  */
 public class HashAutomaton extends AbstractAutomaton {
 	public static boolean useLinear = false;
 			while (expanded.level < stepSize) {
 				expanded = expand(expanded);
 			}
-			
+
 			System.out.print("Step size: " + (1 << stepSize) + ", population: " + expanded.size());
 			n = nextGeneration(expanded, stepSize);		// level == node.level + 1
 			System.out.println(", new population: " + n.size());
 		return c;
 	}
 
+	@SuppressWarnings("unchecked")
 	private HashNode nextGeneration(HashNode node, int linearLevel) {
 		if (node.next != null) {
 			return node.next;
 
 		HashNode nextNode;
 		if (node.level == 2) {
-			HashNode nw = checkNeighbourCount(node.nw.se, sum(node.nw, 0, 1, 3) + sum(node.ne, 0, 3) + sum(node.sw, 0, 1) + sum(node.se, 0));
-			HashNode ne = checkNeighbourCount(node.ne.sw, sum(node.nw, 1, 2) + sum(node.ne, 0, 1, 2) + sum(node.sw, 1) + sum(node.se, 0, 1));
-			HashNode sw = checkNeighbourCount(node.sw.ne, sum(node.nw, 2, 3) + sum(node.ne, 3) + sum(node.sw, 0, 2, 3) + sum(node.se, 0, 3));
-			HashNode se = checkNeighbourCount(node.se.nw, sum(node.nw, 2) + sum(node.ne, 2, 3) + sum(node.sw, 1, 2) + sum(node.se, 1, 2, 3));
+			HashNode nw = getNextState(node.nw.se, merge(sum(node.nw, 0, 1, 3), sum(node.ne, 0, 3), sum(node.sw, 0, 1), sum(node.se, 0)));
+			HashNode ne = getNextState(node.ne.sw, merge(sum(node.nw, 1, 2), sum(node.ne, 0, 1, 2), sum(node.sw, 1), sum(node.se, 0, 1)));
+			HashNode sw = getNextState(node.sw.ne, merge(sum(node.nw, 2, 3), sum(node.ne, 3), sum(node.sw, 0, 2, 3), sum(node.se, 0, 3)));
+			HashNode se = getNextState(node.se.nw, merge(sum(node.nw, 2), sum(node.ne, 2, 3), sum(node.sw, 1, 2), sum(node.se, 1, 2, 3)));
 
 			nextNode = HashNode.create(cache, nw, ne, sw, se);
 		} else {
 			HashNode nwc, top, nec, lef, cen, rig, swc, dwn, sec;
-			if (/*node.level == 3 ||*/node.level - 2 > linearLevel) { // Linear
+			if (node.level - 2 > linearLevel) { // Linear
 				nwc = centeredSubnode(node.nw);				// nw center
 				top = centeredHorizontal(node.nw, node.ne);	// top
 				nec = centeredSubnode(node.ne);				// ne center
 				sec = nextGeneration(node.se, linearLevel);				// se center
 			}
 
-			nextNode = HashNode.create(cache, 
+			nextNode = HashNode.create(cache,
 					nextGeneration(HashNode.create(cache, nwc, top, lef, cen), linearLevel),
 					nextGeneration(HashNode.create(cache, top, nec, cen, rig), linearLevel),
 					nextGeneration(HashNode.create(cache, lef, cen, swc, dwn), linearLevel),
 				c.se.nw.nw);
 	}
 
-	private HashNode checkNeighbourCount(HashNode node, int count) {
-		boolean isDead;
+	private HashNode getNextState(HashNode node, HashMap<Cell, Integer> count) {
+		return HashContentNode.create(cache, automaton.getNextState(getCell(node), count));
+	}
+
+	private Cell getCell(HashNode node) {
 		if (node == null) {
-			isDead = true;
+			return null;
 		} else {
 			if (node instanceof HashContentNode == false) {
 				throw new AssertionError(node);
 			}
 			@SuppressWarnings("unchecked")
 			HashContentNode<Cell> current = ((HashContentNode<Cell>) node);
-			isDead = current.content == null;
-		}
-
-		if (isDead && born.contains(count)) {
-			return HashContentNode.create(cache, new Cell());
-		} else if (survive.contains(count)) {
-			return node;
-		} else {
-			return HashContentNode.create(cache, null);
+			return current.content;
 		}
 	}
 
-	private int sum(HashNode node, int... cells) {
-		int count = 0;
+	private HashMap<Cell, Integer> sum(HashNode node, int... cells) {
+		HashMap<Cell, Integer> count = new HashMap<Cell, Integer>();
 
 		for (int cellIndex : cells) {
 			HashNode cellNode = getNodeByIndex(node, cellIndex);
 				@SuppressWarnings("unchecked")
 				HashContentNode<Cell> contentNode = (HashContentNode<Cell>) cellNode;
 				if (contentNode.content != null) {
-					count++;
+					Integer i = count.get(contentNode.content);
+					if (i != null) {
+						count.put(contentNode.content, i + 1);
+					} else {
+						count.put(contentNode.content, 1);
+					}
 				}
 			}
 		}
 		return count;
 	}
 
+	private HashMap<Cell, Integer> merge(HashMap<Cell, Integer>... parts) {
+		HashMap<Cell, Integer> all = new HashMap<Cell, Integer>();
+
+		for (HashMap<Cell, Integer> c : parts) {
+			for (Map.Entry<Cell, Integer> entry : c.entrySet()) {
+				Cell cell = entry.getKey();
+				Integer partCount = entry.getValue();
+				Integer currentCount = all.get(cell);
+
+				assert partCount != null;
+				if (currentCount != null) {
+					all.put(cell, currentCount + partCount);
+				} else {
+					all.put(cell, partCount);
+				}
+			}
+		}
+
+		return all;
+	}
+
 	private HashNode getNodeByIndex(HashNode node, int index) {
 		if (index == 0) {
 			return node.nw;
 				&& cur.ne.nw == space && cur.ne.ne == space && cur.ne.se == space
 				&& cur.sw.nw == space && cur.sw.sw == space && cur.sw.se == space
 				&& cur.se.ne == space && cur.se.sw == space && cur.se.se == space) {
-			cur = HashNode.create(cache, 
+			cur = HashNode.create(cache,
 					cur.nw.se, cur.ne.sw, cur.sw.ne, cur.se.nw);
 			if (cur.level >= 2) {
 				space = hashTree.getSpaceNode(cur.level - 2);

File src/org/bitbucket/zetro/squaredino/backend/experimental/QuadBoard.java

View file
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Map.Entry;
+import org.bitbucket.zetro.squaredino.backend.AbstractAutomaton;
 import org.bitbucket.zetro.squaredino.backend.AbstractBoard;
 import org.bitbucket.zetro.squaredino.backend.Board;
 import org.bitbucket.zetro.squaredino.backend.Cell;
 	 */
 	public QuadBoard() {
 		tree = new QuadTree<Cell>();
+		rule = AbstractAutomaton.STANDARD_RULE;
 	}
 
 	private void treeChanged() {
 
 	private void buildAutomaton() {
 		auto = new HashAutomaton(hashTree);
-		if (rule != null) {
-			auto.setRule(rule);
-		}
+		auto.setRule(rule);
 	}
 
 	private void rebuildQuadTree() {
 	}
 
 	@Override
-	public void setRule(String rule) {
+	public void setRule(String rule) throws IllegalArgumentException {
+		if (rule == null || rule.isEmpty()) {
+			throw new IllegalArgumentException();
+		}
+
 		this.rule = rule;
 
 		if (hashTree != null) {