368 lines
12 KiB
Python
368 lines
12 KiB
Python
#!/usr/bin/env python3
|
|
"""Builds a queryable room adjacency graph from .tscn files with BFS pathfinding.
|
|
|
|
Parses all scene files to extract TransitionPiece exits, builds an adjacency
|
|
graph, and provides shortest-path queries between any two rooms.
|
|
|
|
Usage:
|
|
python scripts/build_room_graph.py # print full graph
|
|
python scripts/build_room_graph.py --from kq4_001_beach --to kq4_092_lolottes_throne_room
|
|
|
|
Can also be imported as a module for use by other tools.
|
|
"""
|
|
|
|
import re
|
|
import sys
|
|
from dataclasses import dataclass, field
|
|
from pathlib import Path
|
|
from typing import Optional
|
|
|
|
|
|
@dataclass
|
|
class TransitionInfo:
|
|
"""A single room exit / TransitionPiece."""
|
|
|
|
exit_node_name: str # Node name in source room's scene tree (e.g., "kq4_010_forest_path")
|
|
target_uid: str # UID of destination .tscn file
|
|
appear_at_node: str # Node name in destination room where player appears
|
|
label: str # Human-readable label (e.g., "Forest Path")
|
|
polygon: list[tuple[float, float]] # Polygon vertices relative to transition node position
|
|
position: tuple[float, float] = (0.0, 0.0) # Node position in parent space
|
|
scale: tuple[float, float] = (1.0, 1.0) # Node scale factors
|
|
|
|
def viewport_centroid(self) -> tuple[float, float]:
|
|
"""Compute the polygon centroid transformed to viewport coordinates."""
|
|
if not self.polygon:
|
|
return self.position
|
|
cx = sum(p[0] for p in self.polygon) / len(self.polygon)
|
|
cy = sum(p[1] for p in self.polygon) / len(self.polygon)
|
|
return (
|
|
self.scale[0] * (self.position[0] + cx),
|
|
self.scale[1] * (self.position[1] + cy),
|
|
)
|
|
|
|
|
|
@dataclass
|
|
class RoomInfo:
|
|
"""Metadata for a single room."""
|
|
|
|
name: str # e.g., "kq4_004_ogres_cottage"
|
|
uid: Optional[str] # Scene UID from .tscn header
|
|
path: Path # Absolute path to .tscn file
|
|
transitions: list[TransitionInfo] = field(default_factory=list)
|
|
|
|
|
|
@dataclass(frozen=True)
|
|
class NavigationStep:
|
|
"""One step in a navigation plan (source room → destination room)."""
|
|
|
|
from_room: str # Source room name
|
|
exit_node_name: str # TransitionPiece node name to click on
|
|
to_room: str # Destination room name
|
|
label: str # Human-readable label
|
|
polygon: list[tuple[float, float]]
|
|
position: tuple[float, float] = (0.0, 0.0)
|
|
scale: tuple[float, float] = (1.0, 1.0)
|
|
|
|
def viewport_centroid(self) -> tuple[float, float]:
|
|
"""Compute the polygon centroid transformed to viewport coordinates."""
|
|
if not self.polygon:
|
|
return self.position
|
|
cx = sum(p[0] for p in self.polygon) / len(self.polygon)
|
|
cy = sum(p[1] for p in self.polygon) / len(self.polygon)
|
|
return (
|
|
self.scale[0] * (self.position[0] + cx),
|
|
self.scale[1] * (self.position[1] + cy),
|
|
)
|
|
|
|
|
|
def find_uid_files(root: Path) -> dict[str, Path]:
|
|
"""Build a mapping of UID → file path from all .uid files."""
|
|
uid_map = {}
|
|
for uid_file in root.rglob("*.uid"):
|
|
content = uid_file.read_text().strip()
|
|
if content.startswith("uid://"):
|
|
resource_path = uid_file.with_suffix("")
|
|
uid_map[content] = resource_path
|
|
return uid_map
|
|
|
|
|
|
def parse_transitions(body: str, room_name: str) -> list[TransitionInfo]:
|
|
"""Extract TransitionPiece transitions from a .tscn file body."""
|
|
transitions = []
|
|
|
|
transition_pattern = re.compile(
|
|
r'\[node name="([^"]+)"[^\]]*instance=ExtResource\([^\)]+\)\]\s*\n'
|
|
r"(([^\[]+(?:\n|$))*?)(?=\[|$)",
|
|
re.MULTILINE,
|
|
)
|
|
|
|
for match in transition_pattern.finditer(body):
|
|
node_name = match.group(1)
|
|
body_text = match.group(2)
|
|
|
|
target_match = re.search(r'^target = "([^"]+)"', body_text, re.MULTILINE)
|
|
appear_match = re.search(
|
|
r'^(?:appear_at_node = "([^"]+)"|appear_at_node = &"([^"]+)")',
|
|
body_text,
|
|
re.MULTILINE,
|
|
)
|
|
|
|
if not (target_match and appear_match):
|
|
continue
|
|
|
|
target_uid = target_match.group(1)
|
|
appear_at = appear_match.group(1) or appear_match.group(2)
|
|
|
|
label_match = re.search(r'^label = "([^"]+)"', body_text, re.MULTILINE)
|
|
label = label_match.group(1) if label_match else node_name
|
|
|
|
# Parse position (defaults to 0, 0)
|
|
pos_match = re.search(r"^position\s*=\s*Vector2?\(([^)]+)\)", body_text, re.MULTILINE)
|
|
if pos_match:
|
|
pos_nums = [float(x.strip()) for x in pos_match.group(1).split(",")]
|
|
node_position = (pos_nums[0], pos_nums[1])
|
|
else:
|
|
node_position = (0.0, 0.0)
|
|
|
|
# Parse scale (defaults to 1, 1)
|
|
scale_match = re.search(r"^scale\s*=\s*Vector2?\(([^)]+)\)", body_text, re.MULTILINE)
|
|
if scale_match:
|
|
scale_nums = [float(x.strip()) for x in scale_match.group(1).split(",")]
|
|
node_scale = (scale_nums[0], scale_nums[1])
|
|
else:
|
|
node_scale = (1.0, 1.0)
|
|
|
|
polygon_str_match = re.search(
|
|
r"^polygon = PackedVector2Array\((.+?)\)",
|
|
body_text,
|
|
re.MULTILINE,
|
|
)
|
|
polygon: list[tuple[float, float]] = []
|
|
if polygon_str_match:
|
|
nums = re.findall(r"[-+]?[0-9]*\.?[0-9]+", polygon_str_match.group(1))
|
|
floats = [float(n) for n in nums]
|
|
polygon = [(floats[i], floats[i + 1]) for i in range(0, len(floats), 2)]
|
|
|
|
transitions.append(
|
|
TransitionInfo(
|
|
exit_node_name=node_name,
|
|
target_uid=target_uid,
|
|
appear_at_node=appear_at,
|
|
label=label,
|
|
polygon=polygon,
|
|
position=node_position,
|
|
scale=node_scale,
|
|
)
|
|
)
|
|
|
|
return transitions
|
|
|
|
|
|
def build_graph(scenes_dir: Path) -> dict[str, RoomInfo]:
|
|
"""Parse all room .tscn files and return a dict keyed by room name."""
|
|
scene_files = sorted(scenes_dir.glob("kq4_*/kq4_*.tscn"))
|
|
|
|
graph: dict[str, RoomInfo] = {}
|
|
for sf in scene_files:
|
|
if "placeholder_template" in str(sf):
|
|
continue
|
|
|
|
content = sf.read_text()
|
|
uid_match = re.search(r'\[gd_scene[^\]]*uid="([^"]+)"', content)
|
|
room_uid = uid_match.group(1) if uid_match else None
|
|
|
|
room_name = sf.stem
|
|
transitions = parse_transitions(content, room_name)
|
|
|
|
graph[room_name] = RoomInfo(
|
|
name=room_name,
|
|
uid=room_uid,
|
|
path=sf,
|
|
transitions=transitions,
|
|
)
|
|
|
|
return graph
|
|
|
|
|
|
def _resolve_target_room(trans: TransitionInfo, graph: dict[str, RoomInfo]) -> Optional[str]:
|
|
"""Given a transition and the room graph, find which room it targets."""
|
|
for room_name, room_info in graph.items():
|
|
if room_info.uid == trans.target_uid:
|
|
return room_name
|
|
return None
|
|
|
|
|
|
def find_path(
|
|
graph: dict[str, RoomInfo], start_room: str, end_room: str
|
|
) -> Optional[list[NavigationStep]]:
|
|
"""BFS from start to end. Returns ordered list of steps or None."""
|
|
if start_room not in graph:
|
|
raise ValueError(f"Start room not found in graph: {start_room}")
|
|
if end_room not in graph:
|
|
raise ValueError(f"End room not found in graph: {end_room}")
|
|
|
|
if start_room == end_room:
|
|
return []
|
|
|
|
from collections import deque
|
|
|
|
adj: dict[str, list[tuple[str, TransitionInfo]]] = {}
|
|
for rname, rinfo in graph.items():
|
|
adj[rname] = []
|
|
for t in rinfo.transitions:
|
|
target = _resolve_target_room(t, graph)
|
|
if target:
|
|
adj[rname].append((target, t))
|
|
|
|
visited = {start_room}
|
|
queue = deque([(start_room, [])])
|
|
|
|
while queue:
|
|
current, path_steps = queue.popleft()
|
|
for neighbor, trans in adj.get(current, []):
|
|
if neighbor in visited:
|
|
continue
|
|
|
|
step = NavigationStep(
|
|
from_room=current,
|
|
exit_node_name=trans.exit_node_name,
|
|
to_room=neighbor,
|
|
label=trans.label,
|
|
polygon=trans.polygon,
|
|
position=trans.position,
|
|
scale=trans.scale,
|
|
)
|
|
new_steps = path_steps + [step]
|
|
|
|
if neighbor == end_room:
|
|
return new_steps
|
|
|
|
visited.add(neighbor)
|
|
queue.append((neighbor, new_steps))
|
|
|
|
return None
|
|
|
|
|
|
def get_connected_components(graph: dict[str, RoomInfo]) -> list[set[str]]:
|
|
"""Return list of connected components in the room graph."""
|
|
adj: dict[str, set[str]] = {r: set() for r in graph}
|
|
for rname, rinfo in graph.items():
|
|
for t in rinfo.transitions:
|
|
target = _resolve_target_room(t, graph)
|
|
if target:
|
|
adj[rname].add(target)
|
|
adj[target].add(rname)
|
|
|
|
visited = set()
|
|
components = []
|
|
|
|
for room in graph:
|
|
if room in visited:
|
|
continue
|
|
component = set()
|
|
stack = [room]
|
|
while stack:
|
|
current = stack.pop()
|
|
if current in visited:
|
|
continue
|
|
visited.add(current)
|
|
component.add(current)
|
|
stack.extend(adj[current] - visited)
|
|
components.append(component)
|
|
|
|
return sorted(components, key=len, reverse=True)
|
|
|
|
|
|
def print_graph_summary(graph: dict[str, RoomInfo]) -> None:
|
|
"""Print a human-readable summary of the room graph."""
|
|
total_rooms = len(graph)
|
|
total_exits = sum(len(r.transitions) for r in graph.values())
|
|
components = get_connected_components(graph)
|
|
|
|
print(f"Rooms: {total_rooms}")
|
|
print(f"Total transition exits: {total_exits}")
|
|
print(f"Connected components: {len(components)}")
|
|
|
|
if len(components) > 1:
|
|
for i, comp in enumerate(components):
|
|
print(f" Component {i + 1} ({len(comp)} rooms): {', '.join(sorted(comp)[:6])}{'...' if len(comp) > 6 else ''}")
|
|
else:
|
|
print(" All rooms connected!")
|
|
|
|
|
|
def print_room(graph: dict[str, RoomInfo], room_name: str) -> None:
|
|
"""Print exits for a specific room."""
|
|
if room_name not in graph:
|
|
print(f"Room not found: {room_name}")
|
|
return
|
|
|
|
room = graph[room_name]
|
|
print(f"Room: {room_name} (uid: {room.uid or 'unknown'})")
|
|
print(f" Exits ({len(room.transitions)}):")
|
|
for t in room.transitions:
|
|
target_room = _resolve_target_room(t, graph)
|
|
target_str = target_room or t.target_uid[:12]
|
|
print(f" {t.exit_node_name} → {target_str} [{t.label}] (polygon: {len(t.polygon)} pts)")
|
|
|
|
|
|
def find_and_print_path(
|
|
graph: dict[str, RoomInfo], start_room: str, end_room: str
|
|
) -> None:
|
|
"""Find and print a path between two rooms."""
|
|
steps = find_path(graph, start_room, end_room)
|
|
|
|
if not steps:
|
|
print(f"No path from {start_room} to {end_room}")
|
|
components = get_connected_components(graph)
|
|
for comp in components:
|
|
if start_room in comp:
|
|
print(f" {start_room} is in component with {len(comp)} rooms")
|
|
break
|
|
for comp in components:
|
|
if end_room in comp:
|
|
print(f" {end_room} is in component with {len(comp)} rooms")
|
|
break
|
|
return
|
|
|
|
print(f"Path from {start_room} → {end_room} ({len(steps)} step{'s' if len(steps) != 1 else ''}):")
|
|
for i, step in enumerate(steps):
|
|
coord_str = ""
|
|
cx, cy = step.viewport_centroid()
|
|
coord_str = f" (click at: {cx:.0f}, {cy:.0f})"
|
|
print(
|
|
f" {i + 1}. Click '{step.exit_node_name}' "
|
|
f"in {step.from_room} "
|
|
f"→ {step.to_room} [{step.label}]{coord_str}"
|
|
)
|
|
|
|
|
|
def main() -> None:
|
|
import argparse
|
|
|
|
parser = argparse.ArgumentParser(description="KQ4 room graph builder and BFS pathfinder")
|
|
parser.add_argument("--from", dest="from_room", help="Starting room name (e.g., kq4_001_beach)")
|
|
parser.add_argument("--to", dest="to_room", help="Destination room name")
|
|
parser.add_argument("--room", help="Show exits for a specific room")
|
|
args = parser.parse_args()
|
|
|
|
root = Path(__file__).resolve().parent.parent
|
|
scenes_dir = root / "scenes"
|
|
|
|
if not scenes_dir.exists():
|
|
print(f"ERROR: Scenes directory not found at {scenes_dir}", file=sys.stderr)
|
|
sys.exit(1)
|
|
|
|
graph = build_graph(scenes_dir)
|
|
|
|
if args.room:
|
|
print_room(graph, args.room)
|
|
elif args.from_room and args.to_room:
|
|
find_and_print_path(graph, args.from_room, args.to_room)
|
|
else:
|
|
print_graph_summary(graph)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
main()
|