4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

ゲームをつくる:A*経路探索を実装した

Posted at

#この記事は、
戦略シミュレーションゲーム好きが理想のゲームを自分で作る記録です。

この記事のまとめ

  • A*経路探索を作成した

#動作しているもの
こちらのリンクから、動作しているものを確認できます。
 タップ:Move Cost内の移動範囲を表示
 ドラッグ:最短経路を表示
  緑のヘックス:  平原:移動コスト2
  灰色のヘックス: 道路:移動コスト1
平原を突っ切るよりも、遠回りして道路を選択することから、経路探索が正しく動いていることを確認できます。

経路探索

SLGでは、ユニットの移動範囲や、移動経路の為に、経路探索を行う必要があります。
そこで、代表的な経路探索のアルゴリズムの1つ、Aを実装しました。
A
の詳しい説明に関しては、Wikipediaを参考にしてください。

完成したA*のソースコードはこちら。

AStar経路探索コード
A-Star.js
// *************************************************
// A*経路探索
// *************************************************
// 探索モード
let MODE = {
  ROUTE: 0, // 
  REACH: 1, //
};

// 探索ノードのステータス
let STAT = {
  NONE: 0, // 未探索
  OPEN: 1, // オープン
  CLOSED: 2, // クローズド
  WALL: 3, // 壁
};

const MaxStageX = 100;
const MaxStageY = 100;

class AStar {
  // *************************
  // コンストラクタ
  // *************************
  constructor() {
    cc.log('A-Star constructor');
    this.Field = []; // フィールド構造体
    this.OpenList = []; // オープンリス
    this.CloseList = []; // クローズリスト = 到達可能場所リスト
    this.CurrentSize = { // 使用しているマップのサイズs
      colX: 0,
      rowY: 0,
    };

    this.Mode;

    // フィールド構造体の宣言
    for (let loop = 0; loop < MaxStageY; loop++) {
      this.Field[loop] = [];
      for (let loop1 = 0; loop1 < MaxStageX; loop1++) {
        this.Field[loop][loop1] = {
          Pos: { // 座標
            colX: loop1,
            rowY: loop,
          },
          Stat: STAT.NONE,
          IsUnit: false,
          ACost: undefined,
          HCost: undefined,
          Score: undefined,
          Parent: null,
        };
      }
    }
  }

  // *************************
  // すべて初期化
  // *************************
  resetAll() {
    this.OpenList.length = 0; // オープンリストを空にする
    this.CloseList.length = 0; // オープンリストを空にする
    // フィールドの初期化
    let node;
    for (let loop = 0; loop < MaxStageY; loop++) {
      for (let loop1 = 0; loop1 < MaxStageX; loop1++) {
        node = this.Field[loop][loop1];
        node.Stat = STAT.NONE; // ステータス
        node.IsUnit = false; // ユニットが乗っているか
        node.ACost = undefined; // 実コスト Actual Cost
        node.HCost = undefined; // 推定コスト Hyulistic Cost
        node.Score = undefined; // スコア 実コスト+推定コスト
        node.Parent = null; // 親ノードへの参照
      }
    }
  }

  // *************************
  // 探索フィールドの初期化
  // *************************
  initSearchField(mapData) {
    cc.log('    A-Star: Init Search Field');

    this.resetAll(); // 初期化
    // ステージのサイズの設定
    this.CurrentSize.rowY = mapData[0].length;
    this.CurrentSize.colX = mapData.length;
    cc.log('CurrentSize X,Y:' + this.CurrentSize.colX + ', ' + this.CurrentSize.rowY);

    this.mapData = mapData;
  }

  // *************************
  // ユニット位置の更新
  // *************************
  updateObjectPosition() {
    // すべてクリアにする
    for (let row = 0; row < this.CurrentSize.rowY; row++) {
      for (let col = 0; col < this.CurrentSize.colX; col++) {
        this.Field[row][col].IsUnit = false;
      }
    }
    // ユニット位置にユニットフラグを立てる
    for (let loop = 0; loop < OM.OBJ.USED; loop++) {
      let [colX, rowY] = OM.getObjectPosition(loop);
      // cc.log('Find Object:' + loop + ' : ' + colX + ', ' + rowY);
      this.Field[rowY][colX].IsUnit = true;

    }
  }

  // *************************
  // ヒューリスティックを計算する
  // *************************
  calcHeuristic(colX, rowY) {
    // モードは到着探索
    if (this.Mode === MODE.REACH) {
      return 0; // ヒューリスティック計算は常に0を返す
    }
    let distX = Math.abs(this.GoalColX - colX);
    let distY = Math.abs(this.GoalRowY - rowY);
    if (distX > distY) {
      return distX;
    }
    return distY;

  }

  // *************************
  // ノードが有効かチェックする
  // *************************
  checkIsNodeValid(colX, rowY, parent) {
    // フィールド外チェック
    if (colX < 0 || rowY < 0) {
      return false;
    }
    if (colX >= this.CurrentSize.colX || rowY >= this.CurrentSize.rowY) {
      return false;
    }

    // cc.log('      Check Node: ' + colX + ', ' + rowY + '  Stat: ' + this.Field[rowY][colX].Stat + '  IsUnit:' + this.Field[rowY][colX].IsUnit);

    // 未オープンチェック(同時に壁チェックもしている)
    if (this.Field[rowY][colX].Stat !== STAT.NONE) {
      return false;
    }

    /*
    // ユニット位置チェック
    if (this.Field[rowY][colX].IsUnit === true) {
      return false;
    }
    */

    // 地形と移動タイプから実コストを計算

    if (this.mapData[colX][rowY] === undefined) {
      cc.log('Node Valid check Error');
      cc.log('(' + colX + ', ' + rowY + ')');
      cc.warn('ParentNode: ' + parent);
      cc.warn(parent);
    }
    let aCost = parent.ACost + this.mapData[colX][rowY].Terrain.cost[this.moveType];
    if (aCost > this.moveCost) { // 移動コストより大きい場合、オープンしない
      return false;
    }

    return true; // 有効。OK!
  }

  // *************************
  // ノードをオープンする
  // *************************
  openNode(colX, rowY, parent) {
    cc.log('    Open Node: ' + colX + ', ' + rowY);

    let node = this.Field[rowY][colX];

    node.Stat = STAT.OPEN; // ステータス オープン
    // 地形と移動タイプから実コストを計算
    node.ACost = parent.ACost + this.mapData[colX][rowY].Terrain.cost[this.moveType];

    node.HCost = this.calcHeuristic(colX, rowY); // 推定コストを設定
    node.Score = node.ACost + node.HCost;
    node.Parent = parent; // 親ノードを設定

    // オープンリストに追加
    this.OpenList.push(node);
  }

  // *************************
  // スタートノードをオープンする
  // *************************
  openStartNode(colX, rowY) {
    cc.log('    Open Start Node: ' + colX + ', ' + rowY);

    let node = this.Field[rowY][colX];

    node.Stat = STAT.OPEN; // ステータス オープン
    // 地形と移動タイプから実コストを計算
    node.ACost = 0;

    node.HCost = this.calcHeuristic(colX, rowY); // 推定コストを設定
    node.Score = node.ACost + node.HCost;
    node.Parent = null; // 親ノードはnull

    // オープンリストに追加
    this.OpenList.push(node);
  }

  // *************************
  // オープンリストから最小スコアのノードを見つけて取り出す(削除する)
  // *************************
  takeMinScoreNodeFromOpenList() {

    // 最小スコアの初期化
    let minScore = 9999999;
    // 最小実コストの初期化
    let minACost = 9999999;
    // 最小ノードのID(loopの値)
    let minNodeID = null;

    let listMax = this.OpenList.length;
    let node;

    for (let loop = 0; loop < listMax; loop++) {
      node = this.OpenList[loop];
      if (node.Score > minScore) {
        // スコアが大きい
        continue;
      }
      if (node.Score === minScore && node.ACost >= minACost) {
        // スコアが同じときは実コストも比較する
        continue;
      }

      // 最小値更新.
      minScore = node.Score;
      minACost = node.ACost;
      minNodeID = loop;
    }

    // リストが空でないのに、最小のノードがみつけられなかった
    if (CC_DEBUG) {
      if (minNodeID === null) {
        cc.log('Assert');
        cc.log(this.OpenList);
        cc.assert(false, 'Cant find minNode:' + this.OpenList);
      }
    }

    let minNode = this.OpenList[minNodeID]; // 該当要素の参照を保存
    minNode.Stat = STAT.CLOSED; // ステータスをクローズドに変更
    this.OpenList.splice(minNodeID, 1); // this.OpenListから、該当要素を1つ削除
    this.CloseList.push(minNode); // クローズリストに追加
    return minNode;
  }

  // *************************
  // ゴールしたかチェック
  // *************************
  isGoal(node) {
    let colX = node.Pos.colX;
    let rowY = node.Pos.rowY;

    // ゴールチェック
    if (colX === this.GoalColX && rowY === this.GoalRowY) {
      cc.log('*********** Find Goal ***************');
      return true;
    }
    return false;
  }

  // *************************
  // 周囲のノードをオープンする
  // *************************
  openSurroundingNodes(currentNode) {
    let colX = currentNode.Pos.colX;
    let rowY = currentNode.Pos.rowY;

    // let node;
    // cc.log('Open Surrounding');

    // 上のライン
    // node = this.Field[rowY][colX + 1];
    if (this.checkIsNodeValid(colX, rowY + 1, currentNode)) {
      this.openNode(colX, rowY + 1, currentNode);
    }

    // 偶数のときは、X座標−1と隣接している
    if (rowY % 2) {
      if (this.checkIsNodeValid(colX + 1, rowY + 1, currentNode)) {
        this.openNode(colX + 1, rowY + 1, currentNode);
      }
    }
    else {

      if (this.checkIsNodeValid(colX - 1, rowY + 1, currentNode)) {
        this.openNode(colX - 1, rowY + 1, currentNode);
      }
    }

    // 下のライン
    if (this.checkIsNodeValid(colX, rowY - 1, currentNode)) {
      this.openNode(colX, rowY - 1, currentNode);
    }

    // 偶数のときは、X座標−1と隣接している
    if (rowY % 2) {
      if (this.checkIsNodeValid(colX + 1, rowY - 1, currentNode)) {
        this.openNode(colX + 1, rowY - 1, currentNode);
      }
    }
    else {
      if (this.checkIsNodeValid(colX - 1, rowY - 1, currentNode)) {
        this.openNode(colX - 1, rowY - 1, currentNode);
      }
    }

    // 横のライン
    if (this.checkIsNodeValid(colX - 1, rowY, currentNode)) {
      this.openNode(colX - 1, rowY, currentNode);
    }

    if (this.checkIsNodeValid(colX + 1, rowY, currentNode)) {
      this.openNode(colX + 1, rowY, currentNode);
    }
  }

  // *************************
  // 経路を返す スタート地点は含まない
  // *************************
  getPath(node) {
    let path = [];

    path.unshift({
      colX: node.Pos.colX,
      rowY: node.Pos.rowY,
      Obj: null,
    });
    // eslint-disable-next-line no-constant-condition
    while (true) {
      if (node.Parent.Parent === null) { // スタート地点は含まない
        return path;
      }
      node = node.Parent;
      path.unshift({
        colX: node.Pos.colX,
        rowY: node.Pos.rowY,
        Obj: null,
      });
    }
  }

  // *************************
  // フィールドのリフレッシュ
  // ルート探索する前に、すでにオープンやクローズされたnodeをNONEにする
  // *************************
  refreshField(mapData) {
    // 最初に壁の探索
    let stat;
    for (let row = 0; row < this.CurrentSize.rowY; row++) {
      for (let col = 0; col < this.CurrentSize.colX; col++) {
        stat = this.Field[row][col].Stat;
        // 壁 か 空白 だったら探索領域から外す
        if (stat === STAT.OPEN || stat === STAT.CLOSED) { // すでにOPENやCLOSEDだったら
          this.Field[row][col].Stat = STAT.NONE; // ステータスをNULLにする
        }
      }
    }
    this.OpenList.length = 0;
    this.CloseList.length = 0;
  }

  // *************************
  // 経路探索
  // moveType: 移動タイプ
  // *************************
  findRoute(moveType, startHex, goalHex) {
    console.time('    A-Star: Find Root');
    this.Mode = MODE.ROUTE; // ルート探索モードをセット

    this.moveType = moveType;

    this.refreshField(); // リフレッシュする

    // ゴールの登録
    this.GoalColX = goalHex.x;
    this.GoalRowY = goalHex.y;

    // 移動コスト 十分大きければOK
    this.moveCost = 1000;

    // スタートのノードを追加
    this.openStartNode(startHex.x, startHex.y);

    // 経路探索のループ;
    let currentNode = null;
    // eslint-disable-next-line no-constant-condition
    while (true) {
      // リストが空 = 経路が見つけられなかった
      if (this.OpenList.length === 0) {
        cc.log('    A-Star: Cant Find Root');
        console.timeEnd('    A-Star: Find Root');
        return false;
      }

      currentNode = this.takeMinScoreNodeFromOpenList(); // スコア最小ノードの取り出し (そしてクローズ)

      // ゴールしたかどうかのチェック
      if (this.isGoal(currentNode)) {
        console.timeEnd('    A-Star: Find Root');
        return this.getPath(this.Field[currentNode.Pos.rowY][currentNode.Pos.colX]);
      }

      // 周囲のノードをオープンする
      this.openSurroundingNodes(currentNode);
    }
  }

  // *************************
  // 到達可能エリア探索
  // flag: trueにすると到達可能確認モードになる
  // *************************
  getReachableArea(moveType, startHex, moveCost) {
    console.time('    A-Star: Reachable check');
    this.Mode = MODE.REACH; // 到着探索モードをセット

    this.moveType = moveType; // 移動タイプ
    this.moveCost = moveCost; // 移動コスト

    this.refreshField(); // リフレッシュする

    // スタートのノードを追加
    this.openStartNode(startHex.x, startHex.y);

    // 経路探索のループ;
    let currentNode = null;
    // eslint-disable-next-line no-constant-condition
    while (true) {

      // リストが空 = 到達可能エリアの探索終了
      if (this.OpenList.length === 0) {
        console.timeEnd('    A-Star: Reachable check');
        return this.CloseList;
      }
      currentNode = this.takeMinScoreNodeFromOpenList(); // スコア最小ノードの取り出し (そしてクローズ)

      this.openSurroundingNodes(currentNode);
    }
  }

  /*
  // *************************
  // 到達可能確認
  // *************************
  checkReachable() {
    // キャラクター位置から到達可能をチェック
    return this.findRoot(null, null, CM.Position.colX, CM.Position.rowY, true);
  }
  */
}
export default new AStar();

Hexマップに対応しているため、周囲のノードを開く、openSurroundingNodesメソッドでは、
隣接する6つのHexをオープンしています。

使い方:
まず、インポートします。

import AStar from '../A-Star/A-Star';

実際に探索を行う前に、探索するフィールドでAstarを初期化します。

AStar.initSearchField(MapHexData);

MapHexDataはメンバにTerrainをもつ、2次元配列です。
メンバであるTerrainは、以前設定した、下記地形データ配列のいずれかを参照しています。

const TerrainData = [
  { id: 0, cost: [1, 1, 1, 1, 1, 100], def: 0.40, cap: true },
  { id: 1, cost: [1, 1, 1, 1, 1, 100], def: 0.10, cap: true },
  { id: 2, cost: [1, 1, 1, 1, 1, 100], def: 0.10, cap: true },
  { id: 3, cost: [1, 1, 1, 1, 1, 100], def: 0.10, cap: true },
  { id: 4, cost: [1, 1, 1, 1, 1, 100], def: 0.30, cap: true },
  { id: 5, cost: [1, 1, 1, 1, 1, 100], def: 0.35, cap: true },
  { id: 6, cost: [1, 1, 1, 1, 1, 100], def: 0.50, cap: false },
  { id: 7, cost: [1, 1, 1, 1, 1, 100], def: 0.00, cap: false },
  { id: 8, cost: [1, 1, 1, 1, 1, 100], def: 0.00, cap: false },
  { id: 9, cost: [1, 2, 1, 1, 1, 100], def: 0.05, cap: false },
  { id: 10, cost: [2, 3, 2, 1, 1, 100], def: 0.05, cap: false },
  { id: 11, cost: [1, 2, 1, 1, 1, 100], def: 0.15, cap: false },
  { id: 12, cost: [1, 3, 2, 1, 1, 100], def: 0.25, cap: false },
  { id: 13, cost: [2, 3, 2, 1, 1, 100], def: 0.10, cap: false },
  { id: 14, cost: [3, 100, 100, 1, 1, 100], def: 0.30, cap: false },
  { id: 15, cost: [100, 100, 100, 100, 1, 100], def: 0.00, cap: false },
  { id: 16, cost: [2, 2, 2, 1, 1, 100], def: 0.00, cap: false },
  { id: 17, cost: [3, 2, 2, 1, 1, 100], def: 0.00, cap: false },
  { id: 18, cost: [3, 100, 100, 1, 1, 100], def: 0.00, cap: false },
  { id: 19, cost: [100, 100, 100, 1, 1, 100], def: 0.00, cap: false },
  { id: 20, cost: [100, 100, 100, 1, 1, 100], def: 0.00, cap: false },
  { id: 21, cost: [100, 100, 100, 1, 1, 1], def: 0.00, cap: false },
];

到達可能範囲の取得
以下のような形で、MoveCost内の、到達可能範囲を、cc.Vex2の配列で取得します。

let reachableArea = AStar.getReachableArea(CONST.MoveType.WHEEL, selectHex, MoveCost);

ルート探索
以下のような形で、最短ルートを、cc.Vex2の配列で取得します。

let route = AStar.findRoute(CONST.MoveType.WHEEL, selectHex, moveHex);

次は、ユニットなどを表示するために、ユニットのグラフィックを作っていこうと思います。

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?