//假設(shè)已經(jīng)定義Width和Height分別為地圖的長和寬
bool barrierList[Width][Height];
bool closetList[Width][Height];

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

struct OpenPoint{
    int x;
    int y;
    int cost;                 // 耗費值
    int pred;                 // 預(yù)測值
    OpenPoint* father;        // 父節(jié)點
    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;
        //預(yù)測值pred = (max–n)*14+n*10+c
        pred = std::max(relativeX, relativeY) * 14 - std::abs(n) * 4 + c;
    }
};

//比較器，用以優(yōu)先隊列的指針類型比較
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];   //地圖數(shù)據(jù)
int depth = 0;                   //記錄深度
const int depthLimit = 2000;     //深度限制
bool closeAndBarrierList[width][height];    //記錄障礙物+關(guān)閉點的二維表
//八方的位置
int direction[8][2] = { {1,0},{0,1},{-1,0},{0,-1},{1,1},{ -1,1 },{ -1,-1 },{ 1,-1 } };
//使用最大優(yōu)先隊列
std::priority_queue<OpenPoint*, std::vector<OpenPoint*>, OpenPointPtrCompare> openlist;
//存儲OpenPoint的內(nèi)存空間
std::vector<OpenPoint> pointList = std::vector<OpenPoint>(depthLimit);

//是否在障礙物或者關(guān)閉列表
inline bool inBarrierAndCloseList(int pX,int pY) {
    if (pX < 0 || pY < 0 || pX >= width || pY >= height)
        return true;
    return closeAndBarrierList[pX][pY];
}

//創(chuàng)建一個開啟點
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();
}

// 開啟檢查，檢查父節(jié)點
void open(OpenPoint& pointToOpen, int endX,int endY) {
    //將父節(jié)點從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;
    // 創(chuàng)建并開啟一個父節(jié)點
    openlist.push(createOpenPoint(startX,startY, endX,endY, 0, nullptr));
    OpenPoint* toOpen = nullptr;
    //重復(fù)尋找預(yù)測和花費之和最小節(jié)點開啟檢查
    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;
}

//創(chuàng)建地圖
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;
    //創(chuàng)建地圖
    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*搜索的路徑經(jīng)過的點標(biāo)記為'O'
    for (auto& p : road){mapBuffer[p->x][p->y] = 'O';}
    //打印走過路后的地圖
    printMap();
    system("pause");
    return 0;
}