/*
* Copyright (c) 2007 michiyasu wada
* http://www.seyself.com/
* 
* Distributed under The MIT License.
* [http://www.opensource.org/licenses/mit-license.php]
*/


package 
{
	
	public class Maze
	{
		public var map:Array;
		
		private var XMAX:uint;
		private var YMAX:uint;
		private var MAXSITE:uint;
		private var nsite:int;
		private var xx:Array;
		private var yy:Array;
		private var dx:Array;
		private var dy:Array;
		private var dirtable:Array;
		
		public function Maze( x:uint, y:uint )
		{
			_init( x, y );
		}
		
		/**
		* サイトに加える
		* @param	i
		* @param	j
		* @return
		*/
		public function add( i:int, j:int ):void
		{
			xx[nsite] = i; yy[nsite] = j; nsite++;
		}
		
		/**
		* サイトを乱数で選ぶ
		* @param	i
		* @param	j
		* @return
		*/
		public function select( i:int, j:int ):Array
		{
			var r:int;
			
			if(nsite==0) return null;
			nsite--; r = ( nsite * Math.random() ) >> 0;
			i = xx[r]; xx[r] = xx[nsite];
			j = yy[r]; yy[r] = yy[nsite];
			return [i,j];
		}
		
		public function create():Array
		{
			var i:int, j:int, i1:int, j1:int, d:int, t:int;
			var res:Array, tt:Array;
			
			/* 地図を初期化 */
			for(i=0; i<=XMAX; i++){
				for( j=0;j<=YMAX; j++ ) map[i][j] = 1;
			}
			for( i=3; i<=XMAX-3; i++ ){
				for( j=3; j<=YMAX-3; j++ ) map[i][j] = 0;
			}
			map[2][3] = 0;
			map[XMAX-2][YMAX-3] = 0;
			
			/* サイトを加える */
			for(i=4;i<=XMAX-4;i+=2){
				add( i, 2 ); add( i, YMAX-2 );
			}
			for(j=4;j<=YMAX-4;j+=2){
				add( 2, j ); add( XMAX-2, j );
			}
			
			/* サイトを選ぶ */
			while( res = select( i , j ) ){
				i = res[0];
				j = res[1];
				for(var n=1;n==1;n=1){
					tt = dirtable[Math.floor(24*Math.random())];
					for(d=3;d>=0;d--){
						t=tt[d]; i1=i+dx[t]; j1=j+dy[t];
						if( map[i1][j1]==0) break;
					}
					if(d<0) break;
					map[(i+i1)/2][(j+j1)/2] = 1;
					i=i1; j=j1; map[i][j]=1; add(i,j);
				}
			}
			return map;
		}
		
		public function toString():String
		{
			var i:int, j:int;
			var output:String = '';
			//for(j=2;j<=YMAX-2;j++){
				//for(i=2;i<=XMAX-2;i++){
					//if( map[i][j] ) output += 'X'; else output+=' ';
				//}
				//output+='\n';
			//}
			var y:int = map[0].length;
			var x:int = map.length;
			for(j=0;j<y;j++){
				for(i=0;i<x;i++){
					if( map[i][j] ) output += 'X'; else output+=' ';
				}
				output+='\n';
			}
			return output;
		}
		
		private function _init( x:uint, y:uint ):void
		{
			XMAX = x;
			YMAX = y;
			MAXSITE = XMAX * YMAX / 4;
			nsite = 0;
			map = arrayMatrix( XMAX + 1, YMAX + 1 );
			xx = new Array( MAXSITE );
			yy = new Array( MAXSITE );
			dx = [ 2, 0, -2,  0 ];
			dy = [ 0, 2,  0, -2 ];
			dirtable = [ [0,1,2,3], [0,1,3,2], [0,2,1,3], [0,2,1,3], [0,3,1,2], [0,3,2,1],
						 [1,0,2,3], [1,0,3,2], [1,2,0,3], [1,2,3,0], [1,3,0,2], [1,3,2,0],
						 [2,0,1,3], [2,0,3,1], [2,1,0,3], [2,1,3,0], [2,3,0,1], [2,3,1,0],
						 [3,0,1,2], [3,0,2,1], [3,1,0,2], [3,1,2,0], [3,2,0,1], [3,2,1,0] ];
		}
		
		public function arrayMatrix( x:uint, y:uint ):Array
		{
			var i:int, j:int;
			var a:Array = new Array( x );
			for (i = 0; i < x; i++) a[i] = new Array( y );
			return a;
		}
		
	}
	
	
}