2c:null 2d:["$","title",null,{"children":"The Fastest Trace Estimation with Dynamic Programming | Chuncheng | Observable"}] 32:T48d,# The Fastest Trace Estimation with Dynamic Programming It is the **Dynamic Programming** method to estimate the fastest trace. I set up an ellipse shaped racing path. And the object aims to reach the end point (180) from the start point (0), with the **shortest** time. The shallow blue nodes are the possible path in the dynamic programming, and the dark blue path is the final answer. ## Dynamic Programming I design the velocity and acceleration function follows the inverse proportionality relationship. ### Improvement The raw dynamic programming method is iterated by the leading nodes with their distance. It will cause the object falls into the trap of local best, and harm the final path. To improve it, I use the combined rule of the balance between distance and time cost. The improvement method works better. ## Options The options are controllers of the display - Road: Whether to display the road marks; - Process: Whether to display the process of dynamic programming; - Improve: Whether to use the Improvement method of dynamic programming; - Trace: Whether to display the path of final answer; - Goal: Control where the Goal Point is. 33:T95a,canvas = { const ctx = DOM.context2d(width, height); // Background 1 ctx.fillStyle = "hsl(216deg 100% 13%)"; ctx.fillRect(0, 0, width, height); // Road ctx.beginPath(); ctx.ellipse( center.x, center.y, road.radiusX + road.wideX, road.radiusY + road.wideY, 0, 0, Math.PI * 2 ); ctx.fillStyle = "hsl(36deg 30% 90%)"; ctx.fill(); // Background 2 ctx.beginPath(); ctx.ellipse( center.x, center.y, road.radiusX - road.wideX, road.radiusY - road.wideY, 0, 0, Math.PI * 2 ); ctx.fillStyle = "hsl(216deg 100% 13%)"; ctx.fill(); // Bound Nodes var { nodes, extent } = boundNodes; for (let i = 0; i < nodes.length; i++) { let opacity = Math.abs(nodes[i][2] - 1); opacity = opacity < 0.2 ? 0 : opacity; ctx.fillStyle = d3.rgb(255, 0, 0, opacity); ctx.fillRect(nodes[i][0], nodes[i][1], 2, 2); } // Road Nodes if (checkboxOptions.find((e) => e === "Road")) { var { nodes } = roadNodes; ctx.font = "20px serif"; for (let i = 0; i < nodes.length; i++) { ctx.fillStyle = d3.rgb(nodes[i][2] / 3, 0, 0, 0.4); ctx.fillText(parseInt(nodes[i][2]), nodes[i][0], nodes[i][1]); ctx.fillRect(nodes[i][0], nodes[i][1], 5, 5); } } // Cars if (checkboxOptions.find((e) => e === "Process")) { ctx.fillStyle = d3.rgb(0, 0, 255, 0.2); ctx.fillRect(initPosition.x, initPosition.y, 10, 10); ctx.font = "20px serif"; for (let i = 0; i < path.length; i++) { ctx.fillStyle = d3.rgb(0, 0, 255, 0.2); if (path[i][5]) { ctx.fillStyle = d3.rgb(0, 255, 255, 0.2); } ctx.fillRect(path[i][0], path[i][1], 5, 5); // ctx.fillText(i, path[i][0], path[i][1]); ctx.fillText(path[i][6], path[i][0], path[i][1]); } } // Trace if (checkboxOptions.find((e) => e === "Trace")) { const trace = [...path[0][7]]; ctx.beginPath(); for (let i = 0; i < trace.length; i++) { if (i === 0) { ctx.moveTo(trace[i][0], trace[i][1]); } else { ctx.lineTo(trace[i][0], trace[i][1]); } ctx.fillStyle = d3.rgb(255, 0, 0); ctx.font = "40px serif"; ctx.fillRect(trace[i][0], trace[i][1], 5, 5); ctx.fillText(i, trace[i][0], trace[i][1]); } ctx.strokeStyle = d3.rgb(0, 20, 200, 0.8); ctx.lineWidth = 5; ctx.stroke(); } return ctx.canvas; }34:T55b,path = { const status = []; // x, y, vx, vy, remain, crush, steps, trace // 0, 1, 2, 3, 4, 5, 6, 7 status.push([initPosition.x, initPosition.y, 0, 0, 1, false, 0, []]); for (let count = 0; count < 1000; count++) { const length = status.length; for (let i = 0; i < length; i++) { if (status[i][4] < 1) { continue; } status[i][4] = 0; if (status[i][5]) { continue; } const { sorted } = carNewStatus( status[i][0], status[i][1], status[i][2], status[i][3] ); const trace = [...status[i][7]]; trace.push([status[i][0], status[i][1]]); for (let j = 0; j < sorted.length; j++) { const s = sorted[j]; if (crushDetect(s[0], s[1])) { continue; } status.push([ s[0], s[1], s[2], s[3], 1, false, status[i][6] + 1, trace ]); if (progress(s[0], s[1]) > rangeGoal) { status.sort((firstEl, secondEl) => { return compare(firstEl, secondEl); }); status[0][7].push([s[0], s[1]]); return status; } } break; } status.sort((firstEl, secondEl) => { return compare(firstEl, secondEl); }); } return status; }35:[] 30:{"id":"d42d10f37f28121b","slug":"the-fastest-trace-estimation-with-dynamic-programming","title":"The Fastest Trace Estimation with Dynamic Programming","thumbnail":"f4637e483c4968e12120d6d5c2afb577b6f85483ad4689d167872ca5132490fc","access_level":"public","create_time":"$D2022-02-08T06:24:41.416Z","update_time":"$D2022-02-09T08:57:22.318Z","view_time":null,"first_public_time":"$D2022-02-08T15:38:58.619Z","fork":{"id":"588e80df1b09ca8c","slug":"simple-html-canvas","title":"Simple HTML Canvas","owner":{"id":"f35c755083683fe5","login":"observablehq","name":"Observable"}},"stars":0,"starred":false,"owner":{"type":"team","id":"bcd65cef1cb4d2ed","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":"starter_2024"},"version":625,"publish_version":625,"role":null,"authored":false,"authors":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null}],"members":[{"type":"individual","id":"16328058352682a8","login":"listenzcc","name":"Chuncheng","avatar_url":"https://avatars-next.observableusercontent.com/bb3c68e77a708a587ffc2d663bb83421f20d67991dbe6c1623c6e5d2fb73d15e","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"The Fastest Trace Estimation with Dynamic Programming","cells":[{"id":0,"value":"$32","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":589,"value":"(v_1 - v_2) \\cdot (a(v_1) - a(v_2)) \\leq 0","pinned":false,"hidden":false,"mode":"tex","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":541,"value":"viewof checkboxOptions = Inputs.checkbox(\n [\"Road\", \"Process\", \"Improve\", \"Trace\"],\n {\n label: \"Options\",\n value: [\"Road\", \"Process\", \"Improve\", \"Trace\"]\n }\n)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":615,"value":"viewof rangeGoal = Inputs.range([100, 260], {\n label: \"Goal\",\n step: 10,\n value: 260\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":5,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"progress = (x, y) => {\n const r = Math.sqrt((center.x - x) ** 2 + (center.y - y) ** 2);\n\n if (x > center.x && y > center.y) {\n return 180 - (Math.asin((center.x - x) / r) / Math.PI) * 180;\n }\n\n if (x > center.x) {\n return -1;\n }\n\n if (y < center.y) {\n return (Math.asin((center.x - x) / r) / Math.PI) * 180;\n }\n\n if (y == center.y) {\n return 90;\n }\n\n if (y > center.y) {\n return 180 - (Math.asin((center.x - x) / r) / Math.PI) * 180;\n }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":342,"value":"compare = (a, b) => {\n const d = a[6] - b[6];\n let c = 0;\n if (d !== undefined) {\n c = d * 10;\n }\n if (!checkboxOptions.find((e) => e === \"Improve\")) {\n c *= 0;\n }\n return c + progress(b[0], b[1]) - progress(a[0], a[1]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":301,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":382,"value":"crushDetect = (x, y) => {\n const crushValue = detect(x, y);\n let crush = false;\n if (Math.abs(crushValue - 1) > 0.2) {\n crush = true;\n }\n\n return crush;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":210,"value":"carNewStatus = (x, y, vx, vy) => {\n const newStatus = [];\n\n const v = Math.sqrt(vx ** 2 + vy ** 2);\n // let a = d3.scaleLinear().domain([0, 10]).range([20, 1])(v);\n const amax = 20,\n amin = 1;\n let a = d3.scaleLinear().domain([0, 10]).range([amax, amin])(v);\n a = Math.abs(a);\n a = a > amax ? amax : a;\n\n const angleNum = 15;\n const angleScaler = d3\n .scaleLinear()\n .domain([0, angleNum])\n .range([0, Math.PI * 2]);\n\n for (let i = 0; i < angleNum; i++) {\n const newVx = vx + a * Math.cos(angleScaler(i)),\n newVy = vy + a * Math.sin(angleScaler(i));\n\n newStatus.push([x + newVx, y + newVy, newVx, newVy]);\n }\n\n const sorted = [...newStatus].sort((firstEl, secondEl) => {\n return compare(firstEl, secondEl);\n });\n\n return { sorted };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":202,"value":"initPosition = {\n const y = center.y - road.radiusY,\n x = center.x;\n return { x, y };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"boundNodes = {\n const nodes = [];\n for (let x = 0; x < width; x += 10) {\n for (let y = 0; y < height; y += 10) {\n nodes.push([x, y, detect(x, y)]);\n }\n }\n\n const extent = d3.extent(nodes.map((e) => e[2]));\n\n return { nodes, extent };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":255,"value":"roadNodes = {\n const angleNum = 40;\n const angleScaler = d3\n .scaleLinear()\n .domain([0, angleNum])\n .range([0, Math.PI * 2]);\n\n const nodes = [];\n for (let i = 0; i < angleNum; i++) {\n const x = center.x + road.radiusX * Math.cos(angleScaler(i)),\n y = center.y + road.radiusY * Math.sin(angleScaler(i));\n nodes.push([x, y, progress(x, y)]);\n }\n return { nodes };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"detect = (x, y) => {\n const value =\n ((x - center.x) / road.radiusX) ** 2 + ((y - center.y) / road.radiusY) ** 2;\n return value;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":51,"value":"center = {\n const x = width / 2,\n y = height / 2;\n return { x, y };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":92,"value":"road = {\n const radiusX = width * 0.4,\n radiusY = height * 0.4;\n\n const wideX = radiusX * 0.11,\n wideY = radiusY * 0.11;\n\n return { wideX, wideY, radiusX, radiusY };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"height = 600","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":135,"value":"d3 = require(\"d3\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 31:"$30:body"