Skip to content

Instantly share code, notes, and snippets.

@Reconcyl
Last active September 15, 2018 08:32
Show Gist options
  • Save Reconcyl/ee1dd86019ada4a9a065c278a3f2b21e to your computer and use it in GitHub Desktop.
Save Reconcyl/ee1dd86019ada4a9a065c278a3f2b21e to your computer and use it in GitHub Desktop.
Maze generator
import random
import time
WALL = " "
GAP = "@"
def split(string, width):
for i in range(0, len(string), width):
yield string[i : i+width]
def random_point(width, height):
return (random.randrange(width),
random.randrange(height))
def favored_random(i):
i -= 1
while i and random.randrange(2):
i -= 1
return i
DIRECTIONS = [
( 0, 1),
( 0, -1),
( 1, 0),
(-1, 0)
]
def perp(d):
x, y = d
return (add(d, (y, x)),
d,
add(d, (-y, -x)))
MOORE = [
( 1, 1),
( 1, 0),
( 1, -1),
( 0, -1),
(-1, -1),
(-1, 0),
(-1, 1),
( 0, 1),
]
def add(pos1, pos2):
x1, y1 = pos1
x2, y2 = pos2
return (x1 + x2, y1 + y2)
class Grid:
def __init__(self, width, height):
self.width = width
self.height = height
self.data = [WALL for _ in range(width * height)]
def valid_index(self, x, y):
return (x in range(self.width)
and y in range(self.height))
def translate_index(self, pos):
x, y = pos
if self.valid_index(x, y):
return y * self.width + x
else:
raise IndexError(x, y)
def __getitem__(self, pos):
return self.data[self.translate_index(pos)]
def __setitem__(self, pos, new):
self.data[self.translate_index(pos)] = new
def blank_neighbors(self, point, d):
original_direction = tuple(-c for c in d)
count = 0
for d in MOORE:
if d in perp(original_direction):
continue
try:
neighbor = self[add(point, d)]
except IndexError:
pass
else:
count += (neighbor == GAP)
return count
def __str__(self):
return "\n".join(
"".join(s) for s in split(self.data, self.width))
def __repr__(self):
return str(self)
def __len__(self):
return len(self.data)
# Generates a maze.
#
# Guarantees that there is only one way to get from one point
# to another.
def generate_maze(width, height):
points = [random_point(width, height)]
grid = Grid(width, height)
grid[points[0]] = GAP
while points:
# Pick an point randomly to expand upon, but favor points that
# were more recently created.
index = favored_random(len(points))
point = points[index]
valid_directions = 0
for d in random.sample(DIRECTIONS, 4):
neighbor = add(d, point)
if neighbor in points:
continue
if not grid.valid_index(*neighbor):
continue
bn = grid.blank_neighbors(neighbor, d)
if bn != 0:
continue
valid_directions += 1
grid[neighbor] = GAP
points.append(neighbor)
if valid_directions == 0:
del points[index]
return grid
print(generate_maze(200, 100))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment