#この記事は、
戦略シミュレーションゲーム好きが理想のゲームを自分で作る記録です。
この記事のまとめ
- A*経路探索を作成した
#動作しているもの
こちらのリンクから、動作しているものを確認できます。
タップ:Move Cost内の移動範囲を表示
ドラッグ:最短経路を表示
緑のヘックス: 平原:移動コスト2
灰色のヘックス: 道路:移動コスト1
平原を突っ切るよりも、遠回りして道路を選択することから、経路探索が正しく動いていることを確認できます。
経路探索
SLGでは、ユニットの移動範囲や、移動経路の為に、経路探索を行う必要があります。
そこで、代表的な経路探索のアルゴリズムの1つ、Aを実装しました。
Aの詳しい説明に関しては、Wikipediaを参考にしてください。
完成したA*のソースコードはこちら。
AStar経路探索コード
// *************************************************
// 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);
次は、ユニットなどを表示するために、ユニットのグラフィックを作っていこうと思います。