370417/index.html

## 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>

## 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();

}
	<!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>
	"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();

	}