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

1
코드는 일단 이렇습니다.   #include "stdafx.h"   #define TileSize 2 #define NOFIND NULL   // 커서를 콘솔 x,y 좌표로 이동. void gotoxy(int x, int y) {         COORD pos = { x, y };         SetConsoleCursorPosition(GetStd..

코드는 일단 이렇습니다.

 

#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

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

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

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

C++ C Algorhythm astar
HanB28 2018-10-30
+
HanB28 님께서 2018-10-30에 API에 올린 질문

댓글

조회수 891
답글 0
URL