[Daily Contents] A star 알고리즘

MAP

• S에서 E까지 가는 최단경로

- 평행 이동거리 : 10
- 대각선 이동거리 : 14
- 평행한 이웃 Node가 Block >> 대각선 방향으로 이동 X

Node 4-state

- Close : 가본 곳
- Open : 발견됨, 가 봐야 될 곳
- Empty : 미 발견됨, 안 가봄
- Block : 갈 수 없는 곳

Step

Step 1

S1 : 도착한 노드는 CLose state

Step 2

S2 : 주변 Node 탐색, State에 따라

- EMPTY => OPEN state
- BLOCK => Nothing(대각선 Node 포함)
- CLOSE => Nothing
- OPEN => -G 값이 작다 => 부모 Node 바꿈
		  -G 값이 크다 => Nothings

Step 3

S3 : Open Node 중, 최소 F값 Node로 이동

- G : 출발지에서 이동한 거리
- H : 도착지까지 남은 거리 => 멘하튼 Distance 방식, 직교하는 거리
- F = G + H

Step 1~3

• 반복하여 수행
• 도착 Node를 찾으면 Success

Failed Case

• 반복해도 Open Node는 줄어들고 Close Node만 많아지다가 모든 노드가 Close Node로 바뀐 후 Fail

Source URL

• https://github.com/sweetchild222/vanilla-algorithm

data = [
	0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, -1, 0, 0, 0,
    0, 0, 0, 0, -1, 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]

widrh = 8
height = 6

start = Point(2, 3)
stop = Point(6, 3)

map = Map(data, width, height, stop)
node = aStar(start, stop, map)

while node:
	print(node.getPoint())
    node = node.getParent()

(6, 3)
(6, 2)
(5, 1)
(4, 1)
(3, 1)
(3, 2)
(2, 3)

class State(Enum):
	EMPTY = 0
    OPEN = 1
    CLOSE = 2
    BLOCK = 3

class Node:
	def __init__(self, point, h):
    	self.state = State.EMPTY
        self.point = point
        self.h = h
        self.parent = None

def aStar(start, stop, nodeMap):
	openList = OpenList()
    node = map.getNode(start)
    while True:
    	node.setClose()
        if node.getPoint() == stop:
        	return node
        childList = lookAround(node, nodeMap)
        openList.append(childList)
        node = openList.minCostFnode()
        if node is None:
        	return None

• S1 : 도착한 Node는 Close state
• S2 : 주변 Node 탐색, State에 따라…
• S3 : Open Node 중, 최소 F값 Node로 이동

def lookAround(node, map):

    childDelta = [Point(1, 0), Point(1, -1), Point(0, -1), Point(-1, -1),
                 Point(-1, 0), Point(-1, 1), Point(0, 1), Point(1, 1)]

    openList = []

    for delta in childDelta:

        childPoint = node.getPoint() + delta
        childNode = map.getNode(childPoint)

        if childNode is None:
            continue

        if neighborBlock(node, delta, map) is True:
            continue

        if childNode.isBlock():
            continue
        elif childNode.isClose():
            continue
        elif childNode.isEmpty():
            childNode.setParent(node)
            childNode.setOpen()
            openList.append(childNode)
        elif childNode.isOpen():
            currentCostG = childNode.costG()
            newCostG = childNode.calcCostG(node)
            if currentCostG > newCostG:
                childNode.setParent(node)
        else:
            print('error!')

    return openList

S2 : 주변 Node 탐색, State에 따라

- EMPTY => OPEN state
- BLOCK => Nothing(대각선 Node 포함)
- CLOSE => Nothing
- OPEN => -G 값이 작다 => 부모 Node 바꿈
		  -G 값이 크다 => Nothings