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
# Time Complexity는 H에 따라 다르다.
# O(b^d), where d = depth, b = 각 노드의 하위 요소 수
# heapque를 이용하면 길을 출력할 때 reverse를 안해도 됨
import heapq # priority queue
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 __lt__(self, other):
return self.f < other.f
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 = []
closedSet = set()
# openList에 시작 노드 추가
heapq.heappush(openList, startNode)
# endNode를 찾을 때까지 실행
while openList:
# 현재 노드 지정
currentNode = heapq.heappop(openList)
closedSet.add(currentNode.position)
# 현재 노드가 목적지면 current.position 추가하고
# current의 부모로 이동
if currentNode == endNode:
path = []
while currentNode is not None:
path.append(currentNode.position)
currentNode = currentNode.parent
return path[::-1]
# 인접한 xy좌표 전부, DFS
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], currentNode.position[1] + newPosition[1])
# 미로 maze index 범위 안에 있어야함
if nodePosition[0] > len(maze) - 1 or nodePosition[0] < 0 or nodePosition[1] > len(maze[0]) - 1 or nodePosition[1] < 0:
continue
# 장애물이 있으면 다른 위치 불러오기
if maze[nodePosition[0]][nodePosition[1]] != 0:
continue
new_node = Node(currentNode, nodePosition)
# 자식이 closedList에 있으면 continue
if new_node.position in closedSet:
continue
# f, g, h값 업데이트
new_node.g = currentNode.g + 1
new_node.h = heuristic(new_node, endNode)
new_node.f = new_node.g + new_node.h
# 자식이 openList에 있으고, g값이 더 크면 continue
# new_node.g >= child.g 로 하면 openList 중복성을 줄일 수도 있습니다.
# 하지만 이건 시나리오에 따라 다르고, 대부분 엄격히 더 낮은 g 값을 확인하면 충분할 수 있습니다.
if any(child for child in openList if new_node == child and new_node.g > child.g):
continue
heapq.heappush(openList, new_node)
def main():
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
