[Algorithm] A* 길찾기 알고리즘 구현

미로에서의 길 찾기

벽 짚고 따라가기는 방법을 사용한다.

오른쪽 또는 왼쪽의 노드가 벽인지 판단하고 벽이라면 한칸 이동하는 방법을 사용한다. 그렇다면 결국에는 출구에 도착한다( 미로에 경우 )

목적지에 도착은 하지만 최단경로는 찾을 수 없다.

 

최단경로 찾기 - 너비 우선 탐색

1. 시작 칸을 큐에 추가한다.
2. 시작 칸에 표시를 한다(방문했다는 증거)
3. 큐에서 맨 앞 노드를 뽑아낸다.
4. 현재 칸이 목표이면 알고리즘 종료.
5. 현재 칸의 자식들 중에 방문표시가 없으면 그 칸들의 이전 포인터를 현재포인터로 설정하고 큐에 추가한다.
6. 알고리즘이 종료될 때 까지 3~5 반복한다.

 

문제점

대각선이동과 수평이동의 크기가 같다고 판정하기 때문에 대각이동을 많이 하게 된다. 그렇게 되면 실제 거리를 재었을 때 더 길 수 있다.

해결책

1. 방문순서의 변경
    방문순서를 수평이동이 우선시 되게 한다. 방문순서가 다르면 길도 달라진다.
2. 거리의 반영
    목적지와의 거리를 체크해서 거리가 가장 가까운 곳 먼저 방문한다.
    큐를 지속적으로 정렬하면 방문 우선순위가 변경된다.

 

너비 우선 길찾기 구현 코드

각 칸의 정보를 담는 클래스

 

큐에 칸의 정보를 저장할 때 필요한 것만 저장하기 위한 클래스

 

비교 함수

다음 칸을 찾기 위한 함수

 

 

초기화

각 칸을 초기화 해주는 함수

 

 

FindDistance 거리찾기 함수

 

 

상수들

일부 계산들의 속도개선을 위한 상수

 

 

길찾기 알고리즘

 

매우 길지만 내가 이해한것들을 주석으로 처리하여 놓았다.

 

이 알고리즘의 문제점은 항상 모든 노드를 검사하는 것이다. 그로 인해 속도도 느리다.

더 효율적인 탐색을 위해 휴리스틱 값을 이용하자.

 

새로운 휴리스틱 함수를 구현하였다.

 

주석을 잘못 썻다.

인접한 방향으로의 방향값을 더해준 뒤 목적지와 거리를 구해서 리턴한다.

 

기존 BFS 길찾기 알고리즘에서 cur.heuristic = dist 만 수정해준다.