5年後起業することを夢見る、初心者ゲームプログラマーの神楽坂 冬月による同人と気ままな日記ブログです。

探索!探索!

2016.04.10
クロ まえに一度紹介した気がしますが
敵の移動に必要な経路探索プログラムの勉強をしてました
よりリアルになるほど、こういうアルゴリズムは必要になってきます


数ある経路探索のアルゴリズムから選んだのは
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が出来上がるというわけですね


関連記事

テーマ : プログラミング

ジャンル : コンピュータ

コメント
コメントの投稿


管理者にだけ表示を許可する

FC2カウンター
プロフィール

神楽坂 冬月(かぐらざか ふゆつき)

Author:神楽坂 冬月(かぐらざか ふゆつき)
【イベント情報】

2015年08月14日(1日目)
コミックマーケット88に参加します!
【金曜日 東地区 "ソ" ブロック 43a】
です!
東方紅魔烏【ウォーシミュレーション】
妖夢龍剣伝(体験版)【アクション】
の2点を出店予定です
よろしくお願い致します!

-----------------------------------------
2014年12月29日
コミックマーケット87に参加します!
【月曜日 東地区 "ハ" ブロック 50a】
参加してくださった型、ありがとうございます&
お疲れ様でした!

-----------------------------------------

めざせ!業界有名人!ということで新米ゲームプログラマーとして活動しています。
次の段階へ移行!
5年後起業という目標に目指してがんばりますぞ!

バナー2
http://studio-cross.com/
HPも作ってますので、どうぞよろしくお願いします

pixiv
月別アーカイブ