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
# 시간 복잡도는 H에 따라 다르다.
# O(b^d), where d = depth, b = 각 노드의 하위 요소 수
# heapqueue를 이용하면 길을 출력할 때 reverse를 안해도 된다.
class Node:
def __init__(self, parent=None, position=None):
self.parent = parent
self.position = position
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return self.position == other.position
def heuristic(node, goal, D=1, D2=2 ** 0.5): # Diagonal Distance
dx = abs(node.position[0] - goal.position[0])
dy = abs(node.position[1] - goal.position[1])
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
def aStar(maze, start, end):
# startNode와 endNode 초기화
startNode = Node(None, start)
endNode = Node(None, end)
# openList, closedList 초기화
openList = []
closedList = []
# openList에 시작 노드 추가
openList.append(startNode)
# endNode를 찾을 때까지 실행
while openList:
# 현재 노드 지정
currentNode = openList[0]
currentIdx = 0
# 이미 같은 노드가 openList에 있고, f 값이 더 크면
# currentNode를 openList안에 있는 값으로 교체
for index, item in enumerate(openList):
if item.f < currentNode.f:
currentNode = item
currentIdx = index
# openList에서 제거하고 closedList에 추가
openList.pop(currentIdx)
closedList.append(currentNode)
# 현재 노드가 목적지면 current.position 추가하고
# current의 부모로 이동
if currentNode == endNode:
path = []
current = currentNode
while current is not None:
# maze 길을 표시하려면 주석 해제
# x, y = current.position
# maze[x][y] = 7
path.append(current.position)
current = current.parent
return path[::-1] # reverse
children = []
# 인접한 xy좌표 전부
for newPosition in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]:
# 노드 위치 업데이트
nodePosition = (
currentNode.position[0] + newPosition[0], # X
currentNode.position[1] + newPosition[1]) # Y
# 미로 maze index 범위 안에 있어야함
within_range_criteria = [
nodePosition[0] > (len(maze) - 1),
nodePosition[0] < 0,
nodePosition[1] > (len(maze[len(maze) - 1]) - 1),
nodePosition[1] < 0,
]
if any(within_range_criteria): # 하나라도 true면 범위 밖임
continue
# 장애물이 있으면 다른 위치 불러오기
if maze[nodePosition[0]][nodePosition[1]] != 0:
continue
new_node = Node(currentNode, nodePosition)
children.append(new_node)
# 자식들 모두 loop
for child in children:
# 자식이 closedList에 있으면 continue
if child in closedList:
continue
# f, g, h값 업데이트
child.g = currentNode.g + 1
child.h = ((child.position[0] - endNode.position[0]) **
2) + ((child.position[1] - endNode.position[1]) ** 2)
# child.h = heuristic(child, endNode) 다른 휴리스틱
# print("position:", child.position) 거리 추정 값 보기
# print("from child to goal:", child.h)
child.f = child.g + child.h
# 자식이 openList에 있으고, g값이 더 크면 continue
if len([openNode for openNode in openList
if child == openNode and child.g > openNode.g]) > 0:
continue
openList.append(child)
def main():
# 1은 장애물
maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
start = (0, 0)
end = (7, 6)
path = aStar(maze, start, end)
print(path)
if __name__ == '__main__':
main()
# [(0, 0), (1, 1), (2, 2), (3, 3), (4, 3), (5, 4), (6, 5), (7, 6)]
Enter to Rename, Shift+Enter to Preview
