-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSolveMaze.py
executable file
·161 lines (154 loc) · 6.3 KB
/
SolveMaze.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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
from OpenList import OpenList
from OpenListInFavorOfSmallerG import OpenListInFavorOfSmallerG
class SolveMaze:
def forward_A_star(self, start_node, goal_node, actual_maze, w):
start_node.update_g(0)
start_node.update_h(goal_node)
goal_node.update_g(float("inf"))
open_list = OpenList()
open_list.insert(start_node)
closed_list = set()
while open_list.is_empty() is False:
current = open_list.del_min()
if current == goal_node:
return
if current in closed_list:
continue
closed_list.add(current)
w.inClosed(current)
#w.master.update()
for i in range(0, 4):
child = current.traverse_children(i)
if child is None: continue
if child.cost != 1: continue
if child in closed_list: continue
if open_list.contains(child) is False:
child.update_g(float("inf"))
child.update_h(goal_node)
if child.g > current.g + child.cost:
newG = current.g + child.cost
child.update_g(newG)
child.parent = actual_maze[current.x][current.y]
open_list.insert(child)
w.inOpen(child)
# w.master.update()
w.master.update()
if open_list.is_empty() is True and goal_node not in closed_list:
return 0
return 1
def forward_A_star_in_favor_of_smaller_g(self, start_node, goal_node, actual_maze, w):
start_node.update_g(0)
start_node.update_h(goal_node)
goal_node.update_g(float("inf"))
open_list = OpenListInFavorOfSmallerG()
open_list.insert(start_node)
closed_list = set()
while open_list.is_empty() is False:
current = open_list.del_min()
if current == goal_node:
return
if current in closed_list:
continue
closed_list.add(current)
w.inClosed(current)
#w.master.update()
for i in range(0, 4):
child = current.traverse_children(i)
if child is None: continue
if child.cost != 1: continue
if child in closed_list: continue
if open_list.contains(child) is False:
child.update_g(float("inf"))
child.update_h(goal_node)
if child.g > current.g + child.cost:
newG = current.g + child.cost
child.update_g(newG)
child.parent = actual_maze[current.x][current.y]
open_list.insert(child)
w.inOpen(child)
# w.master.update()
w.master.update()
if open_list.is_empty() is True and goal_node not in closed_list:
return 0
return 1
def backward_A_star(self, start_node, goal_node, actual_maze, w):
goal_node.update_g(0)
goal_node.update_h(start_node)
start_node.update_g(float("inf"))
open_list = OpenList()
open_list.insert(goal_node)
closed_list = set()
while open_list.is_empty() is False:
current = open_list.del_min()
if current == start_node:
return
if current in closed_list:
continue
closed_list.add(current)
w.inClosedB(current)
#w.master.update()
for i in range(0, 4):
child = current.traverse_children(i)
if child is None: continue
if child.cost != 1: continue
if child in closed_list: continue
if open_list.contains(child) is False:
child.update_g(float("inf"))
child.update_h(start_node)
if child.g > current.g + child.cost:
newG = current.g + child.cost
child.update_g(newG)
child.parent = actual_maze[current.x][current.y]
open_list.insert(child)
w.inOpen(child)
# w.master.update()
w.master.update()
if open_list.is_empty() is True and start_node not in closed_list:
return 0
return 1
def adaptive_A_star(self, start_node, goal_node, lastClosedList, w):
lastGoalCost = goal_node.g
start_node.update_g(0)
if lastGoalCost == float("inf"):
start_node.update_h(goal_node)
else:
start_node.update_hnew(lastGoalCost)
goal_node.update_g(float("inf"))
open_list = OpenList()
open_list.insert(start_node)
closed_list = set()
while (open_list.is_empty() is False):
current = open_list.del_min()
if current == goal_node:
closed_list.add(current)
lastClosedList.update(closed_list)
return 1
if current in closed_list: continue
closed_list.add(current)
w.inClosed(current)
# w.master.update()
for i in range(0, 4):
child = current.traverse_children(i)
if child is None: continue
if child.cost != 1: continue
if child in closed_list: continue
if open_list.contains(child) == False:
if ( len(lastClosedList)==0 and lastGoalCost == float("inf")) or (child.h == 0):
child.update_h(goal_node)
elif child in lastClosedList:
if (child.f < lastGoalCost):
child.update_hnew(lastGoalCost)
child.update_g(float("inf"))
if child.g > current.g + child.cost:
newG = current.g + child.cost
child.update_g(newG)
child.parent = current
open_list.insert(child)
w.inOpen(child)
# w.master.update()
# w.master.update()
w.master.update()
lastClosedList.update(closed_list)
if open_list.is_empty() is True and goal_node not in closed_list:
return 0
return 1