Astar

Astar.as

package
{
	public class Astar
	{
		private var _abierto:Array;
		private var _cerrado:Array;
		private var _cuadricula:Cuadricula;
		private var _nodoFinal:Nodo;
		private var _nodoInicial:Nodo;
		private var _ruta:Array;
		//private var _heuristica:Function = manhattan;
		private var _heuristica:Function = euclidian;
		//private var _heuristica:Function = diagonal;
		private var _costoLateral:Number = 1.0;
		private var _costoDiagonal:Number = Math.SQRT2;
		public function Astar()
		{
		}
		public function buscaRuta(cuadricula:Cuadricula)
		{
			_cuadricula = cuadricula;
			_abierto = new Array();
			_cerrado = new Array();
			_nodoInicial = _cuadricula.nodoInicial;
			_nodoFinal = _cuadricula.nodoFinal;
			_nodoInicial.g = 0;
			_nodoInicial.h = _heuristica(_nodoInicial);
			_nodoInicial.f = _nodoInicial.g + _nodoInicial.h;
			return busca();
		}
		public function busca():Boolean
		{
			var nodo:Nodo = _nodoInicial;
			while (nodo != _nodoFinal)
			{
				var X1:int = Math.max(0,nodo.x - 1);
				var X2:int = Math.min(_cuadricula.Columnas - 1,nodo.x + 1);
				var Y1:int = Math.max(0,nodo.y - 1);
				var Y2:int = Math.min(_cuadricula.Filas - 1,nodo.y + 1);
				for (var i:int = X1; i <= X2; i++)
				{
					for (var j:int = Y1; j <= Y2; j++)
					{
						var prueba:Nodo = _cuadricula.dameNodo(i,j);
						if (prueba == nodo || ! prueba.permitido || ! _cuadricula.dameNodo(nodo.x,prueba.y).permitido || !_cuadricula.dameNodo(prueba.x,nodo.y).permitido)
						{
							continue;
						}
						var costo:Number = _costoLateral;
						if (!((nodo.x == prueba.x) || (nodo.y == prueba.y)))
						{
							costo = _costoDiagonal;
						}
						var g:Number = nodo.g + costo;
						var h:Number = _heuristica(prueba);
						var f:Number = g + h;
						if (estaAbierto(prueba) || estaCerrado(prueba))
						{
							if (prueba.f > f)
							{
								prueba.f = f;
								prueba.g = g;
								prueba.h = h;
								prueba.padre = nodo;
							}
						}
						else
						{
							prueba.f = f;
							prueba.g = g;
							prueba.h = h;
							prueba.padre = nodo;
							_abierto.push(prueba);
						}
					}
				}
				_cerrado.push(nodo);
				if (_abierto.length == 0)
				{
					trace("No se encontro el camino");
					return false;
				}
				_abierto.sortOn("f",Array.NUMERIC);
				nodo = _abierto.shift() as Nodo;
			}
			construirRuta();
			return true;
		}
		private function construirRuta():void
		{
			_ruta = new Array();
			var nodo:Nodo = _nodoFinal;
			_ruta.push(nodo);
			while (nodo != _nodoInicial)
			{
				nodo = nodo.padre;
				_ruta.unshift(nodo);
			}
		}
		public function get ruta():Array
		{
			return _ruta;
		}
		private function estaAbierto(nodo:Nodo):Boolean
		{
			for (var i:int = 0; i < _abierto.length; i++)
			{
				if (_abierto[i] == nodo)
				{
					return true;
				}
			}
			return false;
		}
		private function estaCerrado(nodo:Nodo):Boolean
		{
			for (var i:int = 0; i < _cerrado.length; i++)
			{
				if (_cerrado[i] == nodo)
				{
					return true;
				}
			}
			return false;
		}
		private function manhattan(nodo:Nodo):Number
		{
			return Math.abs(nodo.x - _nodoFinal.x) * _costoLateral + Math.abs(nodo.y - _nodoFinal.y) * _costoLateral;
		}
		private function euclidian(nodo:Nodo):Number
		{
			var dx:Number = nodo.x - _nodoFinal.x;
			var dy:Number = nodo.y - _nodoFinal.y;
			return Math.sqrt(dx * dx + dy * dy) * _costoLateral;
		}
		private function diagonal(nodo:Nodo):Number
		{
			var dx:Number = Math.abs(nodo.x - _nodoFinal.x);
			var dy:Number = Math.abs(nodo.y - _nodoFinal.y);
			var diagonal:Number = Math.min(dx,dy);
			var derecho:Number = dx + dy;
			return _costoDiagonal * diagonal + _costoLateral * derecho - 2 * diagonal;
		}
		public function get visitado():Array
		{
			return _cerrado.concat(_abierto);
		}
	}
}