Case Study 2: Crypts of Pascalia — The Dungeon Map as a Graph with Pathfinding
The Scenario
The player of Crypts of Pascalia finds themselves in the Entrance of a dungeon with 8 rooms. Each room connects to others via corridors of varying danger levels. The player's goal: find the safest path to the Exit.
This is a graph problem. Rooms are vertices. Corridors are weighted edges (danger level as weight). Finding the safest path is Dijkstra's shortest-path problem.
The Dungeon Layout
Entrance(0) --2-- Great Hall(1) --3-- Armory(2)
| |
4 5
| |
Library(3) --2-- Crypt(4)
| |
6 8
| |
Treasury(5) Dragon Lair(6)
| |
3 1
| |
+---- Exit(7) -------+
Implementation
program DungeonMap;
uses
SysUtils;
const
MAX_V = 20;
INF = MaxInt;
type
TGraph = record
VCount: Integer;
Labels: array[0..MAX_V-1] of string[20];
Matrix: array[0..MAX_V-1, 0..MAX_V-1] of Integer;
end;
procedure InitGraph(var G: TGraph; N: Integer);
var
I, J: Integer;
begin
G.VCount := N;
for I := 0 to N - 1 do
for J := 0 to N - 1 do
G.Matrix[I][J] := 0;
end;
procedure AddEdge(var G: TGraph; U, V, W: Integer);
begin
G.Matrix[U][V] := W;
G.Matrix[V][U] := W; { Undirected }
end;
procedure BuildDungeon(var G: TGraph);
begin
InitGraph(G, 8);
G.Labels[0] := 'Entrance';
G.Labels[1] := 'Great Hall';
G.Labels[2] := 'Armory';
G.Labels[3] := 'Library';
G.Labels[4] := 'Crypt';
G.Labels[5] := 'Treasury';
G.Labels[6] := 'Dragon Lair';
G.Labels[7] := 'Exit';
AddEdge(G, 0, 1, 2); { Entrance - Great Hall }
AddEdge(G, 1, 2, 3); { Great Hall - Armory }
AddEdge(G, 1, 3, 4); { Great Hall - Library }
AddEdge(G, 2, 4, 5); { Armory - Crypt }
AddEdge(G, 3, 4, 2); { Library - Crypt }
AddEdge(G, 3, 5, 6); { Library - Treasury }
AddEdge(G, 4, 6, 8); { Crypt - Dragon Lair }
AddEdge(G, 5, 7, 3); { Treasury - Exit }
AddEdge(G, 6, 7, 1); { Dragon Lair - Exit }
end;
{ --- DFS: Explore reachable rooms --- }
procedure DFSVisit(const G: TGraph; V: Integer;
var Visited: array of Boolean;
var Order: array of Integer;
var Count: Integer);
var
W: Integer;
begin
Visited[V] := True;
Order[Count] := V;
Inc(Count);
for W := 0 to G.VCount - 1 do
if (G.Matrix[V][W] > 0) and (not Visited[W]) then
DFSVisit(G, W, Visited, Order, Count);
end;
{ --- BFS: Find shortest path (fewest rooms) --- }
procedure BFS(const G: TGraph; Start: Integer;
var Dist: array of Integer;
var Prev: array of Integer);
var
Visited: array[0..MAX_V-1] of Boolean;
Queue: array[0..MAX_V-1] of Integer;
Front, Rear, V, W: Integer;
begin
for V := 0 to G.VCount - 1 do begin
Visited[V] := False;
Dist[V] := -1;
Prev[V] := -1;
end;
Visited[Start] := True;
Dist[Start] := 0;
Front := 0; Rear := 0;
Queue[Rear] := Start; Inc(Rear);
while Front < Rear do begin
V := Queue[Front]; Inc(Front);
for W := 0 to G.VCount - 1 do
if (G.Matrix[V][W] > 0) and (not Visited[W]) then begin
Visited[W] := True;
Dist[W] := Dist[V] + 1;
Prev[W] := V;
Queue[Rear] := W; Inc(Rear);
end;
end;
end;
{ --- Dijkstra: Find safest path (minimum danger) --- }
procedure Dijkstra(const G: TGraph; Source: Integer;
var Dist: array of Integer;
var Prev: array of Integer);
var
Visited: array[0..MAX_V-1] of Boolean;
V, U, W, MinDist, NewDist: Integer;
begin
for V := 0 to G.VCount - 1 do begin
Dist[V] := INF;
Prev[V] := -1;
Visited[V] := False;
end;
Dist[Source] := 0;
for V := 0 to G.VCount - 1 do begin
U := -1; MinDist := INF;
for W := 0 to G.VCount - 1 do
if (not Visited[W]) and (Dist[W] < MinDist) then begin
MinDist := Dist[W]; U := W;
end;
if U = -1 then Break;
Visited[U] := True;
for W := 0 to G.VCount - 1 do
if (G.Matrix[U][W] > 0) and (not Visited[W]) then begin
NewDist := Dist[U] + G.Matrix[U][W];
if NewDist < Dist[W] then begin
Dist[W] := NewDist;
Prev[W] := U;
end;
end;
end;
end;
{ --- Path reconstruction --- }
procedure PrintPath(const G: TGraph; const Prev: array of Integer;
Target: Integer);
begin
if Prev[Target] <> -1 then begin
PrintPath(G, Prev, Prev[Target]);
Write(' -> ');
end;
Write(G.Labels[Target]);
end;
{ === MAIN === }
var
Dungeon: TGraph;
Dist: array[0..MAX_V-1] of Integer;
Prev: array[0..MAX_V-1] of Integer;
Visited: array[0..MAX_V-1] of Boolean;
Order: array[0..MAX_V-1] of Integer;
Count, I: Integer;
begin
WriteLn('=== Crypts of Pascalia: Dungeon Map ===');
WriteLn;
BuildDungeon(Dungeon);
{ DFS exploration }
WriteLn('--- DFS Exploration from Entrance ---');
for I := 0 to MAX_V - 1 do Visited[I] := False;
Count := 0;
DFSVisit(Dungeon, 0, Visited, Order, Count);
Write(' Rooms explored: ');
for I := 0 to Count - 1 do begin
Write(Dungeon.Labels[Order[I]]);
if I < Count - 1 then Write(', ');
end;
WriteLn;
WriteLn(' All ', Count, ' rooms are reachable!');
WriteLn;
{ BFS shortest path (fewest rooms) }
WriteLn('--- BFS: Shortest Path (fewest rooms) ---');
BFS(Dungeon, 0, Dist, Prev);
Write(' Entrance to Exit: ');
PrintPath(Dungeon, Prev, 7);
WriteLn;
WriteLn(' Rooms traversed: ', Dist[7]);
WriteLn;
{ Dijkstra safest path (minimum danger) }
WriteLn('--- Dijkstra: Safest Path (minimum danger) ---');
Dijkstra(Dungeon, 0, Dist, Prev);
Write(' Entrance to Exit: ');
PrintPath(Dungeon, Prev, 7);
WriteLn;
WriteLn(' Total danger: ', Dist[7]);
WriteLn;
{ Show all distances from entrance }
WriteLn('--- Danger Levels from Entrance ---');
for I := 0 to Dungeon.VCount - 1 do
if Dist[I] < INF then
WriteLn(' ', Dungeon.Labels[I]:15, ': ', Dist[I])
else
WriteLn(' ', Dungeon.Labels[I]:15, ': unreachable');
WriteLn;
{ Comparing paths }
WriteLn('--- Path Comparison ---');
WriteLn(' Via Treasury (safe): Entrance->Great Hall->Library->Treasury->Exit');
WriteLn(' Danger: 2 + 4 + 6 + 3 = 15');
WriteLn(' Via Dragon (dangerous): Entrance->Great Hall->Library->Crypt->Dragon Lair->Exit');
WriteLn(' Danger: 2 + 4 + 2 + 8 + 1 = 17');
WriteLn(' Dijkstra finds the safest route automatically!');
end.
Key Insights
- DFS confirms that all rooms are reachable — the dungeon is connected.
- BFS finds the path with the fewest rooms (but ignores danger).
- Dijkstra finds the path with the minimum total danger — the safest route.
The player would choose the Dijkstra path in practice: it minimizes total danger. But a speedrunner might prefer the BFS path: fewest rooms means fastest completion.
Discussion Questions
- What if the player wants to visit the Treasury (for loot) on the way to the Exit? How would you modify the pathfinding?
- If the Dragon Lair gives a powerful weapon that reduces all subsequent danger by half, how would you model this?
- How would you detect if removing a single room would disconnect the dungeon (making the Exit unreachable)?
- How would you extend this to a dungeon with 1000 rooms? What representation and algorithm changes would be needed?