코드는 일단 이렇습니다. #include "stdafx.h" #define TileSize 2 #define NOFIND NULL // 커서를 콘솔 x,y 좌표로 이동. void gotoxy(int x, int y) { COORD pos = { x, y }; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE), pos); } // // Tile Class // class CTile { private: bool m_bMarked; // 검색 여부 체크 bool m_bBlock; // 이동 불가 타일 체크 int G; // 시작-현재타일 사이 비용 int X; // 타일의 좌표 int Y; int m_nLastX; // 검색된 이전 칸 인덱스 int m_nLastY; public: bool check; CTile() :m_bBlock(0), m_bMarked(0), check(0), m_nLastX(NULL), m_nLastY(NULL), G(0){} ~CTile(){}; void SetG(int m_G) { G = m_G; } void SetFrontTile(int px, int py) { m_nLastX = px; m_nLastY = py; } void SetMarked(bool pM) { m_bMarked = pM; } void SetBlock(bool pB) { m_bBlock = pB; } void SetPos(int px, int py) { X = px; Y = py; } bool GetMarked() { return m_bMarked; } bool GetBlock() { return m_bBlock; } int GetG() { return G; } int GetFX() { return m_nLastX; } int GetFY() { return m_nLastY; } int GetX() { return X; } int GetY() { return Y; } }; // 길 찾은 후 저장할 STL list<CTile*> g_Loop; // 길찾기 g 값 비교 할 find 참조 구조체 struct sort_list_f_g { bool operator() (CTile* n1, CTile* n2) const { return n1->GetG() < n2->GetG(); } }; // // Tile Map Class // class CTilemap { private: int m_nWidth, m_nHeight; // 맵 가로, 세로 사이즈 CTile* m_pMapdata; // 맵 배열 list<CTile*> Open_list; // 오픈리스트 public: CTilemap() :m_nHeight(NULL), m_nWidth(NULL), m_pMapdata(NULL) {} CTilemap(int pW, int pH) :m_nHeight(pH), m_nWidth(pW){ m_pMapdata = new CTile[m_nWidth*m_nHeight + m_nWidth]; } ~CTilemap() { if (m_pMapdata) delete[] m_pMapdata; m_pMapdata = NULL; } // 텍스트 타일맵 파일 읽고 맵 배열에 저장 bool SetMapdata(const TCHAR* filename) { FILE* pf; _tfopen_s(&pf, filename, _T("rt")); TCHAR BlockIndex[128]; int x, y; for (y = 0; y<m_nHeight; y++) { if (!(_fgetts(BlockIndex, 128, pf))) { fclose(pf); return false; } for (x = 0; x<m_nWidth; x++) { (m_pMapdata + (y*m_nWidth + x))->SetBlock((BlockIndex[x] == '0' ? true : false)); (m_pMapdata + (y*m_nWidth + x))->SetPos(x, y); } } fclose(pf); return true; } // 콘솔에 타일 맵 데이터 그리기 void DrawMap() { int x, y; for (y = 0; y<m_nHeight; y++) { for (x = 0; x<m_nWidth; x++) { // 이동 가능 타일 ▨, 이동 불가능 타일 ■ gotoxy(x * 2, y); cout << ((m_pMapdata + (y*m_nWidth + x))->GetBlock() ? "▨" : "■"); } } } // A* 길찾기 경로가 있으면 목표지점 리턴하고 없으면 Null 리턴 CTile* findpath(int& StartingX, int& StartingY, int& GoalX, int& GoalY) { list<CTile*>::iterator itor = Open_list.begin(); list<CTile*>::iterator End = Open_list.end(); int x = StartingX; int y = StartingY; int inX; int inY; bool Cell_is = true; // 검사해야될 타일인지 여부 체크 변수 int TempG; // 중간 비용 변수 CTile* Goal = (m_pMapdata + GoalY * m_nWidth + GoalX); CTile* Son = NULL; Open_list.push_back((m_pMapdata + StartingY * m_nWidth + StartingX)); itor = Open_list.begin(); (*itor)->SetFrontTile(x, y); // 목적지와 시작점이 같거나 목적지가 이동불가 지역일 경우 실패 리턴 if (*itor == Goal || Goal->GetBlock() == false) return NOFIND; // 오픈리스트가 있을경우 길찾기 시작! or 계속 while (!(Open_list.empty())) { // 첫번째 타일 꺼내기 itor = Open_list.begin(); while ((*itor)->check == true) { if (itor == End) return NOFIND; itor++; } (*itor)->check = true; x = (*itor)->GetX(); y = (*itor)->GetY(); // 현재 타일을 기준으로 상하좌우 타일에 대하여 검사 for (inY = y - 1; inY <= y + 1; inY++) { for (inX = x - 1; inX <= x + 1; inX++) { // 부모 타일인 경우 건너뜀; if (inX == x && inY == y) continue; // 검사 타일이 배열 밖이면 건너뜀; if (!(inY*m_nWidth + inX >= 0 && inY*m_nWidth + inX < m_nWidth*m_nHeight + m_nWidth)) continue; // 상하좌우 검색 시에 대각선 타일이 이동불가 타일이면 건너뜀; if (abs(x - inX) + abs(y - inY) == 2) { // 이동불가 타일인 경우에 대한 조건 완성 if( ) continue; // } // 경계에 있을시 다음 or 이전 줄로 이동하는 것 방지 if (inX == x - 1) Cell_is = x != 0; else if (inX == x + 1) Cell_is = x != m_nWidth - 1; // // 중간 비용 계산을 위하여 대각선인 경우 14, 수평,수직인 경우 10 TempG = // // 오픈리스트에 저장할 자식타일이 있을 경우 if (Cell_is) { Son = (m_pMapdata + (inY*m_nWidth + inX)); // 자식타일이 이동불가 타일과 검색한 적이 없다면 if (Son->GetBlock()) { if (Son->GetMarked() == false) { // 오픈 리스트에 저장할 정보 Son->SetFrontTile(x, y); Son->SetG(TempG); Son->SetMarked(true); Son->SetPos(inX, inY); // // 오픈리스트에 자식타일 추가하기 // // 목표지점일 경우 리턴 if (Son == Goal) return Son; } else { // 검색한 적이 있는 타일의 경우 if (Son->GetG() > (*itor)->GetG() + TempG) { // // 비용 검사하여 더 작은 비용으로 업데이트 // // 부모타일로 업데이트 Son->SetFrontTile(x, y); } } } } } } // 비용 g가 제일 작은 순으로 정렬. Open_list.sort(sort_list_f_g()); } // 길을 찾지 못했을 경우 NULL 리턴 return NOFIND; } // 길찾기 함수 실행후 리턴받은 값으로 STL 리스트 작성. bool FindLoop(int& StartingX, int& StartingY, int& GoalX, int& GoalY) { CTile* Temp = findpath(StartingX, StartingY, GoalX, GoalY); if (Temp != NOFIND) { while (Temp != (m_pMapdata + StartingY*m_nWidth + StartingX)) { g_Loop.push_front(Temp); Temp = (m_pMapdata + Temp->GetFY()*m_nWidth + Temp->GetFX()); } return true; } return false; } }; void main() { list<CTile*>::iterator itor = g_Loop.begin(); list<CTile*>::iterator End = g_Loop.end(); char key; bool loop = true; // 타일맵 그리기 CTilemap* p_Map = new CTilemap(16, 16); if (!(p_Map->SetMapdata("MapAstar.txt"))) return; p_Map->DrawMap(); // 시작점, 끝점 int StartX, StartY, GoalX, GoalY; StartX = 4; StartY = 7; GoalX = 12; GoalY = 8; gotoxy(StartX * 2, StartY); cout << "S"; gotoxy(GoalX * 2, GoalY); cout << "E"; gotoxy(2, 17); cout << "Press AnyKey for 1 Step"; gotoxy(5, 18); cout << "or SpaceBar for All Step"; // 루프 찾기 p_Map->FindLoop(StartX, StartY, GoalX, GoalY); itor = g_Loop.begin(); // 찾은 루프를 시작점부터 끝점까지 그리기 while (itor != End) { if (loop) key = getch(); if (key == ' ') loop = false; // 찾은 길 "○"표시 gotoxy((*itor)->GetX() * 2, (*itor)->GetY()); cout << "○"; itor++; } // 길찾기 후 콘솔의 커서위치 재설정 gotoxy(0, 20); delete p_Map; } 상당히 긴 편인데요. 궁금한 부분은 이렇습니다. // 이동불가 타일인 경우에 대한 조건 완성 // 중간 비용 계산을 위하여 대각선인 경우 14, 수평,수직인 경우 10 // 오픈리스트에 자식타일 추가하기 // 비용 검사하여 더 작은 비용으로 업데이트 염치 불구하고 질문드립니다. 감사합니다 도와주세요~~

HanB28

통계

질문A STAR 알고리즘 관련 문제입니다. 전반적인 구현은 여기저기서 어떻게든 했는데. 몇 군데에서 안되는 부분이 있습니다. 도움을 주신다면 정말 감사하겠습니다.