Eliminando el obstáculo que produce la mejor ruta desde un mapa después de A * recorrido

Question

Atravieso un laberinto 16x16 utilizando mi propia implementación A *.

Todo está bien. Sin embargo, después del recorrido, me gustaría saber qué pared me daría el mejor camino alternativo. Además de eliminar cada bloque y volver a ejecutar A * en el laberinto, ¿qué es una solución más inteligente y elegante?

Estaba pensando dar cada nodo de pared (ignorado por A *), un valor F tentativo, y cambiar la estructura del nodo para tener también una lista n-size de node *tentative_parent donde n es el número de paredes en el laberinto. ¿Podría esto ser viable?

Answer 1

Cuando agrega un nodo a la lista de nodos a considerar, también agregue un indicador de si la ruta a través de ese nodo ya pasó por una pared.

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

A continuación, al considerar los posibles caminos de un nodo, si no ha pasado por una pared, considere las paredes adyacentes a ser caminos justos.

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

que ya tiene para mantener la distancia desde el nodo inicial al nodo actual está procesando, y utiliza lo que ya tiene en su lugar.

prueba completa del concepto:

Vemos que operator== se define también considerar si es o no el camino ha chocado contra un muro aún. Esto nos permite considerar un nodo dos veces si es necesario, cuando buscamos en el conjunto cerrado para ver si ya hemos encontrado este nodo. Este es el caso en el pasillo central en el ejemplo de laberinto en la fuente a continuación.

Las partes del código marcadas con #ifdef I_AM_ALLOWED_TO_GO_THROUGH_A_WALL muestran las partes necesarias para aumentar un algoritmo A * normal para poder atravesar una única pared.

#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

Encontrar áreas candidatas para la eliminación de la pared:

A lo largo de su original A * camino encontrado, retener el distancia previa, y siempre que la distancia anterior es mayor que la distancia actual, tenga en cuenta el nodo anterior como un potencial para la eliminación de una pared.

que sostienen que se captura los casos de mayor impacto:

Ejemplo 1:

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

Dónde:

R (0,0) es el corredor curso de conejo de aspecto G (2,0) es el objetivo

En este caso, comenzamos en (0,0), con una distancia de 2. El siguiente movimiento disponible es (0,1), con una distancia de 2.23 (raíz cuadrada de 5). Su distancia simplemente creció, por lo que su ubicación anterior tenía potencial para derribar una pared.

Ejemplo 2:

 

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

de inicio: (0,0) End: (6,6) Un curso *: (0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6) Distancias: 8.5, 7.1, 5.7, 4.2, 2.8, 1.4 (o raíz cuadrada de 72, 50, 32, 18, 8, 2) Sin pared óptima para eliminar.

La determinación de qué pared para quitar:

trazar una línea entre el nodo y el nodo marcado gol. La primera pared a lo largo de esa línea (más cercana al nodo marcado) baja. Dale un poco de pelusa para poder quitar la pared a lo largo de una diagonal recta que solo golpearía las esquinas. Compare sus caminos alternativos para encontrar el más corto.