Ricerca male in un * Codice pathing

Question

Ho qualche codice C ++ che ho scritto per trovare un A * percorso, ma è comportarsi in modo strano. C'è un po 'di codice qui, quindi mi dividerlo in pezzi e cercare di spiegare quello che sto facendo. Non ho intenzione di spiegare come un * opere pathing. Suppongo che se si sta cercando di aiutare si conosce già l'algoritmo.

Prima di tutto, ecco la mia funzione per il calcolo del valore di un nodo 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;
}

Sono abbastanza sicuro che non c'è nessun problema qui; roba abbastanza semplice.

Classe

Avanti mia Nodo. E so, lo so, fare getter queste variabili private e uso; Ho appena fatto in questo modo a scopo di test.

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;
};

Ogni nodo ha una variabile X e Y. Ho unico negozio G e H, senza F, e calcolare F quando ne ho bisogno (che è solo una volta nel mio codice). Poi ci sono i valori Capogruppo X e Y. List è un valore booleano:. Fale = lista aperta, vero = chiuso elenco

Ho anche un classe Object. Le uniche variabili che importa qui sono X, Y, e Accettabile, tutte accessibili tramite getter.
Ora ecco l'inizio del mio codice pathfinding vero e proprio. Si restituisce una stringa di numeri corrispondenti alle direzioni come illustrato di seguito:
432
501
678
Quindi 1 significa spostarsi a destra, 8 significa andare verso il basso e destra, 0 significa non vanno da nessuna parte.

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));

Ora ciclo attraverso fino a trovare la destinazione. Si noti che SizeLimit è solo per assicurarsi che non ciclo per sempre (non ci vorrà se posso risolvere questo codice. A partire da ora è molto necessario). Tutto da questo punto in poi, fino a quando ho marchio in caso contrario, è dentro il loop i j.

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;
                }
            }

parte successivo:

 // 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;
                }
            }

Continuando su:

// 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;
                }
            }

Questa è l'ultima parte del ciclo j i:

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));
            }
    }
}

Ora troviamo il nodo con il punteggio più basso F, cambiarlo nel nodo corrente, e aggiungerlo alla lista chiusa. La protezione contro la potatura infinito è anche finito qui:

// 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 "";
}

Il problema che sto avendo è che non si trovano alcuni percorsi. Sembra non funzionare se il percorso sale o lasciato in qualsiasi momento. Giù, sinistra, destra e tutti bene il lavoro. Il più delle volte, comunque. Non ho assolutamente idea di che cosa sta causando questo problema; ad un certo punto ho anche provato manualmente dopo il mio codice per vedere dove fosse il problema. Nessuna sorpresa che non ha funzionato.

E ancora una cosa: se si sta contando le mie parentesi graffe (prima di tutto wow, avete più impegno di quanto pensassi), si noterà che mi manca una parentesi di chiusura alla fine. Per non parlare la mia dichiarazione di ritorno. C'è un po 'di codice alla fine di fare effettivamente il percorso che ho lasciato fuori. So che quella parte non è il problema tuttavia; Io attualmente ho è commentata e non ha ancora il lavoro nello stesso modo. Ho aggiunto un po 'di codice per me dove non funziona dirlo, ed è in parte pathfinding, non l'interpretazione.

Ci dispiace il mio codice è così disordinata e inefficiente. Sono nuovo di C ++, in modo da tutto il consiglio critico sulla mia tecnica è il benvenuto pure.

Answer 1

Credo che quando si sta cercando per il prossimo "nodoCorrente", non si dovrebbe iniziare con lowestF = (nodes[currentNode].g + nodes[currentNode].h); perché quel valore, in linea di principio, sarà (sempre) sia inferiore o uguale a tutti gli altri nodi del open-set . Basta partire con il valore di std::numeric_limits<int>::max() o qualche numero molto grande, o utilizzare una coda di priorità, invece di un std::vector per memorizzare i nodi (come std::priority_queue o boost::d_ary_heap_indirect).

Sono abbastanza sicuro che è il problema. E dal momento che il vostro euristica può spesso essere uguale al percorso-distanza effettiva ottenuto, c'è una buona probabilità che seguenti nodi del open-set risultano avere lo stesso costo (g + h) come nodoCorrente. Questo spiegherebbe perché alcuni percorsi vengono esplorate e gli altri non lo fanno e perché si blocca.