<footer><div id=version></div></footer>
html, body {
  height: 100%;
}

body {
  margin: 0;
  padding: 0;
  background: #111;
  color: #eee;
  font: caption;
}

#version {
  position: absolute;
  left: 0;
  top: 0;
  padding: 5px;
  background: rgba(0, 0, 0, 0.8)
}
/* global colors, Dungeon, Phaser, simplify, Tweakpane */

// eslint-disable-next-line no-unused-vars
const { black, white, red, yellow, blue, fuchsia, green } = colors.hexColors;

const options = {
	RANGE: 8,
	SIMPLIFY_TOLERANCE: 0.1,
	SIMPLIFY_HIGH: true,
};

const debug = {
	GetLineToLine: 0,
	rays: 0,
	time: 0,
	vertices: 0,
	visibleVertices: 0,
};

// Some defaults
const TILE_ALPHA = 0.2;
const WALLS_ALPHA = 0;
const FIELD_ALPHA = 0.2;
const DEBUG_ALPHA = 0.4;
const SET_MASK = false;
const ZOOM = 2;

// Dungeon
const DUNGEON_WIDTH = 60;
const DUNGEON_HEIGHT = 20;
const ROOM_WIDTH_MIN = 7;
const ROOM_WIDTH_MAX = 11;
const ROOM_HEIGHT_MIN = 3;
const ROOM_HEIGHT_MAX = 11;

// Colors
const FILL_COLOR = white;
const DEBUG_EDGE_COLOR = red;
const DEBUG_RAY_COLOR = blue;
const DEBUG_VERTEX_COLOR = yellow;

// Shortcuts
const { Line, Rectangle } = Phaser.Geom;
const { Extend } = Phaser.Geom.Line;
const { Vector2 } = Phaser.Math;
const { GetLineToLine } = Phaser.Geom.Intersects;
const { GetBounds, SetLeft, SetTop } = Phaser.Display.Bounds;

const gameConfig = {
	pixelArt: true,
	roundPixels: false,
	input: { mouse: { preventDefaultDown: false }, windowEvents: false },
	scene: { preload, create, update },
	loader: {
		baseURL: "https://labs.phaser.io",
		crossOrigin: "anonymous",
	},
};

const playerBounds = new Rectangle();

let cursors;
let dungeon;
let maskGraphics;
let debugGraphics;
let edgesTree;
let verticesTree;
let tilemapLayer;
let map;
let mask;
let player;
let pane;

// Tile index mapping to make the code more readable
const TILES = {
	FLOOR_EMPTY: 6,
	STAIRS: 81,
	BOX: 108,
	BARREL: 109,
	CHEST: 166,
	TRAPDOOR: 167,
	TOP_LEFT_WALL: 3,
	TOP_RIGHT_WALL: 4,
	BOTTOM_RIGHT_WALL: 23,
	BOTTOM_LEFT_WALL: 22,
	TOP_WALL: [
		{ index: 39, weight: 4 },
		{ index: 57, weight: 1 },
		{ index: 58, weight: 1 },
		{ index: 59, weight: 1 },
	],
	LEFT_WALL: [
		{ index: 21, weight: 4 },
		{ index: 76, weight: 1 },
		{ index: 95, weight: 1 },
		{ index: 114, weight: 1 },
	],
	RIGHT_WALL: [
		{ index: 19, weight: 4 },
		{ index: 77, weight: 1 },
		{ index: 96, weight: 1 },
		{ index: 115, weight: 1 },
	],
	BOTTOM_WALL: [
		{ index: 1, weight: 4 },
		{ index: 78, weight: 1 },
		{ index: 79, weight: 1 },
		{ index: 80, weight: 1 },
	],
	FLOOR: [
		{ index: 6, weight: 1000 },
		{ index: 63, weight: 10 },
		{ index: 64, weight: 20 },
		{ index: 65, weight: 1 },
		{ index: 66, weight: 5 },
	],
};

document.getElementById("version").textContent = `Phaser v${Phaser.VERSION}`;

// eslint-disable-next-line no-new
new Phaser.Game(gameConfig);

function preload() {
	// Credits! Michele "Buch" Bucelli (tilset artist) & Abram Connelly (tileset sponser)
	// https://opengameart.org/content/top-down-dungeon-tileset
	this.load.image(
		"tiles",
		"assets/tilemaps/tiles/buch-dungeon-tileset-extruded.png",
	);

	this.load.spritesheet("cat", "assets/sprites/baddie_cat_1.png", {
		frameWidth: 16,
		frameHeight: 16,
	});

	this.load.once("complete", () => {
		this.anims.create({
			key: "right",
			frames: [3, 2].map((f) => ({ key: "cat", frame: f })),
			frameRate: 10,
		});
		this.anims.create({
			key: "left",
			frames: [0, 1].map((f) => ({ key: "cat", frame: f })),
			frameRate: 10,
		});
	});
}

function create() {
	console.time("dungeon");

	dungeon = new Dungeon({
		width: DUNGEON_WIDTH,
		height: DUNGEON_HEIGHT,
		rooms: {
			width: { min: ROOM_WIDTH_MIN, max: ROOM_WIDTH_MAX, onlyOdd: true },
			height: { min: ROOM_HEIGHT_MIN, max: ROOM_HEIGHT_MAX, onlyOdd: true },
		},
	});

	console.timeEnd("dungeon");

	map = this.make.tilemap({
		tileWidth: 16,
		tileHeight: 16,
		width: dungeon.width,
		height: dungeon.height,
	});

	// (tilesetName, key, tileWidth, tileHeight, tileMargin, tileSpacing, gid)
	const tileset = map.addTilesetImage("tiles", "tiles", 16, 16, 1, 2);

	console.time("layer");

	tilemapLayer = map.createBlankLayer("Layer 1", tileset).setAlpha(TILE_ALPHA);

	// Fill with black tiles
	tilemapLayer.fill(20);

	// Use the array of rooms generated to place tiles in the map

	for (const room of dungeon.rooms) {
		const { x, y, width, height } = room;
		const cx = Math.floor(x + 0.5 * width);
		const cy = Math.floor(y + 0.5 * height);
		const left = x;
		const right = x + (width - 1);
		const top = y;
		const bottom = y + (height - 1);

		// Fill the floor with mostly clean tiles, but occasionally place a dirty tile
		// See "Weighted Randomize" example for more information on how to use weightedRandomize.
		map.weightedRandomize(TILES.FLOOR, x, y, width, height);

		// Place the room corners tiles
		map.putTileAt(TILES.TOP_LEFT_WALL, left, top);
		map.putTileAt(TILES.TOP_RIGHT_WALL, right, top);
		map.putTileAt(TILES.BOTTOM_RIGHT_WALL, right, bottom);
		map.putTileAt(TILES.BOTTOM_LEFT_WALL, left, bottom);

		// Fill the walls with mostly clean tiles, but occasionally place a dirty tile
		map.weightedRandomize(TILES.TOP_WALL, left + 1, top, width - 2, 1);
		map.weightedRandomize(TILES.BOTTOM_WALL, left + 1, bottom, width - 2, 1);
		map.weightedRandomize(TILES.LEFT_WALL, left, top + 1, 1, height - 2);
		map.weightedRandomize(TILES.RIGHT_WALL, right, top + 1, 1, height - 2);

		// Dungeons have rooms that are connected with doors. Each door has an x & y relative to the rooms location
		const doors = room.getDoorLocations();

		for (let i = 0; i < doors.length; i++) {
			map.putTileAt(TILES.FLOOR_EMPTY, x + doors[i].x, y + doors[i].y);
		}

		if (room.width <= 3 || room.height <= 3) {
			continue;
		}

		// Place some random stuff in rooms occasionally
		const rand = Math.random();

		if (rand <= 0.2) {
			tilemapLayer.putTileAt(TILES.CHEST, cx, cy);
		} else if (rand <= 0.3) {
			tilemapLayer.putTileAt(TILES.STAIRS, cx, cy);
		} else if (rand <= 0.4) {
			tilemapLayer.putTileAt(TILES.TRAPDOOR, cx, cy);
		} else if (rand <= 0.6) {
			if (room.height >= 9) {
				// We have room for 4 towers
				tilemapLayer.putTilesAt([[186], [205]], cx - 1, cy + 1);
				tilemapLayer.putTilesAt([[186], [205]], cx + 1, cy + 1);
				tilemapLayer.putTilesAt([[186], [205]], cx - 1, cy - 2);
				tilemapLayer.putTilesAt([[186], [205]], cx + 1, cy - 2);
			} else if (room.height >= 7) {
				tilemapLayer.putTilesAt([[186], [205]], cx - 1, cy - 1);
				tilemapLayer.putTilesAt([[186], [205]], cx + 1, cy - 1);
			}
		}
	}

	console.timeEnd("layer");

	// console.table(dungeon.rooms);

	tilemapLayer.setCollisionByExclusion([
		...TILES.FLOOR.map((tile) => tile.index),
		TILES.CHEST,
		TILES.STAIRS,
		TILES.TRAPDOOR,
	]);

	console.time("geom");

	const edges = [];
	const tileBounds = new Rectangle();
	const cam = this.cameras.main;

	// Horizontal lines (top and bottom faces)

	let topEdge;
	let bottomEdge;
	for (let y = 0; y < map.height; y++) {
		const row = map.layer.data[y];

		for (let x = 0; x < map.width; x++) {
			const tile = row[x];

			if (tile.faceTop) {
				const { left, right, top } = tile.getBounds(cam, tileBounds);

				if (topEdge) {
					topEdge.x2 = right;
					topEdge.y2 = top;
				} else {
					topEdge = new Line(left, top, right, top);
					edges.push(topEdge);
				}
			} else {
				topEdge = null;
			}

			if (tile.faceBottom) {
				const { left, right, bottom } = tile.getBounds(cam, tileBounds);

				if (bottomEdge) {
					bottomEdge.x2 = right;
					bottomEdge.y2 = bottom;
				} else {
					bottomEdge = new Line(left, bottom, right, bottom);
					edges.push(bottomEdge);
				}
			} else {
				bottomEdge = null;
			}
		}

		topEdge = null;
		bottomEdge = null;
	}

	// Vertical lines (left and right faces)

	let leftEdge;
	let rightEdge;
	for (let x = 0; x < map.width; x++) {
		for (let y = 0; y < map.height; y++) {
			const tile = map.layer.data[y][x];

			if (tile.faceLeft) {
				const { left, top, bottom } = tile.getBounds(cam, tileBounds);

				if (leftEdge) {
					leftEdge.x2 = left;
					leftEdge.y2 = bottom;
				} else {
					leftEdge = new Line(left, top, left, bottom);
					edges.push(leftEdge);
				}
			} else {
				leftEdge = null;
			}

			if (tile.faceRight) {
				const { right, top, bottom } = tile.getBounds(cam, tileBounds);

				if (rightEdge) {
					rightEdge.x2 = right;
					rightEdge.y2 = bottom;
				} else {
					rightEdge = new Line(right, top, right, bottom);
					edges.push(rightEdge);
				}
			} else {
				rightEdge = null;
			}
		}

		leftEdge = null;
		rightEdge = null;
	}

	console.timeEnd("geom");

	console.info("%i edges", edges.length);
	// console.table(edges);

	edgesTree = new Phaser.Structs.RTree();
	edgesTree.load(edges);

	const vertices = uniq(
		edges.flatMap((edge) => [edge.getPointA(), edge.getPointB()]),
	);

	console.info("%i vertices", vertices.length);
	// console.table(vertices);

	verticesTree = new Phaser.Structs.RTree();
	verticesTree.toBBox = ({ x, y }) => ({ minX: x, maxX: x, minY: y, maxY: y });
	verticesTree.load(vertices);

	const wallGraphics = this.add.graphics().setAlpha(WALLS_ALPHA);
	drawLines(wallGraphics, edges, DEBUG_EDGE_COLOR);
	drawPoints(wallGraphics, vertices, DEBUG_VERTEX_COLOR);

	// Place the player in the first room
	const [playerRoom] = dungeon.rooms;

	player = this.add.sprite(0, 0, "cat", 2);

	SetLeft(player, map.tileToWorldX(playerRoom.x + 1));
	SetTop(player, map.tileToWorldY(playerRoom.y + 1));

	player.play("right", false, 1);

	maskGraphics = this.add.graphics().setAlpha(FIELD_ALPHA);
	mask = new Phaser.Display.Masks.GeometryMask(this, maskGraphics);
	debugGraphics = this.add.graphics().setAlpha(DEBUG_ALPHA);

	cam.setBounds(0, 0, tilemapLayer.width, tilemapLayer.height);
	cam.setZoom(ZOOM);
	cam.startFollow(player);

	if (SET_MASK) {
		cam.setMask(mask, false);
	}

	cursors = this.input.keyboard.createCursorKeys();

	// PANE

	pane = new Tweakpane.Pane({ title: "Dungeon" });
	pane.containerElem_.style.width = "320px";

	pane.addInput(options, "RANGE", { min: 1, max: 64, step: 1 });
  pane.addInput(options, "SIMPLIFY_TOLERANCE", { min: 0, max: 4, step: 0.1 });
  pane.addInput(options, "SIMPLIFY_HIGH");
	pane.addInput(tilemapLayer, "alpha", {
		label: "tile alpha",
		min: 0,
		max: 1,
		step: 0.1,
	});
	pane.addInput(wallGraphics, "alpha", {
		label: "walls alpha",
		min: 0,
		max: 1,
		step: 0.1,
	});
	pane.addInput(maskGraphics, "alpha", {
		label: "field alpha",
		min: 0,
		max: 1,
		step: 0.1,
	});
	pane.addInput(debugGraphics, "alpha", {
		label: "debug alpha",
		min: 0,
		max: 1,
		step: 0.1,
	});
	pane.addInput(cam, "zoom", { min: 1, max: 4, step: 1 });

	pane.addMonitor(debug, "rays", { format: Math.floor });
	pane.addMonitor(debug, "GetLineToLine", { format: Math.floor });
	pane.addMonitor(debug, "visibleVertices", { format: Math.floor });
	pane.addMonitor(debug, "time", {
		label: "time (ms)",
		view: "graph",
		min: 0,
		max: 10,
	});

	pane.addButton({ title: "Set Mask" }).on("click", () => {
		cam.setMask(mask, false);
	});
	pane.addButton({ title: "Clear Mask" }).on("click", () => {
		cam.clearMask();
	});
}

function update() {
	const { RANGE } = options;

	maskGraphics.clear();
	debugGraphics.clear();

	updatePlayerMovement(this.input.activePointer);

	const startTime = performance.now();

	// Range

	const range = Phaser.Geom.Rectangle.FromXY(
		Math.max(0, player.x - RANGE * map.tileWidth),
		Math.max(0, player.y - RANGE * map.tileHeight),
		Math.min(map.widthInPixels, player.x + RANGE * map.tileWidth),
		Math.min(map.heightInPixels, player.y + RANGE * map.tileHeight),
	);

	const rangeVertices = [
		new Vector2(range.left, range.top),
		new Vector2(range.right, range.top),
		new Vector2(range.right, range.bottom),
		new Vector2(range.left, range.bottom),
	];

	const rangeEdges = [
		range.getLineA(),
		range.getLineB(),
		range.getLineC(),
		range.getLineD(),
	];

	const rangeMinMax = {
		minX: range.left,
		minY: range.top,
		maxX: range.right,
		maxY: range.bottom,
	};

	// Range–wall intersections

	const rangeWallIntersections = [];
	for (const rangeEdge of rangeEdges) {
		for (const wallEdge of edgesTree.search(edgesTree.toBBox(rangeEdge))) {
			const rangeWallIntersection = GetLineToLine(wallEdge, rangeEdge);

			if (rangeWallIntersection) {
				rangeWallIntersections.push(rangeWallIntersection);
			}
		}
	}

	const vertices = [
		...rangeVertices,
		...rangeWallIntersections,
		...verticesTree.search(rangeMinMax),
	];

	// One ray to each vertex
	const rays = [];
	for (const { x, y } of vertices) {
		rays.push(new Line(player.x, player.y, x, y));
	}

	debug.GetLineToLine = 0;

	// Calculate field of view
	const visibleVertices = simplify(
		calc(player, rays),
		options.SIMPLIFY_TOLERANCE,
		options.SIMPLIFY_HIGH,
	);

	debug.rays = rays.length;
	debug.visibleVertices = visibleVertices.length;
	debug.time = performance.now() - startTime;

	drawLines(debugGraphics, rays, DEBUG_RAY_COLOR);
	drawLines(debugGraphics, rangeEdges, DEBUG_EDGE_COLOR);
	drawPoints(debugGraphics, vertices, DEBUG_VERTEX_COLOR);
	drawPoly(maskGraphics, visibleVertices, FILL_COLOR);
	drawPoints(debugGraphics, visibleVertices, DEBUG_VERTEX_COLOR);
}

function updatePlayerMovement(pointer) {
	// const pass = cursors.shift.isDown;
	const { isDown, worldX, worldY } = pointer;
	const dx = isDown ? worldX - player.x : 0;
	const dy = isDown ? worldY - player.y : 0;

	if (cursors.down.isDown || dy > 4) {
		const { left, right, bottom } = GetBounds(player, playerBounds);
		const tileBelowLeft = map.getTileAtWorldXY(left, bottom + 2);
		const tileBelowRight = map.getTileAtWorldXY(right - 1, bottom + 2);

		if (tileBelowLeft || tileBelowRight) {
			player.anims.play(player.anims.getName() || "right", true);

			if (tileBelowLeft.faceTop || tileBelowRight.faceTop) {
				player.y += Math.min(
					2,
					Math.min(tileBelowLeft.getTop(), tileBelowRight.getTop()) - bottom,
				);
			} else {
				player.y += 2;
			}
		}
	} else if (cursors.up.isDown || dy < -4) {
		const { left, right, top } = GetBounds(player, playerBounds);
		const tileAboveLeft = map.getTileAtWorldXY(left, top - 2);
		const tileAboveRight = map.getTileAtWorldXY(right - 1, top - 2);

		if (tileAboveLeft || tileAboveRight) {
			player.anims.play(player.anims.getName() || "left", true);

			if (tileAboveLeft.faceBottom || tileAboveRight.faceBottom) {
				player.y -= Math.min(2, top - tileAboveLeft.getBottom());
			} else {
				player.y -= 2;
			}
		}
	}

	if (cursors.left.isDown || dx < -4) {
		const { left, top, bottom } = GetBounds(player, playerBounds);
		const tileAboveLeft = map.getTileAtWorldXY(left - 2, top);
		const tileBelowLeft = map.getTileAtWorldXY(left - 2, bottom - 1);

		if (tileAboveLeft || tileBelowLeft) {
			player.anims.play("left", true);

			if (tileAboveLeft.faceRight || tileBelowLeft.faceRight) {
				player.x -= Math.min(2, left - tileAboveLeft.getRight());
			} else {
				player.x -= 2;
			}
		}
	} else if (cursors.right.isDown || dx > 4) {
		const { right, top, bottom } = GetBounds(player, playerBounds);
		const tileAboveRight = map.getTileAtWorldXY(right + 2, top);
		const tileBelowRight = map.getTileAtWorldXY(right + 2, bottom - 1);

		if (tileAboveRight || tileBelowRight) {
			player.anims.play("right", true);

			if (tileAboveRight.faceLeft || tileBelowRight.faceLeft) {
				player.x += Math.min(2, tileAboveRight.getLeft() - right);
			} else {
				player.x += 2;
			}
		}
	}
}

function drawLines(graphics, lines, color) {
	graphics.lineStyle(1, color);
	for (const line of lines) {
		graphics.strokeLineShape(line);
	}
}

function drawPoints(graphics, points, color) {
	graphics.fillStyle(color);
	for (const point of points) {
		graphics.fillPointShape(point, 2);
	}
}

function drawPoly(graphics, points, color) {
	graphics.fillStyle(color).fillPoints(points, true);
}

function calc(source, rays) {
	debug.GetLineToLine = 0;

	const field = [];

	for (const ray of rays) {
		const hits = [];

		for (const edge of edgesTree.search(edgesTree.toBBox(ray))) {
			debug.GetLineToLine += 1;

			const hit = GetLineToLine(ray, edge);

			if (hit) {
				hits.push(hit);
			}
		}

		if (hits.length > 0) {
			field.push(hits.sort(sortZ)[0]);
		} else {
			field.push(ray.getPointB());
		}
	}

	return sortClockwise(field, source);
}

function sortZ(a, b) {
	return a.z - b.z;
}

function sortClockwise(points, center) {
	// Adapted from <https://stackoverflow.com/a/6989383/822138> (ciamej)
	var cx = center.x;
	var cy = center.y;

	var sort = function (a, b) {
		if (a.x - cx >= 0 && b.x - cx < 0) {
			return -1;
		}

		if (a.x - cx < 0 && b.x - cx >= 0) {
			return 1;
		}

		if (a.x - cx === 0 && b.x - cx === 0) {
			if (a.y - cy >= 0 || b.y - cy >= 0) {
				return a.y > b.y ? 1 : -1;
			}

			return b.y > a.y ? 1 : -1;
		}

		// Compute the cross product of vectors (center -> a) * (center -> b)
		var det = (a.x - cx) * -(b.y - cy) - (b.x - cx) * -(a.y - cy);

		if (det < 0) {
			return -1;
		}

		if (det > 0) {
			return 1;
		}

		/*
		 * Points a and b are on the same line from the center
		 * Check which point is closer to the center
		 */
		var d1 = (a.x - cx) * (a.x - cx) + (a.y - cy) * (a.y - cy);
		var d2 = (b.x - cx) * (b.x - cx) + (b.y - cy) * (b.y - cy);

		return d1 > d2 ? -1 : 1;
	};

	return points.sort(sort);
}

function uniq(values) {
	return [...new Map(values.map((v) => [JSON.stringify(v), v])).values()];
}
Run Pen

External CSS

This Pen doesn't use any external CSS resources.

External JavaScript

  1. https://cdn.jsdelivr.net/npm/phaser@3.60.0-beta.12/dist/phaser.js
  2. https://cdn.jsdelivr.net/npm/@samme/colors@1.2.0
  3. https://cdn.jsdelivr.net/npm/@mikewesthad/dungeon@2.0.1
  4. https://cdn.jsdelivr.net/npm/simplify-js@1.2.4
  5. https://cdn.jsdelivr.net/npm/tweakpane@3.1.0