1176 lines
38 KiB
Python
1176 lines
38 KiB
Python
import abc, enum, random
|
|
|
|
|
|
class Maze(abc.ABC):
|
|
|
|
@property
|
|
@abc.abstractmethod
|
|
def width(self) -> int:
|
|
pass
|
|
|
|
@property
|
|
@abc.abstractmethod
|
|
def height(self) -> int:
|
|
pass
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
pass
|
|
|
|
@abc.abstractmethod
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
pass
|
|
|
|
@abc.abstractmethod
|
|
def step(self) -> bool: # returns False when algorithm is done
|
|
pass
|
|
|
|
def run(self, i=1_000_000) -> bool:
|
|
for _ in range(i):
|
|
if not self.step(): return True
|
|
return False
|
|
|
|
def secondary(self, index: tuple[int,int]) -> bool:
|
|
return True
|
|
|
|
def __str__(self) -> str:
|
|
s = ""
|
|
for y in range(self.height):
|
|
for x in range(self.width):
|
|
s += ' ' if self[x,y] else 'x'
|
|
s += '\n'
|
|
return s
|
|
|
|
def __list__(self) -> list[list[bool]]:
|
|
return [list(
|
|
[self[x,y] for x in range(self.width)]) for y in range(self.height)]
|
|
|
|
def _neighbors(self, index: tuple[int,int]) -> list[tuple[int,int]]:
|
|
neighbors: list[tuple[int,int]] = []
|
|
x, y = index
|
|
|
|
if x - 2 >= 0:
|
|
neighbors.append((x - 2,y))
|
|
if x + 2 < self.width:
|
|
neighbors.append((x + 2,y))
|
|
if y - 2 >= 0:
|
|
neighbors.append((x,y - 2))
|
|
if y + 2 < self.height:
|
|
neighbors.append((x,y + 2))
|
|
|
|
return neighbors
|
|
|
|
|
|
class VectorEnum(enum.Enum):
|
|
Null = -1
|
|
Zero = 0
|
|
Up = 2
|
|
Down = 4
|
|
Left = 8
|
|
Right = 16
|
|
|
|
def __or__(self, value: "VectorEnum | int") -> int:
|
|
if not isinstance(value, int): value = value.value
|
|
return self.value | value
|
|
|
|
def __ror__(self, value: "VectorEnum | int") -> int:
|
|
if not isinstance(value, int): value = value.value
|
|
return self.value | value
|
|
|
|
def __and__(self, value: "VectorEnum | int") -> "VectorEnum":
|
|
if not isinstance(value, int): value = value.value
|
|
return VectorEnum(self.value & value)
|
|
|
|
def __rand__(self, value: "VectorEnum | int") -> "VectorEnum":
|
|
if not isinstance(value, int): value = value.value
|
|
return VectorEnum(self.value & value)
|
|
|
|
|
|
class VectorMaze(Maze):
|
|
|
|
@abc.abstractmethod
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
pass
|
|
|
|
def secondary(self, index: tuple[int,int]) -> VectorEnum:
|
|
return VectorEnum.Null
|
|
|
|
def __list__(self) -> list[list[VectorEnum]]:
|
|
return [list(
|
|
[self[x,y] for x in range(self.width)]) for y in range(self.height)]
|
|
|
|
def _neighbors(self, index: tuple[int,int]) -> list[tuple[int,int]]:
|
|
neighbors: list[tuple[int,int]] = []
|
|
x, y = index
|
|
|
|
if x - 1 >= 0:
|
|
neighbors.append((x - 1,y))
|
|
if x + 1 < self.width:
|
|
neighbors.append((x + 1,y))
|
|
if y - 1 >= 0:
|
|
neighbors.append((x,y - 1))
|
|
if y + 1 < self.height:
|
|
neighbors.append((x,y + 1))
|
|
|
|
return neighbors
|
|
|
|
|
|
class VectorWrapper(Maze):
|
|
|
|
__maze: VectorMaze
|
|
|
|
def __init__(self, maze: VectorMaze):
|
|
self.__maze = maze
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__from_vec(self.__maze.width)
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__from_vec(self.__maze.height)
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__maze.highlighted is not None:
|
|
return (
|
|
self.__from_vec(self.__maze.highlighted[0]),
|
|
self.__from_vec(self.__maze.highlighted[1])
|
|
)
|
|
else: return None
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
return self.__value(index, lambda o: self.__maze[o])
|
|
|
|
def secondary(self, index: tuple[int,int]) -> bool:
|
|
return self.__value(index, lambda o: self.__maze.secondary(o))
|
|
|
|
def __value(self, index: tuple[int,int], key) -> bool:
|
|
x, y = index
|
|
if x % 2 and y % 2:
|
|
if key((self.__to_vec(x), self.__to_vec(y))) != VectorEnum.Null:
|
|
return False
|
|
elif x % 2:
|
|
if self.__to_vec(y-1) >= 0:
|
|
if key((self.__to_vec(x), self.__to_vec(y-1))) == \
|
|
VectorEnum.Down:
|
|
return False
|
|
if self.__to_vec(y+1) < self.__maze.height:
|
|
if key((self.__to_vec(x), self.__to_vec(y+1))) == \
|
|
VectorEnum.Up:
|
|
return False
|
|
elif y % 2:
|
|
if self.__to_vec(x-1) >= 0:
|
|
if key((self.__to_vec(x-1), self.__to_vec(y))) == \
|
|
VectorEnum.Right:
|
|
return False
|
|
if self.__to_vec(x+1) < self.__maze.width:
|
|
if key((self.__to_vec(x+1), self.__to_vec(y))) == \
|
|
VectorEnum.Left:
|
|
return False
|
|
return True
|
|
|
|
def step(self) -> bool: return self.__maze.step()
|
|
|
|
@property
|
|
def maze(self) -> VectorMaze:
|
|
return self.__maze
|
|
|
|
@staticmethod
|
|
def __from_vec(i: int) -> int:
|
|
return ((i * 2) + 1)
|
|
|
|
@staticmethod
|
|
def __to_vec(i: int) -> int:
|
|
return ((i - 1) // 2)
|
|
|
|
@classmethod
|
|
def convert(cls, maze: Maze, origin: tuple[int,int] | None = None) -> "VectorWrapper":
|
|
width, height = cls.__to_vec(maze.width), cls.__to_vec(maze.height)
|
|
|
|
if origin is None:
|
|
stack = [(random.randint(0,width-1),random.randint(0,height-1))]
|
|
else:
|
|
stack = [origin]
|
|
|
|
cells = [list([VectorEnum.Null for _ in range(width)]) for _ in range(height)]
|
|
|
|
cells[stack[-1][1]][stack[-1][0]] = VectorEnum.Zero
|
|
|
|
while stack:
|
|
x, y = stack.pop()
|
|
if x - 1 >= 0 and cells[y][x - 1] == VectorEnum.Null and not maze[cls.__from_vec(x) - 1, cls.__from_vec(y)]:
|
|
stack.append((x - 1, y))
|
|
cells[y][x - 1] = VectorEnum.Right
|
|
if x + 1 < width and cells[y][x + 1] == VectorEnum.Null and not maze[cls.__from_vec(x) + 1, cls.__from_vec(y)]:
|
|
stack.append((x + 1, y))
|
|
cells[y][x + 1] = VectorEnum.Left
|
|
if y - 1 >= 0 and cells[y - 1][x] == VectorEnum.Null and not maze[cls.__from_vec(x), cls.__from_vec(y) - 1]:
|
|
stack.append((x, y - 1))
|
|
cells[y - 1][x] = VectorEnum.Down
|
|
if y + 1 < height and cells[y + 1][x] == VectorEnum.Null and not maze[cls.__from_vec(x), cls.__from_vec(y) + 1]:
|
|
stack.append((x, y + 1))
|
|
cells[y + 1][x] = VectorEnum.Up
|
|
|
|
return cls(OriginShift.clone(cells))
|
|
|
|
|
|
class RecursiveBacktracker(Maze):
|
|
|
|
__cells: list[list[bool]]
|
|
__stack: list[tuple[int,int]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
def __init__(self, width: int, height: int | None = None):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
self.__cells = [
|
|
list([True for _ in range(self.width)]) for _ in range(self.height)]
|
|
self.__stack = [(
|
|
(random.randint(0, ((self.width - 1) // 2) - 1) * 2) + 1,
|
|
(random.randint(0, ((self.height - 1) // 2) - 1) * 2) + 1
|
|
)]
|
|
|
|
self.__cells[self.__stack[-1][1]][self.__stack[-1][0]] = False
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__stack: return self.__stack[-1]
|
|
else: return None
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
return self.__cells[index[1]][index[0]]
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None:
|
|
neighbors = self.__unvisited_neighbors(self.highlighted)
|
|
if neighbors:
|
|
cell = neighbors[random.randint(0,len(neighbors)-1)]
|
|
x = (self.highlighted[0] + cell[0]) // 2
|
|
y = (self.highlighted[1] + cell[1]) // 2
|
|
self.__cells[y][x] = False
|
|
self.__cells[cell[1]][cell[0]] = False
|
|
self.__stack.append(cell)
|
|
else: self.__stack.pop()
|
|
return True
|
|
else: return False
|
|
|
|
def __unvisited_neighbors(
|
|
self,
|
|
index: tuple[int,int],
|
|
) -> list[tuple[int,int]]:
|
|
return [(x,y) for x,y in self._neighbors(index) if self[x,y]]
|
|
|
|
|
|
class OriginShift(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
def __init__(self, width: int, height: int | None = None):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__cells = [
|
|
list([self.__start(x,y) for x in range(self.width)])
|
|
for y in range(self.height)]
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
for y, row in enumerate(self.__cells):
|
|
for x, cell in enumerate(row):
|
|
if cell == VectorEnum.Zero:
|
|
return (x, y)
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None:
|
|
x, y = self.highlighted
|
|
neighbors = self._neighbors((x,y))
|
|
if neighbors:
|
|
cell = neighbors[random.randint(0,len(neighbors)-1)]
|
|
self.__cells[y][x] = self.__direction((x,y), cell)
|
|
self.__cells[cell[1]][cell[0]] = VectorEnum.Zero
|
|
return True
|
|
else: return False
|
|
|
|
@classmethod
|
|
def clone(cls, other: VectorMaze | list[list[VectorEnum]]) -> "OriginShift":
|
|
if isinstance(other, VectorMaze):
|
|
self = cls(other.width, other.height)
|
|
self.__cells = [
|
|
list([other[x,y] for x in range(other.width)])
|
|
for y in range(other.height)]
|
|
else:
|
|
self = cls(len(other[0]), len(other))
|
|
self.__cells = [
|
|
list([other[y][x] for x in range(len(other[0]))])
|
|
for y in range(len(other))]
|
|
return self
|
|
|
|
def __direction(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int]
|
|
) -> VectorEnum:
|
|
if start[0] - end[0] > 0: return VectorEnum.Left
|
|
if start[0] - end[0] < 0: return VectorEnum.Right
|
|
if start[1] - end[1] > 0: return VectorEnum.Up
|
|
if start[1] - end[1] < 0: return VectorEnum.Down
|
|
return VectorEnum.Zero
|
|
|
|
def __start(self, x: int, y: int) -> VectorEnum:
|
|
if x == self.width - 1 and y == self.height - 1: return VectorEnum.Zero
|
|
elif x == self.width - 1: return VectorEnum.Down
|
|
else: return VectorEnum.Right
|
|
|
|
|
|
class BinaryTree(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
__bias: int
|
|
|
|
__x: int
|
|
__y: int
|
|
|
|
def __init__(
|
|
self,
|
|
width: int,
|
|
height: int | None = None,
|
|
*, bias: int | None = None,
|
|
):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__bias = bias or (VectorEnum.Up | VectorEnum.Left)
|
|
|
|
self.__x = 0
|
|
self.__y = 0
|
|
|
|
self.__cells = [
|
|
list([VectorEnum.Null for _ in range(self.width)])
|
|
for _ in range(self.height)]
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__x < self.width and self.__y < self.height:
|
|
return self.__x, self.__y
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None:
|
|
neighbors = self._neighbors(self.highlighted)
|
|
if neighbors:
|
|
cell = neighbors[random.randint(0,len(neighbors)-1)]
|
|
self.__cells[self.__y][self.__x] = self.__direction(
|
|
self.highlighted, cell)
|
|
else:
|
|
self.__cells[self.__y][self.__x] = VectorEnum.Zero
|
|
self.__x += 1
|
|
if self.__x >= self.width:
|
|
self.__x = 0
|
|
self.__y += 1
|
|
return True
|
|
else: return False
|
|
|
|
def __direction(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Left
|
|
if start[0] < end[0]: return VectorEnum.Right
|
|
if start[1] > end[1]: return VectorEnum.Up
|
|
if start[1] < end[1]: return VectorEnum.Down
|
|
return VectorEnum.Zero
|
|
|
|
def _neighbors(self, index: tuple[int,int]) -> list[tuple[int,int]]:
|
|
neighbors: list[tuple[int,int]] = []
|
|
x, y = index
|
|
|
|
if x - 1 >= 0 and (self.__bias & VectorEnum.Left) == VectorEnum.Left:
|
|
neighbors.append((x - 1,y))
|
|
if x + 1 < self.width and (self.__bias & VectorEnum.Right) == \
|
|
VectorEnum.Right:
|
|
neighbors.append((x + 1,y))
|
|
if y - 1 >= 0 and (self.__bias & VectorEnum.Up) == VectorEnum.Up:
|
|
neighbors.append((x,y - 1))
|
|
if y + 1 < self.height and (self.__bias & VectorEnum.Down) == \
|
|
VectorEnum.Down:
|
|
neighbors.append((x,y + 1))
|
|
|
|
return neighbors
|
|
|
|
|
|
class Sidewinder(Maze):
|
|
|
|
__cells: list[list[bool]]
|
|
__run: list[tuple[int,int]]
|
|
|
|
__run_param: float
|
|
__start: VectorEnum
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
def __init__(
|
|
self,
|
|
width: int,
|
|
height: int | None = None,
|
|
*,
|
|
run_param: float = 0.5,
|
|
start: VectorEnum = VectorEnum.Up,
|
|
):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
self.__cells = [
|
|
list([True for _ in range(self.width)]) for _ in range(self.height)]
|
|
self.__start = start
|
|
self.__run_param = run_param
|
|
|
|
if self.__start == VectorEnum.Up:
|
|
self.__run = [(1,1)]
|
|
elif self.__start == VectorEnum.Down:
|
|
self.__run = [(self.width-2,self.height-2)]
|
|
elif self.__start == VectorEnum.Right:
|
|
self.__run = [(self.width-2,self.height-2)]
|
|
elif self.__start == VectorEnum.Left:
|
|
self.__run = [(1,1)]
|
|
else:
|
|
self.__run = []
|
|
|
|
self.__cells[self.__run[-1][1]][self.__run[-1][0]] = False
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__run: return self.__run[-1]
|
|
else: return None
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
return self.__cells[index[1]][index[0]]
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None:
|
|
hx, hy = self.highlighted
|
|
|
|
if hx - 2 >= 0 and self.__start == VectorEnum.Down:
|
|
cell = (hx - 2, hy)
|
|
carve = (
|
|
hy + 2 >= self.height or random.random() > self.__run_param)
|
|
elif hx + 2 < self.width and self.__start == VectorEnum.Up:
|
|
cell = (hx + 2, hy)
|
|
carve = hy - 2 < 0 or random.random() > self.__run_param
|
|
elif hy - 2 >= 0 and self.__start == VectorEnum.Right:
|
|
cell = (hx, hy - 2)
|
|
carve = (
|
|
hx + 2 >= self.width or random.random() > self.__run_param)
|
|
elif hy + 2 < self.height and self.__start == VectorEnum.Left:
|
|
cell = (hx, hy + 2)
|
|
carve = hx - 2 < 0 or random.random() > self.__run_param
|
|
else:
|
|
cell = None
|
|
carve = False
|
|
|
|
if cell is not None and carve:
|
|
x = (hx + cell[0]) // 2
|
|
y = (hy + cell[1]) // 2
|
|
self.__cells[y][x] = False
|
|
self.__cells[cell[1]][cell[0]] = False
|
|
self.__run.append(cell)
|
|
else:
|
|
hx, hy = self.highlighted
|
|
sx, sy = self.__run[random.randint(0,len(self.__run)-1)]
|
|
self.__run.clear()
|
|
|
|
if self.__start == VectorEnum.Down:
|
|
if hx - 2 >= 0:
|
|
x, y = (hx - 2, hy)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
else:
|
|
if hy - 2 >= 0:
|
|
x, y = (self.width - 2, hy - 2)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
if sy + 2 < self.height: cell = (sx, sy + 2)
|
|
else: cell = None
|
|
elif self.__start == VectorEnum.Up:
|
|
if hx + 2 < self.width:
|
|
x, y = (hx + 2, hy)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
else:
|
|
if hy + 2 < self.height:
|
|
x, y = (1, hy + 2)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
if sy - 2 >= 0: cell = (sx, sy - 2)
|
|
else: cell = None
|
|
elif self.__start == VectorEnum.Right:
|
|
if hy - 2 >= 0:
|
|
x, y = (hx, hy - 2)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
else:
|
|
if hx - 2 >= 0:
|
|
x, y = (hx - 2, self.height - 2)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
if sx + 2 < self.height: cell = (sx + 2, sy)
|
|
else: cell = None
|
|
elif self.__start == VectorEnum.Left:
|
|
if hy + 2 < self.height:
|
|
x, y = (hx, hy + 2)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
else:
|
|
if hx + 2 < self.width:
|
|
x, y = (hx + 2, 1)
|
|
self.__run.append((x,y))
|
|
self.__cells[y][x] = False
|
|
if sx - 2 >= 0: cell = (sx - 2, sy)
|
|
else: cell = None
|
|
|
|
if cell is not None:
|
|
x = (sx + cell[0]) // 2
|
|
y = (sy + cell[1]) // 2
|
|
self.__cells[y][x] = False
|
|
return True
|
|
else: return False
|
|
|
|
|
|
class _Window:
|
|
|
|
__maze: "RecursiveDivision"
|
|
__x_start: int
|
|
__x_stop: int
|
|
__y_start: int
|
|
__y_stop: int
|
|
|
|
def __init__(
|
|
self,
|
|
maze: "RecursiveDivision",
|
|
x_start: int,
|
|
x_stop: int,
|
|
y_start: int,
|
|
y_stop: int,
|
|
):
|
|
self.__maze = maze
|
|
self.__x_start = x_start
|
|
self.__x_stop = x_stop
|
|
self.__y_start = y_start
|
|
self.__y_stop = y_stop
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__x_stop - self.__x_start
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__y_stop - self.__y_start
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
return self.__maze[index[1] - self.__x_start, index[0] - self.__y_start]
|
|
|
|
def x(self, x: int) -> int: return x + self.__x_start
|
|
def y(self, y: int) -> int: return y + self.__y_start
|
|
|
|
def vertical_bisect(self, x: int) -> "tuple[_Window, _Window]":
|
|
return _Window(
|
|
self.__maze,
|
|
self.__x_start,
|
|
self.__x_start + x,
|
|
self.__y_start,
|
|
self.__y_stop,
|
|
), _Window(
|
|
self.__maze,
|
|
self.__x_start + x + 1,
|
|
self.__x_stop,
|
|
self.__y_start,
|
|
self.__y_stop,
|
|
)
|
|
|
|
def horizontal_bisect(self, y: int) -> "tuple[_Window, _Window]":
|
|
return _Window(
|
|
self.__maze,
|
|
self.__x_start,
|
|
self.__x_stop,
|
|
self.__y_start,
|
|
self.__y_start + y,
|
|
), _Window(
|
|
self.__maze,
|
|
self.__x_start,
|
|
self.__x_stop,
|
|
self.__y_start + y + 1,
|
|
self.__y_stop,
|
|
)
|
|
|
|
|
|
class RecursiveDivision(Maze):
|
|
|
|
__cells: list[list[bool]]
|
|
__stack: list[tuple[bool | None, _Window]]
|
|
__split: tuple[bool, int, _Window] | None
|
|
|
|
__binary: bool
|
|
__uniform: bool
|
|
__depth_first: bool
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
def __init__(
|
|
self,
|
|
width: int,
|
|
height: int | None = None,
|
|
*,
|
|
binary: bool = False,
|
|
uniform: bool = True,
|
|
depth_first: bool = True,
|
|
):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
self.__binary = binary
|
|
self.__uniform = uniform
|
|
self.__depth_first = depth_first
|
|
self.__cells = [
|
|
list([(not (0 < x < self.width-1 and 0 < y < self.height-1))
|
|
for x in range(self.width)]) for y in range(self.height)]
|
|
self.__stack = [
|
|
((True if self.__uniform else None),
|
|
_Window(self,1,self.width,1,self.height))]
|
|
self.__split = None
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> bool:
|
|
return self.__cells[index[1]][index[0]]
|
|
|
|
def step(self) -> bool:
|
|
if self.__split is not None:
|
|
if self.__split[0]:
|
|
axis, y, window = self.__split
|
|
x = (random.randint(0, (window.width - 1) // 2) * 2)
|
|
self.__cells[window.y(y)][window.x(x)] = False
|
|
a, b = [
|
|
((not axis if self.__uniform else None), w)
|
|
for w in window.horizontal_bisect(y)]
|
|
else:
|
|
axis, x, window = self.__split
|
|
y = (random.randint(0, (window.height - 1) // 2) * 2)
|
|
self.__cells[window.y(y)][window.x(x)] = False
|
|
a, b = [
|
|
((not axis if self.__uniform else None), w)
|
|
for w in window.vertical_bisect(x)]
|
|
if a[1].width > 2 and a[1].height > 2: self.__stack.append(a)
|
|
if b[1].width > 2 and b[1].height > 2: self.__stack.append(b)
|
|
self.__split = None
|
|
return True
|
|
elif self.__stack:
|
|
axis, window = self.__stack.pop(-1 if self.__depth_first else 0)
|
|
if axis is None: axis = bool(random.randint(0,1))
|
|
if axis:
|
|
if self.__binary: y = (((window.height - 3) // 4) * 2) + 1
|
|
else: y = (random.randint(0, (window.height - 3) // 2) * 2) + 1
|
|
for x in range(window.width):
|
|
self.__cells[window.y(y)][window.x(x)] = True
|
|
self.__split = axis, y, window
|
|
else:
|
|
if self.__binary: x = (((window.width - 3) // 4) * 2) + 1
|
|
else: x = (random.randint(0, (window.width - 3) // 2) * 2) + 1
|
|
for y in range(window.height):
|
|
self.__cells[window.y(y)][window.x(x)] = True
|
|
self.__split = axis, x, window
|
|
return True
|
|
else: return False
|
|
|
|
|
|
class Prim(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
__frontier: set[tuple[int,int]]
|
|
|
|
def __init__(self, width: int, height: int | None = None):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__cells = [
|
|
list([VectorEnum.Null for _ in range(self.width)])
|
|
for _ in range(self.height)]
|
|
|
|
x, y = random.randint(0,self.width-1), random.randint(0,self.height-1)
|
|
|
|
self.__cells[y][x] = VectorEnum.Zero
|
|
|
|
self.__frontier = set(self._neighbors((x,y), False))
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def step(self) -> bool:
|
|
if self.__frontier:
|
|
cell_a = list(
|
|
self.__frontier)[random.randint(0,len(self.__frontier)-1)]
|
|
self.__frontier.remove(cell_a)
|
|
neighbors = self._neighbors(cell_a, True)
|
|
cell_b = neighbors.pop(random.randint(0,len(neighbors)-1))
|
|
|
|
self.__cells[cell_a[1]][cell_a[0]] = self.__direction(
|
|
cell_a, cell_b)
|
|
|
|
self.__frontier.update(self._neighbors(cell_a, False))
|
|
return True
|
|
else: return False
|
|
|
|
def __direction(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Left
|
|
if start[0] < end[0]: return VectorEnum.Right
|
|
if start[1] > end[1]: return VectorEnum.Up
|
|
if start[1] < end[1]: return VectorEnum.Down
|
|
return VectorEnum.Zero
|
|
|
|
def _neighbors(
|
|
self,
|
|
index: tuple[int,int],
|
|
inside=False,
|
|
) -> list[tuple[int,int]]:
|
|
neighbors: list[tuple[int,int]] = []
|
|
x, y = index
|
|
|
|
if inside:
|
|
if x - 1 >= 0 and self.__cells[y][x-1] != VectorEnum.Null:
|
|
neighbors.append((x - 1,y))
|
|
if x + 1 < self.width and self.__cells[y][x+1] != VectorEnum.Null:
|
|
neighbors.append((x + 1,y))
|
|
if y - 1 >= 0 and self.__cells[y-1][x] != VectorEnum.Null:
|
|
neighbors.append((x,y - 1))
|
|
if y + 1 < self.height and self.__cells[y+1][x] != VectorEnum.Null:
|
|
neighbors.append((x,y + 1))
|
|
else:
|
|
if x - 1 >= 0 and self.__cells[y][x-1] == VectorEnum.Null:
|
|
neighbors.append((x - 1,y))
|
|
if x + 1 < self.width and self.__cells[y][x+1] == VectorEnum.Null:
|
|
neighbors.append((x + 1,y))
|
|
if y - 1 >= 0 and self.__cells[y-1][x] == VectorEnum.Null:
|
|
neighbors.append((x,y - 1))
|
|
if y + 1 < self.height and self.__cells[y+1][x] == VectorEnum.Null:
|
|
neighbors.append((x,y + 1))
|
|
|
|
return neighbors
|
|
|
|
|
|
class Wilson(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
__path: dict[tuple[int,int], VectorEnum]
|
|
__start: tuple[int,int] | None
|
|
|
|
def __init__(self, width: int, height: int | None = None):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__cells = [
|
|
list([VectorEnum.Null for _ in range(self.width)])
|
|
for _ in range(self.height)]
|
|
|
|
x, y = random.randint(0,self.width-1), random.randint(0,self.height-1)
|
|
self.__cells[y][x] = VectorEnum.Zero
|
|
|
|
self.__start = self.__new_start()
|
|
if self.__start is not None:
|
|
self.__path = {self.__start: VectorEnum.Zero}
|
|
else:
|
|
self.__path = {}
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__start is not None:
|
|
for key, value in self.__path.items():
|
|
if value == VectorEnum.Zero:
|
|
return key
|
|
return None
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def secondary(self, index: tuple[int,int]) -> VectorEnum:
|
|
if self.__start is not None:
|
|
if index in self.__path.keys():
|
|
cell: tuple[int,int] = self.__start
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
if cell == index: return self.__path[cell]
|
|
cell = self.__next(cell, self.__path[cell])
|
|
return VectorEnum.Null
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None and self.__start is not None:
|
|
highlighted = self.highlighted
|
|
neighbors = self._neighbors(highlighted)
|
|
cell = neighbors[random.randint(0, len(neighbors)-1)]
|
|
self.__path[highlighted] = self.__direction(highlighted, cell)
|
|
if self.__cells[cell[1]][cell[0]] == VectorEnum.Null:
|
|
self.__path[cell] = VectorEnum.Zero
|
|
self.__optimize_path()
|
|
else:
|
|
cell: tuple[int,int] = self.__start
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
self.__cells[cell[1]][cell[0]] = self.__path[cell]
|
|
cell = self.__next(cell, self.__path[cell])
|
|
self.__start = self.__new_start()
|
|
if self.__start is not None:
|
|
self.__path = {self.__start: VectorEnum.Zero}
|
|
else:
|
|
self.__path = {}
|
|
return True
|
|
else: return False
|
|
|
|
def __optimize_path(self):
|
|
if self.__start is not None:
|
|
purge = set(self.__path.keys())
|
|
cell: tuple[int,int] = self.__start
|
|
purge.remove(cell)
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
cell = self.__next(cell, self.__path[cell])
|
|
purge.remove(cell)
|
|
for cell in purge:
|
|
del self.__path[cell]
|
|
|
|
def __new_start(self) -> tuple[int, int] | None:
|
|
empty = []
|
|
for x in range(self.width):
|
|
for y in range(self.height):
|
|
if self.__cells[y][x] == VectorEnum.Null:
|
|
empty.append((x,y))
|
|
if empty: return empty[random.randint(0,len(empty)-1)]
|
|
else: return None
|
|
|
|
def __direction(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Left
|
|
if start[0] < end[0]: return VectorEnum.Right
|
|
if start[1] > end[1]: return VectorEnum.Up
|
|
if start[1] < end[1]: return VectorEnum.Down
|
|
return VectorEnum.Zero
|
|
|
|
def __next(
|
|
self,
|
|
index: tuple[int,int],
|
|
direction: VectorEnum,
|
|
) -> tuple[int,int]:
|
|
if direction == VectorEnum.Up: return index[0], index[1]-1
|
|
elif direction == VectorEnum.Down: return index[0], index[1]+1
|
|
elif direction == VectorEnum.Left: return index[0]-1, index[1]
|
|
elif direction == VectorEnum.Right: return index[0]+1, index[1]
|
|
else: return index[0], index[1]
|
|
|
|
|
|
class AldousBroder(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
__current: tuple[int,int]
|
|
__remaining: int
|
|
|
|
def __init__(self, width: int, height: int | None = None):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__cells = [
|
|
list([VectorEnum.Null for _ in range(self.width)])
|
|
for _ in range(self.height)]
|
|
|
|
x, y = random.randint(0,self.width-1), random.randint(0,self.height-1)
|
|
|
|
self.__cells[y][x] = VectorEnum.Zero
|
|
|
|
self.__current = (x,y)
|
|
self.__remaining = self.width * self.height - 1
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__remaining > 0: return self.__current
|
|
else: return None
|
|
|
|
def __getitem__(self, index: tuple[int, int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None:
|
|
neighbors = self._neighbors(self.highlighted)
|
|
cell = neighbors[random.randint(0,len(neighbors)-1)]
|
|
if self.__cells[cell[1]][cell[0]] == VectorEnum.Null:
|
|
self.__cells[cell[1]][cell[0]] = self.__direction(
|
|
self.highlighted, cell)
|
|
self.__remaining -= 1
|
|
self.__current = cell
|
|
return True
|
|
else: return False
|
|
|
|
def __direction(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Right
|
|
if start[0] < end[0]: return VectorEnum.Left
|
|
if start[1] > end[1]: return VectorEnum.Down
|
|
if start[1] < end[1]: return VectorEnum.Up
|
|
return VectorEnum.Zero
|
|
|
|
|
|
class AldousBroderWilson(VectorMaze):
|
|
|
|
__cells: list[list[VectorEnum]]
|
|
|
|
__width: int
|
|
__height: int
|
|
|
|
__path: dict[tuple[int,int], VectorEnum]
|
|
__start: tuple[int,int] | None
|
|
|
|
__current: tuple[int,int]
|
|
__remaining: int
|
|
|
|
__switch: float
|
|
|
|
def __init__(
|
|
self,
|
|
width: int,
|
|
height: int | None = None,
|
|
*, switch: float = 0.5
|
|
):
|
|
self.__width = width
|
|
self.__height = height or width
|
|
|
|
self.__cells = [
|
|
list([VectorEnum.Null for _ in range(self.width)])
|
|
for _ in range(self.height)]
|
|
|
|
x, y = random.randint(0,self.width-1), random.randint(0,self.height-1)
|
|
self.__cells[y][x] = VectorEnum.Zero
|
|
|
|
self.__start = None
|
|
self.__path = {}
|
|
|
|
self.__current = (x,y)
|
|
self.__remaining = self.width * self.height - 1
|
|
|
|
self.__switch = switch
|
|
|
|
@property
|
|
def width(self) -> int:
|
|
return self.__width
|
|
|
|
@property
|
|
def height(self) -> int:
|
|
return self.__height
|
|
|
|
@property
|
|
def highlighted(self) -> tuple[int,int] | None:
|
|
if self.__start is not None:
|
|
for key, value in self.__path.items():
|
|
if value == VectorEnum.Zero:
|
|
return key
|
|
elif self.__remaining > 0: return self.__current
|
|
return None
|
|
|
|
def __getitem__(self, index: tuple[int,int]) -> VectorEnum:
|
|
x, y = index
|
|
return self.__cells[y][x]
|
|
|
|
def secondary(self, index: tuple[int,int]) -> VectorEnum:
|
|
if self.__start is not None:
|
|
if index in self.__path.keys():
|
|
cell: tuple[int,int] = self.__start
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
if cell == index: return self.__path[cell]
|
|
cell = self.__next(cell, self.__path[cell])
|
|
return VectorEnum.Null
|
|
|
|
def step(self) -> bool:
|
|
if self.highlighted is not None and self.__start is not None:
|
|
highlighted = self.highlighted
|
|
neighbors = self._neighbors(highlighted)
|
|
cell = neighbors[random.randint(0, len(neighbors)-1)]
|
|
self.__path[highlighted] = self.__direction_wilson(
|
|
highlighted, cell)
|
|
if self.__cells[cell[1]][cell[0]] == VectorEnum.Null:
|
|
self.__path[cell] = VectorEnum.Zero
|
|
self.__optimize_path()
|
|
else:
|
|
cell: tuple[int,int] = self.__start
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
self.__cells[cell[1]][cell[0]] = self.__path[cell]
|
|
cell = self.__next(cell, self.__path[cell])
|
|
self.__remaining -= len(self.__path)
|
|
self.__start = self.__new_start()
|
|
if self.__start is not None:
|
|
self.__path = {self.__start: VectorEnum.Zero}
|
|
else:
|
|
self.__path = {}
|
|
return True
|
|
elif self.highlighted is not None:
|
|
neighbors = self._neighbors(self.highlighted)
|
|
cell = neighbors[random.randint(0,len(neighbors)-1)]
|
|
if self.__cells[cell[1]][cell[0]] == VectorEnum.Null:
|
|
self.__cells[cell[1]][cell[0]] = self.__direction_aldous_broder(
|
|
self.highlighted, cell)
|
|
self.__remaining -= 1
|
|
self.__current = cell
|
|
if self.__remaining / (self.width * self.height) < self.__switch:
|
|
self.__start = self.__new_start()
|
|
if self.__start is not None:
|
|
self.__path = {self.__start: VectorEnum.Zero}
|
|
return True
|
|
else: return False
|
|
|
|
def __optimize_path(self):
|
|
if self.__start is not None:
|
|
purge = set(self.__path.keys())
|
|
cell: tuple[int,int] = self.__start
|
|
purge.remove(cell)
|
|
while self.__path.get(cell, VectorEnum.Zero) != VectorEnum.Zero:
|
|
cell = self.__next(cell, self.__path[cell])
|
|
purge.remove(cell)
|
|
for cell in purge:
|
|
del self.__path[cell]
|
|
|
|
def __new_start(self) -> tuple[int, int] | None:
|
|
empty = []
|
|
for x in range(self.width):
|
|
for y in range(self.height):
|
|
if self.__cells[y][x] == VectorEnum.Null:
|
|
empty.append((x,y))
|
|
if empty: return empty[random.randint(0,len(empty)-1)]
|
|
else: return None
|
|
|
|
def __direction_wilson(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Left
|
|
if start[0] < end[0]: return VectorEnum.Right
|
|
if start[1] > end[1]: return VectorEnum.Up
|
|
if start[1] < end[1]: return VectorEnum.Down
|
|
return VectorEnum.Zero
|
|
|
|
def __direction_aldous_broder(
|
|
self,
|
|
start: tuple[int,int],
|
|
end: tuple[int,int],
|
|
) -> VectorEnum:
|
|
if start[0] > end[0]: return VectorEnum.Right
|
|
if start[0] < end[0]: return VectorEnum.Left
|
|
if start[1] > end[1]: return VectorEnum.Down
|
|
if start[1] < end[1]: return VectorEnum.Up
|
|
return VectorEnum.Zero
|
|
|
|
def __next(
|
|
self,
|
|
index: tuple[int,int],
|
|
direction: VectorEnum,
|
|
) -> tuple[int,int]:
|
|
if direction == VectorEnum.Up: return index[0], index[1]-1
|
|
elif direction == VectorEnum.Down: return index[0], index[1]+1
|
|
elif direction == VectorEnum.Left: return index[0]-1, index[1]
|
|
elif direction == VectorEnum.Right: return index[0]+1, index[1]
|
|
else: return index[0], index[1]
|