Loại bỏ các chướng ngại vật mang lại đường đi tốt nhất từ ​​bản đồ sau khi đi qua A *

Question

Tôi đi qua một mê cung 16x16 bằng cách thực hiện A * của riêng tôi.

Tất cả đều tốt. Tuy nhiên, sau khi đi qua, tôi muốn tìm ra bức tường nào sẽ cho tôi con đường thay thế tốt nhất. Ngoài việc loại bỏ mọi khối và chạy lại A * trên mê cung, giải pháp thông minh và thanh lịch hơn là gì?

Tôi đã suy nghĩ cung cấp cho mọi nút tường (bỏ qua A *), giá trị F dự kiến ​​và thay đổi cấu trúc nút để có danh sách n số node *tentative_parent trong đó n là số tường trong mê cung. Điều này có thể là khả thi?

Answer 1

Khi bạn thêm nút vào danh sách các nút cần xem xét, cũng thêm cờ cho dù đường dẫn qua nút đó đã đi qua tường.

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

Sau đó, khi xem xét các đường dẫn có thể từ nút, nếu nó không đi qua tường, hãy xem xét các bức tường liền kề là đường dẫn công bằng.

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

Bạn đã phải duy trì khoảng cách từ nút bắt đầu đến nút hiện tại đang được xử lý và sử dụng nút mà bạn đã có sẵn.

bằng chứng đầy đủ về khái niệm:

Chúng ta thấy rằng operator== được định nghĩa cũng phải xem xét có hay không con đường đã đánh một bức tường được nêu ra. Điều này cho phép chúng ta xem xét một nút hai lần nếu cần thiết, khi chúng ta nhìn vào tập hợp đóng để xem liệu chúng ta đã gặp phải nút này chưa. Đây là trường hợp ở hành lang trung tâm trong mê cung mẫu trong nguồn dưới đây.

Các phần mã được đánh dấu bằng #ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL hiển thị các phần cần thiết để tăng thêm thuật toán A * bình thường để có thể đi qua một bức tường đơn.

#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

Tìm khu vực ứng cử viên cho việc loại bỏ tường:

Tất cả cùng một gốc * con đường tìm thấy, giữ lại khoảng cách trước, và bất cứ khi nào khoảng cách trước là lớn hơn so với khoảng cách hiện tại, lưu ý các nút trước vì có khả năng loại bỏ tường.

tôi gửi rằng nó sẽ bắt các trường hợp của hầu hết các tác động:

Ví dụ 1:

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

đâu:

R (0,0) là thỏ tìm kiếm của bạn dĩ nhiên Á hậu G (2,0) là mục tiêu

Trong trường hợp này, chúng ta bắt đầu tại (0,0), với khoảng cách là 2. Động thái có sẵn tiếp theo là (0,1), với khoảng cách 2,23 (sq gốc của 5). Khoảng cách của bạn chỉ tăng lên, để vị trí trước đó của bạn có tiềm năng cho một bức tường đổ nước mắt xuống.

Ví dụ 2:

 

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

bắt đầu: (0,0) End: (6,6) A * khóa học: (0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) Khoảng cách: 8,5, 7,1, 5,7, 4,2, 2,8, 1,4 (hoặc thư mục gốc của 72, 50, 32, 18, 8, 2) Không có tường tối ưu để loại bỏ.

Xác định mà tường để loại bỏ:

Vẽ một đường giữa nút đánh dấu của bạn và nút mục tiêu của bạn. Bức tường đầu tiên dọc theo đường thẳng đó (gần nhất với nút được đánh dấu) sẽ bị hỏng. Cung cấp cho nó một số lông tơ để cho phép loại bỏ bức tường của bạn dọc theo một đường chéo thẳng mà sẽ chỉ nhấn góc. So sánh các đường dẫn thay thế của bạn để tìm đường đi ngắn nhất.