25:["$","title",null,{"children":"Cellular Automata For Procedural Landscape | Woo-Mi Jeong | Observable"}] 49:T188d,intro = md` ### Short Review on CA and GoL [Cellular Automata](https://en.wikipedia.org/wiki/Cellular_automaton) have since the 1940s been a thought exercise in computer science, and an early homework assignment in most programming education curricula. They were some of the first computer simulations built, and have been used to model just about any dynamic system you can imagine such as [epidemic spread](https://www.hindawi.com/journals/jces/2014/518053/), [traffic flows](https://en.wikipedia.org/wiki/Rule_184), [population and urban growth](https://discovery.ucl.ac.uk/id/eprint/7894/1/7894.pdf), [atmostphere and geologic change](https://academic.oup.com/gji/article/144/3/609/614264), [lifelike terrain and landscapes for games](https://demonstrations.wolfram.com/AlgorithmicTerrainWithCellularAutomata/), [musical composition](http://tones.wolfram.com/about/how-it-works), [wildfire spread](https://www.nat-hazards-earth-syst-sci.net/19/169/2019/), and most intriguingly [heritage](https://link.springer.com/article/10.1007/s00004-016-0292-x) and [contemporary architecture](https://mypages.iit.edu/~krawczyk/rjkga02.pdf). There are many examples beyond these — definitely search around and share anything cool! There are also tons of [great learning resources](https://natureofcode.com/book/chapter-7-cellular-automata/) and interactive simulation websites. To implement a cellular automata model, imagine a 2D matrix with rows and columns. Every cell is an agent — an *automaton* (plural *automata*) — in the matrix and can be either *dead* (0, often shown as white) or *alive* (1, often shown as black), though they begin as *dead*. A 4x4 matrix might be visualized with text, as follows: \`\`\` 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 \`\`\` When we start the simulation, we *populate* the simulation with a zero-eth *generation* of living cells. We might do this randomly, though the initial populations could certainly be based on real data as well. \`\`\` 0 1 0 0 0 0 0 0 0 1 0 1 1 1 1 0 \`\`\` A set of rules are then implemented, which define how an individual cell lives or dies based on the state of its 8 cardinal and diagonal neighbors (or other *neighborhood* definitions). For example, a common set of rules for Cellular Automata, called [*Conway's Game of Life*](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life), which the developer described as a "zero player game", sets up the following conditions: 1. If an automaton is alive, and it has fewer than two living neighbors, it dies from loneliness. (1->0) 2. If an automaton is alive, and it has two or three living neighbors, it stays alive. (1->1) 3. If an automaton has four or more living neighbors, it dies from overpopulation. (1->0) 4. If a dead automaton has exactly three living neighbors, it becomes alive through reproduction. (0->1) 5. If a dead automaton has fewer or more than three living neighbors, it stays dead. (0->0) Many other rule sets are possible, and different patterns and behaviors would emerge depending on how the rules affect the population over time. Let's apply these *Game of Life* rules to produce a new generation. First, we need to count how many of the 8 possible neighbors of each cell are living. The number of living neighbors of each cell is marked below in parentheses. Feel free to skip the textual description and instead watch this [excellent animated interview with the creator of the Game of Life, John Conway](https://www.youtube.com/watch?v=R9Plq-D1gEk). \`\`\` 0(1) 1(0) 0(1) 0(0) 0(1) 0(2) 0(3) 0(1) 0(3) 1(3) 0(4) 1(1) 1(2) 1(3) 1(3) 0(2) \`\`\` We now apply the rules enumerated above and transform all the cells together to define our *second* generation. Living cells with 2 or 3 living neighbors stay alive, dead cells with three living neighbors become alive... \`\`\` 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0 \`\`\` And the rules can be applied again for a *third* generation. First, let's count the living neighbors. \`\`\` 0(0) 0(1) 0(1) 0(1) 0(2) 0(3) 1(1) 0(1) 1(3) 1(4) 0(3) 0(1) 1(3) 1(4) 1(2) 0(1) \`\`\` And transform based on the rules of the game... \`\`\` 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 \`\`\` We can see our population slowly going extinct and moving southwards as we move forward in time. Unfortunately, our initial seed population did not have a good distribution for future thriving. So sad. Also, our world was pretty small - cellular automata are much more interesting on bigger fields where individual cells can be seen as parts of organisms, rather than organisms themselves. Often in cellular automata simulation, animation is used to show the dynamism of the world - though sometimes historic states of the world are retained (these are called [*accretor* cellular automata](https://softologyblog.wordpress.com/2018/01/12/accretor-cellular-automata/)). There are many websites devoted to cellular automata, as well as the emergent behaviors and patterns that commonly occur. Whole communities have developed that explore how these models evolve and change depending on their rules and initial population patterns — and entire vocabularies have developed to describe their behaviors. Definitely check out [LifeWiki](https://www.conwaylife.com/wiki/Main_Page), where discoveries are still being made and logged in this fifty+ year old computer simulation logic. New ideas are currently being codified in [stochastic/random](https://en.wikipedia.org/wiki/Stochastic_cellular_automaton) as well as [asynchronous cellular automata](https://en.wikipedia.org/wiki/Asynchronous_cellular_automaton). Super cool experiments are happening as well in imagining cellular automata in higher dimensions as well! - [BitStorm Game of Life](https://bitstorm.org/gameoflife/) - [Teb's GoL Models](https://tebs-game-of-life.com) and [Medium Post](https://medium.com/tebs-lab/simple-rules-emergent-beauty-and-life-artificial-and-otherwise-208642d6d81c) - [Exploring Cellular Automata](https://observablehq.com/@ramonaisonline/exploring-cellular-automata) - [Conway's Game of Life](https://observablehq.com/@mbostock/conways-game-of-life) - [Cellular Automata on Hyperbolic Plane](https://dmishin.github.io/hyperbolic-ca-simulator/index.html) - [Terra.js](https://rileyjshaw.com/terra/) So now let's write our own simple version! `4a:T1254,function step() { //iterate through the cells to determine if each should live or die for (let i = 0; i < data.length; i++) { //clarifying variable let currentCell = data[i]; //holder to collect all of our living neighbors let neighborSum = 0; //check if this cell is the top-left corner if (currentCell.row == 0 && currentCell.column == 0) { //corners have 3 neighbors neighborSum = data[currentCell.b].alive + data[currentCell.r].alive + data[currentCell.br].alive; } //check if this cell is the top-right corner else if (currentCell.row == 0 && currentCell.column == columns - 1) { neighborSum = data[currentCell.b].alive + data[currentCell.l].alive + data[currentCell.bl].alive; } //check if this cell is the bottom-left corner else if (currentCell.row == rows - 1 && currentCell.column == 0) { neighborSum = data[currentCell.t].alive + data[currentCell.r].alive + data[currentCell.tr].alive; } //check if this cell is the bottom-right corner else if (currentCell.row == rows - 1 && currentCell.column == columns - 1) { neighborSum = data[currentCell.t].alive + data[currentCell.l].alive + data[currentCell.tl].alive; } //check if this cell is on the top edge else if (currentCell.row == 0) { //edge cells have 5 neighbors neighborSum = data[currentCell.b].alive + data[currentCell.l].alive + data[currentCell.r].alive + data[currentCell.br].alive + data[currentCell.bl].alive; } //check if this cell is on the bottom edge else if (currentCell.row == rows - 1) { neighborSum = data[currentCell.t].alive + data[currentCell.l].alive + data[currentCell.r].alive + data[currentCell.tr].alive + data[currentCell.tl].alive; } //check if this cell is on the left-hand edge else if (currentCell.column == 0) { neighborSum = data[currentCell.t].alive + data[currentCell.b].alive + data[currentCell.r].alive + data[currentCell.tr].alive + data[currentCell.br].alive; } //check if this cell is on the right-hand edge else if (currentCell.column == columns - 1) { neighborSum = data[currentCell.t].alive + data[currentCell.b].alive + data[currentCell.l].alive + data[currentCell.tl].alive + data[currentCell.bl].alive; } //if all the checks above fail, this cell is an interior cell else { //interior cells have 8 neighbors neighborSum = data[currentCell.t].alive + data[currentCell.b].alive + data[currentCell.l].alive + data[currentCell.r].alive + data[currentCell.tr].alive + data[currentCell.tl].alive + data[currentCell.br].alive + data[currentCell.bl].alive; } //Rules of the Game //this sim uses the *survive* property to determine if the cell should live or die in the next generation // These rules are *Conway's Game of Life* // Any live cell with two or three live neighbors survives. // Any dead cell with three live neighbors becomes a live cell. // All other live cells die in the next generation. Similarly, all other dead cells stay dead. // is the cell dead? if (currentCell.alive == 0) { //the cell is dead if (neighborSum == 3) { //if the cell is dead with three live neighbors, becem alie currentCell.survive = 1; } else { //otherwise stay dead currentCell.survive = 0; } } else { //the cell is alive... if (neighborSum == 2 || neighborSum == 3) { //the living cell has 2 or 3 live neighbors, so it survives currentCell.survive = 1; } else { //the cell dies currentCell.survive = 0; } } } //replace the alive property with survive //this seems unnecessary, right? why not just update alive directly above? //if we do, things get really buggy, can you think of why? //zach didn't catch it, and pulled out lots of hair trying to solve it! for (let i = 0; i < data.length; i++) { let currentCell = data[i]; currentCell.alive = currentCell.survive; } //update the visualization with a data join d3.select('#mainSvg') .selectAll('.automaton') .data(data) .transition() .duration(generationalDelay) .delay((d, i) => i / 10) .attr('fill', function(d) { if (d.alive == 1) { return 'black'; } else { return 'white'; } }); }4b:[] 29:{"id":"6320c38ba0b94554","slug":null,"title":"Cellular Automata For Procedural Landscape","thumbnail":"90616889b3f497ddd80ca6342258a4a7330097c5cdb0860d82ae575a681bb3da","access_level":"public","create_time":"$D2023-10-31T02:10:46.047Z","update_time":"$D2023-11-01T05:13:27.363Z","view_time":null,"first_public_time":"$D2023-10-31T02:10:46.047Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"536e89b71dfea055","login":"woomi","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/31e0a5a063c4f7c40056ea87b83e7737edd99de7ce9467b98c4b12394d8c0561","tier":"starter_2024","bio":"","following":false},"version":97,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"106dcc0cf6497c8a","login":"woomijeong","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/1b631bfd87ceb9a9978eecf2c926160b7765e71f2b89cb9e83edd9366f41b23f","tier":null,"bio":"","following":false}],"members":[{"type":"team","id":"536e89b71dfea055","login":"woomi","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/31e0a5a063c4f7c40056ea87b83e7737edd99de7ce9467b98c4b12394d8c0561","tier":"starter_2024","role":"editor"},{"type":"individual","id":"106dcc0cf6497c8a","login":"woomijeong","name":"Woo-Mi Jeong","avatar_url":"https://avatars-next.observableusercontent.com/1b631bfd87ceb9a9978eecf2c926160b7765e71f2b89cb9e83edd9366f41b23f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Cellular Automata For Procedural Landscape","cells":[{"id":0,"value":"# Cellular Automata For Procedural Landscape","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":63,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"Import D3.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":22,"value":"d3 = require(\"d3@5\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":24,"value":"import {slider} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"viewof width = slider({\n min: 0,\n max: 800,\n step: 10,\n value: 600,\n title: \"SVG Width\",\n description: \"How wide should the cellular automata grid be?\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":32,"value":"viewof height = slider({\n min: 0,\n max: 800,\n step: 10,\n value: 600,\n title: \"SVG Height\",\n description: \"How tall should the cellular automata grid be?\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"viewof columns = slider({\n min: 0,\n max: 200,\n step: 1,\n value: 50,\n title: \"Cellular Automata Columns\",\n description: \"How many columns in the grid?\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":38,"value":"viewof rows = slider({\n min: 0,\n max: 200,\n step: 1,\n value: 50,\n title: \"Cellular Automata Rows\",\n description: \"how many rows in the grid?\"\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":40,"value":"viewof generationalDelay = slider ({\n min: 0,\n max: 500,\n step: 1,\n value: 300,\n title: \"Generational Update Time\",\n description:\n \"How long should a singleccellular automata generational change animation last?\"\n})","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":42,"value":"createSVG = {\n let backgroundColor = \"black\";\n\n let svg = d3\n .create('svg')\n .attr('width', width)\n .attr('height', height)\n .attr('id', 'mainSvg');\n\n let background = svg\n .append('rect')\n .attr('width', width)\n .attr('height', height)\n .attr('x', 0)\n .attr('y', 0)\n .attr('fill', backgroundColor);\n\n return svg.node();\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":44,"value":" viewof lifeChance = slider({\n min: 0,\n max: 1,\n step: .01,\n value: .25,\n title: \"Living Ratio @ Start\",\n description: \"What proportion of cells should the simulation living?\"\n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"md`\n⬇️ Press the \"Generate New Random Grid\" button first! ⬇️\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"viewof genGrid = {\n //create the button\n let button = html``;\n //attach event listener with the regular javascript method, not d3's .on() for simplicity\n button.onclick = function() {\n randomizeCA();\n drawGrid();\n };\n //show button in Observable\n return button;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":86,"value":"viewof stepCA = {\n let button = html``;\n button.onclick = function() {\n step();\n };\n return button;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":88,"value":"viewof skipCA = {\n let button = html``;\n button.onclick = function() {\n let counter = 0;\n let ticker = d3.interval(elapsed => {\n step();\n counter++;\n if (counter > 10) {\n ticker.stop();\n }\n }, generationalDelay);\n };\n return button;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":84,"value":"viewof jumpCA = {\n //create button HTML entity\n let button = html``;\n //attach event listener without D3's .on(event, function(){})\n button.onclick = function() {\n //keep track of actions\n let counter = 0;\n //start D3 timer\n let ticker = d3.interval(elapsed => {\n //run functions at interval\n step();\n counter++;\n //if we have run 100 times...\n if (counter > 100) {\n //turn off the timer\n ticker.stop();\n }\n }, generationalDelay); //how long the timer should wait between executions\n };\n //show in observable\n return button;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":82,"value":"data = {\n let caData = [];\n\n for (let i = 0; i < rows; i++){\n for (let j = 0; j < columns; j++){\n caData.push({\n row: i,\n column: j,\n alie: 0,\n survive: 0,\n s: i * columns + j,\n r: i * columns + (j + 1),\n l: i * columns + (j - 1),\n b: (i + 1) * columns + j,\n tl: (i - 1) * columns + (j - 1),\n tr: (i - 1) * columns + (j + 1),\n bl: (i + 1) * columns + (j - 1),\n br: (i + 1) * columns + (j + 1) \n });\n }\n }\n return caData;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":96,"value":"function randomizeCA() {\n data.forEach(function(automaton) {\n if (math.random() < lifeChance) {\n automaton.alive = 1;\n } else {\n automaton.alive = 0;\n }\n })\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":90,"value":"function drawGrid() {\n //determine width and height of each cell\n let cellHeight = height / rows;\n let cellWidth = width / columns;\n\n //destroy any existing grid cells\n d3.select('#mainSvg')\n .selectAll('.automaton')\n .remove();\n\n //create grid based on synthetic dataset\n d3.select('#mainSvg')\n .selectAll('.automaton') //look for something that doesn't exist\n .data(data) //compare it against data\n .enter()\n .append('rect')\n .attr('width', cellWidth)\n .attr('height', cellHeight)\n .attr('x', function(d) {\n return d.column * cellWidth;\n })\n .attr('y', function(d) {\n return d.row * cellHeight;\n })\n .attr('fill', function(d) {\n if (d.alive == 1) {\n return 'black';\n } else {\n return 'white';\n }\n })\n .attr('stroke', 'black')\n .attr('stroke-width', '1')\n .attr('class', 'automaton');\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"$4a","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 24:null