출발-도착을 알고있을 때 최단거리 길찾기 알고리즘의 대표격인 A* 알고리즘.
개념만 알고있었지 정작 구현은 해보지 않았었다.
3D 포트폴리오를 만들 때에도 네비매쉬를 사용했었기 때문에..
토이프로젝트를 진행하면서 타일맵을 사용하는 김에
터치로 자동이동할 수 있으면 좋겠다는 생각이 들어 구현해보기로 했다.
혼자 공부할 때 항상 많은 도움이 되는 고라니님 채널의 영상을 참고했다.
결과
빨간점에서 파란점으로 가는 경로를 Gizmo로 표현한 결과물이다.
호박은 장애물을 의미한다.
구현
핵심 개념은 다음과 같다.
* G : 이동한 거리
* H : 목표까지 남은 거리
* F : G + HF가 최소가 되는 지점을 우선적으로 탐색하는 기법이다.
F의 값이 동일할 때에는 H가 작은 순서로 정렬하여 사용했다.
public int CompareTo(Node other)
{
if (F == other.F)
return H.CompareTo(other.H);
return F.CompareTo(other.F);
}SortedSet을 사용하고 싶었는데 사용을 잘못한건지 결과가 정상적으로 나오지 않았다..
그래서 그냥 Node 클래스에 IComparable<Node> 를 상속했다.
계산을 단순하게 하기 위해 한칸 사이는 10이라는 임의의 값으로 설정했다.
10으로 설정하면 후에 대각선 경로를 추가할 때에 대략적으로 14라는 값을 더해주면 되기 때문에 정수 값으로 계산이 가능하다. (영상 링크 참고)
* G = 10씩 더해줌
* H = (목표까지 남은 가로칸수 + 세로 칸수) * 10
* F = 지금까지 이동한 거리 + 목표까지 남은 거리현재 위치로 이동하기 직전 노드 값을 부모로 저장하기 때문에
최종경로는 해당 부모를 거슬러 올라가면 알 수 있다.
📝 다음에 할 일
- 대각선 이동 구현
- 실제 캐릭터 이동
- 맵 정보 저장 개선
