Skip to content

Instantly share code, notes, and snippets.

@J-Swift

J-Swift/devenv.nix

Created December 5, 2025 22:28
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save J-Swift/ceb1db348f46ba167948f734ff0fc604 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save J-Swift/ceb1db348f46ba167948f734ff0fc604 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
devenv.nix
{ pkgs, ... }:
{
cachix.enable = false;
languages.python = {
enable = true;
venv.enable = true;
venv.requirements = ''
pillow
numpy
'';
};
scripts.solve-maze.exec = ''
python "$DEVENV_ROOT/solve_maze.py" "$@"
'';
}
Raw
devenv.yaml
inputs:
nixpkgs:
url: github:cachix/devenv-nixpkgs/rolling
Raw
solve_maze.py
#!/usr/bin/env python3
"""
Maze Solver - Finds optimal path from mouse to cheese using A* algorithm.
"""
import heapq
from pathlib import Path
from PIL import Image
import numpy as np
def load_and_process_maze(image_path: str) -> tuple[np.ndarray, Image.Image]:
"""Load maze image and create binary grid (True = walkable, False = wall)."""
img = Image.open(image_path)
img_array = np.array(img)
# Convert to grayscale for wall detection
if len(img_array.shape) == 3:
gray = np.mean(img_array[:, :, :3], axis=2)
else:
gray = img_array.astype(float)
# Threshold: walls are dark (gray lines ~100-150), paths are light (white ~255)
walkable = gray > 180
return walkable, img
def mask_outside_maze(walkable: np.ndarray, bounds: tuple[int, int, int, int], margin: int = 0) -> np.ndarray:
"""Mark everything outside the maze boundary as non-walkable."""
top, bottom, left, right = bounds
h, w = walkable.shape
masked = walkable.copy()
# Mark areas outside the maze as non-walkable (exclude the boundary itself)
masked[:top, :] = False # Above maze
masked[bottom + 1:, :] = False # Below maze
masked[:, :left] = False # Left of maze
masked[:, right + 1:] = False # Right of maze
return masked
def find_colored_region(img_array: np.ndarray, color_check: callable, search_region: tuple) -> tuple[int, int]:
"""Find center of a colored region within a search area."""
y_start, y_end, x_start, x_end = search_region
region = img_array[y_start:y_end, x_start:x_end]
matching_pixels = []
for y in range(region.shape[0]):
for x in range(region.shape[1]):
if color_check(region[y, x]):
matching_pixels.append((y + y_start, x + x_start))
if not matching_pixels:
return None
# Return center of matching region
avg_y = sum(p[0] for p in matching_pixels) // len(matching_pixels)
avg_x = sum(p[1] for p in matching_pixels) // len(matching_pixels)
return (avg_y, avg_x)
def find_mouse(img_array: np.ndarray) -> tuple[int, int]:
"""Find the mouse (gray with pink ear) in the top-left area."""
h, w = img_array.shape[:2]
# Search top-left quadrant for the mouse (gray body)
def is_mouse_gray(pixel):
if len(pixel) < 3:
return False
r, g, b = int(pixel[0]), int(pixel[1]), int(pixel[2])
# Mouse is gray - similar R, G, B values, not too dark, not too light
return 100 < r < 180 and 100 < g < 180 and 100 < b < 180 and abs(r - g) < 30 and abs(g - b) < 30
result = find_colored_region(img_array, is_mouse_gray, (0, h // 3, 0, w // 3))
if result:
return result
# Fallback: find entrance near top-left
return find_maze_entrance_top_left(img_array)
def find_cheese(img_array: np.ndarray) -> tuple[int, int]:
"""Find the cheese (yellow) in the bottom-right area."""
h, w = img_array.shape[:2]
# Search bottom-right quadrant for yellow cheese
def is_yellow(pixel):
if len(pixel) < 3:
return False
r, g, b = pixel[0], pixel[1], pixel[2]
# Yellow has high R and G, low B
return r > 200 and g > 180 and b < 150
result = find_colored_region(img_array, is_yellow, (2 * h // 3, h, 2 * w // 3, w))
if result:
return result
# Fallback: find entrance near bottom-right
return find_maze_entrance_bottom_right(img_array)
def find_maze_bounds(walkable: np.ndarray) -> tuple[int, int, int, int]:
"""Find the bounding box of the maze (the thick border)."""
h, w = walkable.shape
# Find left edge of maze (first column with significant dark pixels)
left = 0
for x in range(w):
dark_count = np.sum(~walkable[:, x])
if dark_count > h * 0.3: # Significant vertical wall
left = x
break
# Find right edge
right = w - 1
for x in range(w - 1, -1, -1):
dark_count = np.sum(~walkable[:, x])
if dark_count > h * 0.3:
right = x
break
# Find top edge
top = 0
for y in range(h):
dark_count = np.sum(~walkable[y, :])
if dark_count > w * 0.3:
top = y
break
# Find bottom edge
bottom = h - 1
for y in range(h - 1, -1, -1):
dark_count = np.sum(~walkable[y, :])
if dark_count > w * 0.3:
bottom = y
break
return top, bottom, left, right
def find_maze_entry_point(walkable: np.ndarray, near_pos: tuple[int, int], bounds: tuple[int, int, int, int], corner: str) -> tuple[int, int]:
"""Find the entry/exit point of the maze nearest to a position, ensuring it's in the main maze area."""
top, bottom, left, right = bounds
h, w = walkable.shape
# Search further inside to avoid isolated edge pixels
margin = 20
if corner == "top_left":
# Search in top-left region, row by row, then column by column
for y in range(top + margin, top + (bottom - top) // 2):
for x in range(left + margin, left + (right - left) // 2):
if walkable[y, x]:
# Verify this is a substantial walkable area (not isolated pixel)
neighbors = sum([
walkable[y-1, x] if y > 0 else 0,
walkable[y+1, x] if y < h-1 else 0,
walkable[y, x-1] if x > 0 else 0,
walkable[y, x+1] if x < w-1 else 0
])
if neighbors >= 2: # At least 2 walkable neighbors
return (y, x)
elif corner == "bottom_right":
# Search in bottom-right region
for y in range(bottom - margin, bottom - (bottom - top) // 2, -1):
for x in range(right - margin, right - (right - left) // 2, -1):
if walkable[y, x]:
neighbors = sum([
walkable[y-1, x] if y > 0 else 0,
walkable[y+1, x] if y < h-1 else 0,
walkable[y, x-1] if x > 0 else 0,
walkable[y, x+1] if x < w-1 else 0
])
if neighbors >= 2:
return (y, x)
return near_pos
def find_maze_entrance_top_left(img_array: np.ndarray) -> tuple[int, int]:
"""Find walkable entrance point near top-left of maze."""
gray = np.mean(img_array[:, :, :3], axis=2) if len(img_array.shape) == 3 else img_array
h, w = gray.shape
# Scan from top-left for first walkable area inside maze bounds
for y in range(50, h // 3):
for x in range(50, w // 3):
if gray[y, x] > 200: # White/walkable
return (y, x)
return (60, 60)
def find_maze_entrance_bottom_right(img_array: np.ndarray) -> tuple[int, int]:
"""Find walkable entrance point near bottom-right of maze."""
gray = np.mean(img_array[:, :, :3], axis=2) if len(img_array.shape) == 3 else img_array
h, w = gray.shape
# Scan from bottom-right for walkable area
for y in range(h - 50, 2 * h // 3, -1):
for x in range(w - 50, 2 * w // 3, -1):
if gray[y, x] > 200: # White/walkable
return (y, x)
return (h - 60, w - 60)
def find_nearest_walkable(walkable: np.ndarray, point: tuple[int, int]) -> tuple[int, int]:
"""Find the nearest walkable cell to a given point."""
y, x = point
h, w = walkable.shape
# Clamp to bounds
y = max(0, min(y, h - 1))
x = max(0, min(x, w - 1))
if walkable[y, x]:
return (y, x)
# BFS to find nearest walkable
for radius in range(1, max(h, w)):
for dy in range(-radius, radius + 1):
for dx in range(-radius, radius + 1):
ny, nx = y + dy, x + dx
if 0 <= ny < h and 0 <= nx < w and walkable[ny, nx]:
return (ny, nx)
return point
def heuristic(a: tuple[int, int], b: tuple[int, int]) -> float:
"""Manhattan distance heuristic for A*."""
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def check_connectivity(walkable: np.ndarray, start: tuple[int, int], goal: tuple[int, int]) -> tuple[bool, int]:
"""Check if start and goal are in the same connected component using BFS."""
from collections import deque
h, w = walkable.shape
visited = set()
queue = deque([start])
visited.add(start)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while queue:
current = queue.popleft()
if current == goal:
return True, len(visited)
for dy, dx in directions:
neighbor = (current[0] + dy, current[1] + dx)
if not (0 <= neighbor[0] < h and 0 <= neighbor[1] < w):
continue
if neighbor in visited:
continue
if not walkable[neighbor[0], neighbor[1]]:
continue
visited.add(neighbor)
queue.append(neighbor)
return False, len(visited)
def astar(walkable: np.ndarray, start: tuple[int, int], goal: tuple[int, int]) -> list[tuple[int, int]]:
"""A* pathfinding algorithm - finds optimal path."""
h, w = walkable.shape
# Priority queue: (f_score, counter, position)
counter = 0
open_set = [(heuristic(start, goal), counter, start)]
came_from = {}
g_score = {start: 0}
# 4-directional movement (can change to 8 for diagonal)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
while open_set:
_, _, current = heapq.heappop(open_set)
if current == goal:
# Reconstruct path
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return path[::-1]
for dy, dx in directions:
neighbor = (current[0] + dy, current[1] + dx)
if not (0 <= neighbor[0] < h and 0 <= neighbor[1] < w):
continue
if not walkable[neighbor[0], neighbor[1]]:
continue
tentative_g = g_score[current] + 1
if neighbor not in g_score or tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
counter += 1
heapq.heappush(open_set, (f_score, counter, neighbor))
return [] # No path found
def draw_path(img: Image.Image, path: list[tuple[int, int]], line_width: int = 3) -> Image.Image:
"""Draw the solution path on the image in red."""
result = img.copy().convert('RGB')
pixels = result.load()
# Draw path with thickness
red = (255, 0, 0)
for y, x in path:
for dy in range(-line_width // 2, line_width // 2 + 1):
for dx in range(-line_width // 2, line_width // 2 + 1):
ny, nx = y + dy, x + dx
if 0 <= ny < result.height and 0 <= nx < result.width:
pixels[nx, ny] = red
return result
def solve_maze(input_path: str, output_path: str = None, debug: bool = False):
"""Main function to solve the maze."""
input_path = Path(input_path)
if output_path is None:
output_path = input_path.parent / f"{input_path.stem}_solved{input_path.suffix}"
print(f"Loading maze from: {input_path}")
walkable, original_img = load_and_process_maze(input_path)
img_array = np.array(original_img)
print(f"Maze dimensions: {walkable.shape[1]}x{walkable.shape[0]}")
# Find maze boundaries
bounds = find_maze_bounds(walkable)
print(f"Maze bounds (top, bottom, left, right): {bounds}")
# Mask out area outside the maze to force pathfinding through the maze
# Use margin=0 to keep paths right at the boundary accessible
walkable = mask_outside_maze(walkable, bounds, margin=0)
# Debug: save walkable grid visualization (after masking)
if debug:
debug_img = Image.fromarray((walkable * 255).astype(np.uint8))
debug_img.save(input_path.parent / "debug_walkable.png")
print("Debug: saved walkable grid to debug_walkable.png")
# Find start (mouse) and end (cheese) positions
mouse_pos = find_mouse(img_array)
cheese_pos = find_cheese(img_array)
print(f"Mouse found at: {mouse_pos}")
print(f"Cheese found at: {cheese_pos}")
# Find maze entry/exit points (inside the maze proper)
start = find_maze_entry_point(walkable, mouse_pos, bounds, "top_left")
goal = find_maze_entry_point(walkable, cheese_pos, bounds, "bottom_right")
print(f"Path start (maze entry): {start}")
print(f"Path goal (maze exit): {goal}")
print(f"Start walkable: {walkable[start[0], start[1]]}")
print(f"Goal walkable: {walkable[goal[0], goal[1]]}")
# Debug: check connectivity
if debug:
connected, visited_count = check_connectivity(walkable, start, goal)
print(f"Debug: Start and goal connected: {connected}, visited {visited_count} cells")
# Find optimal path using A*
print("Finding optimal path using A* algorithm...")
path = astar(walkable, start, goal)
if not path:
print("ERROR: No path found!")
return
print(f"Path found! Length: {len(path)} pixels")
# Draw path on image
result_img = draw_path(original_img, path, line_width=4)
# Save result
result_img.save(output_path)
print(f"Solution saved to: {output_path}")
if __name__ == "__main__":
import sys
if len(sys.argv) < 2:
input_file = "maze.jpg"
else:
input_file = sys.argv[1]
output_file = sys.argv[2] if len(sys.argv) > 2 else None
debug = "--debug" in sys.argv
solve_maze(input_file, output_file, debug=debug)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment