{
let k = (cellHeight - 1) * cellWidth, q = 0;
const width = cellWidth * (cellSize + cellSpacing) + cellSpacing;
const height = cellHeight * (cellSize + cellSpacing) + cellSpacing;
const context = DOM.context2d(width, height, 1);
context.canvas.style.imageRendering = "pixelated";
context.fillStyle = "#777";
context.fillRect(0, 0, width, height);
context.fillStyle = "#fff";
fillCells(context);
const maxPaths = 50;
obstacles.clear();
const totalCells = cellHeight * cellWidth
const obstacleCount = Math.round(totalCells * obstacleRatio);
obstacleWeights.clear();
while (obstacles.size < obstacleCount) {
const i = Math.floor(Math.random()*totalCells);
obstacles.add(i);
obstacleWeights.set(i, 1+Math.floor(Math.random()*20));
}
// const colors = d3.schemeBuGn[maxPaths]
/* Simulating running the algorithm and finding the best paths. For the first n-1 simulations put some obstacles on the path so it is no longer the best path (i.e. lowest cost). This is done hoping to eliminate trivial paths that go
from one corner to the other almost in a straight line. The last simulation is used to record the best path cells
to show it to the user. */
for (let sim=1; sim<=4; sim++) {
const frontier2 = new Queue();
const parent2 = Object.assign(new Array(cellHeight * cellWidth), {[k]: -1});
for (const j of explore(k, parent2, frontier2)) {
if (score(j) === 0) {
context.fillStyle = "#ddd";
let p = j;
while (p>=0 && p != k) {
if (sim==4) fillCell(context, p);
else if (Math.random() < 0.1 && !obstacles.has(p)) {
obstacles.add(p);
obstacleWeights.set(p, 4);
}
p = parent2[p];
}
yield context.canvas;
break;
}
}
}
obstacles.forEach(i => fillCircle(context,i));
const frontier = new Queue();
const parent = Object.assign(new Array(cellHeight * cellWidth), {[k]: -1});
let found = false;
let lastPath = null;
for (const j of explore(k, parent, frontier)) {
const removedNodes = [];
const dirty = new Set();
const paths = {};
if (lastPath) paths[0] = lastPath;
let rank = 1;
while (frontier.length > 0 && rank <= (found ? (maxPaths * 5) : maxPaths)) {
const score = frontier.peekValue();
const bestIndex = frontier.pop();
removedNodes.push([bestIndex, score]);
if (!paths[rank]) paths[rank] = new Set();
let p = bestIndex;
while (p >= 0 && !dirty.has(p)) {
paths[rank].add(p);
dirty.add(p);
p = parent[p];
}
if (found && paths[rank].size <= 1) paths[rank] = new Set();
else rank += 1;
// rank += 1;
}
let maxRank = rank-1;
removedNodes.forEach(arr => frontier.push(arr[0], arr[1]));
Object.keys(paths).forEach(rank => {
// context.fillStyle = `rgba(0,0,0,${0.2 + 0.8*(maxPaths+1-rank)/maxPaths}`;
// context.fillStyle = colors[rank-1];
// context.fillStyle = d3.interpolateViridis(1 - (0.2 + 0.8*(maxPaths+1-rank)/maxPaths));
// const fillColor = rank == 1 ? "#000" : d3.interpolateViridis(1 - (maxPaths+1-rank)/maxPaths)
const fillColor = rank <= 1 ? "#000" : d3.interpolateViridis(1 - (maxRank+1-rank)/maxRank)
context.fillStyle = fillColor;
paths[rank].forEach(i => {
// fillCircle(context, i);
fillCell(context, i);
if (obstacles.has(i)) {
fillCircle(context,i);
context.fillStyle = fillColor;
}
});
})
yield context.canvas;
// await sleep(50);
if (found) {lastPath = paths[1]; break};
if (score(j) === 0) found=true;
context.fillStyle = "#FFF";
// dirty.forEach(i => fillCircle(context,i, true));
dirty.forEach(i => {
fillCell(context,i);
if (obstacles.has(i)) {
fillCircle(context,i);
context.fillStyle = "#FFF";
}
})
}
}
obstacleColors = {
const obstacleColors = {};
const c = d3.color("brown");
[1,2,3,4,5].forEach(n => {
c.opacity = 0.25 + 0.75*(6-n)/5;
obstacleColors[n]= c.toString();
});
return obstacleColors;
}
obstacleCost = 25
obstacleRatio = 0.10
obstacleWeights = new Map()
function score(i) {
const x = cellWidth - 1 - (i % cellWidth);
const y = 0 - (i / cellWidth | 0);
return x * x + y * y;
}
function generate(cellWidth, cellHeight) {
const heap = new Queue();
const cells = new Uint8Array(cellWidth * cellHeight);
let edge;
heap.push({index: 0, direction: N}, Math.random());
heap.push({index: 0, direction: E}, Math.random());
while (edge = heap.pop()) {
let i0 = edge.index, i1;
let d0 = edge.direction, d1;
let x0 = i0 % cellWidth, x1;
let y0 = i0 / cellWidth | 0, y1;
if (d0 === N) i1 = i0 - cellWidth, x1 = x0, y1 = y0 - 1, d1 = S;
else if (d0 === S) i1 = i0 + cellWidth, x1 = x0, y1 = y0 + 1, d1 = N;
else if (d0 === W) i1 = i0 - 1, x1 = x0 - 1, y1 = y0, d1 = E;
else i1 = i0 + 1, x1 = x0 + 1, y1 = y0, d1 = W;
if (cells[i1] === 0 /* || Math.random() < 0.001 */ ) {
cells[i0] |= d0, cells[i1] |= d1;
if (y1 > 0 && cells[i1 - cellWidth] === 0) {
heap.push({index: i1, direction: N}, Math.random());
}
if (y1 < cellHeight - 1 && cells[i1 + cellWidth] === 0) {
heap.push({index: i1, direction: S}, Math.random());
}
if (x1 > 0 && cells[i1 - 1] === 0) {
heap.push({index: i1, direction: W}, Math.random());
}
if (x1 < cellWidth - 1 && cells[i1 + 1] === 0) {
heap.push({index: i1, direction: E}, Math.random());
}
}
}
return cells;
}
function fillCircle(context, i, clear=false) {
const x = i % cellWidth;
const y = ((i / cellWidth) | 0) + 1;
const cx = x * cellSize + (x + 1) * cellSpacing;
const cy = y * cellSize + (y + 1) * cellSpacing;
context.fillStyle = obstacleColors[obstacleWeights.get(i)];
context.beginPath();
const r = cellSize/3 + (clear ? 1 : 0);
context.arc(cx + (cellSize/2 + cellSpacing) , cy - (cellSize/2 + cellSpacing), r, 0, 2 * Math.PI);
context.fill();
}
function fillPath(context, i1, parent) {
while (true) {
const i0 = parent[i1];
if (i0 < 0) break;
fillEdge(context, i1, i0);
fillCircle(context, i1);
i1 = i0;
}
fillCell(context, i1, false);
}
cells = replay, generate(cellWidth, cellHeight)
cellSize = 4 // 5
cellSpacing = 1
cellWidth = Math.floor((width - cellSpacing) / ( 1.0 * cellSize + cellSpacing))
cellHeight = Math.floor((520 - cellSpacing) / ( 1.0 * cellSize + cellSpacing))
N = 1 << 0
S = 1 << 1
W = 1 << 2
E = 1 << 3
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
