A* 의사코드

원문

priorityqueue Open

list      Closed

 

AStarSearch

     s.g = 0       // s is the start node

     s.h = GoalDistEstimate( s )

     s.f = s.g + s.h

     s.parent = null

     push s on Open

     while Open is not empty

          pop node n from Open  // n has the lowest f

          if n is a goal node

              construct path

              return success

          for each successor n' of n

              newg = n.g + cost(n,n')

              if n' is in Open or Closed,

               and n'.g <= newg

                   skip

              n'.parent = n

              n'.g = newg

              n'.h = GoalDistEstimate( n' )

              n'.f = n'.g + n'.h

              if n' is in Closed

                   remove it from Closed

              if n' is not yet in Open

                   push n' on Open

          push n onto Closed

     return failure  // if no path found

 

 

내맘대로 분석 - 반말이냐? 라고 마음에 상처받지 마시길...

 

//우선순위큐 - 그냥 제일 가능성 높은 노드를 앞에 배치한 open배열이라 생각하자.

priorityqueue Open

//Closed는 그냥 정렬이 필요 없는 배열쯤으로...

list      Closed

 

AStarSearch

    //g의 값은 시작위치에서 자신의 위치까지의 거리이다. 이건 추정치가 아니라 자신이 온

    //만큼의 정확한 수를 가지고 있어야 한다. 처음 시작에서 값이 0인 것은 설명 안하겠

    //다. s 는 시작노드(캐릭터가 있는 노드)

     s.g = 0     

    //GoalDistEstimate(x)는 현재 노드에서 목표까지의 추정거리이다.

    //추정거리는 실제로 계산이 끝난 후 최단 거리보다 길면 안된다. 하지만 현재 노드의 위

    //치에서 목표까지의 직선거리를 h값으로 하면 커질 수 없을 것이다.

    s.h = GoalDistEstimate( s )

    //자신이 걸어온 길과 추정값을 더하여 f를 만든다.

     s.f = s.g + s.h

    //처음 시작이니 부모 노드는 없다. - 자신의 바로 전위치를 링크시키는 거라 생각하

    //라. 나중에 이걸 이용하여 최단거리를 표시하게 된다.

     s.parent = null

 

    //오픈배열에 시작노드를 집어넣는다.

    //위에서 알 수 있듯이 각노드는 g, h, f, parent의 자료를 담고 있다.

     push s on Open

     while Open is not empty //오픈리스트가 비어 있지 않은 한 루프를 돈다.

         //아까 우선순위큐 형식으로 들어간 배열 속의 노드를 꺼낸다.

         //그러니까 open배열 안에서 가장 f값이 적은 놈을 골라내는 것이다.

         //다시 반복해서 말하지만 f값이 작다는 건 그만큼 목표까지 가장 최단거리일 가능

         //성이 농후하다는 말이다.

         //우리가 사람을 첫인상으로 평가할 때 얼굴에 난 기스나 말투, 등으로 이놈 좀 지

         //랄같겠는데... 하고 평가하듯이 그런 놈을 골라 삼청교육대로 보내는 것이다.

         //그런데 얼굴이 험상궂다고 성질이 다 더러운 것은 아니다. A*의 알고리즘의 바

         //로 그런 부분에서 AI의 범주에 들어가는건 아닐까. 추측해 나가면서 목표에 도

         //달한다. 피해자가 속출할 수 있다. 조심하자.

         //그러므로 여기서 n은 가장 낮은 f를 가진 노드 처음에야 선택의 여지가 없

         //지...s(시작노드)를 꺼내온다.

          pop node n from Open 

         //n이 목표노드라면 부모노드들을 가지고 path를 만든다.

         //그리고 성공했다고 만세삼창을 부른다.

          if n is a goal node

              construct path

              return success

       //아래코드들은 목표에 도달 못했을 경우 cpu에게 삽질을 시키는 핵심적인 코드이다.

       //n의 후보 노드들에게 모두 for 루프 안의 명령들을 수행한다.

       //대규모 수색 작업이다. 가능성 있는 곳을 대검으로 쭉쭉 찔러 수색로를 개척하자.

       //아래 그림을 보면 검은색은 장애물이다. 뻘건놈은 현재 노드의 위치이고 보라는

       //보라돌이... 가 아니라 대각선이동을 제한 했을 경우 후보노드들이다.

       //그러니까 대각선 이동이 제한 되었을 경우 후보노드는 아래그림에서는 3개이고 포

       //함했을 때는 6개가 된다.

          for each successor n' of n // n주위의 노드들에게

          //n->n'의 거리와 지금까지 더해온 g를 더한다.

          //그러므로 처음시작위치에서 현재 자신의 위치까지의 실제거리이다.

         

              newg = n.g + cost(n,n') 

         //후보자(n')중에 이미 open이나 closed 배열에 존재(전과기록이 있는놈)하는

         //녀석이 있고 앞서 구한 newg와 n'.g를 비교하여 newg가 크면 스킵한다.

         //다시말해 open에 있다는 얘기는 n'.g가 이미 계산되었다는 말이다.

         //이미 계산된 n'g(open,closed에 있는)와 newg를 비교한다는 말은 open안에

         //들어 있는 녀석의 g값이 새롭게 계산된 g값보다 작다면 그냥 넘어가라는 거다.

         //open안에 들어 있는 녀석이 좀더 범죄적 증거가 많으니까... 그걸 법정에서

         //이용하겠다는 말이다.

              if n' is in Open or Closed,

               and n'.g <= newg

              //flash에서라면 continue에 해당 else에 해당하는 구문을 실행하지

              //않는다.그러니까 다시 g,h,f의 값을 구하지 않는다.

                   skip

            //if조건이 만족하지 못하면 아래를 쭈욱 실행한다.

            //n'에게 있어서 n은 그전에 자기가 있었던 자리이므로 부모로 임명(?)한다.

            //그리고 시작노드에게 했던 고문(?)행위를 실행한다.

              n'.parent = n

              n'.g = newg

              n'.h = GoalDistEstimate( n' )

              n'.f = n'.g + n'.h

             //n'이 닫힌목록에 있을 경우 닫힌 목록에서 삭제한다.

              if n' is in Closed

                   remove it from Closed

             //n'이 아직 열린목록에 없을 때 열린목록에 넣는다.

              if n' is not yet in Open

                   push n' on Open

          //이제 조사가 끝난 노드를 닫힌목록에 넣는다.

          push n onto Closed

     //열린목록이 비어있다면 경로를 못찾는다. 그냥 종료한다.

     return failure  // if no path found

출처 : Tong - mogi879님의 임베디드 소프트웨어 공모대전통