Unity 2D AStar
AStar Algorithm
다음과같은 a*알고리즘을 구성하는데 wall은 제외하고 노드와 구성하는 계산만 구하는 식을 학습하였다.
A*알고리즘이란
F : 총 이동거리
G : 현재 이동거리
H : 남은 이동거리
세가지를 통해서 노드를 연결하고 해당 노드들을 통해 최단거리를 구하는 방법이다.
다익스트라 알고리즘과 비슷한데 두개의 차이점은 다익스트라의 경우 넓은 범위를 모두 돌다가 목표지점과 마주칠 때 거리를 계산하고,
A*의 경우 예상치(H - 휴리스틱)를 통해 목표지점만을 위해 범위를 구성하고 단거리를 구하는 알고리즘이다.
1) 다익스트라
2) A*
한칸에 10의 단위라고 치고 대각선은 14라고 하겠다 시작지점부터 이동했을 경우 다음과같이 주변 노드에 F,G,H 값을 넣고 계산했을한다.
이 때 F가 제일 작은 노드를 선택해서 진행한다(F값이 동일할경우 H값으로 계산)
G : 이동거리는 시작 지점으로 부터 선택한 노드에 따른 이동거리를 뜻하고
H : 목표지점 까지의 추정치로 벽을 제외하고 목표지점까지의 거리를 뜻한다
계산 하게 된다면
이떄 시작지점에서 기준점이 노란 동그라미로 변하게 되고 노란 동그라미 기준으로 기존의 계산했던 노드를 제외하고 계산하게된다.
현재 노란동그라미에서 모두 벽에 가로막히게 된다면, 이 노드들을 제외하고 나머지 노드에서 F가 제일 작은 노드를 선택하게된다
이런 형태로 구성된다.
스크립트
마지막 노드가 목표지점을 닿았을경우 해당 노드의 위치를 부모를 통해 반환받도록 설정했다.
휴리스틱을 구하는 함수로 현재 노드와 목표지점 까지의 거리를 반환한다
map의 최대 크기를 넘어서지 못하도록 설정하고, map의 x,y위치에서 벽이라면 false를 반환하도록 설정했다.
1) FindPath
Node를 선언해주고 노드에 구성요소 F (G + H), G,H 와 목표지점에 도착했을 때 연결해줄 부모노드를 저장하고, 현재 위치의 거리를 Vector2Int형태로 저장하기 위해 Position을 구성해준다.
생성자로 위치를 받아와서 노드의 위치와, G의 초기값으로 최대 값을 넣어준다.
한칸의 경우 x,y중 하나가 1, -1이 될 것이고, 대각선의 경우 x,y가 모두 1,-1의 값을 가질것이다.
경로를 통해 map의 정보를 받아 벽의 정보를 받아올 것이고 start,goal 지점의 정보를 받아 올 것이다.
첫번째 노드의 초기화로 거리를 0, H를 휴리스틱 함수를 가져와서 시작지점과 목표지점의 거리를 가져오고 리스트와 딕셔너리에 시작지점의 정보를 담는다.
nodeList.Count가 0이 되는 시점에서 더이상 탐색 할 노드가 없으니 while문을 종료하고 목표지점까지 갈 수 없음을 리턴한다(null)
Sort는 nodeList에서 (a,b)를 비교해서 노드의 F값이 최소가 되는 지점을 인덱스 0으로 바꾸는 작업을 진행한다 만약 F가 동일할경우 a,b의 H를 비교해서 최소값을 인덱스 0 의 지점으로 보낸다.
정렬한 nodeList에서 인덱스 0의 지점을 선택하고 이 인덱스를 현재 노드로 지정한 다음 nodeList에서 없애준다
다음 Vector2Int를 현재노드의 Position 에서 dir만큼 더하고 nextPos에 할당한다.
만약 다음 위치가 벽이거나 map의 크기를 넘어선다면 while문의 초기로 가도록 설정 하였다.
x,y의 절댓값이 모두 1일때 대각선으로 이동하게 되는데
다음과 같은 상황에서 대각선으로 목표지점에 도달할 수 있으면 안되기 때문에 제외하는 if문이다.
이를 다음 방향이 가로와 세로 모두 막혀있을 경우 continue를 통해 while문으로 다시 돌아간다.
그리고 Directions에 따른 이동거리를 계산하는데 여기서 moveCost는 G값에 더하는 값으로 x,y의 값중 하나라도 0이라면 1, 그외에는 1.4로 설정했다.
newG의 경우 현재노드에서 moveCost만큼 더한 값이다.
만약 모든 노드를 저장하는 딕셔너리에 nextPos가 없다면 새로운 노드를 딕셔너리에 넣어준다.
newG의 경우에는 다음 노드의 G의 값에 해당하고, 이 때 if문을 사용해서 nextNode.G가 클경우는 처음 초기화 작업 때 시작지점의 G값을 MaxValue를 넣어줫기 때문에 다음과같은 작업을 진행했다.
다음 G를 newG로 H를 다음 위치부터 목표지점까지의 거리를, 부모를 현재 노드로 만약 nodeList에 nextNode가 포함되어있지 않다면 추가해주고,
return null의경우 FindPath함수에서 목표지점을 찾을 수 없을 때(모두 가로막힐경우) null을 반환하도록 하였다,
실행결과
PathList에서 해당 Node만 저장해야하는데 이전의 노드들도 저장하고 있기 때문에 바로 길을 찾지 못했다 이를 수정하는 방법을 생각해서 정리를 다시 해봐야겠다.
