코드는 일단 이렇습니다.

#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

// 오픈리스트에 자식타일 추가하기

// 비용 검사하여 더 작은 비용으로 업데이트

염치 불구하고 질문드립니다. 감사합니다 도와주세요~~

#Algorhythm

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