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

この記事は、

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

この記事のまとめ

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

動作しているもの

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

経路探索

SLGでは、ユニットの移動範囲や、移動経路の為に、経路探索を行う必要があります。
そこで、代表的な経路探索のアルゴリズムの１つ、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; // ヒューリスティック計算は常に０を返す
    }
    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から、該当要素を１つ削除
    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座標−１と隣接している
    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座標−１と隣接している
    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メソッドでは、
隣接する６つのHexをオープンしています。

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

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

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

AStar.initSearchField(MapHexData);

MapHexDataはメンバにTerrainをもつ、２次元配列です。
メンバである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);

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