AS3でゲームを作成する　その３７ | Photoshop CC Tutorials
AmebaAmeba 20th Anniv.ホームピグアメブロ
芸能人ブログ人気ブログ
新規登録
ログイン

Photoshop CC Tutorials

-

AS3でゲームを作成する　その３７

今回は下記のサイトのプログラムを参考にし、コンピュータを動かすための
経路探索アルゴリズムを作成しました。

参考文献サイト：http://itpro.nikkeibp.co.jp/article/COLUMN/20070223/263174/?ST=develop

↓このようなコンピュータを自動で動かすアルゴリズムです。
$ピック社長のブログ

実行結果：各マスのコストを表示させてみました。
$ピック社長のブログ

Display.as
package 
{
	/**
	* 
	* 
	*/
	import flash.display.BitmapData;
	import flash.geom.Point;
	import flash.geom.Rectangle;
	import flash.media.Sound;
	import flash.net.URLRequest;
	
	public class Display
	{
		private const MAP_WIDTH:int = 15;/* マップのサイズ */
		private const MAP_HEIGHT:int = 5;

		private const ROBO_XPOS:int = 0;/* ロボットの位置 */
		private const ROBO_YPOS:int = 2;

		private const GOAL_XPOS:int = 14;/* ゴールの位置 */
		private const GOAL_YPOS:int = 2;

		private const ATTR_EMPTY:int = 0;/* マップの1マスぶんの内容 */
		private const ATTR_SEARCH:int = 1;
		private const ATTR_CLOSE:int = 2;
		private const ATTR_WALL:int = 3;
		private const ATTR_GOAL:int = 4;
		private const ATTR_START:int = 5;
		private const ATTR_PATH:int = 6;
		
		/* マップ全体を示すmapfield配列 */
		private var mapfield:Array = [MAP_HEIGHT];
		/* 探索地点を集めるバッファ */
		private const SEARCHQUE_LIMIT:int = 50;
		private var searchque:Array = [SEARCHQUE_LIMIT];
		private var searchque_head:int = 0;
		
		public function Display(source_01:BitmapData, source_02:BitmapData)
		{
			map_init();
			root_search(ROBO_XPOS, ROBO_YPOS, GOAL_XPOS, GOAL_YPOS);
			
			// mapfield配列に格納されているノードオブジェクトを表示する
			for (var i:int = 0; i < MAP_HEIGHT; i++ ) {
				for (var j:int = 0; j < MAP_WIDTH; j++ ) {
					trace(mapfield[i][j].cost);
				}
			}
		}
		
		/* マップの初期化 */
		public function map_init():void
		{
			var j:int, i:int;

			for (i = 0; i < MAP_HEIGHT; i++) {
				mapfield[i] = new Array(MAP_WIDTH);
				for (j = 0; j < MAP_WIDTH; j++) {
					mapfield[i][j] = new t_node();
					mapfield[i][j].pos.x = j;
					mapfield[i][j].pos.y = i;
				}
			}
			
			/* 障害物の設定 */
			for (i = 0; i < 4; i++) {
				mapfield[i][10].attr = ATTR_WALL;
				mapfield[(MAP_HEIGHT - 1) - i][4].attr = ATTR_WALL;
			}
		}


		/* -------------------------------------------------------- */
		/* 2点間の距離を測る */
		public function distance(pos1:t_point, pos2:t_point):int
		{
			var dx:int, dy:int, d:int;

			dx = Math.abs(pos1.x - pos2.x);
			dy = Math.abs(pos1.y - pos2.y);

			d = ((dx < dy) ? dx : dy) / 2;
			return  dx + dy - d;
		}

		/* コストを計る */
		public function poscost(pos:t_point, checkpos:t_point):int
		{
			var cost:int;

			/* 2点間の距離をそのままコストに */
			cost = distance(pos, checkpos);
			return cost;
		}

		/* -------------------------------------------------------- */
		/* キューに探索候補を追加 */
		public function que_push(node:t_node):void
		{
			var tmpnode:t_node;
			var i:int, j:int;

			if (searchque_head >= SEARCHQUE_LIMIT)
				return;
			searchque[searchque_head] = node;
			searchque_head++;

			// コストの低い順でソートしておく
			if (searchque_head <= 1)
				return;
			for (i = 0; i < searchque_head; i++) {
				for (j = 1; j < searchque_head - i; j++) {
					if (searchque[j - 1].cost < searchque[j].cost) {
						tmpnode = searchque[j - 1];
						searchque[j - 1] = searchque[j];
						searchque[j] = tmpnode;
					}
				}
			}
		}

		/* キューから探索候補を取り出す  */
		public function que_pop():t_node
		{
			if (searchque_head == 0)
				return null;
			searchque_head--;
			return searchque[searchque_head];
		}

		/* -------------------------------------------------------- */
		/* 探索されたパスをたどる */
		public function path_check(goaly:int, goalx:int):void
		{
			var x:int, y:int, nextx:int, nexty:int;
			
			nextx = mapfield[goaly][goalx].backpos.x;
			nexty = mapfield[goaly][goalx].backpos.y;
			do {
				x = nextx;
				y = nexty;
				mapfield[y][x].attr = ATTR_PATH;
				nextx = mapfield[y][x].backpos.x;
				nexty = mapfield[y][x].backpos.y;
			} while(mapfield[nexty][nextx].attr != ATTR_START);
		}


		/* -------------------------------------------------------- */
		/* -------------------------------------------------------- */
		/* 探索本体 */
		public function root_search(startx:int, starty:int, goalx:int, goaly:int):void
		{
			/* 8方向を調べるための相対座標 */
			var difpos:Array = [ { x: -1, y: -1 }, { x: 0, y: -1 }, { x:1, y: -1 },
								 { x: -1, y:  0 }, { x: 1, y:  0 },
								 { x: -1, y:  1 }, { x: 0, y:  1 }, { x:1, y:  1 } ];
								 
			var i:int, checkx:int, checky:int, cost:int, checkcount:int;
			var checkxCopy:int, checkyCopy:int;
			var nowpos:t_node;
			searchque_head = 0;
			
			// ゴールとスタートの設定
			mapfield[starty][startx].attr = ATTR_START;
			mapfield[starty][startx].cost = 200;
			mapfield[goaly][goalx].attr = ATTR_GOAL;
			
			// スタート位置をキューに入れる
			que_push(mapfield[starty][startx]);
			
			// checknodeがゴールに行くまでループ
			do {
				// 調べる位置をキューから取り出す
				nowpos = que_pop();
				if(nowpos == null) {
					trace("ゴールに到達できません。\n");
					return;
				}
			
				// 8方向調べる
				checkcount = 0;
				for (i = 0; i < 8; i++) {
					checkxCopy = nowpos.pos.x + difpos[i].x;
					checkyCopy = nowpos.pos.y + difpos[i].y;
					
					// 範囲チェック
					if ((checkxCopy < 0) || (checkxCopy >= MAP_WIDTH) || (checkyCopy < 0) || (checkyCopy >= MAP_HEIGHT))
						continue;
						
					checkx = checkxCopy;
					checky = checkyCopy;

					// ゴールだったら抜ける
					if (mapfield[checky][checkx].attr == ATTR_GOAL) {
						mapfield[checky][checkx].backpos.x = nowpos.pos.x;
						mapfield[checky][checkx].backpos.y = nowpos.pos.y;
						break;
					}

					// 壁や調査済みだったらその位置は使わない
					if (mapfield[checky][checkx].attr != ATTR_EMPTY)
						continue;
					
					// コストを得る
					cost = poscost(mapfield[checky][checkx].pos, 
								   mapfield[goaly][goalx].pos);
								   
					// コストをそこに置いて次の調査へ
					mapfield[checky][checkx].attr = ATTR_SEARCH;
					mapfield[checky][checkx].cost = cost;
					mapfield[checky][checkx].backpos.x = nowpos.pos.x;
					mapfield[checky][checkx].backpos.y = nowpos.pos.y;
					que_push(mapfield[checky][checkx]);
					checkcount++;
				}
				
				// 1回も周囲を調べられなかったら，今後その位置は使わない
				if ((!checkcount) && (nowpos.attr == ATTR_SEARCH))
					nowpos.attr = ATTR_CLOSE;
				if (nowpos.attr == ATTR_EMPTY)
					nowpos.attr = ATTR_SEARCH;
			}
			while(mapfield[checky][checkx].attr != ATTR_GOAL);
			path_check(goaly, goalx);
		}
		
	}
	
}


t_node.as
package  
{
	/**
	 * ノードクラス
	 */
	public class t_node
	{
		public var pos:t_point = new t_point();      /* 自分の場所                 */
		public var backpos:t_point = new t_point();  /* 探索を始めた場所           */
		public var cost:int = 0;         /* 現在位置のコスト           */
		public var attr:int = 0;         /* その地点が探索済みかどうか */
	  
		public function t_node() 
		{
			
		}
		
	}

}


t_point.as
package  
{
	/**
	 * x, y の2点間を示すクラス
	 */
	public class t_point
	{
		public var x:int, y:int;
		
		public function t_point() 
		{
			 
		}
		
	}

}