어떻게 C++로 A*길 찾기 알고리즘 을 실현 합 니까?

1.A*알고리즘 소개
길 을 찾 는 것 은 특정한 출발점 에서 특정한 종점 까지 통과 할 수 있 는 경 로 를 찾 는 것 이다.실제 상황 에서 출발점 과 종점 사이 의 직선 방향 에 장애물 이 있 기 때문에 검색 알고리즘 으로 해결 해 야 한다.
일정한 알고리즘 기반 을 가 진 학생 들 은 특정한 출발점 에서 특정한 종점 까지 깊이 우선 검색(DFS)을 사용 하 는 것 을 알 수 있 습 니 다.DFS 검색 의 검색 방향 은 보통 8 개 방향(경사 방향 검색 이 허용 되 지 않 으 면 4 개)이지 만 우선 순위 가 없습니다.
DFS 검색 이 더욱 효율 적 이 고 욕심 과 결합 할 수 있 도록 검색 방향 에 우선 순 위 를 부여 하고,직관 적 으로 종점 에서 가장 가 까 운 방향(직관 적 으로 장애물 을 무시 한 상태 에서)을 최 우선 검색 방향 으로 하 는 것 이 A*알고리즘 이다.
2.A*알고리즘 절차 분석
(아래 그림 에서 녹색 을 기점 으로 빨간색 은 종점 이 고 파란색 은 통과 할 수 없 는 벽 이다.)

출발점 부터 사방 을 수색 하 다.
(이곳 의 검색 방향 은 8 개 방향 이다)

검색 방향의 우선 순 위 를 구분 하기 위해 검색 할 점 마다 2 개의 값 을 부여 합 니 다.
G 값(소모 치):출발점 에서 이 지점 까지 소모 할 값 을 말 합 니 다.
H 값(예측 치):이 점 에서 종점 까지 의 예측 치(이 점 에서 종점 까지 장애물 을 무시 한 상태 에서 소모 할 값 을 예측 하고 이 점 에서 종점 까지 의 직선 거리의 값 으로 이해 할 수 있 음)
여기 서 값=가 야 할 거리
(실제 적 으로 더 복잡 한 게임 은 지형 이 다 르 기 때문에(예 를 들 어 함정,걷 기 어 려 운 모래땅 등)해당 하 는 서로 다른 가중치 가 있 을 수 있다.값=가 야 할 거리*지형 가중치)
우 리 는 또 한 칸 을 똑바로 가 는 거 리 는 10 과 같 고,한 칸 을 비스듬히 가 는 거 리 는 14 와 같다 고 정의 했다.
F 값(우선 순위):F=G+H
이 공식 은 F 는 출발점 에서 이 점 을 거 쳐 종점 에 도착 하 는 예측 총 비용 이다.F 값 을 계산 하면 F 값 이 가장 작은 방향 을 우선 선택 하여 검색 할 수 있 습 니 다.
(각 점 의 왼쪽 상단 은 F 값,왼쪽 하단 은 G 값,오른쪽 하단 은 H 값)

각 방향의 대응 점 의 F,G,H 값 을 계산 한 후,
이 점 에 현재 노드 의 지침 값 을 부여 해 야 합 니 다.계속 뒤 져 서 종점 을 찾 은 후에 앞의 점 의 지침 이 없 으 면 우 리 는 지난번 에 지나 갈 점 이 어느 점 인지 알 수 없고 종점 까지 가 는 데 소모 되 는 최소 치가 얼마 인지 만 알 수 있 기 때문이다)
그리고 이 점 들 을 openList 에 넣 습 니 다.
그리고 현재 점 을 closeList 에 넣 습 니 다.(목록 닫 기:검색 한 점 을 저장 하고 같은 점 을 중복 검색 하지 않도록 합 니 다)
그리고 openList 에서 F 값 이 가장 작은(최 우선 방향)점 을 꺼 내 똑 같은 검색 을 합 니 다.

검색 과정 에서 검색 방향 에 있 는 점 이 장애물 이거 나 목록 에 있 는 점 을 닫 으 면 건 너 뜁 니 다.
재 귀적 인 검색 을 통 해 여러 차례 검색 한 끝 에 종점 을 찾 았 다.

종점 을 찾 은 후에 앞의 점 의 지침 치 를 통과 하면 우 리 는 종점 에서 한 걸음 한 걸음 통과 하 는 경로 점 을 거 슬러 올 라 갈 수 있다.
(빨간색 은 거 슬러 올 라 가 는 점 을 표시 한다)

3.A*알고리즘 최적화 사고
3.1,openList 우선 대기 열 사용(두 갈래 더미)
openlist(목록 열기)를 볼 수 있 습 니 다.실시 간 으로 추가 점 이 필요 하고 매번 최소 값 의 점 을 꺼 내야 합 니 다.
그래서 우 리 는 우선 대기 열(이 진 더미)을 openList 의 용기 로 사용 할 수 있 습 니 다.
우선 대기 열(이 진 더미):한 점 의 복잡 도 를 O(logN)로 삽입 하고 가장 값 이 복잡 한 점 을 O(logN)로 추출 합 니 다.
3.2.장애물 목록,closeList 는 2 차원 표(2 차원 배열)를 사용한다.
장애물 목록 과 closeList 는 통과 여 부 를 검사 하 는 데 만 사용 되 기 때문에 bool 2 차원 표를 사용 하여 저장 할 수 있 습 니 다.

//      Width Height         
bool barrierList[Width][Height];
bool closetList[Width][Height];

어떤 점(Xa,Yb)이 있 습 니 다.통과 할 수 있 습 니 다.
if(barrierList[Xa][Yb]&&closeList[Xa][Yb])로 판단 합 니 다.
2 차원 표 는 아래 표 로 접근 하기 때문에 효율 이 높 지만 공간 소모 가 비교적 많다.3 차원 지 도 는 3 차원 표를 사용 하면 메모 리 를 더욱 소모 한다.그러나 현재 컴퓨터 는 일반적으로 메모리 공간 이 부족 하지 않 기 때문에 가능 한 한 연산 시간 을 올 리 는 것 을 위주 로 한다)
이것 은 전형 적 인 메모리 공간 을 희생 하여 연산 시간 을 바 꾸 는 예 이다.
3.3 깊이 제한
때때로 검색 해 야 할 경로 가 매우 길 고 A*알고리즘 을 이용 하여 한 번 검색 하 는 데 지불 하 는 대가 가 매우 높 아서 게임 의 중단 을 초래한다.
그러면 매번 검색 이 일정한 대 가 를 초과 하지 않도록 깊이 제한 을 설정 할 수 있 습 니 다.한 번 검색 할 때마다 깊이+1,일정한 깊이 제한 을 찾 아 종점 을 찾 지 못 하면 실패 치 를 반환 합 니 다.
4.A*알고리즘 구현(C+코드)

#include <iostream>
#include <list>
#include <vector>
#include <queue>

struct OpenPoint{
    int x;
    int y;
    int cost;                 //    
    int pred;                 //    
    OpenPoint* father;        //    
    OpenPoint() = default;
    OpenPoint(int pX,int pY, int endX, int endY, int c, OpenPoint* fatherp) : x(pX),y(pY),cost(c), father(fatherp) {
        //    x,y    
        int relativeX = std::abs(endX - pX);
        int relativeY = std::abs(endY - pY);
        //x,y   n
        int n = relativeX - relativeY;
        //   pred = (maxCn)*14+n*10+c
        pred = std::max(relativeX, relativeY) * 14 - std::abs(n) * 4 + c;
    }
};

//   ，             
struct OpenPointPtrCompare {
    bool operator()(OpenPoint* a, OpenPoint* b) {
        return a->pred > b->pred;
    }
};

const int width = 30;            //    
const int height = 100;          //    
char mapBuffer[width][height];   //    
int depth = 0;                   //    
const int depthLimit = 2000;     //    
bool closeAndBarrierList[width][height];    //     +       
//     
int direction[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{ -1,1 },{ -1,-1 },{ 1,-1 } };
//        
std::priority_queue<OpenPoint*, std::vector<OpenPoint*>, OpenPointPtrCompare> openlist;
//  OpenPoint     
std::vector<OpenPoint> pointList = std::vector<OpenPoint>(depthLimit);

//            
inline bool inBarrierAndCloseList(int pX,int pY) {
    if (pX < 0 || pY < 0 || pX >= width || pY >= height)
        return true;
    return closeAndBarrierList[pX][pY];
}

//       
inline OpenPoint* createOpenPoint(int pX,int pY,int endX,int endY, int c, OpenPoint* fatherp) {
    pointList.emplace_back(pX,pY,endX,endY, c, fatherp);
    return &pointList.back();
}

//     ，     
void open(OpenPoint& pointToOpen, int endX,int endY) {
    //     openlist  
    openlist.pop();
    //  +1
    depth++;
    //  p     
    for (int i = 0; i < 4; ++i)
    {
        int toOpenX = pointToOpen.x + direction[i][0];
        int toOpenY = pointToOpen.y + direction[i][1];
        if (!inBarrierAndCloseList(toOpenX,toOpenY)) {
            openlist.push(createOpenPoint(toOpenX, toOpenY, endX,endY, pointToOpen.cost + 10, &pointToOpen));
        }
    }
    for (int i = 4; i < 8; ++i)
    {
        int toOpenX = pointToOpen.x + direction[i][0];
        int toOpenY = pointToOpen.y + direction[i][1];
        if (!inBarrierAndCloseList(toOpenX, toOpenY)) {
            openlist.push(createOpenPoint(toOpenX, toOpenY, endX, endY, pointToOpen.cost + 14, &pointToOpen));
        }
    }
    //    closelist
    closeAndBarrierList[pointToOpen.x][pointToOpen.y] = true;
}

//      
std::list<OpenPoint*> findway(int startX,int startY, int endX,int endY) {
    std::list<OpenPoint*> road;
    //           
    openlist.push(createOpenPoint(startX,startY, endX,endY, 0, nullptr));
    OpenPoint* toOpen = nullptr;
    //                   
    while (!openlist.empty())
    {
        toOpen = openlist.top();
        //      ，     
        if (toOpen->x == endX && toOpen->y ==endY) {break;}//       (1000  )，     
        if (depth >= depthLimit) {
            toOpen = nullptr;
            break;
        }
        open(*toOpen, endX,endY);
    }
    for (auto rs = toOpen; rs != nullptr; rs = rs->father) {road.push_back(rs);}
    return road;
}

//    
void createMap() {
    for (int i = 0; i < width; ++i)
        for (int j = 0; j < height; ++j) {
            //           ，   
            if (rand() % 5 == 0) {
                mapBuffer[i][j] = '*';
                closeAndBarrierList[i][j] = true;
            }
            else {
                mapBuffer[i][j] = ' ';
                closeAndBarrierList[i][j] = false;
            }
        }
}

//    
void printMap() {
    for (int i = 0; i < width; ++i) {
        for (int j = 0; j < height; ++j)
            std::cout << mapBuffer[i][j];
        std::cout << std::endl;
    }
    std::cout << std::endl << std::endl << std::endl;
}

int main() {
    //  
    int beginX = 0;
    int beginY = 0;
    //  
    int endX = 29;
    int endY = 99;
    //    
    createMap();
    //             
    mapBuffer[beginX][beginY] = mapBuffer[endX][endY] = ' ';
    closeAndBarrierList[beginX][beginY] = closeAndBarrierList[endX][endY] = false;
    //A*        
    std::list<OpenPoint*> road = findway(beginX,beginY,endX,endY);
    // A*            'O'
    for (auto& p : road){mapBuffer[p->x][p->y] = 'O';}
    //         
    printMap();
    system("pause");
    return 0;
}

예제 효과:

이상 은 C++로 A*길 찾기 알고리즘 을 어떻게 실현 하 는 지 에 대한 상세 한 내용 입 니 다.C+A*길 찾기 알고리즘 에 관 한 자 료 는 저희 의 다른 관련 글 을 주목 하 세 요!