Skip to content
Computational Lab.

Raycasting Shadows

Every lit cell is a ray that made it.

Intermediate / raycasting / geometry / occlusion

A light carries with your pointer; every floor cell is lit only if a ray-marched path from the light survives the walls. Each ray is a cell-by-cell grid traversal, and the counters show exactly how many were cast to build the frame.

Tagged: DDA, visibility, occlusion, grid traversal

Live simulation

Move the pointer to carry the light; shadows are marched ray by ray.

Speed

Move the pointer to carry the light; shadows are marched ray by ray.

Mathematics

A floor cell is visible from a light exactly when the open segment between them crosses no wall cell. Marching each ray cell-by-cell with the Amanatides-Woo grid traversal (DDA) makes visibility a discrete, countable computation - no floating shadows, just rays that made it.

DDA stepping: advance to the next vertical or horizontal grid line, whichever is nearer in t

blocked when any traversed cell is a wall before the target

light range: cells beyond the radius are culled before marching

The DDA visit order is exact - it touches precisely the cells the geometric ray passes through, so wall detection has no sampling artifacts. The counters (rays cast, cells lit) turn the pretty picture into an auditable cost: the whole frame is a few thousand ray marches.

How it works

The wall layout is the seeded grid from the pathfinding experiments; the light follows the pointer, re-marching every visible cell within range on each move. Walls themselves render dark; lit floor cells glow softly.

Park the light inside a corridor and the shadow boundary is razor sharp: a cell is either reached or it is not - binary visibility, by construction.

Implementation

src/engine/experiments/raycast-shadows.ts · 200 lines · the module running above

TypeScript · fixed-timestep engine

1import { BaseExperiment } from "../core/base-experiment";
2import type { ParameterDef, PointerState, ThemeColors } from "../core/types";
3
4/**
5 * 2-D raycasting shadows: a light follows the pointer, and every floor cell
6 * casts a shadow if any wall cell blocks the ray between it and the light.
7 * Rays are marched cell-by-cell with a DDA walk over the same walled-grid
8 * structure the pathfinding experiments use.
9 */
10export class RaycastShadowsExperiment extends BaseExperiment {
11 readonly id = "raycast-shadows";
12
13 private n = 56;
14 private cell = 0;
15 private offsetX = 0;
16 private offsetY = 0;
17 private walls = new Uint8Array(0);
18 private lit = new Uint8Array(0);
19 private light = { x: 0.5, y: 0.5, set: false };
20 private litCount = 0;
21 private raysCast = 0;
22
23 protected params(): ParameterDef[] {
24 return [
25 { key: "density", label: "Wall density", min: 5, max: 30, step: 1, defaultValue: 12, unit: "%" },
26 { key: "radius", label: "Light range", min: 6, max: 50, step: 2, defaultValue: 28, unit: "cells" },
27 {
28 key: "regen",
29 label: "Walls",
30 options: [
31 { value: "keep", label: "Keep" },
32 { value: "regenerate", label: "Regenerate" },
33 ],
34 defaultValue: "keep",
35 },
36 ];
37 }
38
39 protected onReset(): void {
40 this.n = 56;
41 this.cell = Math.min(this.width, this.height) / this.n;
42 this.offsetX = Math.floor((this.width - this.cell * this.n) / 2);
43 this.offsetY = Math.floor((this.height - this.cell * this.n) / 2);
44 this.walls = new Uint8Array(this.n * this.n);
45 const density = this.num("density") / 100;
46 for (let i = 0; i < this.walls.length; i++) {
47 this.walls[i] = this.rng() < density ? 1 : 0;
48 }
49 // Light starts centered in a clear cell.
50 this.light = { x: this.n / 2, y: this.n / 2, set: false };
51 this.walls[this.clearNear(Math.floor(this.n / 2), Math.floor(this.n / 2))] = 0;
52 this.computeLight();
53 }
54
55 private clearNear(x: number, y: number): number {
56 for (let r = 0; r < 6; r++) {
57 for (let dy = -r; dy <= r; dy++) {
58 for (let dx = -r; dx <= r; dx++) {
59 const nx = x + dx;
60 const ny = y + dy;
61 if (nx > 0 && ny > 0 && nx < this.n - 1 && ny < this.n - 1 && !this.walls[ny * this.n + nx]) {
62 return ny * this.n + nx;
63 }
64 }
65 }
66 }
67 return y * this.n + x;
68 }
69
70 protected onParameterChange(key: string): void {
71 if (key === "density") this.reset();
72 else if (key === "regen") {
73 const value = this.str("regen");
74 this.setInternalValue("regen", "keep");
75 if (value === "regenerate") this.reset();
76 }
77 }
78
79 protected onUpdate(): void {}
80
81 resize(width: number, height: number): void {
82 this.width = width;
83 this.height = height;
84 this.reset();
85 }
86
87 onPointer(state: PointerState): void {
88 if (!state.inside) return;
89 const gx = (state.x - this.offsetX) / this.cell;
90 const gy = (state.y - this.offsetY) / this.cell;
91 if (gx < 0 || gy < 0 || gx >= this.n || gy >= this.n) return;
92 if (!this.walls[Math.floor(gy) * this.n + Math.floor(gx)]) {
93 this.light = { x: gx, y: gy, set: true };
94 this.computeLight();
95 }
96 }
97
98 /** March a ray from (x0,y0) to (x1,y1) cell by cell (Amanatides-Woo DDA). */
99 private rayBlocked(x0: number, y0: number, x1: number, y1: number): boolean {
100 let cx = Math.floor(x0);
101 let cy = Math.floor(y0);
102 const tx = Math.floor(x1);
103 const ty = Math.floor(y1);
104 const dx = x1 - x0;
105 const dy = y1 - y0;
106 const stepX = dx > 0 ? 1 : -1;
107 const stepY = dy > 0 ? 1 : -1;
108 let tMaxX = dx !== 0 ? ((cx + (dx > 0 ? 1 : 0) - x0) / dx) : Infinity;
109 let tMaxY = dy !== 0 ? ((cy + (dy > 0 ? 1 : 0) - y0) / dy) : Infinity;
110 const tDeltaX = dx !== 0 ? Math.abs(1 / dx) : Infinity;
111 const tDeltaY = dy !== 0 ? Math.abs(1 / dy) : Infinity;
112 let guard = 0;
113 while ((cx !== tx || cy !== ty) && guard++ < this.n * 3) {
114 if (tMaxX < tMaxY) {
115 cx += stepX;
116 tMaxX += tDeltaX;
117 } else {
118 cy += stepY;
119 tMaxY += tDeltaY;
120 }
121 if (cx === tx && cy === ty) break;
122 if (cx < 0 || cy < 0 || cx >= this.n || cy >= this.n) return true;
123 if (this.walls[cy * this.n + cx]) return true;
124 }
125 return false;
126 }
127
128 private computeLight(): void {
129 this.lit = new Uint8Array(this.n * this.n);
130 this.litCount = 0;
131 this.raysCast = 0;
132 const lx = this.light.x;
133 const ly = this.light.y;
134 const radius = this.num("radius");
135 const minX = Math.max(0, Math.floor(lx - radius));
136 const maxX = Math.min(this.n - 1, Math.ceil(lx + radius));
137 const minY = Math.max(0, Math.floor(ly - radius));
138 const maxY = Math.min(this.n - 1, Math.ceil(ly + radius));
139 for (let y = minY; y <= maxY; y++) {
140 for (let x = minX; x <= maxX; x++) {
141 const i = y * this.n + x;
142 if (this.walls[i]) continue;
143 const dist = Math.hypot(x - lx, y - ly);
144 if (dist > radius) continue;
145 this.raysCast += 1;
146 if (!this.rayBlocked(lx, ly, x + 0.5, y + 0.5)) {
147 this.lit[i] = 1;
148 this.litCount += 1;
149 }
150 }
151 }
152 }
153
154 render(ctx: CanvasRenderingContext2D, theme: ThemeColors): void {
155 ctx.fillStyle = theme.bg;
156 ctx.fillRect(0, 0, this.width, this.height);
157 for (let y = 0; y < this.n; y++) {
158 for (let x = 0; x < this.n; x++) {
159 const i = y * this.n + x;
160 const px = this.offsetX + x * this.cell;
161 const py = this.offsetY + y * this.cell;
162 if (this.walls[i]) {
163 ctx.fillStyle = theme.fgTertiary;
164 ctx.fillRect(px, py, this.cell - 1, this.cell - 1);
165 } else {
166 ctx.fillStyle = this.lit[i] ? theme.raised : theme.bg;
167 ctx.fillRect(px, py, this.cell - 1, this.cell - 1);
168 if (this.lit[i]) {
169 ctx.fillStyle = theme.accent;
170 ctx.globalAlpha = 0.12;
171 ctx.fillRect(px, py, this.cell - 1, this.cell - 1);
172 ctx.globalAlpha = 1;
173 }
174 }
175 }
176 }
177 ctx.fillStyle = theme.accent;
178 ctx.beginPath();
179 ctx.arc(this.offsetX + this.light.x * this.cell, this.offsetY + this.light.y * this.cell, 5, 0, Math.PI * 2);
180 ctx.fill();
181 }
182
183 getMetrics() {
184 return {
185 litCells: this.litCount.toLocaleString("en-US"),
186 raysCast: this.raysCast.toLocaleString("en-US"),
187 range: `${this.num("radius")} cells`,
188 grid: `${this.n} x ${this.n}`,
189 };
190 }
191
192 describe(): string {
193 return `A light at (${this.light.x.toFixed(0)}, ${this.light.y.toFixed(0)}) casts ${this.raysCast.toLocaleString("en-US")} rays; ${this.litCount.toLocaleString("en-US")} floor cells are lit, the rest hide behind walls. Move the pointer to carry the light.`;
194 }
195
196 entities(): number {
197 return this.n * this.n;
198 }
199}
200

Performance

Time per tick
O(range^2) ray marches per frame, each O(ray length)
Space
One lit-flag grid
Notes
Lower the range slider and the cost drops quadratically - watch the rays-cast counter respond.

Live numbers (FPS, frame time, steps per second, microseconds per step, entity count) are in the performance overlay on the simulation above: the pulse icon in its top-right corner.