{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Conway's Game Of Life" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*This notebook originally appeared as a post on*\n", "[*Pythonic Perambulations*](http://jakevdp.github.io/blog/2013/08/07/conways-game-of-life/)\n", "*by Jake Vanderplas. The code and content is BSD-licensed.*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "In 1970 the British Mathematician John Conway created his \"Game of Life\" -- \n", "a set of rules that mimics the chaotic yet\n", "patterned growth of a colony of biological organisms. The \"game\" takes place on\n", "a two-dimensional grid consisting of \"living\" and \"dead\" cells, and\n", "the rules to step from generation to generation are simple:\n", "\n", "- **Overpopulation:** if a living cell is surrounded by more than three living cells, it dies.\n", "- **Stasis:** if a living cell is surrounded by two or three living cells, it survives.\n", "- **Underpopulation:** if a living cell is surrounded by fewer than two living cells, it dies.\n", "- **Reproduction:** if a dead cell is surrounded by exactly three cells, it becomes a live cell.\n", "\n", "By enforcing these rules in sequential steps, beautiful and unexpected patterns can appear." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "I was thinking about classic problems that could be used to demonstrate the effectiveness\n", "of Python for computing and visualizing dynamic phenomena, and thought back to a high school\n", "course I took where we had an assignment to implement a Game Of Life computation in C++.\n", "If only I'd had access to IPython and associated tools back then, my homework assignment\n", "would have been a whole lot easier!\n", "\n", "Here I'll use Python and NumPy to compute generational steps for the game of life, and use\n", "my [JSAnimation](http://github.com/jakevdp/JSAnimation) package to animate the results.\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Because the Game of Life is so simple, the time step can be computed rather\n", "tersely in Python. Here I implement two possibilities: one using generator expressions,\n", "and one using the ``convolve2d`` function from ``scipy``. Note that neither of\n", "these are extremely performant: they involve creating several temporary arrays,\n", "and will not work well for large problems with many time steps. Nevertheless,\n", "the simplicity makes these functions very attractive, and they are absolutely sufficient\n", "for the small examples we'll consider here:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [], "source": [ "import numpy as np\n", "\n", "def life_step_1(X):\n", " \"\"\"Game of life step using generator expressions\"\"\"\n", " nbrs_count = sum(np.roll(np.roll(X, i, 0), j, 1)\n", " for i in (-1, 0, 1) for j in (-1, 0, 1)\n", " if (i != 0 or j != 0))\n", " return (nbrs_count == 3) | (X & (nbrs_count == 2))\n", "\n", "def life_step_2(X):\n", " \"\"\"Game of life step using scipy tools\"\"\"\n", " from scipy.signal import convolve2d\n", " nbrs_count = convolve2d(X, np.ones((3, 3)), mode='same', boundary='wrap') - X\n", " return (nbrs_count == 3) | (X & (nbrs_count == 2))\n", " \n", "life_step = life_step_1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Note that we've made a choice here about the game boundary. Classically, the\n", "game takes place on an infinite, flat plane. Here, for simplicity, we've used\n", "a torroidal geometry (likely familiar to players of 1980s computer games like\n", "Asteroids), where the grid wraps from top to bottom and left to right." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now we'll use the matplotlib animation submodule to visualize the results\n", "(for a tutorial on matplotlib animations, see my [previous post](http://jakevdp.github.io/)\n", "on the subject). We'll make use of my ``JSAnimation`` package, which you\n", "can read about [here](http://jakevdp.github.io)." ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Populating the interactive namespace from numpy and matplotlib\n" ] } ], "source": [ "%pylab inline" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [], "source": [ "# JSAnimation import available at https://github.com/jakevdp/JSAnimation\n", "from JSAnimation.IPython_display import display_animation, anim_to_html\n", "from matplotlib import animation\n", "\n", "def life_animation(X, dpi=10, frames=10, interval=300, mode='loop'):\n", " \"\"\"Produce a Game of Life Animation\n", " \n", " Parameters\n", " ----------\n", " X : array_like\n", " a two-dimensional numpy array showing the game board\n", " dpi : integer\n", " the number of dots per inch in the resulting animation.\n", " This controls the size of the game board on the screen\n", " frames : integer\n", " The number of frames to compute for the animation\n", " interval : float\n", " The time interval (in milliseconds) between frames\n", " mode : string\n", " The default mode of the animation. Options are ['loop'|'once'|'reflect']\n", " \"\"\"\n", " X = np.asarray(X)\n", " assert X.ndim == 2\n", " X = X.astype(bool)\n", " \n", " X_blank = np.zeros_like(X)\n", " figsize = (X.shape[1] * 1. / dpi, X.shape[0] * 1. / dpi)\n", "\n", " fig = plt.figure(figsize=figsize, dpi=dpi)\n", " ax = fig.add_axes([0, 0, 1, 1], xticks=[], yticks=[], frameon=False)\n", " im = ax.imshow(X, cmap=plt.cm.binary, interpolation='nearest')\n", " im.set_clim(-0.05, 1) # Make background gray\n", "\n", " # initialization function: plot the background of each frame\n", " def init():\n", " im.set_data(X_blank)\n", " return (im,)\n", "\n", " # animation function. This is called sequentially\n", " def animate(i):\n", " im.set_data(animate.X)\n", " animate.X = life_step(animate.X)\n", " return (im,)\n", " animate.X = X\n", "\n", " anim = animation.FuncAnimation(fig, animate, init_func=init,\n", " frames=frames, interval=interval)\n", " \n", " #print anim_to_html(anim)\n", " return display_animation(anim, default_mode=mode)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's give this a try with a random starting field:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "data": { "text/html": [ "\n", "\n", "\n", "