
키워드
어제 이론을 살펴봤다면 오늘은 구현해봤다.
구현
아래 그림과 같이 8 x 8 그리드가 있다.
그리드로 한 이유는 이번 프로젝트에서 써볼 환경이 그리드 환경이라서 그렇다.

휴리스틱 함수 : 맨해튼 거리
휴리스틱 추정값을 구하는 방법이 3개 정도 있다.
- 유클리디안 거리 : 직선 거리 탐색에 유용
- 맨해튼 거리 : 격자형 그래프에서 상하좌우로 움직일 때 적합
- 체스판 거리 : 격자형에서 대각선 이동이 가능할 때 적합
이 중에 맨해튼 거리는 격자형 그래프에서 두 점 간의 거리 계산에 사용되는 방법이다.
이동 방식이 상,하,좌,우 이렇게 네 가지인 경우에 적합하다.
거리 계산 공식
두 점 (x1, y1), (x2, y2)가 있을 때
거리 = | x2 - x1 | + | y2 - y1 |
준비
public class Node
{
public Node parent;
public Vector2Int coord;
public float g;
public float h;
public float cost;
public GameObject obj;
public void RecalculateCost()
{
cost = g + h;
}
}
- 위와 같이 노드 클래스를 미리 준비한다.
- 좌표와 함께 비용 계산에 쓸 g, h, f에 해당하는 변수들도 만들어둔다.
과정
1. 격자 만들기

- 격자 그리드를 만들어준다.
- 사이즈는 8 x 8로 해두었다.
2. 탐색 시작


- 인스펙터에 시작점(0,0)과 목적지(5,4)를 입력해서 탐색을 시작한다.
- 이동 비용은 1로 넣어둔 상태이다.
3. 경로 찾기 : 초기화

- 탐색 예정 노드 목록 openList를 생성한다.
- f값을 통해서 최적값을 구하기 위해서 우선순위 큐를 이용할 수 있다.
- 탐색 완료 노드 목록 closedList를 생성한다.
- 시작 node 초기화
- openList에 시작점을 추가하면서 초기화를 마무리한다.
4. 경로 찾기 (반복) : 탐색

- openList에서 f값(cost)이 가장 작은 것을 꺼내온다.
- 그리고 꺼낸 node의 좌표가 목적지인지 확인해서 탐색 진행 여부를 결정한다.
- 만약 목적지가 아니라면 현재 node는 탐색 완료로 처리한다.
- closedList에 넣음으로써 탐색 완료 처리한다.
5. 경로 찾기 (반복) : 이웃 확인

- 상하좌우의 이웃 좌표를 구한다.
- 유효한 이웃 좌표를 통해 node를 찾는다.
- 만약 이미 탐색한 노드라면 생략한다. (closedList 확인)
- 이웃 노드로 이동했을 때, g값을 미리 계산해둔다.
- 그리고 이 노드가 탐색 중인 것이 아니라면,
g, h값을 갱신하고 부모 노드로 current 노드를 넣는다.
- 이후 openList에 추가해서 비용 검사 대상이 되도록한다.
- 만약에 이미 탐색할 노드인데, 더 나은 경로로 발견했다면 비용과 부모 노드를 갱신한다.
- 더 나은 경로인지 판단할 때, 미리 계산한 g값을 이용한다.
- 이렇게 상하좌우를 다 찾으면 다시 f값(cost)가 가장 작은 노드를 구하고,
목적지인지 확인하는 일련의 과정을 반복한다.

6. 경로 찾기 : 목적지를 찾은 경우

- 목적지를 찾은 경우 현재 노드를 이용해서 경로를 구성한다.

- 현재 노드의 부모 노드를 거슬러 올라가면서 path 리스트를 만든다.
- 단, 이때 방향이 역순이므로 한번 뒤집어주어야한다.
예외. 목적지를 못 찾은 경우

- 어떤 이유로 경로를 못 찾을때 이렇게 null을 반환한다.
결과

- 결과로 이렇게 (5,4) 지점을 찾은 모습이다.
#내일배움캠프 #스파르타내일배움캠프 #스파르타내일배움캠프TIL