2a:null 2b:["$","title",null,{"children":"Reversible Block Cellular Automata | Cora Johnson-Roberson | Observable"}] 30:T746,update = regl({ vert: ` precision mediump float; attribute vec2 position; varying vec2 uv; void main() { uv = 0.5 * (position + 1.0); gl_Position = vec4(position, 0, 1); }`, frag: ` precision mediump float; uniform sampler2D prevState; uniform bool isBlockOffset; uniform int mapping[16]; varying vec2 uv; const float size = ${RADIUS}.0; const float resolution = 1.0 / size; ${pack} ${unpack} ${rule} void main() { const float blockSize = 2.0; vec2 blockOffset = isBlockOffset ? vec2(resolution) : vec2(0.0); vec2 block = fract(floor((uv + blockOffset) * size / blockSize) * (resolution * blockSize)); vec2 offset = step(resolution, fract(uv + blockOffset - block)); mat2 neighbors; if (isBlockOffset) { neighbors[1][1] = texture2D(prevState, block).r; neighbors[1][0] = texture2D(prevState, fract(block - (vec2(1.0, 0.0) * resolution))).r; neighbors[0][1] = texture2D(prevState, fract(block - (vec2(0.0, 1.0) * resolution))).r; neighbors[0][0] = texture2D(prevState, fract(block - (vec2(1.0, 1.0) * resolution))).r; } else { neighbors[0][0] = texture2D(prevState, block).r; neighbors[0][1] = texture2D(prevState, fract(block + (vec2(1.0, 0.0) * resolution))).r; neighbors[1][0] = texture2D(prevState, fract(block + (vec2(0.0, 1.0) * resolution))).r; neighbors[1][1] = texture2D(prevState, fract(block + (vec2(1.0, 1.0) * resolution))).r; } float state = texture2D(prevState, uv).r; state = rule(neighbors, offset); gl_FragColor = vec4(vec3(state), 1); }`, uniforms: { prevState: regl.prop("prevState"), isBlockOffset: regl.prop("isBlockOffset") }, attributes: { position: [-4, -4, 4, -4, 0, 4] }, depth: { enable: false }, count: 3, framebuffer: regl.prop("nextState") })31:[] 2e:{"id":"da9cffd72fd5d3f2","slug":"reversible-block-cellular-automata","title":"Reversible Block Cellular Automata","thumbnail":"4a091bbbb51b61e05797549c930835d49d7e1485d280b3856aa2932b898b5840","access_level":"public","create_time":"$D2020-04-07T02:46:57.926Z","update_time":"$D2020-04-23T03:12:54.570Z","view_time":null,"first_public_time":"$D2020-04-22T00:28:15.007Z","has_unpublished_edits":null,"fork":false,"stars":3,"starred":false,"owner":{"type":"team","id":"db92d1f1c1f5dc49","login":"corajr","name":"Cora Johnson-Roberson","avatar_url":"https://avatars-next.observableusercontent.com/3618c57223a0f75f9087748a5975f595b7ef0c4855feb068a49ce324e4abf4cd","tier":"starter_2024"},"version":1623,"publish_version":1623,"role":null,"authored":false,"authors":[{"type":"individual","id":"029f7c4991899c31","login":"corajr","name":"Cora Johnson-Roberson","avatar_url":"https://avatars-next.observableusercontent.com/3618c57223a0f75f9087748a5975f595b7ef0c4855feb068a49ce324e4abf4cd","tier":null}],"members":[{"type":"individual","id":"029f7c4991899c31","login":"corajr","name":"Cora Johnson-Roberson","avatar_url":"https://avatars-next.observableusercontent.com/3618c57223a0f75f9087748a5975f595b7ef0c4855feb068a49ce324e4abf4cd","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":2,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Reversible Block Cellular Automata","cells":[{"id":0,"value":"md`# Reversible Block Cellular Automata\n\nThis notebook implements a [block celullar automaton](https://en.wikipedia.org/wiki/Block_cellular_automaton) based on the Margolus neighborhood, a 2x2 block pattern that is offset every frame. It is simple to specify reversible rules for such automata, allowing them to be run forward or backward in time.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"regl._gl.canvas","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1219,"value":"viewof timeDelta = select({\n options: [1, 0, -1],\n title: tex`\\Delta t`,\n value: 1,\n description: \"flow of time\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1059,"value":"viewof ruleSelector = select({\n options: [\n { label: \"Tron\", value: \"tron\" },\n { label: \"Critters\", value: \"critters\" },\n { label: \"Billiard Ball Machine\", value: \"billiardBallMachine\" },\n { label: \"BounceGas\", value: \"bounceGas\" },\n { label: \"HPP\", value: \"hppGas\" },\n { label: \"Rotations\", value: \"rotations\" },\n { label: \"Rotations2\", value: \"rotations2\" },\n { label: \"Rotations3\", value: \"rotations3\" },\n { label: \"Rotations4\", value: \"rotations4\" },\n { label: \"StringThing\", value: \"stringThing\" },\n { label: \"StringThing2\", value: \"stringThing2\" },\n { label: \"SwapOnDiag\", value: \"swapOnDiag\" },\n { label: \"No-op\", value: \"noop\" }\n ],\n value: \"tron\",\n description: \"Rule\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1604,"value":"md`Note that rules like Tron which flip all cells in the block may cause the screen to flash. By default, only every 6th frame is shown for such rules, but this option shows every other frame instead. **Do not check this box** if you are sensitive to flashing lights.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1602,"value":"viewof flashing_allowed = checkbox({\n options: [{ value: \"flashing\", label: \"Flashing OK\" }]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":66,"value":"viewof reset = button({\n value: \"Reset\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":965,"value":"viewof initialConditionSelector = select({\n options: [\n { label: \"Manual\", value: \"manual\" },\n { label: \"Random\", value: \"random\" }\n ],\n value: \"manual\",\n description: \"Initial conditions\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":985,"value":"viewof log10density = {\n if (initialConditionSelector === \"random\") {\n const el = slider({\n min: Math.log10((RADIUS * 1) / 4) * -2.0,\n max: 0.0,\n value: -0.5,\n description: \"log10 population density (random initial condition only)\"\n });\n return el;\n } else {\n const el = md`_Population density is only enabled for random initial conditions._`;\n el.value = 0.0;\n return el;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1185,"value":"viewof log2radius = slider({\n min: 3,\n max: 10,\n value: 8,\n step: 1,\n description: md`${tex`\\log_2`} of size`\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1513,"value":"mutable t = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1120,"value":"md`# Code`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1494,"value":"rbca = {\n reset;\n const rbcaState = {\n prevState: state[0],\n nextState: state[1],\n tick: 0,\n isBlockOffset: false,\n old_dt: 1\n };\n rbcaState.swap = () => {\n const oldPrevState = rbcaState.prevState;\n rbcaState.prevState = rbcaState.nextState;\n rbcaState.nextState = oldPrevState;\n };\n rbcaState.step = d_t => {\n rbcaState.tick += d_t;\n mutable t = rbcaState.tick;\n rbcaState.isBlockOffset = !rbcaState.isBlockOffset;\n\n if (d_t != rbcaState.old_d_t) {\n rbcaState.old_d_t = d_t;\n } else {\n rbcaState.swap();\n }\n };\n return rbcaState;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1278,"value":"d_t = parseInt(timeDelta)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"frame = {\n reset;\n let justReset = true;\n let frame = regl.frame(() => {\n const { prevState, nextState, isBlockOffset } = rbca;\n const ruleCanFlash = ruleArray[15] === 0 && ruleArray[0] === 15;\n const absTick = Math.abs(rbca.tick);\n const canDraw =\n !ruleCanFlash || (flashing_allowed ? absTick % 2 == 1 : absTick % 6 == 1);\n\n if (justReset || canDraw) {\n // skip drawing to avoid flashing\n blit({ prevState });\n }\n if (d_t != 0) {\n update({ prevState, isBlockOffset, nextState });\n rbca.step(d_t);\n }\n justReset = false;\n });\n\n invalidation.then(() => {\n frame && frame.cancel();\n });\n yield frame;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1312,"value":"md`## Rules`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1030,"value":"rules = ({\n noop: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],\n tron: [15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 0],\n critters: [15, 14, 13, 3, 11, 5, 6, 1, 7, 9, 10, 2, 12, 4, 8, 0],\n billiardBallMachine: [0, 8, 4, 3, 2, 5, 9, 7, 1, 6, 10, 11, 12, 13, 14, 15],\n bounceGas: [0, 8, 4, 3, 2, 5, 9, 14, 1, 6, 10, 13, 12, 11, 7, 15],\n hppGas: [0, 8, 4, 12, 2, 10, 9, 14, 1, 6, 5, 13, 3, 11, 7, 15],\n rotations: [0, 2, 8, 12, 1, 10, 9, 11, 4, 6, 5, 14, 3, 7, 13, 15],\n rotations2: [0, 2, 8, 12, 1, 10, 9, 13, 4, 6, 5, 7, 3, 14, 11, 15],\n rotations3: [0, 4, 1, 10, 8, 3, 9, 11, 2, 6, 12, 14, 5, 7, 13, 15],\n rotations4: [0, 4, 1, 12, 8, 10, 6, 14, 2, 9, 5, 13, 3, 11, 7, 15],\n stringThing: [0, 1, 2, 12, 4, 10, 9, 7, 8, 6, 5, 11, 3, 13, 14, 15],\n stringThing2: [0, 1, 2, 12, 4, 10, 6, 7, 8, 9, 5, 11, 3, 13, 14, 15],\n swapOnDiag: [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1305,"value":"ruleArray = rules[ruleSelector]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1322,"value":"invert = ary => {\n const mappings = new Array(ary.length);\n ary.forEach((x, i) => {\n mappings[x] = i;\n });\n return mappings;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1117,"value":"md`## Shaders`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1041,"value":"pack = `\nint pack(mat2 neighbors) {\n return (8 * int(neighbors[0][0])) + (2 * int(neighbors[0][1])) + (4 * int(neighbors[1][0])) + (1 * int(neighbors[1][1]));\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1042,"value":"unpack = `\nmat2 unpack(int block) {\n mat2 neighbors;\n float blockf = float(block);\n neighbors[1][1] = mod(blockf, 2.0);\n neighbors[0][1] = mod(blockf / 2.0, 2.0);\n neighbors[1][0] = mod(blockf / 4.0, 2.0);\n neighbors[0][0] = mod(blockf / 8.0, 2.0);\n\n return neighbors;\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":540,"value":"rule = `\nfloat rule(mat2 neighbors, vec2 offset) {\n int block = pack(neighbors);\n ${blockRemap}\n mat2 newNeighbors = unpack(block);\n if (offset == vec2(0.0, 0.0)) {\n return newNeighbors[0][0];\n } else if (offset == vec2(1.0, 0.0)) {\n return newNeighbors[0][1];\n } else if (offset == vec2(0.0, 1.0)) {\n return newNeighbors[1][0];\n } else if (offset == vec2(1.0, 1.0)) {\n return newNeighbors[1][1];\n } else {\n return 0.5;\n }\n}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1083,"value":"blockRemap = {\n let remaps = '';\n let maybeElse = false;\n const rule = d_t >= 0 ? ruleArray : invert(ruleArray);\n for (let i = 0; i < 16; i++) {\n if (rule[i] != i) {\n remaps += `${maybeElse ? 'else ' : ''}if (block == ${i}) { block = ${\n rule[i]\n }; } \\n`;\n maybeElse = true;\n }\n }\n return remaps;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":53,"value":"$30","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":50,"value":"blit = regl({\n frag: `\n precision mediump float;\n uniform sampler2D prevState;\n varying vec2 uv;\n void main() {\n vec4 state = texture2D(prevState, uv);\n gl_FragColor = vec4(state.rgb, 1);\n }`,\n\n vert: `\n precision mediump float;\n attribute vec2 position;\n varying vec2 uv;\n void main() {\n uv = 0.5 * (position + 1.0);\n gl_Position = vec4(position, 0, 1);\n }`,\n\n attributes: {\n position: [-4, -4, 4, -4, 0, 4]\n },\n\n uniforms: {\n prevState: regl.prop(\"prevState\")\n },\n\n depth: { enable: false },\n\n count: 3\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1127,"value":"md`## Textures`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":43,"value":"state = {\n const state = Array(2)\n .fill()\n .map(() =>\n regl.framebuffer({\n color: regl.texture({\n radius: RADIUS,\n data: INITIAL_CONDITIONS,\n wrap: ['repeat', 'repeat']\n }),\n depthStencil: false\n })\n );\n invalidation.then(() => state.forEach(fbo => fbo && fbo.destroy()));\n return state;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1124,"value":"md`## Initial Conditions`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"RADIUS = 1 << log2radius","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1004,"value":"density = Math.pow(10, log10density)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":972,"value":"randomInitial = p => {\n const inCenterRegion = i => {\n const offset = i / 4;\n const quarterRadius = RADIUS / 4;\n const threeQuarterRadius = 3 * quarterRadius;\n const x = offset / RADIUS;\n const y = offset % RADIUS;\n return (\n quarterRadius < x &&\n x < threeQuarterRadius &&\n quarterRadius < y &&\n y < threeQuarterRadius\n );\n };\n const data = Array(RADIUS * RADIUS * 4)\n .fill()\n .map((_, i) =>\n (inCenterRegion(i) && Math.random() < p && i % 4 == 0) || i % 4 == 3\n ? 255\n : 0\n );\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":458,"value":"initial_figure = [\n [1, 1, 0, 0, 0],\n [1, 1, 0, 0, 0],\n [0, 0, 0, 1, 1],\n [0, 0, 0, 1, 1]\n]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":39,"value":"manualInitialCondition = initial_figure => {\n const data = Array(RADIUS * RADIUS * 4)\n .fill()\n .map((_, i) => (i % 4 == 3 ? 255 : 0));\n const halfRadius = RADIUS / 2.0;\n for (let i = 0; i < initial_figure.length; i++) {\n for (let j = 0; j < initial_figure[0].length; j++) {\n const offset = ((i + halfRadius) * RADIUS + j + halfRadius) * 4;\n const value = ~~(initial_figure[i][j] * 255.0);\n data[offset] = value;\n data[offset + 1] = value;\n data[offset + 2] = value;\n }\n }\n return data;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":977,"value":"INITIAL_CONDITIONS = {\n reset;\n switch (initialConditionSelector) {\n case \"random\":\n return randomInitial(density);\n case \"manual\":\n default:\n return manualInitialCondition(initial_figure);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":1141,"value":"md`## Dependencies`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"import { button, checkbox, select, slider } from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":2,"value":"createREGL = require('regl')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"regl = {\n var canvas = document.createElement('canvas');\n var pixelRatio = Math.min(devicePixelRatio, 1);\n var w = Math.min(640, width);\n var h = w;\n canvas.style.width = `${w}px`;\n canvas.style.height = `${h}px`;\n canvas.width = w * pixelRatio;\n canvas.height = h * pixelRatio;\n let regl = createREGL({\n extensions: [],\n optionalExtensions: ['OES_texture_half_float', 'OES_texture_float'],\n canvas,\n pixelRatio: pixelRatio,\n attributes: {\n antialias: false,\n preserveDrawingBuffer: true\n }\n });\n return regl;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1"}} 2f:"$2e:body"