본문 바로가기
프로그래밍/알고리즘

A* 알고리즘

by 눈야옹 2016. 2. 12.

*여기서 H값은 대각선계산은 하지 않았다.
* G값은 8방향 탐색을 위해 대각선 계산을 하였는데 그값은 1.4 직선은 1이다.

*OL : Open List

*CL : Close List

1. 현재노드 (시작은 Start노드)의 주변 8방향을 OL에 넣는다.

2. 주변 8방향의 노드의 부모를 현재 노드로 설정한다.

3. 주변 노드에 G, H , F 값을 기입한다.

4. 현재 OL에 있는 가장 F값이 낮은 값을 찾고 현재노드는 CL로 가고 찾은 곳을 현재 노드로 설정한다.

5. 현재노드에서 주변 8방향으로 다시 검사를 하데 이미 OL에 들어가 있는 곳을 검사 할경우 원래 가지고 있던 F값보다 작을 경우에만 노드 데이타(F,G,H)를 갱신한다.

6. 계속 가장 F값이 낮은 곳만을 찾아가며 주변노드를 탐색하는 과정을 반복한다.

*tip 만약 벽을 가로질러 가기 싫다면 위아래 좌우에 벽이 있을 경우 G값에 +거리(여기선 1)를 해주면 된다.

7. 이 반복작업 끝에 만약 현재 노드가 도착 지점이 된다면 탐색을 종료 하고, 도착지점 부터 가리키는 부모 노드를 타고 시작지점 까지의 노드를 쭉 연결하면 원하는 길을 찾을수 있다.

*tip2 실 게임에서 AI가 실시간 호출하는것은 부하가 많이 먹으므로 되도록 적게 호출하면서 중간에 RayCast를 이용한 직선 이동을 섞어주자.