{"id":212,"date":"2008-05-20T07:00:55","date_gmt":"2008-05-20T11:00:55","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/20\/lookup-tables-conway-game-life\/"},"modified":"2019-10-28T09:32:20","modified_gmt":"2019-10-28T13:32:20","slug":"lookup-tables-conway-game-life","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/20\/lookup-tables-conway-game-life\/","title":{"rendered":"Lookup tables for binary image processing&mdash;Conway&#8217;s Game of Life"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <p>This is the third post about using lookup tables to process binary images.  The first two posts were:<\/p>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/07\/lookup-tables-for-binary-image-processing\/\">Introduction<\/a><\/li>\r\n         <li><a href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/13\/lookup-tables-makelut-applylut\/\">Basic use of <tt>makelut<\/tt> and <tt>applylut<\/tt><\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>The most fun I've had with binary image lookup tables is playing around with Conway's Game of Life, the most famous example\r\n      of a cellular automaton.  Martin Gardner popularized the Game of Life in his Mathematical Games column in Scientific American:\r\n   <\/p>\r\n   <div>\r\n      <ul>\r\n         <li>Mathematical Games: The fantastic combinations of John Conway's new solitaire game \"life\", <i>Scientific American<\/i> , October, 1970\r\n         <\/li>\r\n         <li>Mathematical Games: On cellular automata, self-reproduction, the Garden of Eden and the game \"life\", <i>Scientific American<\/i>, February, 1971\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <p>Of course, there are MANY <a href=\"http:\/\/www.google.com\/search?q=conway+game+of+life&amp;ie=utf-8&amp;oe=utf-8&amp;aq=t&amp;rls=org.mozilla:en-US:official&amp;client=firefox-a\">web sites<\/a> devoted to this game.\r\n   <\/p>\r\n   <p>In Conway's Game of Life, each cell in a rectangular grid is either \"alive\" or \"dead\" at generation N.  Going from one generation\r\n      to the next, cells \"die\" or are \"born\" according to the following rules (as stated in Gardner's first article):\r\n   <\/p>\r\n   <p>1. Survivals. Every counter [cell] with two or three neighboring counters survives for the next generation.<\/p>\r\n   <p>2. Deaths. Each counter with four or more neighbors dies (is removed) from overpopulation. Every counter with one neighbor\r\n      or none dies from isolation.\r\n   <\/p>\r\n   <p>3. Births. Each empty cell adjacent to exactly three neighbors - no more, no fewer - is a birth cell. A counter is placed\r\n      on it at the next move.\r\n   <\/p>\r\n   <p>Gardner talks about \"counters\" because, at the time, computer simulation was simply not available to most readers of Scientific\r\n      American.  In his 1970 article, Gardner explains how to play: \"To play life you must have a fairly large checkerboard and\r\n      a plentiful supply of flat counters of two colors. (Small checkers or poker chips do nicely.) An Oriental \"go\" board can be\r\n      used if you can find flat counters that are small enough to fit within its cells. (Go stones are unusable because they are\r\n      not flat.) It is possible to work with pencil and graph paper but it is much easier, particularly for beginners, to use counters\r\n      and a board.\"\r\n   <\/p>\r\n   <p>OK, back to the present time, when we can use a computer instead of a checkerboard and poker chips.  Conway's rules are based\r\n      on a 3-by-3 neighborhood and so can be implemented using a lookup table.  Here's a function which applies Conway's rules to\r\n      a neighborhood:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">type <span style=\"color: #A020F0\">conway<\/span><\/pre><pre style=\"font-style:oblique\">\r\nfunction out = conway(nhood)\r\n\r\nlive = nhood(2,2) == 1;\r\nP = sum(nhood(:)) - nhood(2,2);  % number of live neighbors\r\n\r\nout = (live &amp;&amp; ((2 &lt;= P) &amp;&amp; (P &lt;= 3))) || ...\r\n   (~live &amp;&amp; (P == 3));\r\n\r\n<\/pre><p>Using <tt>conway<\/tt> and <tt>makelut<\/tt> we can construct a lookup table:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">conway_lut = makelut(@conway, 3);<\/pre><p>Here's a very small \"blinker\" pattern.  The pattern repeats itself with a period of two generations.<\/p>\r\n   <p>Generation 1:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw = zeros(5, 5);\r\nbw(3, 2:4) = 1<\/pre><pre style=\"font-style:oblique\">\r\nbw =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n\r\n<\/pre><p>Generation 2:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw = applylut(bw, conway_lut)<\/pre><pre style=\"font-style:oblique\">\r\nbw =\r\n\r\n     0     0     0     0     0\r\n     0     0     1     0     0\r\n     0     0     1     0     0\r\n     0     0     1     0     0\r\n     0     0     0     0     0\r\n\r\n<\/pre><p>Generation 3:<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">bw = applylut(bw, conway_lut)<\/pre><pre style=\"font-style:oblique\">\r\nbw =\r\n\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n     0     1     1     1     0\r\n     0     0     0     0     0\r\n     0     0     0     0     0\r\n\r\n<\/pre><p>According to the <a href=\"http:\/\/en.wikipedia.org\/wiki\/Conway's_Game_of_Life\">Wikipedia article<\/a> on Conway's Game of Life, the first pattern discovered to grow without bound was the \"Gosper glider gun.\"  A \"glider\" is\r\n      a small configuration of cells that periodically recreates itself one step over.  With sufficient imagination, you can see\r\n      that it \"glides.\"  Here is the glider gun:\r\n   <\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">url = <span style=\"color: #A020F0\">'https:\/\/blogs.mathworks.com\/images\/steve\/2008\/gosper_glider_gun.png'<\/span>;\r\nbw = imread(url);\r\nh = imshow(bw, <span style=\"color: #A020F0\">'InitialMagnification'<\/span>, <span style=\"color: #A020F0\">'fit'<\/span>)<\/pre><pre style=\"font-style:oblique\">\r\nh =\r\n\r\n  349.1982\r\n\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2008\/applylut_3_01.png\"> <p>This pattern will periodically produce new gliders and send them shooting across space.<\/p>\r\n   <p>This code animates the Game of Life board for the Gosper glider gun.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\"><span style=\"color: #0000FF\">for<\/span> k = 1:300\r\n    bw = applylut(bw, conway_lut);\r\n    set(h, <span style=\"color: #A020F0\">'CData'<\/span>, bw);\r\n    pause(0.05);\r\n<span style=\"color: #0000FF\">end<\/span><\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2008\/applylut_3_02.png\">\r\n   <p>My last post (I think!) in this series will be about a lookup table optimization we introduced in a recent release of the\r\n      Image Processing Toolbox.  Look for it soon.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_5c5f99310cd0484fa4b26531fa7cb641() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='5c5f99310cd0484fa4b26531fa7cb641 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 5c5f99310cd0484fa4b26531fa7cb641';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        author = 'Steve Eddins';\r\n        copyright = 'Copyright 2008 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n      \r\n      d.title = title + ' (MATLAB code)';\r\n      d.close();\r\n      }   \r\n      \r\n-->\r\n<\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_5c5f99310cd0484fa4b26531fa7cb641()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.6<br><\/p>\r\n<\/div>\r\n<!--\r\n5c5f99310cd0484fa4b26531fa7cb641 ##### SOURCE BEGIN #####\r\n%%\r\n% This is the third post about using lookup tables to process binary\r\n% images.  The first two posts were:\r\n%\r\n% * <https:\/\/blogs.mathworks.com\/steve\/2008\/05\/07\/lookup-tables-for-binary-image-processing\/ \r\n% Introduction>\r\n% * <https:\/\/blogs.mathworks.com\/steve\/2008\/05\/13\/lookup-tables-makelut-applylut\/ \r\n% Basic use of |makelut| and |applylut|>\r\n%\r\n% The most fun I've had with binary image lookup tables is playing\r\n% around with Conway's Game of Life, the most famous example of a\r\n% cellular automaton.  Martin Gardner popularized the Game of Life\r\n% in his Mathematical Games column in Scientific American:\r\n%\r\n% * Mathematical Games: The fantastic combinations of John Conway's \r\n% new solitaire game \"life\", _Scientific American_ , October, 1970\r\n% * Mathematical Games: On cellular automata, self-reproduction, the \r\n% Garden of Eden and the game \"life\", _Scientific American_, February, \r\n% 1971 \r\n%\r\n% Of course, there are MANY \r\n% <http:\/\/www.google.com\/search?q=conway+game+of+life&ie=utf-8&oe=utf-8&aq=t&rls=org.mozilla:en-US:official&client=firefox-a \r\n% web sites> devoted to this game.\r\n%\r\n% In Conway's Game of Life, each cell in a rectangular grid is\r\n% either \"alive\" or \"dead\" at generation N.  Going from one\r\n% generation to the next, cells \"die\" or are \"born\" according to the\r\n% following rules (as stated in Gardner's first article):\r\n%\r\n% 1. Survivals. Every counter [cell] with two or three neighboring\r\n% counters survives for the next generation.\r\n%\r\n% 2. Deaths. Each counter with four or more neighbors dies (is\r\n% removed) from overpopulation. Every counter with one neighbor or\r\n% none dies from isolation.\r\n%\r\n% 3. Births. Each empty cell adjacent to exactly three neighbors -\r\n% no more, no fewer - is a birth cell. A counter is placed on it at\r\n% the next move.\r\n%\r\n% Gardner talks about \"counters\" because, at the time, computer\r\n% simulation was simply not available to most readers of Scientific\r\n% American.  In his 1970 article, Gardner explains how to play: \"To\r\n% play life you must have a fairly large checkerboard and a\r\n% plentiful supply of flat counters of two colors. (Small checkers\r\n% or poker chips do nicely.) An Oriental \"go\" board can be used if\r\n% you can find flat counters that are small enough to fit within its\r\n% cells. (Go stones are unusable because they are not flat.) It is\r\n% possible to work with pencil and graph paper but it is much\r\n% easier, particularly for beginners, to use counters and a board.\"\r\n%\r\n% OK, back to the present time, when we can use a computer instead\r\n% of a checkerboard and poker chips.  Conway's rules are based on a\r\n% 3-by-3 neighborhood and so can be implemented using a lookup\r\n% table.  Here's a function which applies Conway's rules to a\r\n% neighborhood:\r\n\r\ntype conway\r\n\r\n%%\r\n% Using |conway| and |makelut| we can construct a lookup table:\r\n\r\nconway_lut = makelut(@conway, 3);\r\n\r\n%%\r\n% Here's a very small \"blinker\" pattern.  The pattern repeats itself\r\n% with a period of two generations.\r\n%\r\n% Generation 1:\r\n\r\nbw = zeros(5, 5);\r\nbw(3, 2:4) = 1\r\n\r\n%%\r\n% Generation 2:\r\n\r\nbw = applylut(bw, conway_lut)\r\n\r\n%%\r\n% Generation 3:\r\n\r\nbw = applylut(bw, conway_lut)\r\n\r\n%%\r\n% According to the \r\n% <http:\/\/en.wikipedia.org\/wiki\/Conway's_Game_of_Life Wikipedia \r\n% article> on Conway's Game of Life, the\r\n% first pattern discovered to grow without bound was the \"Gosper glider\r\n% gun.\"  A \"glider\" is a small configuration of cells that\r\n% periodically recreates itself one step over.  With sufficient\r\n% imagination, you can see that it \"glides.\"  Here is the glider\r\n% gun:\r\n\r\nurl = 'https:\/\/blogs.mathworks.com\/images\/steve\/2008\/gosper_glider_gun.png';\r\nbw = imread(url);\r\nh = imshow(bw, 'InitialMagnification', 'fit')\r\n\r\n%%\r\n% This pattern will periodically produce new gliders and send them\r\n% shooting across space.\r\n%\r\n% This code animates the Game of Life board for the Gosper glider\r\n% gun.\r\n\r\nfor k = 1:300\r\n    bw = applylut(bw, conway_lut);\r\n    set(h, 'CData', bw);\r\n    pause(0.05);\r\nend\r\n\r\n%%\r\n% Here's an \r\n% <https:\/\/blogs.mathworks.com\/images\/steve\/2008\/glider_gun\/glider_gun.htm \r\n% 18-second video clip> showing the glider gun in action.\r\n%\r\n% My last post (I think!) in this series will be about a lookup\r\n% table optimization we introduced in a recent release of the Image\r\n% Processing Toolbox.  Look for it soon.\r\n##### SOURCE END ##### 5c5f99310cd0484fa4b26531fa7cb641\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   This is the third post about using lookup tables to process binary images.  The first two posts were:\r\n   \r\n      \r\n         Introduction\r\n         Basic... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2008\/05\/20\/lookup-tables-conway-game-life\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[494,76,36,492,496,126,130],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/212"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=212"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/212\/revisions"}],"predecessor-version":[{"id":2649,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/212\/revisions\/2649"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=212"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=212"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=212"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}