2d:null 2e:["$","title",null,{"children":"Random Walk Along a Street Grid | Matt Khinda | Observable"}] 33:T478,graphic = { let svg = d3.create("svg") .attr("viewBox", [-padding, -padding, width+padding, height+padding]); //draw manhattan outline svg.append("g") .selectAll(".mn") .data(manhattan_geom.features) .join("path") .attr("class", "mn") .attr("stroke", "#263238") .attr("stroke-width", ".65px") .attr("fill", "none") .attr("d", d3.geoPath(projection)); //draw streets svg.append("g") .selectAll(".edge") .data(edges) .join("path") .attr("class", "edge") .attr("stroke", "#bdbdbd") .attr("stroke-width", ".5px") .attr("d", d3.geoPath(projection)); // draw origin point svg.append("g") .selectAll(".origin") .data(origin) .join("path") .attr("class", "origin") .attr("fill", "red") .attr("d", d3.geoPath(projection).pointRadius(3)); //draw random walk svg.append("g") .selectAll(".walk") .data(randomWalk) .join("path") .attr("class", "walk") .attr("fill", "none") .attr("stroke", "red") .attr("stroke-width", "1px") .attr("d", d3.geoPath(projection)); return svg.node() }34:T572,function generateRandomWalk(originPoint) { const currentStart = originPoint[0]; let currentNode = currentStart; let coords = [currentNode.geometry.coordinates]; let distTravelled = 0; // build fast node lookup (same as avoiding walk) const nodeIndex = new Map( nodes.map(d => [d.properties.osmid, d]) ); while (distTravelled < targetDist_ft) { const possibleEdges = []; for (const edge of edges) { const { u, v } = edge.properties; if ( u === currentNode.properties.osmid || v === currentNode.properties.osmid ) { possibleEdges.push(edge); } } // dead end (rare, but possible) if (possibleEdges.length === 0) { return [coords, distTravelled]; } const currentEdge = possibleEdges[Math.floor(Math.random() * possibleEdges.length)]; distTravelled += currentEdge.properties.length_ft; const nextNodeId = currentEdge.properties.u === currentNode.properties.osmid ? currentEdge.properties.v : currentEdge.properties.u; const nextNode = nodeIndex.get(nextNodeId); if (!nextNode) break; currentNode = nextNode; coords.push([ currentNode.geometry.coordinates[0], currentNode.geometry.coordinates[1] ]); } return [coords, distTravelled]; }35:T610,function generateAvoidingRandomWalk(originPoint) { const currentStart = originPoint[0]; let currentNode = currentStart; let coords = [currentNode.geometry.coordinates]; let distTravelled = 0; const visitedEdges = new Set(); const visitedNodes = new Set([currentNode.properties.osmid]); // build fast node lookup const nodeIndex = new Map( nodes.map(d => [d.properties.osmid, d]) ); while (distTravelled < targetDist_ft) { const possibleEdges = []; for (const edge of edges) { const { u, v } = edge.properties; if ( !visitedEdges.has(edge) && ( (u === currentNode.properties.osmid && !visitedNodes.has(v)) || (v === currentNode.properties.osmid && !visitedNodes.has(u)) ) ) { possibleEdges.push(edge); } } if (possibleEdges.length === 0) { return [coords, distTravelled]; // dead end } const currentEdge = possibleEdges[Math.floor(Math.random() * possibleEdges.length)]; visitedEdges.add(currentEdge); distTravelled += currentEdge.properties.length_ft; const nextNodeId = currentEdge.properties.u === currentNode.properties.osmid ? currentEdge.properties.v : currentEdge.properties.u; const nextNode = nodeIndex.get(nextNodeId); if (!nextNode) break; currentNode = nextNode; visitedNodes.add(nextNodeId); coords.push([ nextNode.geometry.coordinates[0], nextNode.geometry.coordinates[1] ]); } return [coords, distTravelled]; }36:[{"id":"beb0b53afd52f5bfee00704c5b19b5417f80d3b29ff37e8dd824ba09c606364f165a8eaa28bb5045aa0044b1f9b7ccc0e2a837f194b2b189fce112af82fa04e6","href":"https://static.observableusercontent.com/files/beb0b53afd52f5bfee00704c5b19b5417f80d3b29ff37e8dd824ba09c606364f165a8eaa28bb5045aa0044b1f9b7ccc0e2a837f194b2b189fce112af82fa04e6","name":"NYC_2020_NTA.geojson","type":"application/geo+json","lastModified":1738812939084.042,"size":4625123},{"id":"67c5a6cbb0e5386673bbde99afc105474a49bd51cc62e9aad799ab9c0164bae49ddd83a6d9bb70f49478a753ff11e661db3902f59e4e56ce7a88b9133a482715","href":"https://static.observableusercontent.com/files/67c5a6cbb0e5386673bbde99afc105474a49bd51cc62e9aad799ab9c0164bae49ddd83a6d9bb70f49478a753ff11e661db3902f59e4e56ce7a88b9133a482715","name":"MN_edge_list.json","type":"application/json","lastModified":1767397159750.54,"size":2957857},{"id":"5bd803c9584bffb743b51bac8d6e27a6113cc2f94da48b82f83a152282a1ba6f60b0b1332799b6ed1a903aa75cf201f2e45a98a7210c3440d012715fd74f3f86","href":"https://static.observableusercontent.com/files/5bd803c9584bffb743b51bac8d6e27a6113cc2f94da48b82f83a152282a1ba6f60b0b1332799b6ed1a903aa75cf201f2e45a98a7210c3440d012715fd74f3f86","name":"MN_node_list.json","type":"application/json","lastModified":1767397162639.126,"size":396225}] 31:{"id":"15e1b68859cfa86a","slug":"random-walk-nyc","title":"Random Walk Along a Street Grid","thumbnail":"b4daceb8603f926937314fa1b8fae074428d171cb1fa21cd85a5983ef00ded52","access_level":"public","create_time":"$D2023-12-29T16:54:35.384Z","update_time":"$D2026-06-25T17:23:53.537Z","view_time":null,"first_public_time":"$D2023-12-29T16:54:35.384Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"bd1a04fba6aa0b96","login":"mpkhinda","name":"Matt Khinda","avatar_url":"https://avatars-next.observableusercontent.com/d3ce820bb0a0da07120f1d18fc5462f4d2dda95075bbb7bd7ac6113a256128dd","tier":"starter_2024"},"version":912,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7ed01765dbd656ee","login":"mpkhinda","name":"Matt Khinda","avatar_url":"https://avatars-next.observableusercontent.com/381c8bb4edddbcd7e2319cbd390f7477b1b4934289bf039a4e881d2d3711d20e","tier":null}],"members":[{"type":"individual","id":"7ed01765dbd656ee","login":"mpkhinda","name":"Matt Khinda","avatar_url":"https://avatars-next.observableusercontent.com/381c8bb4edddbcd7e2319cbd390f7477b1b4934289bf039a4e881d2d3711d20e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":3,"collection":{"id":"d6aec43a82873854","slug":"modeling-simulation","title":"🧮 Modeling & Simulation","owner":{"id":"bd1a04fba6aa0b96","login":"mpkhinda","name":"Matt Khinda"}},"type":"notebook","body":{"title":"Random Walk Along a Street Grid","cells":[{"id":0,"value":"# Random Walk Along a Street Grid","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":481,"value":"A visualization of a random walk along the Manhattan street network for ${miles} miles. Loosely adapted from [this notebook](https://observablehq.com/@fil/manhattan-voronoi-osmnx) by Fil (Philip Rivière). Network edges and nodes come from Geoff Boeing’s [OSMnx](https://github.com/gboeing/osmnx). \n\n_Note: self-avoiding walks ensure the path doesn't double back on itself, but often get trapped and end before the max distance. Self-intersecting walks always run close to the max distance but often appear shorter because they overlap._","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":350,"value":"viewof miles = Inputs.range([0, 10], {step: 1, label: html`Maximum Miles`})\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":662,"value":"viewof avoid = Inputs.radio([\"Yes\", \"No\"], {value: \"Yes\", label: html`Self-Avoiding`})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":487,"value":"viewof animate = Inputs.radio([\"Yes\", \"No\"], {value: \"Yes\", label: html`Animate`})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":180,"value":"viewof regenerate = Inputs.button(\"Regenerate\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":740,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":720,"value":"

Miles travelled: ${milesTravelled.toFixed(2)}

","pinned":false,"hidden":false,"mode":"html","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":5,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":737,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":13,"value":"#### key variables","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":910,"value":"{\n const walk = d3.select(graphic).selectAll(\".walk\");\n if (walk.size() > 0 && animate === \"Yes\") {\n let lineLength = walk.node().getTotalLength();\n walk.attr(\"stroke-dasharray\", `${t/frames * lineLength},${lineLength}`);\n }\n return t;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"height = width * 0.3;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":858,"value":"padding = 20","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":170,"value":"// generates random origin\norigin = {\n regenerate\n let o = nodes[Math.floor(Math.random() * nodes.length)];\n return [o];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":224,"value":"targetDist_ft = 5280*miles;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":438,"value":"frames = 100;","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":428,"value":"t = {\n regenerate;\n for (let i=0; i d.properties.boroname === \"Manhattan\")\n .map(d => {\n if (d.geometry.type !== \"MultiPolygon\") return d;\n const min_m2 = 200_000;\n const r2 = 6371008.8 ** 2; // used to convert steradians (d3.geoArea default) to sq meters using earth radius\n const kept = d.geometry.coordinates.filter(rings =>\n d.properties.nta2020 === \"MN0191\" // filtering gov island and piers\n ? rings[0].some(p => p[1] > 40.702)\n : Math.abs(d3.geoArea({type: \"Polygon\", coordinates: rings})) * r2 > min_m2\n );\n return {...d, geometry: {type: \"MultiPolygon\", coordinates: kept}};\n })\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"nodes = {\n const rows = await FileAttachment(\"MN_node_list.json\").json();\n const edgeList = await FileAttachment(\"MN_edge_list.json\").json();\n\n const connected = new Set();\n for (const e of edgeList) {\n const len = +e.length;\n if (!Number.isFinite(len) || len < minEdgeLength) continue;\n connected.add(e.u);\n connected.add(e.v);\n }\n\n const mn = turf.combine(manhattan_geom).features[0];\n\n return rows\n .filter(d => connected.has(d.osmid))\n .map(d => ({\n type: \"Feature\",\n properties: d,\n geometry: { type: \"Point\", coordinates: [+d.x, +d.y] }\n }))\n .filter(d => turf.booleanPointInPolygon(d, mn));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":699,"value":"nodeIndex = new Map(\n nodes.map(d => [d.properties.osmid, d.geometry.coordinates])\n);","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":29,"value":"edges = {\n const rows = await FileAttachment(\"MN_edge_list.json\").json();\n\n return rows.map(d => {\n const u = nodeIndex.get(d.u);\n const v = nodeIndex.get(d.v);\n\n if (!u || !v) {\n return null;\n }\n\n // coerce once, explicitly\n const length_m = +d.length;\n if (!Number.isFinite(length_m)) {\n return null;\n }\n \n // filter out very short edges that are likely misc data artifacts\n if (length_m < minEdgeLength) return null;\n\n return {\n type: \"Feature\",\n properties: {\n u: d.u,\n v: d.v,\n visited: 0,\n length_m: length_m,\n length_ft: +(length_m * 3.280839895).toFixed(3),\n name: d.name,\n type: d.highway\n },\n geometry: {\n type: \"LineString\",\n coordinates: [ u, v ]\n }\n };\n }).filter(Boolean);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":253,"value":"randomWalk = {\n regenerate;\n edges.forEach(d => d.properties.visited = 0);\n const [coords, distTravelled] = selectWalk(origin);\n return [{\n type: \"Feature\",\n properties: {\n dist_ft: distTravelled\n },\n geometry: {\n type: \"LineString\",\n coordinates: coords\n }\n }];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"### Dependencies","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":40,"value":"d3 = require(\"d3\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":546,"value":"turf = require(\"@turf/turf\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":21,"value":"### Sources: ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":38,"value":"Boeing, Geoff, 2017, \"36-NY-counties-street_networks-node_edge_lists.zip\", U.S. Street Network Shapefiles, Node/Edge Lists, and GraphML Files, https://doi.org/10.7910/DVN/CUWWYJ/MAJIGC, Harvard Dataverse, V2","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"}],"files":"$W36","stdlib":"1","titling":"auto"}} 32:"$31:body"