A* 알고리즘 방식

A* 알고리즘 방식

---

1. 시작사각형에서 검색된 인접사각형들을 열린목록에 넣습니다.

2. 다음의 과정들을 반복합니다.

   a) 열린목록에서 가장 낮은 F 비용을 찾아 현재사각형으로 선택합니다.

   b) 이것을 열린목록에서 꺼내 닫힌목록으로 넣습니다.

   c) 현재 사각형에 인접한 8 개의 사각형에 대해

● 만약 인접한사각형이 갈수없는 것 이거나 그것이 닫힌목록상에 있다면 무시, 그렇지 않은것은 다음을 계속합니다.

● 만약 이것이 열린목록에 있지 않다면, 이것을 열린목록에 추가하고. 이 사각형의 부모를 현재 사각형으로 만듭니다. 사각형의 F,G,H 비용을 기록.

● 만약 이것이 이미 열린목록에 있다면, G비용을 이용하여 이 사각형이 더 나은가 알아보고, 그것의 G비용이 더 작으면 그것이 더 나은 길이라는 것을 의미하므로 부모 사각형을 그 (G비용이 더 작은 ) 사각형으로 바꿉니다, 그리고 그 사각형의 G,F비용을 다시 계산합니다. 만약 여러분의 열린목록을 F비용으로 정렬하고 있다면 바뀐것에 따라서 열린목록을 다시 정렬해야합니다.

   d) 그만해야 할 때

● 길을 찾는 중 목표사각형을 열린목록에 추가하였을때,

● 열린목록이 비어있게 될 경우.

(이때는 목표사각형을 찾는데 실패한것인데 이 경우 길이 없는경우입니다.)

[참고] 더 자세한 내용을 알고 싶을 경우에