A* 알고리즘

//IDIM * JDIM 배열 8*6 배열
const int IDIM = 8;
const int JDIM = 6;
const int NDIR = 4;

const int iDir[NDIR] = { 1, 0, -1, 0 };
const int jDir[NDIR] = { 0, 1, 0, -1 };

int squares[IDIM][JDIM];

//닫힌목록
int clostNodes[IDIM][JDIM];
//열린목록
int openNodes[IDIM][JDIM];

//방향표시 맵..동쪽 0, 북쪽 1, 서쪽 2, 남쪽 3
int dirMap[IDIM][JDIM];

//x,y좌표를 대신하는것...row열과 col행으로..
struct Location
{
 int row, col;
 Location()
 {
  row = col = 0;
 };
 Location(int r, int c)
 {
  row = r;
  col = c;
 };
};

//노드
class Node
{
 //현재 위치
 int rPos;
 int cPos;
 
 //누적되는 G거리의 양..+=해줘야함..
 int GValue;

 //G값과 휴리스틱 h값을 더한거..이 값이 가장 낮은걸 찾아야해..
 int FValue;

public:
 Node(const Location &loc, int g, int f)
 {
  rPos = loc.row;
  cPos = loc.col;
  GValue = g;
  FValue = f;
 }
 Location getLocation() const
 {
  return Location(rPos, cPos);
 }

 int getGValue() const
 {
  return GValue;
 }

 int getFValue() const
 {
  return FValue;
 }

 //F값을 계산하는 함수 매개변수로 현재위치를 넣지요..왜냐면
 //h값을 계산해야하니까..
 void calculateFValue(const Location& locDest)
 {
  FValue = GValue + getHValue(locDest) * 10;
 }

 //G값을 계산하는데 방향을 판단해서 대각 14 직선 10으로 계산
 //i는 위의 jdir이나 idir이 들어갈듯..
 void updateGValue(const int &i) //i : direction
 {
  GValue += (NDIR == 8 ? (i % 2 == 0 ? 10 : 14) : 10);
 }
 
 //휴리스틱 구하는 함수
 const int& getHValue(const Location& locDest) const
 {
  //이 함수내에서 전역처럼 사용하고 싶다는 의미로 static
  static int rd, cd, d;
  //현재 열에서 매개변수의 열을 뺌
  rd = locDest.row - rPos;
  //현재 행에서 매개변수의 행을 뺌
  cd = locDest.col - cPos;

  //맨하탄 방식인데..
  //abs는 절대값..
  d = abs(rd) + abs(cd);
  return d;
 }

 //우선순위 큐의 F값을 위해서 node에 operator< 연산자 구현
 friend bool operator<(const Node& a, const Node& b)
 {
  return a.getFValue() > b.getFValue();
 }
};

//A스타 알고리즘 부분..
string pathFind(const Location& locStart, const Location& locFinish)
{
 //static은 이 함수내에서 전역처럼 쓰고 싶다는 의미
 static priority_queue<Node> q[2];

 static int qi;
 static Node* pNode1;
 static Node* pNode2;

 static int i, j, row, col, iNext, jNext;
 static char c;
 qi = 0;

 //노드를 담는곳을 초기화한다.
 for (j = 0; j < JDIM; j++)
 {
  for (i = 0; i < IDIM; i++)
  {
   clostNodes[i][j] = 0;
   openNodes[i][j] = 0;
  }
 }

 //Pnode1를 시작노드로 설정
 //locStart위치 0g값 0f값
 pNode1 = new Node(locStart, 0, 0);
 //F값을 구하는데 이때 기준은 최종목적지 기준으로
 //함수안에서는 g값 + h값인데 h값도 매개변수를 휴리스틱 최종목적지
 //근데 시작값이라 별 의미없음 g값 0에(누적없음) h값만 존재
 pNode1->calculateFValue(locFinish);
 q[qi].push(*pNode1);

 //반복문
 //우선순위큐를 오픈리스트???
 while (!q[qi].empty())
 {
  //우선순위큐에서 가장 f값이 작은것을 토대로
  //pNode1을 다시 메모리 할당하는 작업..값들 모두
  pNode1 = new Node(q[qi].top().getLocation(), q[qi].top().getGValue(), q[qi].top().getFValue());

  row = pNode1->getLocation().row;
  col = pNode1->getLocation().col;

  //f값이 가장 작은 현재 위치를 표시
  cout << "row, col" << row << " " << col << endl;

  q[qi].pop();
  //오픈리스트에서 제거하는게 0으로 대입..
  //해당 열과 행을 이용해서(즉 위치..)
  openNodes[row][col] = 0;

  //오픈노드에서 꺼내서 닫힌노드로 넣는과정..1이 넣었다는
  //똑같이 해당 열과 행을 이용해서(즉 위치..)
  clostNodes[row][col] = 1;

  //목표 도달했을떄
  if (row == locFinish.row && col == locFinish.col)
  {
   cout << endl;
   //역순으로 길을 찾기위해서 for문이 조금이상함
   //j는 큰숫자에서 작은숫자로...우에서 좌로
   for (j = JDIM - 1; j >= 0; j--)
   {
    //이건 작은숫자에서 큰숫자?
    for (i = 0; i < IDIM; i++)
    {
     cout << dirMap[i][j];
    }
    cout << endl;
   }
   cout << endl;

   string path = "";
   while (!(row == locStart.row && col == locStart.col))
   {
   }

   delete pNode1;
   while (!q[qi].empty())
    q[qi].pop();

   return path;
  }

  //이동방향에 대해 노드탐색 열린노드 ? 장애물? 아예처음?
  //방향에 따라 for문이 돌아감
  for (i = 0; i < NDIR; i++)
  {
   //예상 방향위치에 대해 계산
   iNext = row + iDir[i];
   jNext = col + jDir[i];

   //사각형 squares범위내에 있다면..
   //또는 squeares의 갈수 없는곳 1과 closenodes에 포함되어(1)
   //있지 않다면..
   if (!(iNext<0 || iNext > IDIM - 1 || jNext < 0 || jNext > JDIM - 1
    || squares[iNext][jNext] == 1 || clostNodes[iNext][jNext] == 1))
   {
    //방향에대해서 주변 자식노드를 생성하는데..
    //이때 매개변수는 위치는 예상 방향위치
    //g값을 pnode1부터 누적된 g값 f값은 일단 그냥넣음..
    pNode2 = new Node(Location(iNext, jNext), pNode1->getGValue(), pNode1->getFValue());
    //해당방향으로의 g값을(node1부터 누적된) 누적 최신화
    pNode2->updateGValue(i);
    //이에따라 g값이 위에 변했고 h도 위치가 틀려졌으니 최신 f값을 다시 구함
    pNode2->calculateFValue(locFinish);

    //pNode2의 위치가 오픈노드에 포함되어 있지 않은거라면..
    if (openNodes[iNext][jNext] == 0)
    {
     //open노드에 pnode2의 f값을 넣음..
     openNodes[iNext][jNext] = pNode2->getFValue();
     //왜 우선순위 큐에 넣으나면..
     //이게 오픈노드이니까..f값 최소로 뽑아주잖아..
     //위에 opennodex는 해당 방향에 대해 먼가 저장을 위해..
     q[qi].push(*pNode2);

     //부모 노드의 방향을 표시..
     dirMap[iNext][jNext] = (i + NDIR / 2) % NDIR;

    }

    //예상위치에 기존값이 있고(오픈노드에 값이 있고..)
    //이 값이 새로운 pNode2->f값보다 클 경우에..
    else if (openNodes[iNext][jNext] > pNode2->getFValue())
    {
     //더 작은 node2의 f값으로 최신화함
     openNodes[iNext][jNext] = pNode2->getFValue();

     //더 값이 적으니까..부모방향도 다시 바꿈
     //방향표시 맵..동쪽 0, 북쪽 1, 서쪽 2, 남쪽 3
     //예를들어 for이 0이라면 x방향으로 1이므로 오른쪽인데..
     //예상위치기준으로는 서쪽에서 온거니까 값은 2
     //for문이 1이면? 예상위치 기분으로 남쪽에서 오니 부모는
     //3 남쪽
     dirMap[iNext][jNext] = (i + NDIR / 2) % NDIR;
    }

    //row y col x
    while (!(q[qi].top().getLocation().row == iNext &&
     q[qi].top().getLocation().col == jNext))
    {
     q[1 - qi].push(q[qi].top());
     q[qi].pop();
    }

    q[qi].pop();
   }
  }
 }
};