Created
April 7, 2011 17:55
-
-
Save showell/908317 to your computer and use it in GitHub Desktop.
game of life w/functional JS style
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<a href="game_of_life.html">Game of Life</a> | |
<h3>Computer Programs are...</h3> | |
Poetry for Robots? Maybe...but how about? | |
<ul> | |
<li>Algorithms</li> | |
<li>Configuration</li> | |
<li>Data Structures</li> | |
<li>Execution and Events</li> | |
<li>Functions</li> | |
<li>Models/Views</li> | |
<li>Objects</li> | |
<li>Procedures</li> | |
<li>Tests</li> | |
</ul> | |
<h3>How to Build...</h3> | |
<ul> | |
<li>Scratch an itch</li> | |
<li>Reflect on the problem</li> | |
<li>Start coding!</li> | |
<li>Have a design plan | |
<ul> | |
<li>Don't miss the forest for the trees</li> | |
<li>Eventually you have to plant a tree</li> | |
<li>Write the view code first! (or not)</li> | |
<li>Expect the code to evolve.</li> | |
<li>Code, verify, test, examine, repeat.</li> | |
</ul> | |
</li> | |
</ul> | |
<p><i>"In preparing for battle I have always found that plans | |
are useless, but planning is indispensable."</i></p> -- Dwight Eisenhower | |
<h4>Core ideas of the Game of Life</h4> | |
<h5>INITIAL CONFIGURATION</h5> | |
One interacts with the Game of Life by creating an initial configuration and observing how it evolves. | |
<table> | |
<tr> | |
<td> | |
<img src="http://upload.wikimedia.org/wikipedia/commons/thumb/7/72/Game_of_life_infinite1.svg/162px-Game_of_life_infinite1.svg.png"> | |
</td> | |
<td> | |
<pre> | |
var seed = [ | |
"X ", | |
" ", | |
"XX ", | |
" ", | |
" XXX ", | |
" ", | |
" XXX ", | |
" X ", | |
]; | |
</pre> | |
</td> | |
</tr> | |
</table> | |
<h5>THE UNIVERSE</h5> | |
The universe of the Game of Life is a (...) two-dimensional grid of square cells, | |
each of which is in one of two possible states, live or dead. | |
<pre> | |
function data_2d() { | |
var hash = {}; | |
function key(point) { | |
var x = point[0]; | |
var y = point[1]; | |
return x.toString() + ',' + y.toString(); | |
}; | |
return { | |
alive: function (point) { | |
return hash[key(point)]; | |
}, | |
set: function (point, on) { | |
hash[key(point)] = on; | |
} | |
} | |
} | |
</pre> | |
<h5>THE GEOMETRY</h5> | |
Every cell interacts with its eight neighbors... | |
<pre> | |
var x_deltas = [ | |
-1, 0, 1, | |
-1, 1, | |
-1, 0, 1 | |
] | |
var y_deltas = [ | |
-1, -1, -1, | |
0, 0, | |
1, 1, 1 | |
] | |
</pre> | |
<h5>THE RULE</h5> | |
At each step in time, the following transitions occur... | |
<pre> | |
function point_lives_next_gen(alive, num_neighbors) { | |
var n = num_neighbors; | |
if (alive) { | |
return (n == 2 || n == 3) | |
} else { | |
return (n == 3) | |
} | |
} | |
</pre> | |
<h5>EVOLUTION</h5> | |
<pre> | |
var new_world = world_factory(); | |
old_world.cells().forEach( function (cell) { | |
var is_alive = old_world.alive(cell); | |
var n = old_world.num_alive_neighbors(cell) | |
var on = point_lives_next_gen(is_alive, n); | |
new_world.set(cell, on); | |
}); | |
</pre> | |
<h3>Program Design is...</h3> | |
<ul> | |
<li>Wikipedia-Driven Development?</li> | |
<li>Understanding the essence of the problem</li> | |
<li>Working in multiple paradigms</li> | |
<li>Divide and conquer</li> | |
<li>Math + Language + Engineering + Intuition</li> | |
<li>Evolutionary Design (or emergent design)</li> | |
<li>Quality</li> | |
</ul> | |
<h5>Resources</h5> | |
<ul> | |
<li><a href="http://www.ibiblio.org/lifepatterns/">Advanced Simulator</a></li> | |
<li><a href="http://www.math.com/students/wonders/life/life.html">Wonders of Math</a></li> | |
<li><a href="http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life">Wikipedia: Conway's Game of Life</a></li> | |
<li><a href="https://gist.github.com/908317#file_game_of_life.html">Steve's Implementation in Javascript</a></li> | |
</ul> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<h3>Game of Life</h3> | |
<canvas id="canvas" width="520" height="420" style="border: 1px blue solid"> | |
</canvas> | |
<script> | |
(function () { | |
//- ALGORITHM (iteration) | |
// | |
// Define the Game of Life as f: World -> World. | |
// | |
// We make no assumption about the topology here. The "space" | |
// could be 2D, 3D, finite, toroidal, hexagonal, or infinite. | |
// | |
// An instance of World needs only supply these methods: | |
// cells: return collection of opaque cell references | |
// num_alive_neighbors(cells) | |
// alive(cell) | |
// set(cell, on/off) | |
// | |
// (A small note: f() only talks directly to World, not its cells.) | |
// | |
// Our abstract_game_of_life() returns a function with the contract | |
// f: W -> W. For the "Game" part of the simulation, you would repeatedly | |
// apply the function and render each new instantiation of the World. | |
// | |
// You configure the topology of the world with world_factory. | |
// | |
// You configure the evolutionary algorithm with point_lives_next_gen, | |
// which determines the fate of the cell in the next generation. | |
// | |
function abstract_game_of_life( | |
world_factory, | |
point_lives_next_gen | |
) | |
{ | |
function f(old_world) { | |
var new_world = world_factory(); | |
old_world.cells().forEach( function (cell) { | |
var is_alive = old_world.alive(cell); | |
var n = old_world.num_alive_neighbors(cell) | |
var on = point_lives_next_gen(is_alive, n); | |
new_world.set(cell, on); | |
}); | |
return new_world; | |
} | |
return f; | |
}; | |
//- TEST UTILITY | |
// We do some primitive testing inline. | |
function assert(c, msg) { | |
msg = typeof(msg) != 'undefined' ? msg : "see stack trace"; | |
if (!c) { | |
console.log("assertion failure"); | |
debugger; | |
throw("test fails: " + msg); | |
} | |
} | |
//- TEST W/STUBS | |
// Test abstract_game_of_life. We use a world that has only one cell, | |
// and our evolutionary principle is that you die, then you are reborn, | |
// toggling every generation. | |
(function() { | |
var world_factory = function () { | |
var cells = [false]; | |
return { | |
"cells": | |
function() { return [0] }, | |
"num_alive_neighbors": | |
function(i) { return 0 }, | |
"alive": | |
function(i) { return cells[i] }, | |
"set": | |
function(i, fate) { cells[0] = fate }, | |
"status": | |
function() { return cells[0] } | |
} | |
} | |
function toggle(alive, num_neighbors) { | |
return alive ? false : true; | |
} | |
var f = abstract_game_of_life(world_factory, toggle); | |
var w = world_factory(); | |
assert(!w.status(), "init"); | |
w = f(w); | |
assert(w.status(), "gen 2"); | |
w = f(w); | |
assert(!w.status(), "gen 3"); | |
w = f(w); | |
assert(w.status(), "gen 4"); | |
})(); | |
//- FUNCTION w/no side effects | |
// | |
// This is the classic configuration of the Game of Life. | |
// The notation is B3/S23, where B describes the number of | |
// neighbors required for Birth, and S describes the number | |
// of neighbors required for Survival. | |
// http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life | |
function point_lives_next_gen(alive, num_neighbors) { | |
var n = num_neighbors; | |
if (alive) { | |
return (n == 2 || n == 3) | |
} else { | |
return (n == 3) | |
} | |
} | |
//- TEST | |
// Test point_lives_next_gen. It's not super complicated, | |
// nor likely to change much, so this is just a smoke test. | |
(function() { | |
assert( point_lives_next_gen(true, 2)); | |
assert( point_lives_next_gen(true, 3)); | |
assert( point_lives_next_gen(false, 3)); | |
assert(!point_lives_next_gen(false, 1)); | |
assert(!point_lives_next_gen(true, 1)); | |
assert(!point_lives_next_gen(false, 2)); | |
})(); | |
//- DATA STRUCTURE: hash | |
// | |
// This defines our core data structure for representing | |
// a set of 2D points. | |
// We use a hash, although arguably a | |
// set or array would be better. | |
function data_2d() { | |
var hash = {}; | |
function key(point) { | |
var x = point[0]; | |
var y = point[1]; | |
return x.toString() + ',' + y.toString(); | |
}; | |
return { | |
alive: function (point) { | |
return hash[key(point)]; | |
}, | |
set: function (point, on) { | |
hash[key(point)] = on; | |
} | |
} | |
} | |
//- TEST | |
// | |
// Test data_2d. | |
(function() { | |
d = data_2d(); | |
assert(!d.alive([5,7])); | |
d.set([5,7], true); | |
assert(d.alive([5,7])); | |
d.set([5,7], false); | |
assert(!d.alive([5,7])); | |
})(); | |
//- FUNCTION w/no side effects | |
// | |
// This defines how we find neighbors for a cell. We use a | |
// 2D toroidal geometry, a la PacMan. | |
function get_toroidal_neighbors(point, width, height) { | |
var x = point[0]; | |
var y = point[1]; | |
var x_deltas = [ | |
-1, 0, 1, | |
-1, 1, | |
-1, 0, 1 | |
] | |
var y_deltas = [ | |
-1, -1, -1, | |
0, 0, | |
1, 1, 1 | |
] | |
return x_deltas.map(function(dx, i) { | |
var dy = y_deltas[i]; | |
var xx = (x + dx + width) % width; | |
var yy = (y + dy + height) % height; | |
return [xx, yy]; | |
}); | |
} | |
//- MODEL OBJECT | |
// | |
// The broader World object supports a finite 2D topology and | |
// provides the interface methods that abstract_game_of_life | |
// wants on it. | |
function world(width, height) { | |
var data = data_2d(); | |
function cells() { | |
points = [] | |
for (var x = 0; x < width; ++x) { | |
for (var y = 0; y < height; ++y) { | |
points.push([x,y]); | |
} | |
} | |
return points; | |
} | |
function num_alive_neighbors(loc) { | |
var num = 0; | |
var neighbors = get_toroidal_neighbors(loc, width, height); | |
for (var i in neighbors) { | |
if (data.alive(neighbors[i])) { | |
num += 1; | |
} | |
}; | |
return num; | |
} | |
return { | |
"alive": data.alive, | |
"set": data.set, | |
"cells": cells, | |
"num_alive_neighbors": num_alive_neighbors | |
} | |
} | |
//- TEST | |
// | |
// Test the world class | |
(function () { | |
w = world(10, 10); | |
assert(w.cells().length == 100); | |
w.set([5,5], true); | |
assert(w.alive([5,5])); | |
assert(w.num_alive_neighbors([5,5]) == 0); | |
w.set([5,6], true); | |
assert(w.num_alive_neighbors([5,5]) == 1); | |
w.set([6,6], true); | |
assert(w.num_alive_neighbors([5,5]) == 2); | |
// try to fool us with a far-off cell | |
w.set([9,9], true); | |
assert(w.num_alive_neighbors([5,5]) == 2); | |
// kill thy neighbor | |
w.set([6,6], false); | |
assert(w.num_alive_neighbors([5,5]) == 1); | |
})(); | |
//- FUNCTION (concrete) | |
// | |
// This returns the function that is used to transform our | |
// board for this demo. It mostly configures a concrete geometry | |
// for the Game of Life. | |
function board_transform_function(width, height) { | |
function create_world() { | |
return world(width, height); | |
} | |
return abstract_game_of_life( | |
create_world, | |
point_lives_next_gen | |
); | |
} | |
//- PROCEDURE (event-based) | |
// | |
// This is crude, but can be extended without regards | |
// to the underlying algorithm. (You could add pause | |
// buttons, speed sliders, etc.). | |
function animate( | |
initial_data, | |
step_function, | |
render_func, | |
delay, | |
max_ticks) | |
{ | |
var tick = 0; | |
var current_data = initial_data; | |
function pulse() { | |
tick += 1 | |
render_func(current_data); | |
if (tick < max_ticks) { | |
current_data = step_function(current_data); | |
render_func(current_data); | |
setTimeout(pulse, delay); | |
} | |
} | |
pulse(); | |
} | |
//- VIEW (abstract) | |
// | |
// Warning: this is not well-test, but the interface should be | |
// apparent. Scaling was trial and error. | |
function view_2d (width, height) { | |
var canvas = document.getElementById("canvas"); | |
var ctx = canvas.getContext("2d"); | |
function draw(x, y, on) { | |
ctx.fillStyle = on ? 'black' : 'white'; | |
var w = 10; | |
var h = 10; | |
x = x * w; | |
y = y * h; | |
ctx.fillRect(x, y, w, h); | |
} | |
return { | |
'draw': draw | |
} | |
} | |
//- VIEW (concrete) | |
function display(width, height) { | |
var view = view_2d(width, height); | |
return { | |
'render_board': function(board) { | |
for (var y = 0; y < height; ++y) { | |
for (var x = 0; x < width; ++x) { | |
on = board.alive([x, y]); | |
view.draw(x,y, on); | |
} | |
} | |
} | |
} | |
} | |
//- DATA INITIALIZATION | |
function seed_world(world) { | |
var seed = [ | |
"X ", | |
" ", | |
"XX ", | |
" ", | |
" XXX ", | |
" ", | |
" XXX ", | |
" X ", | |
]; | |
var points = [] | |
for (var x = 0; x < seed.length; ++x) { | |
s = seed[x] | |
for (var y = 0; y < s.length; ++y) { | |
if (s.charAt(y) != ' ') { | |
points.push([x,y]); | |
} | |
} | |
} | |
for (var i = 0; i < points.length; ++i) { | |
var point = points[i]; | |
var x = point[0]; | |
var y = point[1]; | |
world.set([x+5,y+5], true); | |
} | |
} | |
//- CONFIGURATION | |
var WIDTH = 50; | |
var HEIGHT = 40; | |
var MAX_TICKS = 800; | |
var DELAY = 5; // milliseconds | |
//- MAIN EXECUTION LOOP | |
function run() { | |
initial_world = world(WIDTH, HEIGHT); | |
seed_world(initial_world); | |
animate( | |
initial_world, | |
board_transform_function(WIDTH, HEIGHT), | |
display(WIDTH, HEIGHT).render_board, | |
DELAY, | |
MAX_TICKS | |
); | |
} | |
run(); | |
})(); | |
</script> |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'pp' | |
lines = [] | |
def indent(line) | |
# return 99 if line.strip == '' | |
line.rstrip =~ /(\s*)/ | |
$1.size | |
end | |
SECTIONS = [] | |
def new_section | |
section = Array.new | |
SECTIONS << section | |
section | |
end | |
File.open(ARGV[0]) do |f| | |
state = 'prelude' | |
section = new_section | |
f.each_line do |line| | |
if line.strip != '' | |
nesting = indent(line) | |
case state | |
when 'prelude' | |
if nesting == 4 | |
state = 'start' | |
section = new_section | |
end | |
when 'start' | |
if nesting > 4 | |
state = 'middle' | |
end | |
when 'middle' | |
if line[4..4] == '}' | |
section << line | |
state = 'start' | |
section = new_section | |
next | |
end | |
end | |
end | |
section << line | |
end | |
end | |
i = 0 | |
while i < SECTIONS.size do | |
system('clear') | |
section = SECTIONS[i] | |
puts "Page #{i+1}" | |
puts "------------" | |
puts section.join('') | |
puts | |
user_input = STDIN.gets | |
i += 1 | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
abstract_game_of_life | |
-> world_factory | |
-> old_world.cells | |
-> old_world.alive | |
-> old_world.num_alive_neighbors | |
-> point_lives_next_gen | |
point_lives_next_gen | |
data_2d | |
key | |
-> x.toString | |
-> y.toString | |
alive | |
set | |
world | |
-> data_2d | |
num_alive_neighbors | |
-> neigbors | |
-> data.alive | |
alive | |
set | |
cells | |
board_transform_function | |
create_world | |
-> world | |
-> abstract_game_of_life | |
animate | |
pulse | |
-> render_func | |
-> step_function | |
-> setTimeout | |
-> pulse | |
view_2d | |
-> document.getElementById | |
-> canvas.getContext | |
draw | |
on | |
-> draw | |
off | |
-> draw | |
display | |
-> view_2d | |
render_board | |
-> board.alive | |
-> view.on | |
-> view.off | |
seed_world | |
-> world.set | |
run | |
-> world | |
-> seed_world | |
-> animate | |
-> board_transform_function | |
-> display(...).render_board | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment