Entfernen des Hindernisses, das nach A * den besten Pfad aus einer Karte ergibt

Question

Ich durchquere ein 16x16 Labyrinth mit meiner eigenen A * Implementierung.

Alles ist gut. Nach der Durchquerung möchte ich jedoch herausfinden, welche Wand mir den besten alternativen Weg geben würde. Abgesehen davon, jeden Block zu entfernen und A * auf dem Labyrinth neu zu spielen, was ist eine cleverere und elegantere Lösung?

Ich dachte, geben Sie jeden Wandknoten (ignoriert von A *), ein vorläufiger F-Wert und ändern Sie die Knotenstruktur, um auch eine n-große Liste von node *tentative_parent zu haben, wobei n die Anzahl der Wände im Labyrinth ist. Könnte das machbar sein?

Answer 1

Wenn Sie einen Knoten zur Liste der zu berücksichtigenden Knoten hinzufügen, fügen Sie auch ein Flag hinzu, wenn der Pfad durch diesen Knoten bereits durch eine Wand gegangen ist.

possibleNode.heuristic = currentNode.distance + heuristicEstimate(possibleNode) 
possibleNode.goneThroughWall = currentNode.goneThroughWall || possibleNode.isAWall 
allPossiblePaths.insert(possibleNode) // Priority queue sorted on Node.heuristic 

Dann, wenn mögliche Pfade von einem Knoten unter Berücksichtigung, wenn es nicht durch eine Wand gegangen ist, sollten benachbarte Wände faire Wege sein.

foreach neighborNode in neighbors(someNode) 
    if !(someNode.goneThroughWall && neighborNode.isAWall) 
     addToPossiblePaths(neighborNode) 

Sie haben bereits Abstand halten vom Startknoten zu dem aktuellen Knoten verarbeitet werden, und es verwendet, was Sie bereits an der richtigen Stelle.

Voll proof of concept:

Wir sehen, dass operator== auch definiert ist, zu prüfen, ob der Weg noch eine Wand geschlagen hat. Dadurch können wir den Knoten bei Bedarf zweimal betrachten, wenn wir in der geschlossenen Menge nachsehen, ob wir diesen Knoten bereits gefunden haben. Dies ist der Fall im mittleren Flur im Beispiellabyrinth in der Quelle unten. Die mit #ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL gekennzeichneten Teile des Codes zeigen die Teile, die benötigt werden, um einen normalen A * -Algorithmus zu erweitern, um durch eine einzelne Wand gehen zu können.

#include <cassert> 
#include <algorithm> 
#include <cstdlib> 
#include <iostream> 
#include <set> 
#include <vector> 

#define I_AM_ALLOWED_TO_GO_THROUGH_A_WALL 

const int width = 5; 
const int height = 5; 

// Define maze 
const int maze[height][width] = 
    { { 0, 1, 1, 0, 0 }, 
    { 0, 1, 0, 1, 0 }, 
    { 0, 1, 0, 1, 0 }, 
    { 0, 1, 0, 1, 0 }, 
    { 0, 0, 0, 0, 0 } }; 

// Square represents the actual structure of the maze 
// Here, we only care about where it is, and whether it is a wall 
struct Square { 
    Square(int _x, int _y) 
    : x(_x), y(_y) {} 

    bool operator==(const Square& rhs) const { 
    return x == rhs.x && y == rhs.y; 
    } 

    bool isAWall() const { 
    return maze[y][x]; 
    } 

    int distance(const Square& goal) const { 
    return std::abs(x - goal.x) + std::abs(y - goal.y); 
    } 

    int x; 
    int y; 
}; 

// Define start and end of maze 
const Square goalSquare(3, 0); 
const Square startSquare(0, 0); 

// A PathNode describes the A* algorithm's path through the maze 
// It keeps track of its associated Square 
//     its previous PathNode in the path 
//     the length of the path up to the current PathNode 
//     whether the path so far has goneThroughWall 
struct PathNode { 
    explicit PathNode(const Square& s, int length = 0, const PathNode* _prev = NULL) 
    : square(s), 
     prev(_prev), 
     pathLength(length) { 
    heuristic = pathLength + square.distance(goalSquare); 

#ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL 
    if(prev) 
     goneThroughWall = prev->goneThroughWall || square.isAWall(); 
    else 
     goneThroughWall = false; 

    // Sanity check, these should be the same 
    assert(goneThroughWall == hasGoneThroughAWall()); 
#endif 
    } 

    bool operator<(const PathNode& rhs) const { 
    return heuristic < rhs.heuristic; 
    } 

    // This is very important. When examining the closed set to see 
    // if we've already evaulated this node, we want to differentiate 
    // from whether we got to that node using a path through a wall. 
    // 
    // This is especially important in the given example maze. 
    // Without this differentiation, paths going up column 3 will hit 
    // old, closed paths going through the walls in column 2, and not 
    // find the best path. 
    bool operator==(const PathNode& rhs) const { 
    return square == rhs.square 
#ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL 
     && goneThroughWall == rhs.goneThroughWall 
#endif 
     ; 
    } 

    bool weakEquals(const PathNode& rhs) const { 
    return square == rhs.square; 
    } 

    bool weakEquals(const Square& rhs) const { 
    return square == rhs; 
    } 

    // Sanity checker 
    bool hasGoneThroughAWall() const { 
    if(square.isAWall()) return true; 

    const PathNode* p = prev; 
    while(p) { 
     if(p->square.isAWall()) 
     return true; 
     p = p->prev; 
    } 

    return false; 
    } 

    Square square; 
    const PathNode* prev; 
    int heuristic, pathLength; 
#ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL 
    bool goneThroughWall; 
#endif 
}; 

std::ostream& operator<<(std::ostream& ostr, const PathNode& p) { 
    ostr << "(" << p.square.x << ", " << p.square.y << ")"; 
    if(p.square.isAWall()) 
    ostr << " <- Wall!"; 
    return ostr; 
} 

std::vector<Square> getNeighbors(const Square& s) { 
    std::vector<Square> neighbors; 

    if(s.x > 0) 
    neighbors.push_back(Square(s.x - 1, s.y)); 
    if(s.x < width - 1) 
    neighbors.push_back(Square(s.x + 1, s.y)); 
    if(s.y > 0) 
    neighbors.push_back(Square(s.x, s.y - 1)); 
    if(s.y < height - 1) 
    neighbors.push_back(Square(s.x, s.y + 1)); 

    return neighbors; 
} 

void printList(const PathNode* p, int i = 0) { 
    if(p) { 
    printList(p->prev, i + 1); 
    std::cout << *p << std::endl; 
    } else { 
    std::cout << "Length: " << i << std::endl; 
    } 
} 

typedef std::multiset<PathNode> Set; 

int main(int argc, char** argv) { 
    // Print out maze 
    for(int j = 0; j < height; ++j) { 
    for(int i = 0; i < width; ++i) { 
     std::cout << " " << maze[j][i]; 
    } 
    std::cout << std::endl; 
    } 
    std::cout << std::endl; 

    Set closedSet; 
    Set openSet; 
    openSet.insert(PathNode(startSquare)); // Start node (defined at line ~42) 

    int processedCount = 0; 
    while(!openSet.empty()) { 
    Set::iterator currentNode = openSet.begin(); 
    ++processedCount; 

    // We've found the goal, so print solution. 
    if(currentNode->weakEquals(goalSquare)) { 
     std::cout << "Processed nodes: " << processedCount << std::endl; 
     printList(&*currentNode); 
     return 0; 
    } 

    { 
     // Move from open set to closed set 
     Set::iterator del = currentNode; 
     currentNode = closedSet.insert(*currentNode); 
     openSet.erase(del); 
    } 

    std::vector<Square> neighbors = getNeighbors(currentNode->square); 
    for(unsigned int i = 0; i < neighbors.size(); ++i) { 
     PathNode currentNeighbor(neighbors[i], currentNode->pathLength + 1, &*currentNode); 

     // Skip if it is 2nd wall 
     if(
#ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL 
     currentNode->goneThroughWall && 
#endif 
     currentNeighbor.square.isAWall() 
    ) 
     continue; 

     // Skip if it is already in the closed set 
     // Note: Using std::find here instead of std::multiset::find because 
     // std::multiset::find uses the definition !(a < b) && !(b < a) for 
     // searching. I want it to use my overloaded a == b. 
     if(find(closedSet.begin(), closedSet.end(), currentNeighbor) != closedSet.end()) 
     continue; 

     // Skip if we were just there 
     const PathNode* p = currentNode->prev; 
     if(p && p->weakEquals(currentNeighbor)) 
     continue; 

     // See if there is a better alternative in the open set 
     // Note: Using std::find here instead of std::multiset::find. See above. 
     Set::iterator contender = find(openSet.begin(), openSet.end(), currentNeighbor); 
     if(contender == openSet.end()) 
     openSet.insert(currentNeighbor); 
     else if(currentNeighbor.pathLength < contender->pathLength) { 
     // We've found a better alternative, so replace 
     openSet.erase(contender); 
     openSet.insert(currentNeighbor); 
     } 
    } 
    } 

    std::cout << "Failure." << std::endl; 
    return 1; 
} 

Answer 2

Suche nach Kandidatenbereiche für Wandentfernung:

Entlang Ihrer ursprünglichen A * gefunden Pfad, behalten die vorherigen Abstand, und immer dann, wenn der vorherige Abstand größer ist als der aktuelle Abstand, beachten Sie den vorherigen Knoten mit einem Potenzial für eine Wandentfernung.

Ich behaupte, dass es Fälle von den meisten Auswirkungen fangen:

Beispiel 1:

 
    012 
    ***** 
0 *R*G* 
1 * * * 
2 * * * 
3 * * * 
4 * * * 
5 * * * 
6 * * 
    ***** 

Wo:

R (0,0) ist Ihr Kaninchen schau natürlich Läufer G (2,0) ist das Ziel

In diesem Fall beginnen wir bei (0,0) mit einem Abstand von 2. Die nächste verfügbare Bewegung ist (0,1), mit einem Abstand von 2,23 (Quadratwurzel von 5). Deine Distanz ist gerade gewachsen, so dass dein vorheriger Standort das Potenzial für einen Mauerriss hatte.

Beispiel 2:

 

    ********* 
0 *R*  * 
1 ** * * 
2 * * * * 
3 * * * * 
4 * * * * 
5 * * ** 
6 *  *G* 
    ********* 

Start: (0,0) Ende: (6,6) A * Kurs: (0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) Abstände: 8,5, 7,1, 5,7, 4,2, 2,8, 1,4 (oder Quadratwurzel von 72, 50, 32, 18, 8, 2) Keine optimale Wand zum Entfernen.

Ermitteln der Wand zu entfernen:

Ziehen Sie eine Linie zwischen den markierten Knoten und Ihr Ziel-Knoten. Die erste Wand entlang dieser Linie (am nächsten zum markierten Knoten) geht nach unten. Geben Sie etwas Fuzz, um Ihre Wand entlang einer geraden Diagonale zu entfernen, die nur Ecken treffen würde. Vergleichen Sie Ihre alternativen Wege, um den kürzesten zu finden.