Skip to content

Instantly share code, notes, and snippets.

@370417

370417/index.html

Created March 19, 2016 01:16
Show Gist options
  • Save 370417/448d5796e552d579ad20 to your computer and use it in GitHub Desktop.
Save 370417/448d5796e552d579ad20 to your computer and use it in GitHub Desktop.
Download ZIP
Exact recursive shadowcasting
Raw
index.html
<!doctype html>
<html>
<head>
<title>Recursive shadowcasting</title>
<meta charset="utf-8">
<style>
body {
margin: 0;
}
</style>
</head>
<body>
<canvas id="canvas"></canvas>
<script src="index.js"></script>
</body>
</html>
Raw
index.js
"use strict";
/* globals console */
{
// dimensipns
const width = 50;
const height = 50;
// size of a tile
const unit = 12;
// chance of a tile being transparent
const transparentChance = 5/6;
// set up canvas
const canvas = document.getElementById("canvas");
canvas.width = width * unit;
canvas.height = height * unit;
const ctx = canvas.getContext("2d");
// returns true if the point (x, y) is on the edge of the map
const onEdge = (x, y) => {
return x === 0 || y === 0 || x === width - 1 || y === height - 1;
};
// generate a random map
// transparent[x][y] is true if the tile (x, y) is transparent
const transparent = [];
for (let x = 0; x < width; x++) {
transparent[x] = [];
for (let y = 0; y < height; y++) {
transparent[x][y] = !onEdge(x, y) && Math.random() < transparentChance;
}
}
// draw the map
const draw = () => {
for (let x = 0; x < width; x++) for (let y = 0; y < width; y++) {
ctx.fillStyle = transparent[x][y] ? "#888" : "#000";
ctx.fillRect(x * unit, y * unit, unit, unit);
}
};
// represents a polygonal portion of the fov
/* each node has:
an array of child nodes
- visually, child nodes are between closePoints and farPoints
an array, nearPoints, of vertices that are closer to the axes
- vertices are ordered from close to far with respect to origin
an array, farPoints, of vertices that are farther from the axes
- vertices are ordered from far to close with respect ro origin */
const Node = {
create(nearPoints, farPoints) {
const node = Object.create(Node);
node.children = [];
node.nearPoints = nearPoints || [];
node.farPoints = farPoints || [];
return node;
},
add(node) {
if (node) {
this.children.push(node);
}
},
draw(ctx) {
for (let i = 0; i < this.nearPoints.length; i++) {
let [x, y] = this.nearPoints[i];
ctx.lineTo(x * unit, y * unit);
}
for (let i = 0; i < this.children.length; i++) {
this.children[i].draw(ctx);
}
for (let i = 0; i < this.farPoints.length; i++) {
let [x, y] = this.farPoints[i];
ctx.lineTo(x * unit, y * unit);
}
},
};
// draw an octant
const drawOctant = root => {
ctx.beginPath();
ctx.moveTo(root.origin[0] * unit, root.origin[1] * unit);
root/*.children[0]*/.draw(ctx);
ctx.closePath();
ctx.fillStyle = "hsl(" + (root.transform.hour * 45) + ", 100%, 50%)";
ctx.strokeStyle = "#FFF";
ctx.fill();
ctx.stroke();
};
const shadowcast2 = (isTransparent, x0, y0) => {
// integral origin coordinates
const intx = Math.floor(x0);
const inty = Math.floor(y0);
// offset relative to center of tile
const realxoffset = x0 - intx - 0.5;
const realyoffset = y0 - inty - 0.5;
// array of roots of each octant
const octants = [];
[
{ xx: 1, yy: 1, xy: 0, yx: 0, hour: 4 },
{ xx: 1, yy:-1, xy: 0, yx: 0, hour: 1 },
{ xx:-1, yy: 1, xy: 0, yx: 0, hour: 5 },
{ xx:-1, yy:-1, xy: 0, yx: 0, hour: 8 },
{ xx: 0, yy: 0, xy: 1, yx: 1, hour: 2 },
{ xx: 0, yy: 0, xy: 1, yx:-1, hour: 7 },
{ xx: 0, yy: 0, xy:-1, yx: 1, hour: 3 },
{ xx: 0, yy: 0, xy:-1, yx:-1, hour: 6 },
].forEach(transform => {
// rotate coordinates to their actual octant
const rotate = ([x, y]) => [
x * transform.xx + y * transform.yx,
y * transform.yy + x * transform.xy,
];
// rotate actual coordinates to virtual
const reverseRotate = ([x, y]) => [
x * transform.xx + y * transform.xy,
y * transform.yy + x * transform.yx,
];
// turn simulated coordinates into real ones
const realPoint = ([x, y]) => [
x0 + x * transform.xx + y * transform.yx,
y0 + y * transform.yy + x * transform.xy,
];
// turn simulated coordinates into real tile coordinates
const realTile = ([x, y]) => [
intx + x * transform.xx + y * transform.yx,
inty + y * transform.yy + x * transform.xy,
];
const [xoffset, yoffset] = reverseRotate([realxoffset, realyoffset]);
// scan a row of a sector
const scan = (y, start, end) => {
if (start >= end) {
console.log("MISTAKE!");
return "MISTAKE!";
}
const nodes = [];
// distance from origin to center of tile
const ycenter = y - yoffset;
// distance from origin to closer edge of tile
const yinner = ycenter - 0.5;
// distance from origin to farther edge of tile
const youter = ycenter + 0.5;
let nearPoints = [realPoint([
yinner * start,// - xoffset,
yinner,
]), realPoint([
youter * start,// - xoffset,
youter,
])];
let farPoints;
let prevTransparent;
const xmin = Math.round(yinner * start);
const xmax = youter * end;
for (let x = xmin; x < xmax + 0.5; x++) {
let transparent = isTransparent(realTile([x, y]));
if (transparent && prevTransparent === false) {
start = (x - xoffset - 0.5) / yinner;
if (start >= end) {
return nodes;
}
nearPoints = [realPoint([
x - xoffset - 0.5,
yinner,
]), realPoint([
x - xoffset - 0.5 + start,
youter,
])];
} else if (!transparent && prevTransparent) {
// \ | triangle
// \|
if (youter * start > x - xoffset - 0.5) {
nearPoints = [realPoint([
x - xoffset - 0.5,
(x - xoffset - 0.5) / start,
]), realPoint([
Math.min(x - xoffset - 0.5,
yinner * start),
yinner,
])];
} else if (yinner * end < x - xoffset - 0.5) {
farPoints = [realPoint([
x - xoffset - 0.5,
youter,
]), realPoint([
x - xoffset - 0.5,
(x - xoffset - 0.5) / end,
]), realPoint([
yinner * end,
yinner,
])];
let node = Node.create(nearPoints, farPoints);
nodes.push(node);
if (start < (x - xoffset - 0.5) / youter) {
node.children = scan(y + 1, start, (x - xoffset - 0.5) / youter);
}
} else {
farPoints = [realPoint([
x - xoffset - 0.5,
youter,
]), realPoint([
x - xoffset - 0.5,
yinner,
])];
let node = Node.create(nearPoints, farPoints);
nodes.push(node);
if (start < (x - xoffset - 0.5) / youter)
node.children = scan(y + 1, start, (x - xoffset - 0.5) / youter);
}
}
prevTransparent = transparent;
}
if (prevTransparent) {
farPoints = [realPoint([
youter * end,
youter,
]), realPoint([
yinner * end,
yinner,
])];
let node = Node.create(nearPoints, farPoints);
nodes.push(node);
node.children = scan(y + 1, start, end);
}
return nodes;
};
// root node
const root = Node.create();
root.origin = [x0, y0];
root.transform = transform;
root.children = scan(1, 0, 1);
octants[root.transform.hour-1] = root;
drawOctant(root);
});
};
const isTransparent = ([x, y]) => {
if (x < 0 || y < 0 || x >= width || y >= height)
return false;
else
return transparent[x][y];
};
canvas.addEventListener("mousemove", e => {
let x0 = Math.floor(e.clientX / unit) + 0.5;
let y0 = Math.floor(e.clientY / unit) + 0.5;
if (e.shiftKey) {
x0 = e.clientX / unit;
y0 = e.clientY / unit;
}
draw();
shadowcast2(isTransparent, x0, y0);
}, false);
draw();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment