-
Notifications
You must be signed in to change notification settings - Fork 52
/
Sidewinder.py
62 lines (49 loc) · 2.09 KB
/
Sidewinder.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
from random import choice, random
import numpy as np
# If the code is not Cython-compiled, we need to add some imports.
from cython import compiled
if not compiled:
from mazelib.generate.MazeGenAlgo import MazeGenAlgo
class Sidewinder(MazeGenAlgo):
"""
The Algorithm
1. Work through the grid row-wise, starting with the cell at 0,0.
2. Add the current cell to a "run" set.
3. For the current cell, randomly decide whether to carve East.
4. If a passage East was carved, make the new cell the current cell and repeat steps 2-4.
5. If a passage East was not carved, choose any one of the cells in the run set and carve
a passage North. Then empty the run set. Repeat steps 2-5.
6. Continue until all rows have been processed.
Optional Parameters
skew: Float [0.0, 1.0]
If the skew is set less than 0.5 the maze will be skewed East-West, if it set greater
than 0.5 it will be skewed North-South. (default 0.5)
"""
def __init__(self, h, w, skew=0.5):
super(Sidewinder, self).__init__(h, w)
self.skew = skew
def generate(self):
# create empty grid
grid = np.empty((self.H, self.W), dtype=np.int8)
grid.fill(1)
# The first row is always empty, because you can't carve North
for col in range(1, self.W - 1):
grid[1][col] = 0
# loop through the remaining rows and columns
for row in range(3, self.H, 2):
# create a run of cells
run = []
for col in range(1, self.W, 2):
# remove the wall to the current cell
grid[row][col] = 0
# add the current cell to the run
run.append((row, col))
carve_east = random() > self.skew
# carve East or North (can't carve East into the East wall
if carve_east and col < (self.W - 2):
grid[row][col + 1] = 0
else:
north = choice(run)
grid[north[0] - 1][north[1]] = 0
run = []
return grid