algorithm
* 길 찾기 알고리즘

소개

A * Pathfinding의 간단한 예 : 장애물이없는 미로

다음 4x4 격자가 있다고 가정 해 봅시다.

이것이 미로 라고 가정합시다. 그러나 벽 / 장애물은 없습니다. 출발점 (녹색 사각형)과 끝점 (빨간색 사각형) 만 있습니다. 초록색에서 붉은 색으로 가려면 대각선으로 이동할 수 없다고 가정 해 봅시다. 그래서 녹색 사각형에서 시작하여 우리가 이동할 수있는 사각형을 확인하고 파란색으로 강조 표시합니다.

다음으로 이동할 사각형을 선택하려면 2 개의 휴리스틱을 고려해야합니다.

1. "g"값 -이 노드가 녹색 사각형과 얼마나 멀리 떨어져 있는지 나타냅니다.
2. "h"값 -이 노드가 빨간색 사각형과 얼마나 멀리 떨어져 있는지 나타냅니다.
3. "f"값 - "g"값과 "h"값의 합입니다. 이것은 어떤 노드로 이동할 지 알려주는 마지막 번호입니다.

이러한 추론을 계산하기 위해 다음 식을 사용합니다. distance = abs(from.x - to.x) + abs(from.y - to.y)

이것은 "Manhattan Distance" 공식으로 알려져 있습니다.

녹색 사각형의 왼쪽 바로 옆에있는 파란색 사각형에 대한 "g"값을 계산해 봅시다 : abs(3 - 2) + abs(2 - 2) = 1

큰! 우리는 다음 값을 얻었습니다 : 1. 이제 h 값을 계산해 봅시다 : abs(2 - 0) + abs(2 - 0) = 4

완전한. 이제 "f"값을 얻습니다. 1 + 4 = 5

따라서이 노드의 최종 값은 "5"입니다.

다른 모든 파란 사각형에 대해서도 동일하게합시다. 왼쪽 상단의 숫자는 "g"값이고 오른쪽 상단의 숫자는 "h"값인 반면 각 사각형의 중앙에있는 큰 숫자는 "f"값입니다.

모든 파란색 노드에 대해 g, h 및 f 값을 계산했습니다. 자, 우리가 뭘 선택하니?

어느 것이 든 가장 낮은 f 값을가집니다.

그러나이 경우에 우리는 같은 f 값을 갖는 2 개의 노드를 갖습니다. 5. 어떻게 그 노드를 선택합니까?

간단히 하나를 선택하거나 우선 순위를 설정하십시오. 나는 보통 이렇게 우선 순위를 선호 : "오른쪽> 위로> 아래로> 왼쪽"

f 값이 5 인 노드 중 하나는 '아래'방향으로, 다른 노드는 '왼쪽'방향으로 이동합니다. Down은 Left보다 우선 순위가 높으므로 우리는 "Down"을 사용하는 사각형을 선택합니다.

이제 우리는 휴리스틱을 계산 한 노드를 주황색으로 표시하고 이동하지는 않았지만 우리가 시안 색으로 선택한 노드를 표시합니다.

좋아, 시안 노드 주위의 노드에 대해 동일한 경험적 방법을 계산해 보겠습니다.

모든 옵션이 동일한 f 값을 가지기 때문에 다시 시안 노드에서 노드를 선택합니다.

시안 노드가 가지고있는 유일한 이웃에 대한 경험적 방법을 계산해 봅시다.

좋아요, 우리는 다음과 같은 패턴을 따를 것이기 때문에 :

다시 한 번 노드의 이웃에 대한 경험적 방법을 계산해 봅시다.

거기로 가자.

마지막으로, 우리는 우리 옆에 승리 한 광장 이 있다는 것을 알 수 있습니다. 그래서 우리는 거기로 이동하고, 우리는 끝납니다.