どうやってC++でA*道探しのアルゴリズムを実現しますか？

一、A*アルゴリズムの紹介
道を探して、つまりある起点からある終点までのパスを見つけます。実際の状況では、始点と終点の間の直線方向に障害物が多いので、検索のアルゴリズムが必要です。
あるアルゴリズムの基礎を持っている学生は、ある起点からある終点までは通常深さ優先検索（DFS）を使い、DFS検索の検索方向は一般的に8方向であることを知っていますが、優先順位はありません。
DFS検索をより効率的にするために、欲張り思想と結びつけて、検索方向に優先順位を付けました。直観的に終点から一番近い方向（視覚的には障害物を無視した場合）を最優先的に検索する方向です。これがAアルゴリズムです。
二、A＊アルゴリズムステップの解析
（次の図のように、緑を起点とし、赤を終点とし、青は不可通過の壁です。）

スタートから四方を検索する。
（ここの検索方向は8方向）

検索方向の優先度を区別するために、検索するポイントごとに2つの値を付与します。
G値（消費値）：出発点からその点まで歩くのに必要な値です。
H値（予測値）：この点から終点までの予測値（この点から終点までは障害物を無視して予測に要する値を指し、その点から終点までの直線距離の値も理解できる）
ここでは、値=歩く距離
（実際には、より複雑なゲームは、地形が違っています。（例えば、トラップや歩きにくい砂地など）、それぞれの権利があります。
また、まっすぐ歩く距離は10に等しく、斜めに歩く距離は14に等しいと定義しています（45°斜め方向の長さ=sqrt（10^2+10^2）≒14）。
F値（優先度値）：F=G+H
この公式の意味：Fは起点からこの点を通って終点に到達する予測の総消費額です。F値を計算することにより、F値が一番小さい方向を優先的に選択して検索することができます。
（各点の左上はF値、左下はG値、右下はH値）

各方向の対応点のF，G，H値を算出した後、
これらの点には、現在のノードのポインタ値（経路をさかのぼるために）も与える必要がある。まっすぐに検索して終点まで行ったら、前の点の指針がないと、前回の経過はどの点なのか分かりません。終点まで行くと最終的に消費する最小値はいくらなのかだけ分かります。
その後、これらの点をopenListに入れます。（リストを開けます。検索できる点を保存します。）
次に現在の点をcloseListに入れる（リストを閉じる：検索済みの点を保存し、同じ点を重複して検索しないようにする）
そして、openListからF値が一番小さい（最優先方向）の点を取り出し、上記同様の検索を行います。

検索中、検索方向の点が障害物かリスト内の点がオフになったらスキップします。
再帰的な検索によって、何度も検索した結果、最終的にゴールを見つけました。

終点まで探して、そして前の点の針の値を通して、終点から一歩ずつ通過する経路点を追跡することができます。
（赤いマークは遡及点です）

三、A*アルゴリズムの最適化構想
3.1、openListは優先列（二叉山）を使用する。
openlist（オープンリスト）が見られます。リアルタイムで追加して、最小値のポイントを毎回取り出す必要があります。
したがって、優先列（二叉積）をopenListの容器として使用することができます。
優先キュー（二叉ヒープ）：一点を挿入する複雑度はO（logN）で、一番値の複雑度はO（logN）です。
3.2、障害物リスト、closeListは二次元表（二次元配列）を使用する。
障害物リストとcloseListは通過可能かどうかを検出するためだけに使用されますので、ブック二次元テーブルを使用して保存することができます。

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

ある点（Xa，Yb）があります。通過できます。
if(barrier List[Xa]、[Yb]&close List[Xa][Yb]で判断します。
二次元表は下付きでアクセスするので、効率は高いですが、スペースの消耗が多いです。三次元地図は三次元表を使うとメモリが消耗します。でも、今はコンピューターは普通メモリのスペースが足りないので、できるだけ計算時間を上げるようにしています。
これは典型的なメモリ空間を犠牲にして演算時間を交換する例である。
3.3、深さ制限
時には、非常に長いパスを検索するには、Aアルゴリズムを使用して、非常に高い価格でゲームのカートンを作成します。
検索するたびに一定の価格を超えないようにするために、深さ制限を設定し、検索するごとに深さ＋1を検索し、深さ制限があるまではゴールが見つからない場合は、失敗値を返します。
四、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*に関して道を探しますアルゴリズムの資料に関して私達のその他の関連している文章に注意して下さい！