Skip to content

Instantly share code, notes, and snippets.

@jamonholmgren
Created July 31, 2020 05:58
Show Gist options
  • Save jamonholmgren/40870157aee66909f52b699ff4322652 to your computer and use it in GitHub Desktop.
Save jamonholmgren/40870157aee66909f52b699ff4322652 to your computer and use it in GitHub Desktop.
import { Maze } from "./maze";
const state = {
x: 1,
y: 1,
destX: 1,
destY: 1,
path: []
};
type Path = [number, number][];
type Node = {
x: number;
y: number;
cost: number;
previous: undefined | Node;
};
// retraces our steps back to the original node
function retrace(node: Node, path: Path): Path {
// add another step to the path
const newPath = [[node.x, node.y], ...path];
// did we find the origin? if so, we're done!
if (node.previous === undefined) return newPath;
// not yet ... let's keep retracing our steps
return retrace(node.previous, newPath);
}
function exploreNodes(nodes: Node[], exploredNodes: Node[]): Path {
// sort nodes by cost
nodes.sort((a, b) => (a.cost < b.cost ? -1 : 0));
// remove the lowest cost node from the list
const lowestCostNode: Node = nodes.shift()!;
// add it to the explored nodes
exploredNodes.push(lowestCostNode);
// did we find the destination?
if (lowestCostNode.x === state.destX && lowestCostNode.y === state.destY) {
// retrace our steps back to the beginning!
return retrace(lowestCostNode, []);
}
// add any nodes around it that haven't been explored yet
for (let neighborX = -1; neighborX <= 1; neighborX += 1) {
for (let neighborY = -1; neighborY <= 1; neighborY += 1) {
// if it's the center of the 3x3 grid, ignore it
if (neighborX === 0 && neighborY === 0) continue;
// calculate the actual position in the world
const nx = lowestCostNode.x + neighborX;
const ny = lowestCostNode.y + neighborY;
// if it's outside the bounds of the map, skip it
if (nx < 0 || nx > 19 || ny < 0 || ny > 19) continue;
// if it's already in the set of nodes we are exploring, ignore it
if (nodes.find(node => node.x === nx && node.y === ny)) continue;
// if it's already been explored, ignore it
if (exploredNodes.find(node => node.x === nx && node.y === ny)) continue;
// if it's a wall, ignore it
if (Maze[ny][nx] === "wall") continue;
// must be a new node -- let's explore it!
// diagonal moves cost 1.4, horizontal / vertical cost 1
const cost = neighborX === 0 || neighborY === 0 ? 1 : 1.4;
// now let's make a new explorable node
nodes.push({
x: nx,
y: ny,
cost: lowestCostNode.cost + cost,
previous: lowestCostNode
});
}
}
if (nodes.length > 0) {
// let's go explore another node
return exploreNodes(nodes, exploredNodes);
} else {
// couldn't find a path! return an empty one
return [];
}
}
function updatePath() {
// reset the path
state.path = [];
const initialNode = {
x: state.x,
y: state.y,
cost: 0,
previous: undefined
};
const nodes: Node[] = [initialNode];
const exploredNodes: Node[] = [];
state.path = exploreNodes(nodes, exploredNodes);
}
const Main = document.createElement("main");
Object.assign(Main.style, {
backgroundColor: "#602F6B",
width: "600px",
height: "600px",
position: "relative"
});
Maze.forEach((row, y) => {
row.forEach((tile, x) => {
const el = document.createElement("div");
Object.assign(el.style, {
backgroundColor: tile === "wall" ? "#D399E6" : "",
width: "30px",
height: "30px",
float: "left"
});
el.onclick = () => {
state.destX = x;
state.destY = y;
updatePath(); // recalculate path
};
Main.appendChild(el);
});
});
const hamster = document.createElement("div");
Object.assign(hamster.style, {
width: "30px",
height: "30px",
backgroundColor: "#FFFFFF",
borderRadius: "15px",
position: "absolute",
boxShadow: "1px 1px 5px black"
});
Main.appendChild(hamster);
function updateHamster() {
Object.assign(hamster.style, {
left: `${state.x * 30}px`,
top: `${state.y * 30}px`,
transitionDuration: "0.5s"
});
}
updateHamster();
document.getElementById("app")!.appendChild(Main);
setInterval(() => {
// movement loop
if (state.path.length > 0) {
const nextPoint = state.path.shift();
state.x = nextPoint![0];
state.y = nextPoint![1];
updateHamster();
}
}, 500);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment