flex简单基于A*寻路

没设置障碍物，熬了一晚上，原来是个很简单的问题

package drawRect
{
	import flash.events.MouseEvent;
	import flash.geom.Point;
	
	import mx.core.UIComponent;
	import mx.logging.Log;
	import mx.controls.*;
	import node.Node;
	public class MyRect extends UIComponent
	{
		public var rectArray:Array=[];
		public var color:uint=0x3215;
		public var COL:int=15;
		public var ROW:int=10;
		public var LENGTH:int=40;
		
		public function MyRect()
		{
			super();
			trace("init");
			Log.getLogger("drawRect.MyRect").debug("sssss");
			Log.getLogger("drawRect.MyRect").info("dsafdasf");
//			mx.controls.Alert.show("init");
			drawRect();
			initEvent();	
		}
		//一列一列的画
		/**
		 * i:0j:0:(x=0, y=0)
		   i:0j:1:(x=0, y=40)
		   i:0j:2:(x=0, y=80)
		   i:1j:0:(x=40, y=0)
           i:1j:1:(x=40, y=40)
           i:1j:2:(x=40, y=80)
		 * 
		 * 
		 * **/
		public function drawRect():void{
			this.graphics.beginFill(color);
			for(var i:int=0;i<this.COL;i++){
				rectArray[i]=new Array;
				for(var j:int=0;j<this.ROW;j++){
					this.graphics.drawRect(i*LENGTH,j*LENGTH,LENGTH-1,LENGTH-1);
					var nd:Node=new Node;
					nd.x=i;
					nd.y=j;
					nd.point=new Point(i*LENGTH,j*LENGTH);
					rectArray[i][j]=nd;
					
					trace("i:"+i+"j:"+j+":"+rectArray[i][j].point)
				}
				
			}
			this.graphics.endFill();
			
			
		}
		public function initEvent(){
			this.addEventListener(MouseEvent.CLICK,onClick);
		}
		public function onClick(e:MouseEvent){
			
			Alert.show(rectArray[13][5]);
			var mx:Number=e.localX;
			var my:Number=e.localY;
			//方法1得到鼠标点击后的数组索引
//			var nodex:int=Math.floor(mx/LENGTH)+(mx%LENGTH>0?1:0)-1;
//			var nodey:int=Math.floor(my/LENGTH)+(my%LENGTH>0?1:0)-1;
			//方法2
			var nodex:int=Math.floor(mx/LENGTH)
			var nodey:int=Math.floor(my/LENGTH)
			trace("mx/length floor:"+Math.floor(mx/LENGTH))
			trace("mx/length"+mx/LENGTH)
			trace("x:"+nodex+"y:"+nodey)
			drawBox(rectArray[nodex][nodey].point);
		}
		public function drawBox(point:Point){
			this.graphics.beginFill(color);
			this.graphics.drawRect(point.x,point.y,LENGTH-1,LENGTH-1);
			this.graphics.endFill();
		}
	}
}

 

package find
{
	import drawRect.MyRect;
	
	import flash.geom.Point;
	
	import mx.controls.*;
	
	import node.Node;
	/**
	 * 1.
将开始节点放入开放列表(开始节点的F和G值都视为0);
2.
重复一下步骤:
            i.
在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点;
           ii.
把当前节点从开放列表删除, 加入到封闭列表;
         iii.
对当前节点相邻的每一个节点依次执行以下步骤:
1.
如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,则什么操作也不执行,继续检验下一个节点;
2.
如果该相邻节点不在开放列表中,则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节点,同时保存该相邻节点的G和F值;
3.
如果该相邻节点在开放列表中, 则判断若经由当前节点到达该相邻节点的G值是否小于原来保存的G值,若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
        iv.
循环结束条件:
当终点节点被加入到开放列表作为待检验节点时, 表示路径被找到,此时应终止循环;
或者当开放列表为空,表明已无可以添加的新节点,而已检验的节点中没有终点节点则意味着路径无法被找到,此时也结束循环;
3.
从终点节点开始沿父节点遍历, 并保存整个遍历到的节点坐标,遍历所得的节点就是最后得到的路径;
	 
	 * G＝从起点A沿着已生成的路径到一个给定方格的移动开销。 

       H＝从给定方格到目的方格的估计移动开销
	 * * **/
	public class Find
	{
		private var rect:MyRect;//图形
		private var shapeArr:Array=new Array//图形数组
		public var openList:Array=[];
		public var closeList:Array=[];
		public function set Rect(re:MyRect){
			this.rect=re;
		}
		public function Find()
		{
			
		}
		public function init(){
			this.shapeArr=rect.rectArray;
			
		}
		
		public function startfind(start:Node,end:Node){
			
			start.g=0;
			start.h=0;
			start.isOpen=true;
			openList.push(start);
			var i:int=0;
			out:while(openList.length>0){
				var current:Node=this.openList.shift();
				current.isClose=true;
				current.isOpen=false;
				closeList.push(current);
				
				rect.color=0x9999;
				rect.drawBox(current.point);
				if(current.point.equals(end.point)){
					Alert.show(i+"次数");
					break;
				}
				i++;
//				if(i==1){
//					rect.color=0x9999;
//					rect.drawBox(current.point);
//					trace("f:"+current.f)
//					trace("g:"+current.g);
//					trace("h:"+current.h);
//					var nodes:Array=getAround(current,end);
//					for each(var n:Node in nodes){
//						trace("f:"+n.f)
//						trace("g"+n.g);
//						trace("h"+n.h);
//					}
//					break;
//				}
//				i++;
				var nodes:Array=getAround(current,end);
//				mx.controls.Alert.show("sdaffsaf"+nodes.length);
				
				for each(var n:Node in nodes){
//					rect.color=0x9999;
//					rect.drawBox(n.point);
					var g:int=getG(current,n);
					trace("gggggggg"+g);
					var h:int=getH(n,end);
					trace("h::::::"+h);
					trace("point:::::"+n.point)
					trace(n.x+"xxxxxxxxxxxx"+n.y)
					if(n.isOpen){
						if(g<n.g){
							n.g=g;
							n.h=h;
							n.f=n.g+n.h;
							n.isClose=false;
							n.isOpen=true;
							n.parentNode=current;
							updateNode(current,n);
							
						}
					}else{
						    n.g=g;
							n.h=h;
							n.f=n.g+n.h;
							n.isClose=false;
							n.isOpen=true;
							n.parentNode=current;
							openList.push(n);
							openList.sortOn("f",Array.NUMERIC);
//							Alert.show("h:"+h);
							output();
							
					}
				}
//				if(i==0){
//					break out;
//				}
//				break;
			}	
		}
		
		private function output(){
			for each(var nl:Node in openList){
				trace("list:"+nl.f);
			}
			trace("sp");
		}
		/**
		 * i:0j:0:(x=0, y=0)
		   i:0j:1:(x=0, y=40)
		   i:0j:2:(x=0, y=80)
		   i:1j:0:(x=40, y=0)
           i:1j:1:(x=40, y=40)
           i:1j:2:(x=40, y=80)
		 * 
		 * 
		 * **/		
		public function getG(current:Node,np:Node){
			var g=0;
			if(current.x==np.x){
				g=current.g+10;
				return g;
			}
			if(current.y==np.y){
				g=current.g+10;
				return g;
			}
			 return current.g+14;
		} 
		public function getH(around:Node,end:Node):int{
			var cp:Point=around.point;
			var fn:Point=end.point;
			
			
			var leh:int=(Math.abs(around.x-end.x)+Math.abs(around.y-end.y))*10

			return leh;
		}
		//得到周围的节点
		public function getAround(current:Node,end:Node):Array{
			var nodes:Array=new Array;
			var x:int=current.x;
			var y:int=current.y;
			var indexX:int=x;
			var indexY:int=y;
			//左上
			indexX=x-1;
			indexY=y-1;
			getNode(indexX,indexY,nodes);
			//左
			indexX=x-1;
			indexY=y;
			getNode(indexX,indexY,nodes);
			//左下
			indexX=x-1;
			indexY=y+1;
			getNode(indexX,indexY,nodes);
			
			//上
			indexX=x;
			indexY=y-1;
			getNode(indexX,indexY,nodes);
			//下
			indexX=x;
			indexY=y+1;
			getNode(indexX,indexY,nodes);
			//右上
			indexX=x+1;
			indexY=y-1;
			getNode(indexX,indexY,nodes);
			//右
			indexX=x+1;
			indexY=y;
			getNode(indexX,indexY,nodes);
			//下
			indexX=x+1;
			indexY=y+1;
			getNode(indexX,indexY,nodes);
			return nodes;
		}
		public function getNode(indexX:int,indexY:int,nodes:Array){
			if(isValid(indexX,indexY)){
				var node:Node=shapeArr[indexX][indexY];
				nodes.push(node);
			}
		}
		
		public function isValid(x,y):Boolean{
			if(x<0||x>=rect.COL||y<0||y>=rect.ROW){
//				trace("false");
				return false;
			}	
			trace("x:"+x+"y:"+y)
			if(shapeArr[x][y].isClose){
//				trace("false");
				return false;
			}
			return true;
		}
		public function updateNode(current:Node,nod:Node){
			for each(var ns:Node in this.openList){
				if(ns.point.equals(nod.point)){
					ns=nod;
					break;
				}
			}
			openList.sortOn("f",Array.NUMERIC);
		}
	}
}

 

package node
{
	import flash.geom.Point;
	
	public class Node
	{
		public var x:int=0;
		public var y:int=0;
		public var point:Point;
		public var isOpen:Boolean=false;
		public var isClose:Boolean=false;
		public var g:int=0;
		public var h:int=0;
		public var f:int=0;
		public var parentNode:Node=null;
		public function Node()
		{
		}

	}
}

 

<?xml version="1.0" encoding="utf-8"?>
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" xmlns:shape="shape.*" 
	xmlns:drawRect="drawRect.*">
	<mx:VBox>
		<drawRect:MyRect height="400" id="draw">
		
		</drawRect:MyRect>
		<mx:HBox>
			<mx:Button label="start" id="start" click="draw.color=0x2222">
				
			</mx:Button>
			<mx:Button label="end" id="end" click="draw.color=0x8546">
				
			</mx:Button>
			<mx:Button label="fin" click="test()">
				
			</mx:Button>
		</mx:HBox>
	</mx:VBox>
	<mx:Script>
		<![CDATA[
			import find.Find;
			public function test(){
				draw.color=0x4444;
				var fi:Find=new Find;
				fi.Rect=draw;
				fi.init();
				fi.startfind(draw.rectArray[5][0],draw.rectArray[13][9]);
				trace("find");
			}
		]]>
	</mx:Script>
</mx:Application>