Implement the Game of Life on Anything but a Regular Grid
Penrose rhombii in Python, +97 points
I chose a penrose tiling composed of two different shaped rhombuses, meeting 3-8 per vertex. This penrose tiling is proven aperiodic elsewhere. The simulation is graphical (via pygame) and interactive. Comments indicate two places in the code where algorithm implementation was taken from another source.
There are many small neighborhood still lifes:
Any vertex with four "on" neighbors is a still life:
Any loop where no dead interior cells touch three cells on the loop is also a still life:
There are oscillators at various frequencies:
p2: (many variations)
p3:
p4:
p5:
p6:
p7:
p12:
p20:
The rules and clarifications as written mostly do not allow for gliders or guns in a non-planned aperiodic tiling. That leaves infinite growth, which I would argue isn't likely, and a p30+ oscillator, which almost certainly exists but will take a while to find.
python penrose-life.py will generate a single randomly colored periodic tiling
python -O penrose-life.py or just ./penrose-life.py will actually run the simulation. While running it will try to identify oscillators, and when it finds one (p>2) it will screenshot it. After recording an oscillator, or a stalled board, the board is randomized.
Clicking a cell in the simulation will toggle it.
The following keyboard shortcuts exist in the simulation:
- Escape - quit the program
- Space - randomize the whole board
- P - pause the simulation
- S - single step the simulation
- F - toggle "fast" mode, rendering only every 25th frame
The initial seed of the penrose tiling algorithm is a circle of ten narrow triangles. This could be changed to single triangle, or a different arrangement of triangles, symmetric or not.
Source:
#!/usr/bin/env python -O
# tiling generation code originally from http://preshing.com/files/penrose.py
import sys
import math
import time
import cairo
import cmath
import random
import pygame
#TODO: command line parameters
#------ Configuration --------
IMAGE_SIZE = (1200, 1200)
OFFX = 600
OFFY = 600
RADIUS = 600
if __debug__: NUM_SUBDIVISIONS = 5
else: NUM_SUBDIVISIONS = 7
#-----------------------------
goldenRatio = (1 + math.sqrt(5)) / 2
class Triangle():
def __init__(self, parent = None, color = 0, corners = []):
self.parent = parent
self.other_half = None
# immediate neighbor 0 is on BA side, 1 is on AC side
self.neighbors = [None, None]
# all_neighbors includes diagonal neighbors
self.all_neighbors = set()
# child 0 is first on BA side, 1 is second, 2 is on AC side
self.children = []
self.color = color
if __debug__: self.debug_color = (random.random(),random.random(),random.random())
self.state = random.randint(0,1)
self.new_state = 0
self.corners = corners
self.quad = None
def __repr__(self):
return "Triangle: state=" + str(self.state) + \
" color=" + str(self.color) + \
" parent=" + ("yes" if self.parent else "no") + \
" corners=" + str(self.corners)
# break one triangle up into 2-3 smaller triangles
def subdivide(self):
result = []
A,B,C = self.corners
if self.color == 0:
# Subdivide red triangle
P = A + (B - A) / goldenRatio
result = [Triangle(self, 0, (C, P, B)), Triangle(self, 1, (P, C, A))]
else:
# Subdivide blue triangle
Q = B + (A - B) / goldenRatio
R = B + (C - B) / goldenRatio
result = [Triangle(self, 1, (Q, R, B)), Triangle(self, 0, (R, Q, A)), Triangle(self, 1, (R, C, A))]
self.children.extend(result)
return result;
# identify the left and right neighbors of a triangle
def connect_immediate(self):
o = None
n = self.neighbors
if self.parent:
if self.color == 0: # red child
if self.parent.color == 0: # red parent
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
o = self.parent.neighbors[0].children[0]
else: # blue left neighbor
o = self.parent.neighbors[0].children[1]
n[0] = self.parent.children[1]
if self.parent.other_half:
n[1] = self.parent.other_half.children[0]
else: # blue parent
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
o = self.parent.neighbors[0].children[0]
else: # blue left neighbor
o = self.parent.neighbors[0].children[1]
n[0] = self.parent.children[0]
n[1] = self.parent.children[2]
else: # blue child
if self.parent.color == 0: # red parent
if self.parent.neighbors[1]:
if self.parent.neighbors[1].color == 0: # red right neighbor
o = self.parent.neighbors[1].children[1]
else: # blue right neighbor
o = self.parent.neighbors[1].children[2]
n[0] = self.parent.children[0]
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
n[1] = self.parent.neighbors[0].children[1]
else: # blue left neighbor
n[1] = self.parent.neighbors[0].children[0]
else: # blue child of blue parent
if self.corners[2] == self.parent.corners[1]: # first blue child
if self.parent.other_half:
o = self.parent.other_half.children[0]
n[0] = self.parent.children[1]
if self.parent.neighbors[0]:
if self.parent.neighbors[0].color == 0: # red left neighbor
n[1] = self.parent.neighbors[0].children[1]
else: #blue left neighbor
n[1] = self.parent.neighbors[0].children[0]
else: # second blue child
if self.parent.neighbors[1]:
if self.parent.neighbors[1].color == 0: # red right neighbor
o = self.parent.neighbors[1].children[1]
else: # blue right neighbor
o = self.parent.neighbors[1].children[2]
if self.parent.other_half:
n[0] = self.parent.other_half.children[2]
n[1] = self.parent.children[1]
self.other_half = o
if o:
self.state = self.other_half.state
if __debug__: self.debug_color = self.other_half.debug_color
#TODO: different seed triangle configurations
# Create wheel of red triangles around the origin
triangles = [[]]
for i in xrange(10):
B = cmath.rect(RADIUS, (2*i - 1) * math.pi / 10)+OFFX+OFFY*1j
C = cmath.rect(RADIUS, (2*i + 1) * math.pi / 10)+OFFX+OFFY*1j
if i % 2 == 0:
B, C = C, B # Make sure to mirror every second triangle
triangles[0].append(Triangle(None, 0, (OFFX+OFFY*1j, B, C)))
# identify the neighbors of the starting triangles
for i in xrange(10):
if i%2:
triangles[0][i].neighbors[0] = triangles[0][(i+9)%10]
triangles[0][i].neighbors[1] = triangles[0][(i+1)%10]
else:
triangles[0][i].neighbors[1] = triangles[0][(i+9)%10]
triangles[0][i].neighbors[0] = triangles[0][(i+1)%10]
# Perform subdivisions
for i in xrange(NUM_SUBDIVISIONS):
triangles.append([])
for t in triangles[i]:
triangles[i+1].extend(t.subdivide())
for t in triangles[i+1]:
t.connect_immediate()
# from here on, we only deal with the most-subdivided triangles
tris = triangles[NUM_SUBDIVISIONS]
# make a dict of every vertex, containing a list of every triangle sharing that vertex
vertices = {}
for t in tris:
for c in t.corners:
if c not in vertices:
vertices[c] = []
vertices[c].append(t)
# every triangle sharing a vertex are neighbors of each other
for v,triset in vertices.iteritems():
for t in triset:
t.all_neighbors.update(triset)
# combine mirrored triangles into quadrilateral cells
quads = []
total_neighbors = 0
for t in tris:
if t.quad == None and t.other_half != None:
quads.append(t)
q = t
q.corners = (q.corners[0], q.corners[1], q.other_half.corners[0], q.corners[2])
q.quad = q
q.other_half.quad = q
q.all_neighbors.update(q.other_half.all_neighbors)
q.all_neighbors.remove(q.other_half)
q.all_neighbors.remove(q)
total_neighbors += len(q.all_neighbors)
# clean up quads who still think they have triangles for neighbors
for q in quads:
new_neighbors = set()
for n in q.all_neighbors:
if len(n.corners)==3:
if n.other_half:
if len(n.other_half.corners)==4:
new_neighbors.add(n.other_half)
else:
new_neighbors.add(n)
q.all_neighbors = new_neighbors
# # adopt your other half's neighbors, minus them and yourself. mark other half as dead.
# for t in tris:
# if t.other_half:
# t.all_neighbors.update(t.other_half.all_neighbors)
# t.all_neighbors.remove(t)
# if t.other_half and t.other_half in t.all_neighbors:
# t.all_neighbors.remove(t.other_half)
# if t.other_half and not t.dead_half:
# t.other_half.dead_half = True
pygame.init()
screen = pygame.display.set_mode(IMAGE_SIZE, 0, 32)
pygame.display.set_caption("Penrose Life")
pygame.display.flip()
paused = False
fast = False
randomize = True
found_oscillator = 0
randomized_tick = 0
tick = 0
timed_tick = 0
timed_tick_time = time.clock()
render_countdown = 0
history_length = 45
quad_history = [[0]*len(quads)]*history_length
quad_pointer = 0
myfont = pygame.font.SysFont("monospace", 15)
guidish = random.randint(0,99999999)
while True:
tick += 1
if tick - randomized_tick > 1000 and render_countdown == 0:
randomize = True
edited = False
step = False
if found_oscillator > 0 and render_countdown == 0:
print "Potential p" + str(found_oscillator) + " osillator"
render_countdown = found_oscillator
if render_countdown == 0: # don't handle input while rendering an oscillator
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit(0)
elif event.type == pygame.KEYDOWN:
# print event
if event.scancode == 53: # escape
sys.exit(0)
elif event.unicode == " ": # randomize
randomize = True
edited = True
elif event.unicode == "p": # pause
paused = not paused
elif event.unicode == "f": # fast
fast = not fast
elif event.unicode == "s": # step
paused = True
step = True
elif event.type == pygame.MOUSEBUTTONDOWN:
# click to toggle a cell
x = event.pos[0]
y = event.pos[1]
for q in quads:
poly = [(c.real,c.imag) for c in q.corners]
# http://www.ariel.com.au/a/python-point-int-poly.html
n = len(poly)
inside = False
p1x,p1y = poly[0]
for i in range(n+1):
p2x,p2y = poly[i % n]
if y > min(p1y,p2y):
if y <= max(p1y,p2y):
if x <= max(p1x,p2x):
if p1y != p2y:
xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x,p1y = p2x,p2y
if inside:
edited = True
q.state = 0 if q.state==1 else 1
if randomize and render_countdown == 0:
randomized_tick = tick
randomize = False
for q in quads:
q.state = random.randint(0,1)
edited = True
if (not fast) or (tick%25==0) or edited or render_countdown > 0:
# draw filled quads
for q in quads:
cs = [(c.real,c.imag) for c in q.corners]
if __debug__:
color = q.debug_color
color = (int(color[0]*256)<<24)+(int(color[1]*256)<<16)+(int(color[2]*256)<<8)+0xFF
else:
if q.state == 0:
color = 0xFFFFFFFF
else:
color = 0x000000FF
pygame.draw.polygon(screen, color, cs, 0)
# draw edges
for q in quads:
if len(q.corners)==3:
exit(1)
cs = [(c.real,c.imag) for c in q.corners]
width = 3
pygame.draw.lines(screen, 0x7F7F7FFF, 1, cs, int(width))
now = time.clock()
speed = (tick-timed_tick)/(now-timed_tick_time)
timed_tick_time = now
timed_tick = tick
screen.blit(screen, (0, 0))
label = myfont.render("%4.2f/s"%speed, 1, (255,255,255))
screen.fill(pygame.Color("black"), (0, 0, 110, 15))
screen.blit(label, (0, 0))
pygame.display.update()
if __debug__:
break
if paused and not step and render_countdown == 0:
time.sleep(0.05)
continue
# screenshot
if render_countdown > 0:
filename = "oscillator_p%03d_%08d_%03d.png" % (found_oscillator, guidish, found_oscillator - render_countdown)
pygame.image.save(screen,filename)
render_countdown -= 1
if render_countdown == 0:
guidish = random.randint(0,99999999)
found_oscillator = 0
randomize = True
continue
# calculate new cell states based on the Game of Life rules
for q in quads:
a = sum([n.state for n in q.all_neighbors])
q.new_state = q.state
# dead cells with three neighbors spawn
if q.state == 0 and a == 3:
q.new_state = 1
# live cells only survive with two or three neighbors
elif a < 2 or a > 3:
q.new_state = 0
# update cell states
for q in quads:
q.state = q.new_state
this_state = [q.state for q in quads]
# don't bother checking
if render_countdown == 0:
# compare this board state to the last N-1 states
for i in range(1,history_length):
if quad_history[(quad_pointer-i)%history_length] == this_state:
if i == 1 or i == 2: # stalled board or p2 oscillator (boring)
randomize = True
break
#TODO: give up if the "oscillator" includes border cells
#TODO: identify cases of two oprime oscillators overlapping
elif i > 2:
found_oscillator = i
break # don't keep looking
# remember this board state
quad_history[quad_pointer] = this_state
quad_pointer = (quad_pointer+1)%history_length
if __debug__:
filename = "penrose.png"
pygame.image.save(screen,filename)
time.sleep(1)
C++ w/ OpenGL (+17)
So I tried 3-Isohedral convex pentagon grid. Works for me ;) Standard game of life rules apply, except the grid is not infinite - there are border cells outside the image. 30% of the cells are initially alive.
This is how the grid looks like:
The live version:
Blue cells are alive, white are dead. Red cells just died, green were just born. Note that the artifacts in the image are the result of gif compression, SO doesn't like 10MB gifs :(.
Still life: (+2)
Oscillators T=2, T=3, T=12: (+9)
Oscillators T=6 , T=7: (+6)
There are many more different oscillators... But it seems that the grid is not regular enough for a ship...
This is nothing (no points), but I like it:
The code is a mess :) Uses some ancient fixed OpenGL. Otherwise used GLEW, GLFW, GLM and ImageMagick for gif export.
/**
* Tile pattern generation is inspired by the code
* on http://www.jaapsch.net/tilings/
* It saved me a lot of thinkink (and debugging) - thank you, sir!
*/
#include <GL/glew.h>
#include <GLFW/glfw3.h>
#include <FTGL/ftgl.h> //debug only
#include <ImageMagick-6/Magick++.h> //gif export
#include "glm/glm.hpp"
#include <iostream>
#include <array>
#include <vector>
#include <set>
#include <algorithm>
#include <unistd.h>
typedef glm::vec2 Point;
typedef glm::vec3 Color;
struct Tile {
enum State {ALIVE=0, DEAD, BORN, DIED, SIZE};
static const int VERTICES = 5;
static constexpr float SCALE = 0.13f;
static constexpr std::array<std::array<int, 7>, 18> DESC
{{
{{1, 0,0, 0,0,0, 0}},
{{0, 1,2, 0,2,1, 0}},
{{2, 2,3, 0,2,3, 1}},
{{1, 0,4, 0,0,1, 0}},
{{0, 1,2, 3,2,1, 0}},
{{2, 2,3, 3,2,3, 1}},
{{1, 0,4, 3,0,1, 0}},
{{0, 1,2, 6,2,1, 0}},
{{2, 2,3, 6,2,3, 1}},
{{1, 0,4, 6,0,1, 0}},
{{0, 1,2, 9,2,1, 0}},
{{2, 2,3, 9,2,3, 1}},
{{1, 0,4, 9,0,1, 0}},
{{0, 1,2,12,2,1, 0}},
{{2, 2,3,12,2,3, 1}},
{{1, 0,4,12,0,1, 0}},
{{0, 1,2,15,2,1, 0}},
{{2, 2,3,15,2,3, 1}}
}};
const int ID;
std::vector<Point> coords;
std::set<Tile*> neighbours;
State state;
State nextState;
Color color;
Tile() : ID(-1), state(DEAD), nextState(DEAD), color(1, 1, 1) {
const float ln = 0.6f;
const float h = ln * sqrt(3) / 2.f;
coords = {
Point(0.f, 0.f),
Point(ln, 0.f),
Point(ln*3/2.f,h),
Point(ln, h*4/3.f),
Point(ln/2.f, h)
};
for(auto &c : coords) {
c *= SCALE;
}
}
Tile(const int id, const std::vector<Point> coords_) :
ID(id), coords(coords_), state(DEAD), nextState(DEAD), color(1, 1, 1) {}
bool operator== (const Tile &other) const {
return ID == other.ID;
}
const Point & operator[] (const int i) const {
return coords[i];
}
void updateState() {
state = nextState;
}
/// returns "old" state
bool isDead() const {
return state == DEAD || state == DIED;
}
/// returns "old" state
bool isAlive() const {
return state == ALIVE || state == BORN;
}
void translate(const Point &p) {
for(auto &c : coords) {
c += p;
}
}
void rotate(const Point &p, const float angle) {
const float si = sin(angle);
const float co = cos(angle);
for(auto &c : coords) {
Point tmp = c - p;
c.x = tmp.x * co - tmp.y * si + p.x;
c.y = tmp.y * co + tmp.x * si + p.y;
}
}
void mirror(const float y2) {
for(auto &c : coords) {
c.y = y2 - (c.y - y2);
}
}
};
std::array<std::array<int, 7>, 18> constexpr Tile::DESC;
constexpr float Tile::SCALE;
class Game {
static const int CHANCE_TO_LIVE = 30; //% of cells initially alive
static const int dim = 4; //evil grid param
FTGLPixmapFont &font;
std::vector<Tile> tiles;
bool animate; //animate death/birth
bool debug; //show cell numbers (very slow)
bool exportGif; //save gif
bool run;
public:
Game(FTGLPixmapFont& font) : font(font), animate(false), debug(false), exportGif(false), run(false) {
//create the initial pattern
std::vector<Tile> init(18);
for(int i = 0; i < Tile::DESC.size(); ++i) {
auto &desc = Tile::DESC[i];
Tile &tile = init[i];
switch(desc[0]) { //just to check the grid
case 0: tile.color = Color(1, 1, 1);break;
case 1: tile.color = Color(1, 0.7, 0.7);break;
case 2: tile.color = Color(0.7, 0.7, 1);break;
}
if(desc[3] != i) {
const Tile &tile2 = init[desc[3]];
tile.translate(tile2[desc[4]] - tile[desc[1]]);
if(desc[6] != 0) {
float angleRad = getAngle(tile[desc[1]], tile[desc[2]]);
tile.rotate(tile[desc[1]], -angleRad);
tile.mirror(tile[desc[1]].y);
angleRad = getAngle(tile[desc[1]], tile2[desc[5]]);
tile.rotate(tile[desc[1]], angleRad);
}
else {
float angleRad = getAngle(tile[desc[1]], tile[desc[2]], tile2[desc[5]]);
tile.rotate(tile[desc[1]], angleRad);
}
}
}
const float offsets[4] {
init[2][8].x - init[8][9].x,
init[2][10].y - init[8][11].y,
init[8][12].x - init[14][13].x,
init[8][14].y - init[14][15].y
};
// create all the tiles
for(int dx = -dim; dx <= dim; ++dx) { //fuck bounding box, let's hardcode it
for(int dy = -dim; dy <= dim; ++dy) {
for(auto &tile : init) {
std::vector<Point> vert;
for(auto &p : tile.coords) {
float ax = dx * offsets[0] + dy * offsets[2];
float ay = dx * offsets[1] + dy * offsets[3];
vert.push_back(Point(p.x + ax, p.y + ay));
}
tiles.push_back(Tile(tiles.size(), vert));
tiles.back().color = tile.color;
tiles.back().state = tile.state;
}
}
}
//stupid bruteforce solution, but who's got time to think..
for(Tile &tile : tiles) { //find neighbours for each cell
for(Tile &t : tiles) {
if(tile == t) continue;
for(Point &p : t.coords) {
for(Point &pt : tile.coords) {
if(glm::distance(p, pt) < 0.01 ) {
tile.neighbours.insert(&t);
break;
}
}
}
}
assert(tile.neighbours.size() <= 9);
}
}
void init() {
for(auto &t : tiles) {
if(rand() % 100 < CHANCE_TO_LIVE) {
t.state = Tile::BORN;
}
else {
t.state = Tile::DEAD;
}
}
}
void update() {
for(auto &tile: tiles) {
//check colors
switch(tile.state) {
case Tile::BORN: //animate birth
tile.color.g -= 0.05;
tile.color.b += 0.05;
if(tile.color.b > 0.9) {
tile.state = Tile::ALIVE;
}
break;
case Tile::DIED: //animate death
tile.color += 0.05;
if(tile.color.g > 0.9) {
tile.state = Tile::DEAD;
}
break;
}
//fix colors after animation
switch(tile.state) {
case Tile::ALIVE:
tile.color = Color(0, 0, 1);
break;
case Tile::DEAD:
tile.color = Color(1, 1, 1);
break;
}
//draw polygons
glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
glBegin(GL_POLYGON);
glColor3f(tile.color.r, tile.color.g, tile.color.b);
for(auto &pt : tile.coords) {
glVertex2f(pt.x, pt.y); //haha so oldschool!
}
glEnd();
}
//draw grid
glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
glColor3f(0, 0, 0);
for(auto &tile : tiles) {
glBegin(GL_POLYGON);
Point c; //centroid of tile
for(auto &pt : tile.coords) {
glVertex2f(pt.x, pt.y);
c += pt;
}
glEnd();
if(debug) {
c /= (float) Tile::VERTICES;
glRasterPos2f(c.x - 0.025, c.y - 0.01);
font.Render(std::to_string(tile.ID).c_str()); //
}
}
if(!run) {
return;
}
//compute new generation
for(Tile &tile: tiles) {
tile.nextState = tile.state; //initialize next state
int c = 0;
for(auto *n : tile.neighbours) {
if(n->isAlive()) c++;
}
switch(c) {
case 2:
break;
case 3:
if(tile.isDead()) {
tile.nextState = animate ? Tile::BORN : Tile::ALIVE;
tile.color = Color(0, 1, 0);
}
break;
default:
if(tile.isAlive()) {
tile.nextState = animate ? Tile::DIED : Tile::DEAD;
tile.color = Color(1, 0, 0);
}
break;
}
}
//switch state to new
for(Tile &tile: tiles) {
tile.updateState();
}
}
void stop() {run = false;}
void switchRun() {run = !run;}
bool isRun() {return run;}
void switchAnim() {animate = !animate;}
bool isAnim() {return animate;}
void switchExportGif() {exportGif = !exportGif;}
bool isExportGif() {return exportGif;}
void switchDebug() {debug = !debug;}
bool isDebug() const {return debug;}
private:
static float getAngle(const Point &p0, const Point &p1, Point const &p2) {
return atan2(p2.y - p0.y, p2.x - p0.x) - atan2(p1.y - p0.y, p1.x - p0.x);
}
static float getAngle(const Point &p0, const Point &p1) {
return atan2(p1.y - p0.y, p1.x - p0.x);
}
};
class Controlls {
Game *game;
std::vector<Magick::Image> *gif;
Controlls() : game(nullptr), gif(nullptr) {}
public:
static Controlls& getInstance() {
static Controlls instance;
return instance;
}
static void keyboardAction(GLFWwindow* window, int key, int scancode, int action, int mods) {
getInstance().keyboardActionImpl(key, action);
}
void setGame(Game *game) {
this->game = game;
}
void setGif(std::vector<Magick::Image> *gif) {
this->gif = gif;
}
private:
void keyboardActionImpl(int key, int action) {
if(!game || action == GLFW_RELEASE) {
return;
}
switch (key) {
case 'R':
game->stop();
game->init();
if(gif) gif->clear();
break;
case GLFW_KEY_SPACE:
game->switchRun();
break;
case 'A':
game->switchAnim();
break;
case 'D':
game->switchDebug();
break;
break;
case 'G':
game->switchExportGif();
break;
};
}
};
int main(int argc, char** argv) {
const int width = 620; //window size
const int height = 620;
const std::string window_title ("Game of life!");
const std::string font_file ("/usr/share/fonts/truetype/arial.ttf");
const std::string gif_file ("./gol.gif");
if(!glfwInit()) return 1;
GLFWwindow* window = glfwCreateWindow(width, height, window_title.c_str(), NULL, NULL);
glfwSetWindowPos(window, 100, 100);
glfwMakeContextCurrent(window);
GLuint err = glewInit();
if (err != GLEW_OK) return 2;
FTGLPixmapFont font(font_file.c_str());
if(font.Error()) return 3;
font.FaceSize(8);
std::vector<Magick::Image> gif; //gif export
std::vector<GLfloat> pixels(3 * width * height);
Game gol(font);
gol.init();
Controlls &controlls = Controlls::getInstance();
controlls.setGame(&gol);
controlls.setGif(&gif);
glfwSetKeyCallback(window, Controlls::keyboardAction);
glClearColor(1.f, 1.f, 1.f, 0);
while(!glfwWindowShouldClose(window) && !glfwGetKey(window, GLFW_KEY_ESCAPE)) {
glClear(GL_COLOR_BUFFER_BIT);
gol.update();
//add layer to gif
if(gol.isExportGif()) {
glReadPixels(0, 0, width, height, GL_RGB, GL_FLOAT, &pixels[0]);
Magick::Image image(width, height, "RGB", Magick::FloatPixel, &pixels[0]);
image.animationDelay(50);
gif.push_back(image);
}
std::string info = "ANIMATE (A): ";
info += gol.isAnim() ? "ON " : "OFF";
info += " | DEBUG (D): ";
info += gol.isDebug() ? "ON " : "OFF";
info += " | EXPORT GIF (G): ";
info += gol.isExportGif() ? "ON " : "OFF";
info += gol.isRun() ? " | STOP (SPACE)" : " | START (SPACE)";
font.FaceSize(10);
glRasterPos2f(-.95f, -.99f);
font.Render(info.c_str());
if(gol.isDebug()) font.FaceSize(8);
if(!gol.isDebug()) usleep(50000); //not so fast please!
glfwSwapBuffers(window);
glfwPollEvents();
}
//save gif to file
if(gol.isExportGif()) {
std::cout << "saving " << gif.size() << " frames to gol.gif\n";
gif.back().write("./last.png");
Magick::writeImages(gif.begin(), gif.end(), gif_file);
}
glfwTerminate();
return 0;
}
Go, ? points
So rather than pin myself down to a particular tiling, I wrote a program that takes a gif or png of a tiling and runs life on it. The gif/png must use a single color for all the tiles.
package main
import (
"flag"
"image"
"image/color"
"image/gif"
"image/png"
"math/rand"
"os"
"strings"
)
func main() {
flag.Parse()
filename := flag.Args()[0]
r, err := os.Open(filename)
if err != nil {
panic(err)
}
var i image.Image
if strings.HasSuffix(filename, ".gif") {
i, err = gif.Decode(r)
if err != nil {
panic(err)
}
}
if strings.HasSuffix(filename, ".png") {
i, err = png.Decode(r)
if err != nil {
panic(err)
}
}
// find background color
back := background(i)
// find connected regions
n, m := regions(i, back)
// find edges between regions
edges := graph(i, m)
// run life on the tiling
life(i, n, m, edges)
}
// Find the most-common occurring color.
// This is the "background" color.
func background(i image.Image) color.Color {
hist := map[color.Color]int{}
b := i.Bounds()
for y := b.Min.Y; y < b.Max.Y; y++ {
for x := b.Min.X; x < b.Max.X; x++ {
hist[i.At(x, y)]++
}
}
maxn := 0
var maxc color.Color
for c, n := range hist {
if n > maxn {
maxn = n
maxc = c
}
}
return maxc
}
// find connected regions. Returns # of regions and a map from pixels to their region numbers.
func regions(i image.Image, back color.Color) (int, map[image.Point]int) {
// m maps each background point to a region #
m := map[image.Point]int{}
// number regions consecutively
id := 0
b := i.Bounds()
for y := b.Min.Y; y < b.Max.Y; y++ {
for x := b.Min.X; x < b.Max.X; x++ {
if i.At(x, y) != back {
continue
}
p := image.Point{x, y}
if _, ok := m[p]; ok {
continue // already in a region
}
q := []image.Point{p}
m[p] = id
k := 0
for k < len(q) {
z := q[k]
k++
for _, n := range [4]image.Point{{z.X - 1, z.Y}, {z.X + 1, z.Y}, {z.X, z.Y - 1}, {z.X, z.Y + 1}} {
if !n.In(b) || i.At(n.X, n.Y) != back {
continue
}
if _, ok := m[n]; ok {
continue
}
m[n] = id
q = append(q, n)
}
}
if len(q) < 10 {
// really tiny region - probably junk in input data
for _, n := range q {
delete(m, n)
}
continue
}
id++
}
}
return id, m
}
// edge between two regions. r < s.
type edge struct {
r, s int
}
// returns a set of edges between regions.
func graph(i image.Image, m map[image.Point]int) map[edge]struct{} {
// delta = max allowed spacing between adjacent regions
const delta = 6
e := map[edge]struct{}{}
for p, r := range m {
for dx := -delta; dx <= delta; dx++ {
for dy := -delta; dy <= delta; dy++ {
n := image.Point{p.X + dx, p.Y + dy}
if _, ok := m[n]; !ok {
continue
}
if m[n] > r {
e[edge{r, m[n]}] = struct{}{}
}
}
}
}
return e
}
// run life engine
// i = image
// n = # of regions
// m = map from points to their region #
// edges = set of edges between regions
func life(i image.Image, n int, m map[image.Point]int, edges map[edge]struct{}) {
b := i.Bounds()
live := make([]bool, n)
nextlive := make([]bool, n)
palette := []color.Color{color.RGBA{0, 0, 0, 255}, color.RGBA{128, 0, 0, 255}, color.RGBA{255, 255, 128, 255}} // lines, on, off
var frames []*image.Paletted
var delays []int
// pick random starting lives
for j := 0; j < n; j++ {
if rand.Int()%2 == 0 {
live[j] = true
nextlive[j] = true
}
}
for round := 0; round < 100; round++ {
// count live neighbors
neighbors := make([]int, n)
for e := range edges {
if live[e.r] {
neighbors[e.s]++
}
if live[e.s] {
neighbors[e.r]++
}
}
for j := 0; j < n; j++ {
nextlive[j] = neighbors[j] == 3 || (live[j] && neighbors[j] == 2)
}
// add a frame
frame := image.NewPaletted(b, palette)
for y := b.Min.Y; y < b.Max.Y; y++ {
for x := b.Min.X; x < b.Max.X; x++ {
frame.SetColorIndex(x, y, 0)
}
}
for p, r := range m {
if live[r] {
frame.SetColorIndex(p.X, p.Y, 1)
} else {
frame.SetColorIndex(p.X, p.Y, 2)
}
}
frames = append(frames, frame)
delays = append(delays, 30)
live, nextlive = nextlive, live
}
// write animated gif of result
w, err := os.Create("animated.gif")
if err != nil {
panic(err)
}
gif.EncodeAll(w, &gif.GIF{Image: frames, Delay: delays, LoopCount: 100})
w.Close()
}
Then I just went on the web, grabbed some fun tiling images and ran the program on them.
go run life.go penrose1.go
It generates a file called "animated.gif" which contains a 100-step life simulation of the given tiling.
Standard life:
Penrose tiles:
Above one has an oscillator of period 12.
Above one has an oscillator of period 3.