HTB: Tunnel Madness – 3D Maze Pathfinding

#!/usr/bin/env python3
"""
Parse the 3D maze structure from binary data
"""
import struct
from pathlib import Path

MAZE_SIZE = 20
NODE_SIZE = 24

class MazeNode:
    def __init__(self, data):
        # Unpack the 24-byte node structure
        fields = struct.unpack('11B13x', data)
        
        self.x = fields[0]
        self.y = fields[1]
        self.z = fields[2]
        self.visited = fields[3]
        self.up = fields[4]
        self.down = fields[5]
        self.left = fields[6]
        self.right = fields[7]
        self.forward = fields[8]
        self.backward = fields[9]
        self.flag_char = chr(fields[10]) if 32 <= fields[10] < 127 else '?'
    
    def get_connections(self):
        """Return list of valid moves from this node"""
        moves = []
        if self.up:       moves.append(('up', 0, 1, 0))
        if self.down:     moves.append(('down', 0, -1, 0))
        if self.left:     moves.append(('left', -1, 0, 0))
        if self.right:    moves.append(('right', 1, 0, 0))
        if self.forward:  moves.append(('forward', 0, 0, 1))
        if self.backward: moves.append(('backward', 0, 0, -1))
        return moves
    
    def __repr__(self):
        return f"Node({self.x},{self.y},{self.z}) '{self.flag_char}'"

def load_maze(filename):
    """Load maze from binary file"""
    data = Path(filename).read_bytes()
    
    maze = {}
    offset = 0
    
    for z in range(MAZE_SIZE):
        for y in range(MAZE_SIZE):
            for x in range(MAZE_SIZE):
                node_data = data[offset:offset+NODE_SIZE]
                node = MazeNode(node_data)
                
                # Verify coordinates match expected position
                assert node.x == x and node.y == y and node.z == z, \
                    f"Coordinate mismatch at ({x},{y},{z})"
                
                maze[(x, y, z)] = node
                offset += NODE_SIZE
    
    return maze

# Load the maze
maze = load_maze('maze.bin')
print(f"[+] Loaded {len(maze)} nodes")

# Examine start node
start = maze[(0, 0, 0)]
print(f"[+] Start node: {start}")
print(f"    Available moves: {[m[0] for m in start.get_connections()]}")

# Examine goal node
goal = maze[(19, 19, 19)]
print(f"[+] Goal node: {goal}")

#!/usr/bin/env python3
"""
Solve the 3D maze using BFS and extract the flag
"""
from collections import deque
from parse_maze import load_maze

def bfs_solve(maze, start, goal):
    """
    Find shortest path through maze using BFS
    Returns: list of nodes in path order
    """
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        current, path = queue.popleft()
        
        # Check if we reached the goal
        if current == goal:
            return path
        
        # Get current node
        node = maze[current]
        
        # Try all valid moves
        for move_name, dx, dy, dz in node.get_connections():
            next_pos = (current[0] + dx, current[1] + dy, current[2] + dz)
            
            # Check bounds
            if not all(0 <= c < 20 for c in next_pos):
                continue
            
            # Check if already visited
            if next_pos in visited:
                continue
            
            # Mark as visited and add to queue
            visited.add(next_pos)
            queue.append((next_pos, path + [next_pos]))
    
    return None  # No path found

# Load maze
print("[*] Loading maze...")
maze = load_maze('maze.bin')

# Solve
print("[*] Solving maze with BFS...")
start_pos = (0, 0, 0)
goal_pos = (19, 19, 19)

path = bfs_solve(maze, start_pos, goal_pos)

if path is None:
    print("[!] No path found!")
    exit(1)

print(f"[+] Found path with {len(path)} nodes")

# Extract flag
print("[*] Extracting flag from path...")
flag_chars = []
for pos in path:
    node = maze[pos]
    flag_chars.append(node.flag_char)
    print(f"  {pos} -> '{node.flag_char}'")

flag = ''.join(flag_chars)
print(f"\n[+] FLAG: {flag}")

#!/usr/bin/env python3
"""
Visualize the maze solution path
"""
from parse_maze import load_maze
from solve_maze import bfs_solve
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

# Load and solve
maze = load_maze('maze.bin')
path = bfs_solve(maze, (0, 0, 0), (19, 19, 19))

# Extract coordinates
xs = [pos[0] for pos in path]
ys = [pos[1] for pos in path]
zs = [pos[2] for pos in path]

# Create 3D plot
fig = plt.figure(figsize=(12, 10))
ax = fig.add_subplot(111, projection='3d')

# Plot path
ax.plot(xs, ys, zs, 'b-', linewidth=2, label='Solution Path')

# Mark start and end
ax.scatter([0], [0], [0], c='green', s=200, marker='o', label='Start')
ax.scatter([19], [19], [19], c='red', s=200, marker='*', label='Goal')

# Labels
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_zlabel('Z')
ax.set_title(f'3D Maze Solution Path ({len(path)} nodes)')
ax.legend()

plt.savefig('maze_solution.png', dpi=150)
print("[+] Saved visualization to maze_solution.png")

def bfs(start, goal):
    queue = [start]
    visited = {start}
    
    while queue:
        current = queue.pop(0)  # FIFO: shortest path first
        
        if current == goal:
            return "found!"
        
        for neighbor in current.neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

def dfs(current, goal, visited):
    if current == goal:
        return "found!"
    
    for neighbor in current.neighbors:
        if neighbor not in visited:
            visited.add(neighbor)
            dfs(neighbor, goal, visited)  # Go deep immediately

import heapq

def dijkstra(start, goal):
    pq = [(0, start)]  # (cost, node)
    costs = {start: 0}
    
    while pq:
        current_cost, current = heapq.heappop(pq)
        
        if current == goal:
            return current_cost
        
        for neighbor, edge_cost in current.neighbors:
            new_cost = current_cost + edge_cost
            
            if neighbor not in costs or new_cost < costs[neighbor]:
                costs[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor))

# Google Maps uses variants of Dijkstra/A*
shortest_path = dijkstra(
    start="Home",
    goal="Work",
    weights=lambda road: road.distance + road.traffic_delay
)

# BGP finds paths through internet routers
best_route = shortest_path(
    start=source_router,
    goal=destination_router,
    metric=lambda link: link.latency + link.cost
)

# NPCs pathfind through game world
path = a_star(
    start=enemy.position,
    goal=player.position,
    heuristic=euclidean_distance
)

# Robot navigation using flood fill
def flood_fill(maze):
    # BFS from goal backwards
    distances = bfs(goal, all_cells)
    
    # Robot follows decreasing distances
    while current != goal:
        current = min(neighbors, key=lambda n: distances[n])