c++ - A* パスコードでの間違った検索

Question

A* パスを見つけるために書いた C++ コードがいくつかありますが、奇妙な動作をしています。ここにはかなりの量のコードがあるので、いくつかのコードに分割して、何をしているのかを説明しようと思います。A* パスがどのように機能するかについては説明しません。あなたがアルゴリズムをすでに知っているのを助けようとしているなら、私は仮定します。

まず、ノードの h 値を計算するための関数を次に示します。

int
calculateH(int cX, int cY, int eX, int eY, int horiCost = 10, int diagCost = 14) {
int h;
int xDist = abs(eX - cX);
int yDist = abs(eY - cY);

if (xDist > yDist)
    h = (diagCost * yDist) + (horiCost * (xDist - yDist));
else
    h = (diagCost * xDist) + (horiCost * (yDist - xDist));

return h;
}

ここには問題がないと確信しています。かなり単純なもの。

次は Node クラスです。そして、私は知っています、私は知っています、それらの変数を非公開にし、getter を使用します。テスト目的でこのようにしました。

class Node {
public:
Node(int x_, int y_, int g_, int h_, int pX_, int pY_, bool list_) {
    x = x_;
    y = y_;
    g = g_;
    h = h_;
    pX = pX_;
    pY = pY_;
    list = list_;
};
int x, y, g, h, pX, pY;
bool list;
};

各ノードには X 変数と Y 変数があります。F ではなく G と H のみを格納し、必要なときに F を計算します (これは私のコードでは 1 回だけです)。次に、親の X 値と Y 値があります。リストはブール値です。fale = オープンリスト、true = クローズリスト。

Object クラスもあります。ここで重要な変数は X、Y、および Passable だけで、すべて getter を介してアクセスされます。
これが私の実際の経路探索コードの始まりです。以下に示すように、方向に対応する数字の文字列を返します:
432
501
678
したがって、1 は右に移動することを意味し、8 は下と右に移動することを意味し、0 はどこにも行かないことを意味します。

string
findPath(int startX, int startY, int finishX, int finishY) {
// Check if we're already there.
if (startX == finishX && startY == finishY)
    return "0";
// Check if the space is occupied.
for (int k = 0; k < objects.size(); k ++)
    if ((objects[k] -> getX() == finishX) &&
        (objects[k] -> getY() == finishY) &&
        (!objects[k] -> canPass()))
        return "0";
// The string that contains our path.
string path = "";
// The identifier of the current node.
int currentNode = 0;
// The list of nodes.
vector<Node> nodes;
// Add the starting node to the closed list.
nodes.push_back(Node(startX, startY, 0,
    calculateH(startX, startY, finishX, finishY),
    startX, startY, true));

次に、目的地が見つかるまでループします。sizeLimit は、永遠にループしないことを確認するためのものであることに注意してください (このコードを修正できれば問題ありません。現時点では非常に必要です)。この時点から、別の方法でマークするまで、すべてが ij ループ内にあります。

int sizeLimit = 0;
while ((nodes[currentNode].x != finishX) | (nodes[currentNode].y != finishY)) {

    // Check the surrounding spaces.
    for (int i = -1;  i <= 1; i ++) {
        for (int j = -1; j <= 1; j ++) {
            bool isEmpty = true;
            // Check if there's a wall there.
            for (int k = 0; k < objects.size(); k ++) {
                if ((objects[k] -> getX() == (nodes[currentNode].x + i)) &&
                    (objects[k] -> getY() == (nodes[currentNode].y + j)) &&
                    (!objects[k] -> canPass())) {
                    isEmpty = false;
                }
            }

次の部分:

 // Check if it's on the closed list.
            for (int k = 0; k < nodes.size(); k ++) {
                if ((nodes[k].x == (nodes[currentNode].x + i)) &&
                    (nodes[k].y == (nodes[currentNode].y + j)) &&
                    (nodes[k].list)) {
                    isEmpty = false;
                }
            }

続き：

// Check if it's on the open list.
            for (int k = 0; k < nodes.size(); k ++) {
                if ((nodes[k].x == (nodes[currentNode].x + i)) &&
                    (nodes[k].y == (nodes[currentNode].y + j)) &&
                    (!nodes[k].list)) {
                    // Check if the G score is lower from here.
                    if (nodes[currentNode].g + 10 + (abs(i * j) * 4) <= nodes[k].g) {
                        nodes[k].g = nodes[currentNode].g + 10 + (abs(i * j) * 4);
                        nodes[k].pX = nodes[currentNode].x;
                        nodes[k].pY = nodes[currentNode].y;
                    }
                    isEmpty = false;
                }
            }

これは、ij ループの最後の部分です。

if (isEmpty) {
                nodes.push_back(Node(nodes[currentNode].x + i,
                    nodes[currentNode].y + j,
                    nodes[currentNode].g + 10 + (abs(i * j) * 4),
                    calculateH(nodes[currentNode].x + i, nodes[currentNode].y + j, finishX, finishY),
                    nodes[currentNode].x,
                    nodes[currentNode].y,
                    false));
            }
    }
}

ここで、F スコアが最も低いノードを見つけて、それを現在のノードに変更し、クローズドリストに追加します。無限ロッピングに対する保護もここで終了します。

// Set the current node to the one with the lowest F score.
    int lowestF = (nodes[currentNode].g + nodes[currentNode].h);
    int lowestFIndex = currentNode;
    for (int k = 0; k < nodes.size(); k ++) {
        if (((nodes[k].g + nodes[k].h) <= lowestF) &&
            (!nodes[k].list)) {
            lowestF = (nodes[k].g + nodes[k].h);
            lowestFIndex = k;
        }
    }
    currentNode = lowestFIndex;
    // Change it to the closed list.
    nodes[currentNode].list = true;

    sizeLimit ++;
    if (sizeLimit > 1000)
        return "";
}

私が抱えている問題は、特定のパスが見つからないことです。パスが任意の時点で上または左に移動すると、機能しないようです。下、左、右すべて正常に動作します。とにかくほとんどの場合。この問題の原因はまったくわかりません。ある時点で、コードを手動でたどって問題の場所を確認しようとさえしました。うまくいかなかったのも当然です。

もう 1 つ: 中かっこを数えている場合 (まず第一に、思ったよりも献身的です)、最後に右中かっこがないことに気付くでしょう。私のリターンステートメントは言うまでもありません。最後に、省略したパスを実際に作成するためのコードが少しあります。ただし、その部分が問題ではないことはわかっています。現在、コメントアウトしていますが、それでも同じようには機能しません。どこが機能していないかを教えてくれるコードをいくつか追加しましたが、それは解釈ではなくパスファインディング部分にあります。

申し訳ありませんが、私のコードはとても面倒で非効率的です。私は c++ を初めて使用するので、私のテクニックに関する重要なアドバイスも歓迎します。

c++ - A* パスコードでの間違った検索

1 に答える 1

Related

Reference