forked from mikepound/mazesolving
-
Notifications
You must be signed in to change notification settings - Fork 0
/
mazes.py
112 lines (93 loc) · 2.75 KB
/
mazes.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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class Maze:
class Node:
def __init__(self, position):
self.Position = position;
self.Neighbours = [None, None, None, None];
#self.Weights = [0, 0, 0, 0];
def __init__(self, im):
width = im.width;
height = im.height;
data = list(im.getdata(0));
self.start = None;
self.end = None;
# Top row buffer
topnodes = [None] * width;
count = 0;
# Start row
for x in range (1, width - 1):
if data[x] > 0:
self.start = Maze.Node((0,x));
topnodes[x] = self.start;
count += 1;
for y in range (1, height - 1):
#print ("row", str(y)); # Uncomment this line to keep a track of row progress
rowoffset = y * width;
rowaboveoffset = rowoffset - width;
rowbelowoffset = rowoffset + width;
# Initialise previous, current and next values
prv = False;
cur = False;
nxt = data[rowoffset + 1] > 0;
leftnode = None;
for x in range (1, width - 1):
# Move prev, current and next onwards. This way we read from the image once per pixel, marginal optimisation
prv = cur;
cur = nxt;
nxt = data[rowoffset + x + 1] > 0;
n = None;
if cur == False:
# ON WALL - No action
continue;
if prv == True:
if nxt == True:
# PATH PATH PATH
# Create node only if paths above or below
if data[rowaboveoffset + x] > 0 or data[rowbelowoffset + x] > 0:
n = Maze.Node((y,x));
leftnode.Neighbours[1] = n;
n.Neighbours[3] = leftnode;
leftnode = n;
else:
# PATH PATH WALL
# Create path at end of corridor
n = Maze.Node((y,x));
leftnode.Neighbours[1] = n;
n.Neighbours[3] = leftnode;
leftnode = None;
else:
if nxt == True:
# WALL PATH PATH
# Create path at start of corridor
n = Maze.Node((y,x));
leftnode = n;
else:
# WALL PATH WALL
# Create node only if in dead end
if (data[rowaboveoffset + x] == 0) or (data[rowbelowoffset + x] == 0):
#print ("Create Node in dead end");
n = Maze.Node((y,x));
# If node isn't none, we can assume we can connect N-S somewhere
if n != None:
# Clear above, connect to waiting top node
if (data[rowaboveoffset + x] > 0):
t = topnodes[x];
t.Neighbours[2] = n;
n.Neighbours[0] = t;
# If clear below, put this new node in the top row for the next connection
if (data[rowbelowoffset + x] > 0):
topnodes[x] = n;
else:
topnodes[x] = None;
count += 1;
# End row
rowoffset = (height - 1) * width;
for x in range (1, width - 1):
if data[rowoffset + x] > 0:
self.end = Maze.Node((height - 1,x));
t = topnodes[x];
t.Neighbours[2] = self.end;
self.end.Neighbours[0] = t;
count += 1;
self.count = count;
self.width = width;
self.height = height;