在A *遍歷後移除產生最佳路徑的障礙

Question

我使用自己的A *實現遍歷16x16迷宮。

一切都很好。但是，在遍歷之後，我想知道什麼牆會給我提供另一條路徑。除了去除迷宮中的每個塊並重新運行A *，還有什麼更聰明更優雅的解決方案？

我在想每個牆節點（被A *忽略），一個暫定的F值，並且改變節點結構也有一個n大小的列表node *tentative_parent其中n是迷宮中牆的數量。這可能是可行的嗎？

Answer 1

當您將節點添加到要考慮的節點列表中時，還要添加一個標誌，確定通過該節點的路徑是否已經穿過牆壁。

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

然後，當考慮節點可能的路徑，如果它沒有穿過牆壁，考慮相鄰牆壁是公平的路徑。

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

您已經維持到當前正在處理的節點從起始節點的距離，並使用你已經到位。

概念的充分證明：

我們看到operator==定義也考慮道路是否已經撞牆了呢。這使得我們可以在需要的時候考慮一​​個節點兩次，當我們查看閉集時，看看我們是否已經遇到了這個節點。下面來源中示例迷宮的中央走廊就是這種情況。

標記爲#ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL的代碼部分顯示了增強普通A *算法以便能夠穿過單個牆所需的部分。

#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

用於牆面拆除發現候選領域：

一直以來你原來的A *找到的路徑，保留以前距離，每當前面的距離比目前的距離較大，請注意前一個節點有可能去除牆壁。

我認爲它會趕上的最具影響力的情況下：

例1：

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

其中：

R（0,0）是你的兔子看的當然亞軍 g^（2,0）是目標

在這種情況下，我們從（0,0）開始，距離爲2.下一個可用的移動是（0,1），距離爲2.23（sq root 5）。你的距離剛剛增長，這樣你之前的位置就有可能被拆除。

實施例2：

 

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

開始：（0,0） 結束：（6,6） A *課程：（0,0），（1,1），（2,2 ），（3,3），（4,4），（5,5），（6,6） 距離：8.5,7.1,5.7,4.2,2.8,1.4（或72,50,32， 18，8，2） 沒有最佳牆壁去除。

確定要刪除的牆：

畫出你的標記點和你的目標節點之間的線路。沿着該線的第一個牆（最接近標記的節點）下降。給它一些絨毛，以便沿着只會碰到角落的直線對角線去除你的牆。比較你的替代路徑找到最短。