Unityですごろくを作ってみる2 - 株式会社BEFOOL ブログ

はい、こんにちは〜。
今回は前回のすごろくに経路探索を組み込んで見ました。
やったことは

ゴールまでのマスの数の表示
道が選択できるときに、近いほうの矢印を赤くしました。

サイコロの挙動が怪しいのは直してないです。(;w;)
どこがおかしいんだろな〜w

##参考書籍 ActionScript3.0にアニメーションというオライリーの書籍です。
ActionScript3.0用のソースをちょっとUnityようにいじって、すごろく用にアレンジしています。
経路探索についてはゲーム開発者のためのAI入門という本（こちらもオライリー）にも記載があります。

##今回の作成結果すごろくのようなもの2

ゴールの場所を変更してもちゃんと計算されます。

##経路探索のクラス追加した経路探索用のクラスです。

Node.js
一つの探索したノードの情報を格納するクラス
gがこのノードまでの距離、hがこのノードからゴールまでの予測の距離、fにgとhを足した値が入ります。
parentはこのノードの前のノード
walkableは移動できるかどうかです。

public class Node{
	var x:int;
	var y:int;
	var f:float;
	var g:float;
	var h:float;
	var walkable:boolean = true;
	var parent:Node;
 
	public function Node(x:int, y:int){
		this.x = x;
		this.y = y;
	}
}

Grid.js
検索するタイルの情報を保持するクラス

public class Grid{
	private var _startNode:Node;
	private var _endNode:Node;
	private var _nodes:Array;
	private var _numCols:int;
	private var _numRows:int;
 
	public function Grid(numCols:int, numRows:int){
		_numCols = numCols;
		_numRows = numRows;
		_nodes = new Array();
		for(var x:int = 0; x < _numCols; x++){
			for(var y:int = 0; y < _numRows; y++){
				_nodes[x + y *  _numCols] = new Node(x,y);
			}
		}
	}
 
	public function getNode(x:int, y:int):Node{
		return _nodes[x + y *  _numCols] as Node;
	}
 
	public function setEndNode(x:int, y:int):void{
		_endNode = getNode(x,y) as Node;
	}
 
	public function setStartNode(x:int, y:int):void{
		_startNode = getNode(x,y) as Node;
	}
 
	public function setWalkable(x:int, y:int, value:boolean):void{
		getNode(x,y).walkable = value;
	}
 
	public function get endNode():Node{
		return _endNode;
	}
 
	public function get numCols():int{
		return _numCols;
	}
 
	public function get numRows():int{
		return _numRows;
	}
 
	public function get startNode():Node{
		return _startNode;
	}
 
}

AStar.js
こちら実際に経路探索を行うクラス
_heuristicはhを計算する方法です。細かいことは割愛w
_pathにスタートからゴールまでのNodeのリストが格納されます

public class AStar{
	private var _open:Array;
	private var _closed:Array;
	private var _grid:Grid;
	private var _endNode:Node;
	private var _startNode:Node;
	private var _path:Array;
	private var _straightCost:float = 1.0;
	private var _diagCost:float = Mathf.Sqrt(2);
	private var _heuristic:Function = manhattan;    // マンハッタン法
	// private var _heuristic:Function = euclidian; // ユークリッド法
	// private var _heuristic:Function = diagonal;  // 対角線法
	private var _skewPathFlg:boolean;	// 斜め移動許可
 
	public function AStar(){
	}
 
	public function findPath(grid:Grid, skewFlg:boolean){
		_grid = grid;
		_skewPathFlg = skewFlg;
		_open = new Array();
		_closed = new Array();
		_startNode = _grid.startNode;
		_endNode = _grid.endNode;
		_startNode.g = 0;
		_startNode.h = _heuristic(_startNode);
		_startNode.f = _startNode.g + _startNode.h;
 
		return search();
	}
 
 
 
	public function search():boolean{
		var node:Node = _startNode;
		while(node != _endNode){
			var startX:int = Mathf.Max(0, node.x -1);
			var endX:int = Mathf.Min(_grid.numCols - 1, node.x + 1);
			var startY:int = Mathf.Max(0, node.y - 1);
			var endY:int = Mathf.Min(_grid.numRows - 1, node.y + 1);
 
			for(var i:int = startX; i <= endX; i++){
				for(var j:int = startY; j <= endY; j++){
					var test:Node= _grid.getNode(i,j);
					if(test == node || !test.walkable){
						continue;
					}
 
					// 斜め移動禁止
					if(!_skewPathFlg){
						var dx:Number = node.x - test.x;
						var dy:Number = node.y - test.y;
						var num:float = Mathf.Sqrt(dx * dx + dy * dy) * _straightCost;
						if(num > 1){
							continue;
						}
					}
 
					var cost:Number = _straightCost;
					if(!((node.x == test.x) || (node.y == test.y))){
						cost = _diagCost;
					}
					var g:float = node.g + cost;
					var h:float = _heuristic(test);
					var f:float = g + h;
					if(isOpen(test) || isClosed(test)){
						if(test.f > f){
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
						}
					}else{
						test.f = f;
						test.g = g;
						test.h = h;
						test.parent = node;
						_open.push(test);
					}
				}
			}
			_closed.push(node);
			if(_open.length == 0){
				Debug.Log("経路がないよ");
				return false;
			}
			BubbleSort(_open);
			node = _open.shift() as Node;
		}
 
		buildPath();
		return true;
	}
 
	// ソート
	private function BubbleSort(_nodeList:Array):Array{
		for(var i:int = 0; i < _nodeList.length; i++){
			for(var j:int = 0; j < _nodeList.length-1; j++) {
				if(Sort(_nodeList[j], _nodeList[j+1])){
					var tmp:Node = _nodeList[j+1];
					_nodeList[j+1] = _nodeList[j];
					_nodeList[j] = tmp;
				}        
			}
		}
		return _nodeList;
	}
 
 
	private function Sort(node1:Node, node2:Node){
		return node2.f - node1.f;
	}
 
	private function buildPath():void{
		_path = new Array();
		var node:Node = _endNode;
		_path.push(node);
		while(node != _startNode){
			node = node.parent;
			_path.unshift(node);
		}
	}
 
	public function get path():Array{
		return _path;
	}
 
	private function isOpen(node:Node):boolean{
		for(var i:int = 0; i < _open.length; i++){
			if(_open[i] == node){
				return true;
			}
		}
		return false;
	}
 
	private function isClosed(node:Node):boolean{
		for(var i:int = 0; i < _closed.length; i++){
			if(_closed[i] == node){
				return true;
			}
		}
		return false;
	}
 
	private function manhattan(node:Node):float{
		return Mathf.Abs(node.x - _endNode.x) * _straightCost + 
		Mathf.Abs(node.y - _endNode.y) * _straightCost;
	}
 
	private function euclidian(node:Node):float{
		var dx:Number = node.x - _endNode.x;
		var dy:Number = node.y - _endNode.y;
		return Mathf.Sqrt(dx * dx + dy * dy) * _straightCost;
	}
 
	private function diagonal(node:Node):Number{
		var dx:int = Mathf.Abs(node.x - _endNode.x);
		var dy:int = Mathf.Abs(node.y - _endNode.y);
		var diag:int = Mathf.Min(dx, dy);
		var straight:int = dx + dy;
		return _diagCost * diag + _straightCost * (straight - 2 * diag);
	}
 
	public function get visited():Array{
		return _closed.concat(_open);
	}
}

##使い方使い方はまずタイルの初期化部分でGridデータを作成します。
引数は横のタイルの数と、縦のタイルの数です。

grid = new Grid(masuColSize,masuRowSize);

次にマスのループ内で各マスが移動可能かをセットします

grid.setWalkable(x,y,false);

そして、スタート位置、ゴール位置をセットします

grid.setStartNode(x, y);
grid.setEndNode(x, y);

これで初期設定完了

実際に経路探索する場合はこんな感じ

var astar:AStar = new AStar();
	if(astar.findPath(grid, false)){
		astarPath = astar.path;
		goalMoveText.GetComponent(TextMesh).text = "ゴールまで残り" + (astarPath.length-1) + "マス";
	}else{
		Debug.LogError("ゴールできません");
	}

AStarクラスのfindPathメソッドを呼ぶ。
引数はGridデータと斜め移動を許可するかどうかのフラグです。すごろくの場合は斜め移動はないので指定できるようにしました。
すると、astar.pathに、現在地点からゴールまでのNodeのリストが入っています。
次のマスを取得したい場合はastarPath[1];です。
最初に現在のノードが入っているので、ゴールまでのマスの数は-1するのを忘れずに。
これを移動するたびに行えばOK!

##今回の感想前回のにそのまま経路探索組み込んだだけなのでかなりチープなすごろくですがまぁご愛嬌ということで。
経路探索を使えばマス目形のゲームで大助かりです。
たとえば

今回のようなゴールへのマス数、最短経路を表示するようなすごろく
ダンジョンゲームで敵が追いかけてくる経路の計算
あるいはマスに好きに配置できる形のタワーディフェンスで、おけるかどうかのチェックや、敵の経路の計算

ぱっと思いつくので３つ。
ソースを変更すれば六角形のマスとかも同じ考え型でいけるはず。

では今回はこの辺で＾＾