Help us understand the problem. What is going on with this article?

[DTL]A*アルゴリズムによる海上の経路探索🚢

⚓最短航路の作成⚓

astar2.gif

今回は自動生成したワールドデータに航路を自動生成していきます。

💻A*による経路探索💻

探索アルゴリズムである"A*アルゴリズム"を使用して最短経路を求めます。
下図のようにコストが低い場所から優先して探索していきます。

astar3.gif

⚙Vec2クラスとNodeクラスの作成⚙

まずは基本クラスである"Vec2クラス""Nodeクラス"の作成です。

Vec2
 struct AStarVec2 {
  //X座標値を格納する
  std::int_fast32_t x{};
  //Y座標値を格納する
  std::int_fast32_t y{};
  constexpr AStarVec2() noexcept = default;
  constexpr AStarVec2(const std::int_fast32_t x_, const std::int_fast32_t y_) noexcept :x(x_), y(y_) {}
  constexpr bool operator==(const AStarVec2& vec2_) const noexcept {
   return vec2_.x == x && vec2_.y == y;
  }
 };
Node
 struct AStarNode {
  //位置
  AStarVec2 position{};
  //親ノード
  AStarVec2 parent_node{};
  //距離
  std::int_fast32_t distance{};
  //コスト
  std::int_fast32_t cost{};

  constexpr AStarNode() noexcept = default;
  constexpr AStarNode(const AStarVec2& pos_, const AStarVec2& parent_node_, const std::int_fast32_t distance_, const std::int_fast32_t cost_) noexcept
   :position(pos_), parent_node(parent_node_), distance(distance_), cost(cost_) {}
  constexpr bool operator==(const AStarNode& node_) const noexcept {
   return position == node_.position;
  }
  constexpr bool operator==(const AStarVec2& vec2_) const noexcept {
   return position == vec2_;
  }
 };

⭐️A*クラスの実装⭐️

astar4.gif

次は肝心のA*クラスの作成です。

AStar基本部分
 class AStar {
 private:
 //始点
  AStarVec2 start_vec2{};
 //終点
  AStarVec2 end_vec2{};
  std::array <AStarVec2, 8> adjacent_cell{ {AStarVec2(-1, -1),AStarVec2(1, -1),AStarVec2(-1, 1),AStarVec2(1, 1),AStarVec2(0, -1),AStarVec2(-1, 0),AStarVec2(0, 1),AStarVec2(1, 0)} };
  std::list<AStarNode> open{};
  std::list<AStarNode> closed{};

 public:
  constexpr AStar() noexcept = default;
  constexpr AStar(const AStarVec2& start_vec2_, const AStarVec2& end_vec2_) noexcept
   :start_vec2(start_vec2_), end_vec2(end_vec2_) {}
};

astar5.gif

⚙ヒューリスティック関数⚙

コストを算出する関数を作成します。

private
  constexpr std::int_fast32_t calculateDistance(const AStarVec2 & vec2_) const noexcept {
   const std::int_fast32_t x{ end_vec2.x - vec2_.x };
   const std::int_fast32_t y{ end_vec2.y - vec2_.y };
   return (x >= y) ? x : y;
  }

⚙範囲指定⚙

private
  constexpr bool isRange(const AStarVec2 & vec2_, const std::int_fast32_t x_, const std::int_fast32_t y_) const noexcept {
   return vec2_.x >= 0 && vec2_.y >= 0 && vec2_.x < x_ && vec2_.y < y_;
  }

⚙座標判定⚙

private
  bool existPoint(const AStarVec2 & vec2_, const std::int_fast32_t cost_) noexcept {
   auto i{ std::find(closed.begin(), closed.end(), vec2_) };
   if (i != closed.end()) {
    if ((*i).cost + (*i).distance < cost_) return true;
    else {
     closed.erase(i);
     return false;
    }
   }
   i = std::find(open.begin(), open.end(), vec2_);
   if (i != open.end()) {
    if ((*i).cost + (*i).distance < cost_) return true;
    else {
     open.erase(i);
     return false;
    }
   }
   return false;
  }

astar8.gif
このように周りから探索していきます。

⚙周囲のセルを開く⚙

private
  template<typename Matrix_>
  bool cellOpen(const AStarNode & node_, const Matrix_ & matrix_, const std::int_fast32_t x_, const std::int_fast32_t y_) noexcept {
   std::int_fast32_t node_cost;
   std::int_fast32_t distance;
   AStarVec2 neighbour;
   for (std::int_fast32_t x{}; x < 8; ++x) {
    neighbour.x = node_.position.x + adjacent_cell[x].x;
    neighbour.y = node_.position.y + adjacent_cell[x].y;
    if (neighbour == end_vec2) return true;
    if (!isRange(neighbour, x_, y_) || matrix_[neighbour.y][neighbour.x]) continue;
    //コスト計算
    node_cost = 1 + node_.cost;
    distance = calculateDistance(neighbour);
    if (existPoint(neighbour, node_cost + distance)) continue;
    open.emplace_back(AStarNode(neighbour, node_.position, distance, node_cost));
   }
   return false;
  }

astar7.gif

⚙探索⚙

public
  template<typename Matrix_>
  bool search(const Matrix_ & matrix_, const std::int_fast32_t x_, const std::int_fast32_t y_) noexcept {
   open.emplace_back(AStarNode(start_vec2, {}, calculateDistance(start_vec2), 0));
   while (!open.empty()) {
    const AStarNode nn{ open.front() };
    open.pop_front();
    closed.emplace_back(nn);
    if (cellOpen(nn, matrix_, x_, y_)) return true;
   }
   return false;
  }

⚙探索結果の保存⚙

public
  template<typename Path_>
  std::int_fast32_t setPath(Path_ & path_) noexcept {
   path_.emplace_front(end_vec2);
   std::int_fast32_t cost{ 1 + closed.back().cost };
   path_.emplace_front(closed.back().position);
   AStarVec2 parent_node{ closed.back().parent_node };
   for (auto&& i{ closed.rbegin() }; i != closed.rend(); ++i) {
    if (!((*i).position == parent_node) || ((*i).position == start_vec2)) continue;
    path_.emplace_front((*i).position);
    parent_node = (*i).parent_node;
   }
   path_.emplace_front(start_vec2);
   return cost;
  }

astar6.gif
これでA*アルゴリズムの実装は終わりました!

⚓完成⚓

astar2.gif

航路の自動生成が出来ました。


今回使用したワールドマップの自動生成アルゴリズムは、"セルオートマトン法"です。
(>> セルオートマトン法について解説した記事はこちら)

🏯航路の始点と終点の生成🏯

最初に設置する航路の始点と終点の生成は"イベント生成"を使用しました。
(>> イベント生成について解説した記事はこちら)

実装ライブラリ(ソースコード)

今回解説した自動生成は"Dungeon Template Library"を使用して実装されています。
GitHubに全ソースコードを載せています。ご参考になれば幸いです。
ぜひ、活用してみてください!

logo640.gif

ソースコードのライセンス

These codes are licensed under CC0.
CC0

この記事のソースコードはCC0ライセンスとします。
ぜひ、自由に改変して遊んでみてください。

"いいね"をつけてくださると大変励みになります。
最後までお読みいただきありがとうございました!

Gaccho
People pass away, but their deeds abide.
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした