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

# ⚓最短航路の作成⚓
![astar2.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/6e687922-99e8-d9a3-01c7-28aaa46fb1ab.gif)

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

# 💻A*による経路探索💻

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

![astar3.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/dc0fb1c8-ef5a-f976-58f9-8ed358a9e3c3.gif)

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

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

```cpp: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;
  }
 };
```

```cpp: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](https://qiita-image-store.s3.amazonaws.com/0/213065/38d14c54-81a3-2e92-d205-fa4a340bf97e.gif)

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

```cpp: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](https://qiita-image-store.s3.amazonaws.com/0/213065/b912437b-330f-d9be-d89e-cbd01ad27f5b.gif)

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

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

```cpp: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;
  }
```

### ⚙範囲指定⚙

```cpp: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_;
  }
```

### ⚙座標判定⚙

```cpp: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](https://qiita-image-store.s3.amazonaws.com/0/213065/e62ab9b1-5c26-2b0b-c49c-ae8a099e4d16.gif)
このように周りから探索していきます。

### ⚙周囲のセルを開く⚙

```cpp: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](https://qiita-image-store.s3.amazonaws.com/0/213065/790726a7-7edf-c78a-ed65-69ca26bdfd8f.gif)


### ⚙探索⚙

```cpp: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;
  }
```

### ⚙探索結果の保存⚙

```cpp: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](https://qiita-image-store.s3.amazonaws.com/0/213065/028a430e-e017-14d0-9b10-0c9458e16f18.gif)
これでA*アルゴリズムの実装は終わりました！

# ⚓完成⚓
![astar2.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/6e687922-99e8-d9a3-01c7-28aaa46fb1ab.gif)

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

---

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

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

最初に設置する航路の始点と終点の生成は[**"イベント生成"**](https://qiita.com/Gaccho/items/2269dc8f01d6faf24cb3)を使用しました。
[**(>> イベント生成について解説した記事はこちら)**](https://qiita.com/Gaccho/items/2269dc8f01d6faf24cb3)

# [実装ライブラリ(ソースコード)](https://github.com/Kasugaccho/DungeonTemplateLibrary)

今回解説した自動生成は**["Dungeon Template Library"](https://github.com/Kasugaccho/DungeonTemplateLibrary)**を使用して実装されています。
GitHubに全ソースコードを載せています。ご参考になれば幸いです。
ぜひ、活用してみてください！

[![logo640.gif](https://qiita-image-store.s3.amazonaws.com/0/213065/b84a7834-2042-6704-fbbe-782a31f06091.gif)](https://github.com/Kasugaccho/DungeonTemplateLibrary)

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

These codes are licensed under CC0.
[![CC0](https://mirrors.creativecommons.org/presskit/buttons/88x31/svg/cc-zero.svg "CC0")](http://creativecommons.org/publicdomain/zero/1.0/deed.ja)

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

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