A Star 알고리즘 (길찾기)

준비사항

전체 Map은 2차원 행렬로 구성

출발점(S), 목표지점(D)

openList , closeList 구성.

openList 는 길(Path)의 경로 중 하나가 될 가능성이 열려 있다는 뜻

closeList 는 반대로 이건 더이상 볼 필요 없다는 뜻

맵과, 출발점S, 도착점D, 중앙에 세개의 장애물 존재

출발점을 우선 closeList에 추가한다.

그리고 8방향을 따져봤을때 다 갈수 있음을 알 수 있다.

이 8방향의 부모노드를 출발점으로 세팅해준다.

출발점으로 부터 8방향으로 이동하는 비용을 계산

수직, 수평 이동할 경우 10, 대각선 이동 할 경우 14를 적용한다.

이유는 말하지 않아도 알수있으리라(루트2 == 1.41414….)

비용을 사각 영역 왼쪽 아래에 기록( 이 비용을  R이라고 함 )

또 다른 비용 계산

8방향 각각으로 부터 D까지의 비용을 계산

이번엔 장애물의 존재 여부는 고려치 않고 수직,수평 이동만을 고려해서 계산

(대각이동은 없는 것으로 간주)

비용을 사각 영역 오른쪽 아래에 기록( 이 비용을  H 라고 함 )

총비용 F = R + H 으로 계산

사각 영역 왼쪽 상단에 기록

openList에 들어있는 지점들 중 총 비용이 가장 적은 곳을 선택

이 빨간 지점 중심으로 방금 한 일을 수행할 것이기 때문에

openList에서 제거하고 closeList에 넣는다.

8방향 체크해 보니 새롭게 openList에 넣어야 할 지점이 없다.

이동 불가의 장애물,

closeList에 속한 지점,

이미 openList에 속한 지점 들 뿐이다.

그러나 한가지 확인해야 할 것이 있다.

이미 openList에 속한 지점 중에서 현재 중심이 되고 있는 빨간 지점을 거쳐서 갈 경우

기존의 R값 보다 더 적은 값이 나오는지를 확인해 봐야 한다.

만약 빨간 지점을 경유했을때 더 적은 R값이 나왔다면 기존의 부모노드를 버리고

빨간 지점을 부모노드로 설정해 준다.

여기까지 작업했다면 새로운 중심점을 다시 선택하고 했던 작업을 반복한다. 

목표지점 D가 openList에 들어있는 것을 확인하는 순간 길은 찾아진 것이 된다.

지점D의 부모노드의 부모노드의 부모노드로 거쳐서 올라가다 보면

출발점이 나오기 때문이다.