31:T4f8,function* dijkstra(points) { const time = performance.now(); const COSTS = createCostsTexture(points); const t_costs = performance.now() - time; let current = [ Float32Array.from({ length: N }, (_, i) => startNodes.includes(i) ? 0 : 1e9 ), // initial costs Int32Array.from({ length: N }).fill(-1), // initial predecessors Int32Array.from({ length: N }, (_, i) => i), // initial origins Int32Array.from({ length: N }, (_, i) => (startNodes.includes(i) ? 1 : 0)) // initial front ], sum, sum0 = kernelSum(current)[0]; // The easiest way to setup just two variable that you can alternate, // is simply create two kernels, even if they are identical. // They’ll keep their textures straight. const kernel0 = kernel(), kernel1 = kernel(); for (var i = 0; i < 100; i++) { current = kernel1(kernel0(current, COSTS), COSTS); // current = kernel1(kernel0(current, COSTS), COSTS); sum = kernelSum(current)[0]; console.warn(i, performance.now() - time, sum); if (sum >= sum0 - 0.0001) break; sum0 = sum; yield { value: current, t: performance.now() - time, t_costs, sum, i }; } // COSTS.delete(); yield { value: current, t: performance.now() - time, t_costs, sum, i }; }32:[] 2f:{"title":"Dijkstra’s algorithm in gpu.js","cells":[{"id":0,"value":"md`# Dijkstra’s algorithm in gpu.js\n\nFollowing [Xiaoji Chen’s experiment](http://www.xiaoji-chen.com/2019/isochronic-map-webgl) I wanted to compute Dijkstra’s shortest paths on the GPU. Here I'm trying with [gpu.js](https://gpu.rocks), in lieu of [deck.gl](https://deck.gl).\n\nThe results are a bit underwhelming. It's not faster (and in fact quite a bit slower) than what I can get [on the CPU](/@fil/dijkstra). Possibly, because I download the results back to the CPU to display them (in Xiaoji Chen’s approach, the rendering is also done on the GPU). Or just because my GPU programming is totally wrong. The other issue I faced is that the limitations in terms of # of nodes and links are quite severe.\n\nI'm leaving it at that for now. Comment and suggestions welcome!\n\nThanks to [Robert Plummer](https://observablehq.com/@robertleeplummerjr) for the help with GPU.js; it rocks!`","pinned":false,"hidden":false,"mode":"ojs"},{"id":670,"value":"viewof replay = html`