kerboul
45b37f9357
- Replace Manhattan distance with BFS distances (actual maze path length) - Switch from NN to direct sequence genome (what YouTube Shorts actually use) - Mutation-only GA (crossover breaks positional maze paths) - Two-rate mutation: low rate before best-step (preserve prefix), high after (explore tail) - Auto-seed selection finds maze with short BFS path - Default maze 15x15, cell_size=36, max_steps=150 - Typically converges in 5-15 generations
148 lines
4.8 KiB
Python
148 lines
4.8 KiB
Python
import numpy as np
|
|
import random
|
|
from collections import deque
|
|
|
|
NORTH, SOUTH, EAST, WEST = 0, 1, 2, 3
|
|
_DX = [0, 0, 1, -1] # col delta for N,S,E,W
|
|
_DY = [-1, 1, 0, 0] # row delta
|
|
_OPP = [1, 0, 3, 2] # opposite direction
|
|
|
|
|
|
def generate(rows: int, cols: int, seed: int | None = None) -> np.ndarray:
|
|
rng = random.Random(seed)
|
|
grid = np.full((rows, cols), 0b1111, dtype=np.uint8)
|
|
visited = np.zeros((rows, cols), dtype=bool)
|
|
|
|
start_r, start_c = 0, 0
|
|
visited[start_r, start_c] = True
|
|
stack = [(start_r, start_c)]
|
|
|
|
while stack:
|
|
row, col = stack[-1]
|
|
directions = [NORTH, SOUTH, EAST, WEST]
|
|
rng.shuffle(directions)
|
|
|
|
moved = False
|
|
for d in directions:
|
|
nr = row + _DY[d]
|
|
nc = col + _DX[d]
|
|
if 0 <= nr < rows and 0 <= nc < cols and not visited[nr, nc]:
|
|
# Carve passage: clear wall bit on current cell
|
|
grid[row, col] &= (~(1 << d)) & 0xFF
|
|
# Clear opposite wall bit on neighbour
|
|
grid[nr, nc] &= (~(1 << _OPP[d])) & 0xFF
|
|
visited[nr, nc] = True
|
|
stack.append((nr, nc))
|
|
moved = True
|
|
break
|
|
|
|
if not moved:
|
|
stack.pop()
|
|
|
|
return grid
|
|
|
|
|
|
def find_short_seed(rows: int, cols: int, max_ratio: float = 6.5, tries: int = 200) -> tuple[int, np.ndarray, np.ndarray]:
|
|
"""Return (seed, grid, bfs_dist) with a short goal path.
|
|
Tries up to `tries` seeds, picks the one whose BFS path < rows*cols/max_ratio.
|
|
Falls back to the best found if none qualifies.
|
|
"""
|
|
target = int(rows * cols / max_ratio)
|
|
best = None
|
|
for seed in range(tries):
|
|
grid = generate(rows, cols, seed=seed)
|
|
bfs = bfs_distances(grid, rows - 1, cols - 1)
|
|
path_len = int(bfs[0, 0])
|
|
if best is None or path_len < best[0]:
|
|
best = (path_len, seed, grid, bfs)
|
|
if path_len <= target:
|
|
return seed, grid, bfs
|
|
_, seed, grid, bfs = best
|
|
return seed, grid, bfs
|
|
|
|
|
|
def bfs_distances(grid: np.ndarray, goal_row: int, goal_col: int) -> np.ndarray:
|
|
"""BFS distance from every cell to (goal_row, goal_col) through passable walls.
|
|
Returns int array shape (rows, cols); unreachable cells = -1.
|
|
"""
|
|
rows, cols = grid.shape
|
|
dist = np.full((rows, cols), -1, dtype=np.int32)
|
|
dist[goal_row, goal_col] = 0
|
|
q = deque([(goal_row, goal_col)])
|
|
while q:
|
|
r, c = q.popleft()
|
|
for d in range(4):
|
|
if is_passable(grid, r, c, d):
|
|
nr, nc = r + _DY[d], c + _DX[d]
|
|
if 0 <= nr < rows and 0 <= nc < cols and dist[nr, nc] == -1:
|
|
dist[nr, nc] = dist[r, c] + 1
|
|
q.append((nr, nc))
|
|
return dist
|
|
|
|
|
|
def get_walls(grid: np.ndarray, row: int, col: int) -> tuple[bool, bool, bool, bool]:
|
|
cell = int(grid[row, col])
|
|
wall_n = float((cell >> NORTH) & 1)
|
|
wall_s = float((cell >> SOUTH) & 1)
|
|
wall_e = float((cell >> EAST) & 1)
|
|
wall_w = float((cell >> WEST) & 1)
|
|
return (wall_n, wall_s, wall_e, wall_w)
|
|
|
|
|
|
def is_passable(grid: np.ndarray, row: int, col: int, direction: int) -> bool:
|
|
cell = int(grid[row, col])
|
|
return not bool((cell >> direction) & 1)
|
|
|
|
|
|
def render_static(grid: np.ndarray, cfg) -> 'pygame.Surface':
|
|
import pygame
|
|
|
|
rows, cols = grid.shape
|
|
cell_size = getattr(cfg, 'cell_size', 32)
|
|
wall_thickness = getattr(cfg, 'wall_thickness', 2)
|
|
|
|
width = cols * cell_size
|
|
height = rows * cell_size
|
|
|
|
surface = pygame.Surface((width, height))
|
|
surface.fill((15, 15, 20))
|
|
|
|
wall_color = (40, 40, 50)
|
|
t = wall_thickness
|
|
|
|
for row in range(rows):
|
|
for col in range(cols):
|
|
x = col * cell_size
|
|
y = row * cell_size
|
|
cell = int(grid[row, col])
|
|
|
|
# North wall
|
|
if (cell >> NORTH) & 1:
|
|
pygame.draw.rect(surface, wall_color, (x, y, cell_size, t))
|
|
|
|
# South wall
|
|
if (cell >> SOUTH) & 1:
|
|
pygame.draw.rect(surface, wall_color, (x, y + cell_size - t, cell_size, t))
|
|
|
|
# East wall
|
|
if (cell >> EAST) & 1:
|
|
pygame.draw.rect(surface, wall_color, (x + cell_size - t, y, t, cell_size))
|
|
|
|
# West wall
|
|
if (cell >> WEST) & 1:
|
|
pygame.draw.rect(surface, wall_color, (x, y, t, cell_size))
|
|
|
|
# Start cell (0, 0): small cyan circle
|
|
start_cx = cell_size // 2
|
|
start_cy = cell_size // 2
|
|
start_radius = max(2, cell_size // 6)
|
|
pygame.draw.circle(surface, (0, 220, 220), (start_cx, start_cy), start_radius)
|
|
|
|
# Goal cell (rows-1, cols-1): green filled circle
|
|
goal_x = (cols - 1) * cell_size + cell_size // 2
|
|
goal_y = (rows - 1) * cell_size + cell_size // 2
|
|
goal_radius = max(3, cell_size // 4)
|
|
pygame.draw.circle(surface, (0, 200, 80), (goal_x, goal_y), goal_radius)
|
|
|
|
return surface
|