31:T4c4,step = { const pCache = new Uint16Array(params.width); const vCache = new Uint16Array(params.width); const cCache = new Uint8Array(params.width); return (state, p, maxVel) => { const { pos, vel, col } = state; const size = pos.length; let n = 0; for (let i = 0; i < size; i++) { if (!pos[i]) continue; pCache[n] = i; vCache[n] = vel[i]; cCache[n] = col[i]; n++; } // 1. Acceleration for (let i = 0; i < n; i++) { vCache[i] = Math.min(vCache[i] + 1, maxVel); } // 2. Slowing Down for (let i = 0; i < n; i++) { const diff = Math.abs(pCache[(i + 1) % n] - pCache[i]); const d = Math.min(diff, size - diff); vCache[i] = Math.min(vCache[i], d - 1); } // 3. Randomization for (let i = 0; i < n; i++) { if (bernoulli(p)) vCache[i] = Math.max(0, vCache[i] - 1); } // 4. Car Motion for (let i = 0; i < n; i++) { pCache[i] = (pCache[i] + vCache[i]) % size; } pos.fill(0); vel.fill(0); col.fill(0); for (let i = 0; i < n; i++) { pos[pCache[i]] = 1; vel[pCache[i]] = vCache[i]; col[pCache[i]] = cCache[i]; } return state; }; }32:[] 2f:{"title":"Nagel-Schreckenberg Traffic Model","cells":[{"id":0,"value":"md`# Nagel-Schreckenberg Traffic Model`","pinned":false,"hidden":false,"mode":"ojs"},{"id":243,"value":"md`[Nagel–Schreckenberg model](https://en.wikipedia.org/wiki/Nagel%E2%80%93Schreckenberg_model) is a simple model to simulate freeway traffic. \n\nLet ${tex`x \\in \\lbrace 0,1,\\ldots,M-1\\rbrace`} be the position a car, ${tex`v`} its velocity, and ${tex`d`} the distance to the car ahead. The update rules for each step are\n\n1. *Acceleration*: ${tex`v \\gets min(v + 1, v_{max})`}\n2. *Slowing down*: ${tex`v \\gets min(v, d - 1)`}\n3. *Randomization*: ${tex`v \\gets max(0, v - 1) \\qquad \\text{with probability } p`}\n4. *Car motion*: ${tex`x \\gets x + v`}\n\nIn the following diagram, the vertical axis is time and the horizontal is location of cars.\n\n*updates:*\n\n- added \\`dynamic\\` and \\`colorized\\` option suggested by [@fil](https://observablehq.com/@fil).\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"viewof ctx = {\n const ctx = DOM.context2d(params.width, params.height, 1);\n ctx.canvas.value = ctx;\n return ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":200,"value":"viewof density = slider({\n min: 0, \n max: 1,\n step: 0.01, \n value: .30, \n title: \"density\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":207,"value":"viewof maxVel = slider({\n min: 0, \n max: 50,\n step: 1,\n value: 3,\n title: \"max velocity\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":210,"value":"viewof pSlow = slider({\n min: 0, \n max: 1,\n step: 0.01,\n value: 0.30,\n title: \"slowdown prob\",\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":323,"value":"viewof dynamic = checkbox({\n options: [{ value: \"true\", label: \"dynamic\" }],\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":949,"value":"viewof colorized = checkbox({\n options: [{ value: 1, label: \"colorized\" }],\n value: 0\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"md`---\n## Code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":819,"value":"md`### Dynamic`","pinned":false,"hidden":false,"mode":"ojs"},{"id":761,"value":"buffer0 = {\n const img = new ImageData(params.width, 1);\n const data = new Uint32Array(img.data.buffer);\n return { img, data };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":764,"value":"updateDynamic = {\n if (!!!dynamic) return false;\n if (this === false) return true;\n \n tick;\n updateDensity(state, density0, maxVel0);\n const old = ctx.getImageData(0, 1, params.width, params.height - 1);\n\n ctx.fillStyle = 'white'\n ctx.fillRect(0, 0, params.width, params.height);\n ctx.putImageData(old, 0, 0);\n\n step(state, pSlow0, maxVel0);\n const h = 250;\n buffer0.data.fill(255 << 24 | h << 16 | h << 8 | h);\n for (let i = 0; i < params.width; i++) {\n if (!state.pos[i]) continue;\n buffer0.data[i] = colorized ? pallete[state.col[i]] : params.color;\n }\n ctx.putImageData(buffer0.img, 0, params.height - 1);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":755,"value":"tick = {\n while (!!dynamic) yield;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":727,"value":"pSlow0 = approach(this, pSlow, 0.05)","pinned":false,"hidden":false,"mode":"ojs"},{"id":725,"value":"maxVel0 = approach(this, maxVel, 0.05, 1e-2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":722,"value":"density0 = approach(this, density, 0.1)","pinned":false,"hidden":false,"mode":"ojs"},{"id":831,"value":"md`### Static`","pinned":false,"hidden":false,"mode":"ojs"},{"id":352,"value":"buffer = {\n const img = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);\n const data = new Uint32Array(img.data.buffer);\n return { img, data };\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":368,"value":"updateStatic = {\n if (!!dynamic) return false;\n if (this === false) return true;\n updateDensity(state, density, maxVel);\n \n const h = 250;\n buffer.data.fill(255 << 24 | h << 16 | h << 8 | h);\n \n for (let i = 0; i < params.height; i++) {\n for (let j = 0; j < params.width; j++) {\n if (!state.pos[j]) continue;\n const k = i * params.width + j;\n buffer.data[k] = colorized ? pallete[state.col[j]] : params.color;\n }\n step(state, pSlow, maxVel);\n }\n ctx.putImageData(buffer.img, 0, 0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":835,"value":"md`### Misc`","pinned":false,"hidden":false,"mode":"ojs"},{"id":335,"value":"state = ({\n pos: new Uint16Array(params.width),\n vel: new Uint16Array(params.width),\n col: new Uint8Array(params.width)\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":378,"value":"updateDensity = (state, p1, maxVel) => {\n const { pos, vel, col } = state;\n const n = pos.length;\n const p0 = pos.reduce((a, b) => a + b, 0) / n;\n\n if (p1 < p0) {\n const p = (p0 - p1) / p0;\n for (let i = 0; i < n; i++) {\n if (!pos[i] || !bernoulli(p)) continue;\n pos[i] = 0;\n vel[i] = 0;\n col[i] = 0;\n }\n } else {\n const p = (p1 - p0) / (1 - p0);\n for (let i = 0; i < n; i++) {\n if (pos[i] || !bernoulli(p)) continue;\n pos[i] = 1;\n vel[i] = Math.random() * maxVel | 0;\n col[i] = Math.random() * pallete.length | 0;\n }\n }\n \n return state;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":225,"value":"params = ({\n width, \n height: 500,\n color: 255 << 24 | 125 << 16 | 125 << 8 | 125\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":888,"value":"pallete = d3.schemeTableau10.map(c => {\n const { r, g, b } = d3.rgb(c);\n return 255 << 24 | b << 16 | g << 8 | r;\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":813,"value":"md`### Utils`","pinned":false,"hidden":false,"mode":"ojs"},{"id":700,"value":"function* approach(start, end, speed = 0.03, eps = 1e-3) {\n start = start !== undefined ? start : end;\n yield start;\n while (Math.abs(end - start) > eps) {\n yield start += (end - start) * speed;\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":14,"value":"bernoulli = p => Math.floor(Math.random() + p)","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"md`### Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"import {slider,checkbox} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":839,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}