8

独自の A* 実装を使用して、16x16 の迷路を横断します。

すべては順調です。ただし、トラバーサルの後、どの壁が最善の代替パスを提供してくれるかを調べたいと思います。すべてのブロックを削除し、迷路で A* を再実行する以外に、より賢く洗練されたソリューションは何ですか?

node *tentative_parentすべての壁ノード (A* によって無視される) に仮の F 値を与え、ノード構造を変更して、nが迷路内の壁の数である nサイズのリストも持つように考えていました。これは実行可能でしょうか？

4

2 に答える 2

3

考慮するノードのリストにノードを追加するときは、そのノードを通るパスがすでに壁を通過しているかどうかのフラグも追加します。

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==パスがまだ壁にぶつかったかどうかも考慮するように定義されていることがわかります。これにより、必要に応じてノードを 2 回考慮することができます。閉集合を調べて、このノードに既に遭遇しているかどうかを確認します。これは、以下のソースの例の迷路の中央の廊下の場合です。

でマークされたコードの部分は#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;
}
于 2010-03-22T07:07:36.550 に答える
1

壁の除去の候補領域を見つける：

元のA*で見つかったパスに沿って、前の距離を保持します。前の距離が現在の距離よりも大きい場合は、前のノードに壁が削除される可能性があることに注意してください。

私はそれが最も影響のあるケースを捕らえることを提出します：

例1：

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

どこ：

R（0,0）はあなたのウサギのようなコースランナーですG（2,0）はゴールです

この場合、距離2の（0,0）から開始します。次に利用可能な移動は、距離2.23（5の平方根）の（0,1）です。あなたの距離はちょうど伸びたので、あなたの以前の場所は壁が壊れる可能性がありました。

例2：

    0123456
   *********
 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の平方根）削除する最適な壁がありません。

削除する壁の決定：

マークされたノードとゴールノードの間に線を引きます。その線に沿った最初の壁（マークされたノードに最も近い）が下がっています。角にしか当たらない真っ直ぐな対角線に沿って壁を取り外せるように、ファズを付けます。代替パスを比較して、最短のパスを見つけます。

于 2010-03-22T02:58:09.653 に答える