1import { describe, it } from "@effect/vitest"
2import { Data, Graph, Option, type Types } from "effect"
3import { AssertionError } from "node:assert"
4
5// TODO: Add more terrains
6const terrains = {
7 simple: `
8 ##############################
9 #.........#......#...........#
10 #...####.#..~~~~##..^^^^^....#
11 #...####....~~~~....^^^^^....#
12 #...........~~~~....^^^^^....#
13 #...........~~~~##...........#
14 #...MMMM.........#...........#
15 #...MMMM.........#...........#
16 #...MMMM.........#...........#
17 #................#...........#
18 #................#...........#
19 #...^^^^^....####....~~~~....#
20 #...^^^^^....####....~~~~....#
21 #................#...........#
22 ##############################
23 `
24} as const
25
26describe("Dijkstra", () => {
27 it("should find paths using Dijkstra algorithm", () => {
28 const parsed = parseTerrain(terrains.simple)
29 const result = Graph.dijkstra(parsed.graph, {
30 source: parsed.nodes.get("1:1")!,
31 target: parsed.nodes.get("28:13")!,
32 cost: (weight: number) => weight
33 })
34
35 assertPath(parsed, result, "1:1;↓↓↓→→→→→→→→→→→→→→→→→↓↓↓↓↓↓↓↓↓→→→→→→→→→→")
36 })
37})
38
39describe("Bellman-Ford", () => {
40 it("should find paths using Bellman-Ford algorithm", () => {
41 const parsed = parseTerrain(terrains.simple)
42 const result = Graph.bellmanFord(parsed.graph, {
43 source: parsed.nodes.get("1:1")!,
44 target: parsed.nodes.get("28:13")!,
45 cost: (weight: number) => weight
46 })
47
48 assertPath(parsed, result, "1:1;→→→→→→→↓↓→→→→→→→→→→→↓↓→→→→→→→→→↓↓↓↓↓↓↓↓")
49 })
50})
51
52describe("A*", () => {
53 it("should find paths using A* algorithm", () => {
54 const parsed = parseTerrain(terrains.simple)
55 const result = Graph.astar(parsed.graph, {
56 source: parsed.nodes.get("1:1")!,
57 target: parsed.nodes.get("28:13")!,
58 cost: (weight: number) => weight,
59 // Manhattan distance heuristic
60 heuristic: (sourceNodeData: TerrainNode, targetNodeData: TerrainNode) =>
61 Math.abs(targetNodeData.x - sourceNodeData.x) + Math.abs(targetNodeData.y - sourceNodeData.y)
62 })
63
64 assertPath(parsed, result, "1:1;↓↓↓↓→→→→→→→↓→→→→→→→↑↑→→→↓↓↓↓↓↓↓↓↓→→→→→→→→→→")
65 })
66})
67
68// =============================================================================
69// Assertion Helpers
70// =============================================================================
71
72/**
73 * Assert that the result path matches the expected path.
74 */
75const assertPath = (
76 terrain: Terrain,
77 actual: Option.Option<Graph.PathResult<number>>,
78 sequence: Sequence
79) => {
80 const derived = sequenceFromPath(terrain, actual)
81 if (derived !== sequence) {
82 let message = "Path finding result did not match the expected sequence"
83 message += `\n`
84 message += `\nExpected: ${sequence}`
85 message += `\nActual: ${derived}`
86 message += `\n`
87 message += `\nExpected Path:`
88 message += `\n${printSolution(terrain, pathFromSequence(terrain, sequence))}`
89 message += `\n`
90 message += `\nActual Path:`
91 message += `\n${printSolution(terrain, Option.getOrUndefined(actual))}`
92
93 throw new AssertionError({ message, stackStartFn: assertPath })
94 }
95}
96
97type Sequence = `${number}:${number};${string}`
98
99/**
100 * Make a path from a sequence of moves.
101 */
102const pathFromSequence = (
103 terrain: Terrain,
104 sequence: Sequence
105): Graph.PathResult<number> => {
106 const [start, rest] = sequence.split(";") as [`${number}:${number}`, string]
107 if (!terrain.nodes.has(start)) {
108 throw new Error(`Start location ${start} not found in terrain`)
109 }
110
111 const index = terrain.nodes.get(start)!
112 const output: Types.Mutable<Graph.PathResult<number>> = {
113 distance: 0,
114 costs: [],
115 edges: [],
116 path: [index]
117 }
118
119 let [x, y] = start.split(":").map(Number) as [number, number]
120 for (const location of rest.split("")) {
121 if (location === "↓") {
122 y++
123 } else if (location === "↑") {
124 y--
125 } else if (location === "←") {
126 x--
127 } else if (location === "→") {
128 x++
129 } else {
130 throw new Error(`Invalid move ${location} in sequence ${sequence}`)
131 }
132
133 if (!terrain.nodes.has(`${x}:${y}`)) {
134 continue
135 }
136
137 const index = terrain.nodes.get(`${x}:${y}`)!
138 const node = Graph.getNode(terrain.graph, index).pipe(
139 Option.getOrThrowWith(() => new Error(`Location ${location} not found in terrain`))
140 )
141
142 output.distance += node.weight
143 output.costs.push(node.weight)
144 const previousIndex = output.path[output.path.length - 1]
145 const edge = Graph.edgesBetween(terrain.graph, previousIndex, index)[0]
146 if (edge === undefined) {
147 throw new Error(`No edge from ${previousIndex} to ${index}`)
148 }
149 output.edges.push(edge)
150 output.path.push(index)
151 }
152
153 return output
154}
155
156/**
157 * Derive a sequence of moves from a path.
158 */
159const sequenceFromPath = (
160 terrain: Terrain,
161 path: Option.Option<Graph.PathResult<number>>
162): Sequence | undefined => {
163 if (Option.isNone(path) || path.value.path.length === 0) {
164 return undefined
165 }
166
167 const pathValue = path.value
168
169 const sequence = []
170 const start = terrain.coordinates.get(pathValue.path[0])!
171 let previous = Graph.getNode(terrain.graph, terrain.nodes.get(start)!).pipe(
172 Option.getOrThrowWith(() => new Error(`Start location ${start} not found in terrain`))
173 )
174
175 for (const index of pathValue.path.slice(1)) {
176 const current = Graph.getNode(terrain.graph, index).pipe(
177 Option.getOrThrowWith(() => new Error(`Location ${index} not found in terrain`))
178 )
179
180 if (current.x === previous.x) {
181 if (current.y === previous.y - 1) {
182 sequence.push("↑")
183 } else if (current.y === previous.y + 1) {
184 sequence.push("↓")
185 } else {
186 throw new Error(`Invalid move ${current.x}:${current.y} -> ${previous.x}:${previous.y}`)
187 }
188 } else if (current.y === previous.y) {
189 if (current.x === previous.x - 1) {
190 sequence.push("←")
191 } else if (current.x === previous.x + 1) {
192 sequence.push("→")
193 } else {
194 throw new Error(`Invalid move ${current.x}:${current.y} -> ${previous.x}:${previous.y}`)
195 }
196 }
197
198 previous = current
199 }
200
201 return `${start};${sequence.join("")}`
202}
203
204// =============================================================================
205// Terrain Parser
206// =============================================================================
207
208/**
209 * Represents a node in terrain with its grid coordinates and terrain type.
210 */
211class TerrainNode extends Data.TaggedClass("TerrainNode")<{
212 readonly x: number
213 readonly y: number
214 readonly type: string
215 readonly weight: number
216}> {}
217
218/**
219 * Result of parsing terrain ASCII art into a graph.
220 */
221interface Terrain {
222 readonly graph: Graph.DirectedGraph<TerrainNode, number>
223 readonly grid: Array<Array<string>>
224 readonly width: number
225 readonly height: number
226 readonly nodes: Map<`${number}:${number}`, Graph.NodeIndex>
227 readonly coordinates: Map<Graph.NodeIndex, `${number}:${number}`>
228}
229
230/**
231 * Parse ASCII terrain art into a graph structure suitable for pathfinding.
232 *
233 * Converts a 2D ASCII grid into a directed graph where each walkable cell becomes
234 * a node, and edges connect adjacent walkable cells with weights based on terrain type.
235 */
236const parseTerrain = (ascii: string): Terrain => {
237 const lines = ascii.trim().split("\n").map((line) => line.trim()).filter((line) => line.length > 0)
238 if (lines.length === 0) {
239 throw new Error("Terrain must have at least one line")
240 }
241
242 const width = lines[0].length
243 const height = lines.length
244 // Validate all lines have same width
245 for (const line of lines) {
246 if (line.length !== width) {
247 throw new Error("All terrain lines must have the same width")
248 }
249 }
250
251 const grid = lines.map((line) => line.split(""))
252 const nodes = new Map<`${number}:${number}`, Graph.NodeIndex>()
253 const coordinates = new Map<Graph.NodeIndex, `${number}:${number}`>()
254 const graph = Graph.directed<TerrainNode, number>((mutable) => {
255 // First pass: create all nodes
256 for (let y = 0; y < height; y++) {
257 for (let x = 0; x < width; x++) {
258 const char = lines[y][x]
259 const weight = weights.get(char) ?? 1
260 if (weight === Infinity) {
261 // Skip impassable terrain
262 continue
263 }
264
265 const node = new TerrainNode({ x, y, type: char, weight })
266 const index = Graph.addNode(mutable, node)
267 nodes.set(`${x}:${y}`, index)
268 coordinates.set(index, `${x}:${y}`)
269 }
270 }
271
272 // Second pass: create edges between adjacent walkable cells
273 for (let y = 0; y < height; y++) {
274 for (let x = 0; x < width; x++) {
275 const char = lines[y][x]
276 const weight = weights.get(char) ?? 1
277 if (weight === Infinity) {
278 // Skip impassable terrain
279 continue
280 }
281
282 const node = nodes.get(`${x}:${y}`)
283 if (node === undefined) {
284 continue
285 }
286
287 // Check 4-directional adjacency (up, down, left, right)
288 const directions = [
289 [0, -1], // up
290 [0, 1], // down
291 [-1, 0], // left
292 [1, 0] // right
293 ] as const
294
295 for (const [dx, dy] of directions) {
296 const adjacentX = x + dx
297 const adjacentY = y + dy
298
299 // Check bounds
300 if (adjacentX < 0 || adjacentX >= width || adjacentY < 0 || adjacentY >= height) {
301 continue
302 }
303
304 const adjacentChar = lines[adjacentY][adjacentX]
305 const adjacentWeight = weights.get(adjacentChar) ?? 1
306 if (adjacentWeight === Infinity) {
307 // Skip impassable adjacent terrain
308 continue
309 }
310
311 const adjacentNode = nodes.get(`${adjacentX}:${adjacentY}`)
312 if (adjacentNode !== undefined) {
313 Graph.addEdge(mutable, node, adjacentNode, adjacentWeight)
314 }
315 }
316 }
317 }
318 })
319
320 return {
321 graph,
322 width,
323 height,
324 grid,
325 nodes,
326 coordinates
327 }
328}
329
330/**
331 * Weights for common terrain types.
332 */
333const weights = new Map([
334 ["#", Infinity], // Walls
335 [".", 1], // Open terrain
336 ["~", 3], // Water
337 ["^", 5], // Mountains
338 ["M", 2] // Mud
339])
340
341// =============================================================================
342// Terrain Printer
343// =============================================================================
344
345/**
346 * Print terrain as ASCII art with path overlay.
347 */
348const printSolution = (terrain: Terrain, solution?: Graph.PathResult<number>): string => {
349 // Clone the grid to avoid mutating the original
350 const grid = terrain.grid.map((line) => line.slice())
351 const steps = solution === undefined ? [] : solution.path
352
353 for (const [key, index] of steps.entries()) {
354 const node = Graph.getNode(terrain.graph, index).pipe(
355 Option.getOrThrowWith(() => new Error("Path coordinates outside of terrain"))
356 )
357
358 const marker = key === 0 ? "S" : key === steps.length - 1 ? "E" : "*"
359 grid[node.y][node.x] = marker
360 }
361
362 for (let x = 0; x < terrain.width; x++) {
363 for (let y = 0; y < terrain.height; y++) {
364 const character = grid[y][x]
365 const color = colors.colors.get(character)
366 if (color !== undefined) {
367 grid[y][x] = color + character + colors.reset
368 }
369 }
370 }
371
372 return grid.map((line) => line.join("")).join("\n")
373}
374
375/**
376 * ANSI color codes for terminal output.
377 */
378const ANSI = {
379 Reset: "\x1b[0m",
380 Bright: "\x1b[1m",
381 Dim: "\x1b[2m",
382
383 // Foreground colors
384 Black: "\x1b[30m",
385 Red: "\x1b[31m",
386 Green: "\x1b[32m",
387 Yellow: "\x1b[33m",
388 Blue: "\x1b[34m",
389 Magenta: "\x1b[35m",
390 Cyan: "\x1b[36m",
391 White: "\x1b[37m",
392
393 // Bright foreground colors
394 BrightBlack: "\x1b[90m",
395 BrightRed: "\x1b[91m",
396 BrightGreen: "\x1b[92m",
397 BrightYellow: "\x1b[93m",
398 BrightBlue: "\x1b[94m",
399 BrightMagenta: "\x1b[95m",
400 BrightCyan: "\x1b[96m",
401 BrightWhite: "\x1b[97m",
402
403 // Background colors
404 BgBlack: "\x1b[40m",
405 BgRed: "\x1b[41m",
406 BgGreen: "\x1b[42m",
407 BgYellow: "\x1b[43m",
408 BgBlue: "\x1b[44m",
409 BgMagenta: "\x1b[45m",
410 BgCyan: "\x1b[46m",
411 BgWhite: "\x1b[47m"
412} as const
413
414/**
415 * Default color configuration for common terrain types.
416 */
417const colors = {
418 colors: new Map([
419 ["#", ANSI.BrightBlack], // Walls - dark gray
420 [".", ANSI.White], // Open terrain - white
421 ["~", ANSI.Blue], // Water - blue
422 ["^", ANSI.BrightMagenta], // Mountains - bright magenta
423 ["M", ANSI.Yellow], // Mud - yellow
424 ["S", ANSI.BrightGreen], // Start - bright green
425 ["E", ANSI.BrightRed], // End - bright red
426 ["*", ANSI.BrightYellow] // Path - bright yellow
427 ]),
428 reset: ANSI.Reset
429} as const