class Node { // Generic Node class; not dependent on specific problem
constructor(value, label) {
this.value = value;
this.label = label;
this.neighbors = [];
}
addEdgeTo(neighbor) {
this.neighbors.push(neighbor);
}
shortestPathTo(targets) {
targets = new Set(targets); // convert Array to Set
// Standard BFS
let queue = [this]; // Start at current node
let comingFrom = new Map;
comingFrom.set(this, null);
while (queue.length) {
let node = queue.shift();
if (targets.has(node)) { // Found!
let path = []; // Build path from back-linked list
while (node) {
path.push(node);
node = comingFrom.get(node);
}
return path.reverse();
}
for (let nextNode of node.neighbors) {
if (!comingFrom.has(nextNode)) {
comingFrom.set(nextNode, node);
queue.push(nextNode);
}
}
}
return []; // Could not reach target node
}
}
function createGraph(matrix) {
// Convert the matrix and its move-rules into a directed graph
const numCols = matrix[0].length;
const numRows = matrix.length;
const numNodes = numRows * numCols * 4; // |Y| * |X| * |Z|
// Create the nodes
const nodes = [];
for (let y = 0; y < numRows; y++)
for (let x = 0; x < numCols; x++)
for (let z = 0; z < 4; z++) {
let dir = (matrix[y][x] + z) % 4;
nodes.push(new Node({x, y, z, dir}, "<" + x + "," + y + ":" + "NESW"[dir] + ">"));
}
// Create the edges
for (let i = 0; i < nodes.length; i++) {
let node = nodes[i];
let {x, y, z, dir} = node.value;
// The "stand-still" neighbor:
let j = i-z + (z+1)%4;
node.addEdgeTo(nodes[j]);
// The neighbor as determined by the node's "direction"
let dj = 0;
if (dir == 0 && y > 0 ) dj = -numCols*4;
else if (dir == 1 && x+1 < numCols) dj = 4;
else if (dir == 2 && y+1 < numRows) dj = numCols*4;
else if (dir == 3 && x > 0 ) dj = -4;
if (dj) node.addEdgeTo(nodes[j+dj]);
}
// return the nodes of the graph
return nodes;
}
// Sample matrix
let matrix = [
[2, 0, 0, 2, 1, 0, 3],
[0, 0, 0, 2, 0, 0, 1],
[3, 2, 0, 3, 3, 3, 0],
];
// Calculate solution:
const nodes = createGraph(matrix);
const path = nodes[0].shortestPathTo(nodes.slice(-4));
// path now has the sequence of nodes to visit.
// I/O handling for this snippet
const size = 26;
const paint = () => new Promise(resolve => requestAnimationFrame(resolve));
function drawSquare(ctx, x, y, angle) {
ctx.rect(x*size+0.5, y*size+0.5, size, size);
ctx.stroke();
ctx.beginPath();
angle = (270 + angle) * Math.PI / 180;
x = (x+0.5)*size;
y = (y+0.5)*size;
ctx.moveTo(x + 0.5, y + 0.5);
ctx.lineTo(x + Math.cos(angle) * size * 0.4 + 0.5, y + Math.sin(angle) * size * 0.4 + 0.5);
ctx.stroke();
}
function drawBall(ctx, x, y) {
x = (x+0.5)*size;
y = (y+0.5)*size;
ctx.beginPath();
ctx.arc(x, y, size * 0.2, 0, 2 * Math.PI);
ctx.fillStyle = "red";
ctx.fill();
}
async function draw(ctx, matrix, time=0, angle=0, curX=0, curY=0) {
await paint();
time = time % 4;
ctx.clearRect(0, 0, ctx.canvas.width, ctx.canvas.height);
for (let y = 0; y < matrix.length; y++) {
for (let x = 0; x < matrix[0].length; x++) {
drawSquare(ctx, x, y, (matrix[y][x] + time) * 360 / 4 - angle);
}
}
drawBall(ctx, curX, curY);
}
async function step(ctx, matrix, time, curX, curY, toX, toY) {
for (let move = 100; move >= 0; move-=5) {
await draw(ctx, matrix, time, 90, toX + (curX-toX)*move/100, toY + (curY-toY)*move/100);
}
for (let angle = 90; angle >= 0; angle-=5) {
await draw(ctx, matrix, time, angle, toX, toY);
}
}
async function animatePath(ctx, path) {
for (let time = 1; time < path.length; time++) {
await step(ctx, matrix, time, path[time-1].value.x, path[time-1].value.y, path[time].value.x, path[time].value.y);
}
}
const ctx = document.querySelector("canvas").getContext("2d");
draw(ctx, matrix);
document.querySelector("button").onclick = () => animatePath(ctx, path);
<button>Start</button><br>
<canvas width="400" height="160"></canvas>