投稿日: 投稿者: syungetu

探索！探索！

クロ まえに一度紹介した気がしますが
敵の移動に必要な経路探索プログラムの勉強をしてました
よりリアルになるほど、こういうアルゴリズムは必要になってきます
数ある経路探索のアルゴリズムから選んだのは
AStsrアルゴリズムというやつね
実装が簡単なのが特徴です 		霊夢
魔理沙 あともう一つ
障害物を避けてルートを見つけ出す
という特徴があるぞ
とうことで
毎度のことですが
詳しくは続きを読むからどうぞ 		妖夢

Wikipedia A*（A-star, エースター）探索アルゴリズム

クロ 詳しい説明はウィキペディアにお任せするとして
スタートから探索し、そのマスに移動コストを設定していき
回帰処理でゴールまでしその処理を行います
で、ゴールまでたどり着いたら
ゴールからスタートまでコストの少ない道順をたどっていけば
最短距離でそのルートが出てくるというわけね 		霊夢
魔理沙 こいつの利点としては
升目状のマップならどんな形状でも検索できるぞ
逆に言えば碁盤目にしないと動かないけどね
もう一つ欠点として
回帰処理で検索をかけるので処理が比較的重い
点ですね 		妖夢
クロ 大きなマップを使うときには
探索範囲を分けるか、大雑把な判定から細かくしていくなど
使い道に合わせて工夫していくといいと思います 
//===================================================================
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
///
/// A*の検証プログラム
/// 段差が2以上の時、登れない壁となり回避させるようになっている
/// C#にはVector3のクラスはないので自作して動かしている
///
///===Unityだけのクラスなので必要ない===
public class Vector3
{
public int X = 0;
public int Y = 0;
public int Z = 0;
public Vector3(int inX = 0, int inY = 0, int inZ = 0)
{
X = inX;
Y = inY;
Z = inZ;
}
public static Vector3 operator +(Vector3 a, Vector3 b)
{
return new Vector3(
(a.X + b.X),
(a.Y + b.Y),
(a.Z + b.Z)
);
}
public static Vector3 operator -(Vector3 a, Vector3 b)
{
return new Vector3(
(a.X - b.X),
(a.Y - b.Y),
(a.Z - b.Z)
);
}
public static Vector3 operator /(Vector3 a, Vector3 b)
{
return new Vector3(
(a.X / b.X),
(a.Y / b.Y),
(a.Z / b.Z)
);
}
public static Vector3 operator *(Vector3 a, Vector3 b)
{
return new Vector3(
(a.X * b.X),
(a.Y * b.Y),
(a.Z * b.Z)
);
}
public static bool Equal(Vector3 a, Vector3 b)
{
if(a == null)
{
return false;
}
if(b == null)
{
return false;
}
if(
(a.X == b.X) &&
(a.Y == b.Y) &&
(a.Z == b.Z)
)
{
return true;
}
return false;
}
};
///  マップ情報 
public struct GridInfo
{
public Vector3 pos;
public float step;
public float dist;
public float weight;
public Vector3 prev;
};
///  A*クラス 
public class AStarSearch
{
///  マップの横分割数 
public static int GRIDWIDTH = 10;
///  マップの縦分割数 
public static int GRIDHEIGHT = 10;
///  最大マップの高さ 
public static int GRIDALTITUDEMAX = 5;
///  移動のコスト 
public static float MOVEWEIGHT = 1.0f;
///  段差を登るためのコスト 
public static float UPHILLWEIGHT = 1.0f;
///  壁になる高さ 
public static int WALLHEIGHT = 2;
///-- 入力データ --///
///  マップ情報（高さ情報を保持） 
public int[,] _Grids = new int[GRIDWIDTH,GRIDHEIGHT];
///  開始座標 
public Vector3 _StartPos = null;
///  終了座標 
public Vector3 _GoalPos = null;
///-- 入力データ --///
///-- 出力データ --///
///  道のりの情報を保存する配列 
public GridInfo[,] _GridInfos = new GridInfo[GRIDWIDTH, GRIDHEIGHT];
///  道のりをリストで作成（サイズが不定のため） 
public List _activeGrids = new List();
///-- 出力データ --///
//コンストラクタ
public AStarSearch(Vector3 startPos, Vector3 goalPos, int[,] Grids)
{
//必須データの取得
_StartPos = startPos;
_GoalPos = goalPos;
//ループで複製（コピーはしない）
for(int i = 0; i < GRIDWIDTH; i++)
{
for(int j = 0; j < GRIDHEIGHT; j++)
{
_Grids[i, j] = Grids[i, j];
}
}
}
///  経路探索 
public bool SearchPath()
{
//必須データが挿入されてなかった時
if(_StartPos == null)
{
return false;
}
if(_GoalPos == null)
{
return false;
}
if(_Grids == null)
{
return false;
}
///探索にかかったカウント
int SearchCountNum = 0;
// 全グリッド情報を初期化
for (int y = 0; y < GRIDHEIGHT; ++y)
{
for (int x = 0; x < GRIDWIDTH; ++x)
{
_GridInfos[x, y].pos = new Vector3(x, y, 0);
_GridInfos[x, y].step = 0;
_GridInfos[x, y].dist = 0;
_GridInfos[x, y].weight = 1e10F;
_GridInfos[x, y].prev = new Vector3(0, 0, 0);
}
}
// スタート地点をセット
GridInfo info = _GridInfos[_StartPos.X,_StartPos.Y];
info.dist = calcDist(_StartPos, _GoalPos);
//Listすべての要素を削除
_activeGrids.Clear();
//スタート地点を追加
_activeGrids.Add(info);
///=== 自前クラスで作ったので、ココは修正する ===
while (!Vector3.Equal(info.pos, _GoalPos))
{
//周囲4グリッドを計算
for (int i = 0; i < 4; ++i)
{
int sx = ((i % 2 == 0) ? i - 1 : 0);
int sy = ((i % 2 == 1) ? i - 2 : 0);
int tx = info.pos.X + sx;
int ty = info.pos.Y + sy;
if (tx < 0 || tx >= GRIDWIDTH || ty < 0 || ty >= GRIDHEIGHT)
{
continue;
}
GridInfo neighbor = _GridInfos[tx, ty];
// 移動コストを計算。平面のA*であれば通常は 1 で問題なし
float weight = calcStepWeight(info.pos, neighbor.pos);
if (weight < 0)
{
continue; // 0以下を壁とみなし探索を飛ばす
}
neighbor.step = info.step + weight;
neighbor.dist = calcDist(neighbor.pos, _GoalPos);
neighbor.weight = neighbor.step + neighbor.dist;
neighbor.prev = info.pos;
// 対象のグリッドがすでに計算されていて、ウェイトが低ければ上書きしない
if (_GridInfos[tx, ty].weight > neighbor.weight)
{
_GridInfos[tx, ty] = neighbor;
// ウェイトを元に探索対象リストへ挿入
bool added = false;
for (int j = 0; j < _activeGrids.Count; ++j)
{
if (_activeGrids[j].weight > neighbor.weight)
{
_activeGrids.Insert(j, neighbor);
added = true;
break;
}
}
if (added == false)
{
_activeGrids.Add(neighbor);
}
}
}
//検索済みのグリッドを削除
_activeGrids.Remove(info);
if (_activeGrids.Count == 0)
{
// ルートなし
Console.WriteLine("NO_ROUTE");
return false;
}
// 次のグリッドをセット
info = _activeGrids.First();
// 対象がゴール地点なら検索終了
///=== 自前クラスで作ったので、ココは修正する ===
if (Vector3.Equal(_GoalPos, info.pos))
{
Console.WriteLine("SEARCH_SUCCESSFUL Count:(" + SearchCountNum + ")");
return true;
}
SearchCountNum++;
}
Console.WriteLine("SEARCH_FAILURE");
return false;
}
///  移動コストを計算 
protected float calcStepWeight(Vector3 p1, Vector3 p2)
{
// 高さが同一ならば移動コストは通常通り
if (_Grids[p1.X, p1.Y] == _Grids[p2.X, p2.Y])
{
return MOVEWEIGHT;
}
// 上り
if (_Grids[p1.X, p1.Y] < _Grids[p2.X, p2.Y])
{
int sh = _Grids[p2.X, p2.Y] - _Grids[p1.X, p1.Y];
if (sh > WALLHEIGHT)
{
return -1; // 今回は2段以上を壁とする
}
return MOVEWEIGHT + (sh * UPHILLWEIGHT); // 高さ分コストを加える
}
// 下り
if (_Grids[p1.X, p1.Y] > _Grids[p2.X, p2.Y])
{
int sh = _Grids[p1.X, p1.Y] - _Grids[p2.X, p2.Y];
if (sh > WALLHEIGHT)
{
return -1; // 今回は2段以上を壁とする
}
return MOVEWEIGHT + (sh * UPHILLWEIGHT); // 高さ分コストを加える
}
return -1;
}
///  距離を計算 
protected float calcDist(Vector3 p1, Vector3 p2)
{
float sx = p2.X - p1.X;
float sy = p2.Y - p1.Y;
return (float)Math.Sqrt(sx * sx + sy * sy);
}
};
///メイン処理
public class Test
{
//経路探索クラス
private static AStarSearch astarSearch;
///メイン関数
static int Main(string[] args)
{
Console.WriteLine("------------------------------------------------------------\n");
//経路探索の初期化
astarSearch = new AStarSearch(
new Vector3(1, 1, 0),		//スタート地点
new Vector3(8, 8, 0),		//ゴール地点
new int[,]{
{ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3},
{ 3, 1, 1, 1, 1, 1, 1, 1, 1, 3},
{ 3, 1, 3, 3, 1, 1, 3, 3, 1, 3},
{ 3, 1, 3, 3, 1, 1, 3, 3, 1, 3},
{ 3, 1, 1, 1, 1, 1, 1, 1, 1, 3},
{ 3, 1, 1, 1, 1, 1, 1, 1, 1, 3},
{ 3, 1, 3, 3, 1, 1, 3, 3, 1, 3},
{ 3, 1, 3, 3, 1, 1, 3, 3, 1, 3},
{ 3, 1, 1, 1, 1, 1, 1, 1, 1, 3},
{ 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}
}
);
if (astarSearch.SearchPath())
{
//配列の並び的にゴールからの道順になる
GridInfo info = astarSearch._GridInfos[astarSearch._GoalPos.X,astarSearch._GoalPos.Y];
int lootCount = 1;
///=== 自前クラスで作ったので、ココは修正する ===
while(!Vector3.Equal(info.pos, astarSearch._StartPos))
{
//ゴールからスタートまでのログ表示
info = astarSearch._GridInfos[info.prev.X, info.prev.Y];
///Debug.Log("Rout:" + lootCount + "(X:" + info.pos.x + ",Y:" + info.pos.y + ")");
Console.WriteLine("Rout:" + lootCount + "(X:" + info.pos.X + ",Y:" + info.pos.Y + ")");
lootCount++;
}
}
else
{
//失敗
Console.WriteLine("Failure");
}
//正常終了
return 1;
}
};
で、作ってみたのがこんな感じよ
参考にさせていただいたサイトを失念してしまったので
見つけ次第、追記します。スミマセン		 霊夢
魔理沙 Unityを念頭に作ってはいるんだけど
まっさらなC#で作ったので、一部Unityでは必要ない関数があるぞ
そのへんは各自調整してくださいな

実行結果

早速ですが実行した物を上のリンクに用意してみました
Ctri+Enterで実行出来ます
配列をいじることでマップの構造も変更できますよ 		妖夢
クロ で、この結果をキャラの移動先に反映させれば
上手いこと障害物をよけつつ目的のところに移動してくれる
CPUが出来上がるというわけですね

気軽にコメントをどうぞ！

この記事に関すること冬月に聞きたいこと等、小さいことでもコメントしていただける嬉しいです。
冬月に直接連絡したい方は下のお問合せフォームをお使いください。（メール送信されます）

内容に問題なければ、下記の「コメントを送信する」ボタンを押してください。
※メールアドレスは公開されることは有りません。


reCaptcha の認証期間が終了しました。ページを再読み込みしてください。

ゲーム製作の関連記事