flex45度游戏寻路————菱形

一个个的菱形都是坐标同eb163.com 的mapEdit地图编辑器一致，菱形是 左-右下排列，所以行是row*2

下边图片黑色是障碍物，蓝色是寻路得到的各个菱形,粉色是最小f，被蓝色挡住了,寻路类居然发错

package shape
{
	import flash.display.Shape;
	import flash.events.MouseEvent;
	import flash.geom.Point;
	
	import mx.core.UIComponent;
	
	import nod.Node;
	
	import util.CountState;

	public class MapShape extends UIComponent
	{
		
		public  var col:int=30;
		public  var row:int=20;
		public  var tileWidth:int=30;
		public  var tileHeight:int=15;
		public var color=0xf00fff;
		public var arr:Array=new Array;
		
		public function MapShape()
		{
			super();
			draw();
			addEvent();
		}
		//一列一列的画
		public function draw():void{
			var w:int=tileWidth/2;
			var h:int=tileHeight/2;
			for(var i:uint=0;i<col;i++){
				arr[i]=new Array;	
				for(var j:uint=0;j<row;j++){
//					if(i%2!=0){
						//2个2个的画
						//先画一个
						var sh1:Shape=new Shape;
						this.graphics.beginFill(0x486235);
//						this.graphics.lineStyle(1,0x656545);
						
						//step1 i左边
						this.graphics.moveTo(i*tileWidth,j*tileHeight+h);
						// 上边
						this.graphics.lineTo(i*tileWidth+w,j*tileHeight);
						//右边
						this.graphics.lineTo((i+1)*(tileWidth),j*tileHeight+h);
						//下边
						this.graphics.lineTo(i*tileWidth+w,(j+1)*(tileHeight));
						//回到左边
						this.graphics.lineTo(i*tileWidth,j*tileHeight+h);
						this.graphics.endFill();
						var node:Node=new Node();
						node.x=i;
						node.y=j*2;
						node.point=new Point(i*tileWidth,j*tileHeight+h);
						arr[i][j*2]=node;
						
//					}else{
						//然后 右移半个菱形宽
						//下移半个菱形高， 效果就是
						var sh2:Shape=new Shape
						this.graphics.beginFill(0xff0000);
//						
						//step1 i左边
						this.graphics.moveTo(i*tileWidth+w,j*tileHeight+h+h);
						// 上边
						this.graphics.lineTo(i*tileWidth+w+w,j*tileHeight+h);
						//右边
						this.graphics.lineTo((i+1)*(tileWidth)+w,j*tileHeight+h+h);
						//下边
						this.graphics.lineTo(i*tileWidth+w+w,(j+1)*(tileHeight)+h);
						//回到左边
//						this.graphics.lineTo(i*tileWidth,j*tileHeight+h);
						this.graphics.endFill();
						
						
						var nd:Node=new Node();
						nd.x=i;
						nd.y=j*2+1;
						nd.point=new Point(i*tileWidth+w,j*tileHeight+h+h);
						arr[i][(j*2)+1]=nd;
						
//					}
				}
			}
			
		}
		public function addEvent(){
			this.addEventListener(MouseEvent.CLICK,onClick);
		}
		public function onClick(event:MouseEvent){
			var mx:int=mouseX;
			var my:int=mouseY;
//			
//			 drawBox(event.target.point);
//			  var N:int=int(mx/tileWidth - my/tileHeight)
//            var M:int=int(mx/tileWidth + my/tileHeight);
//            mx.controls.Alert.show("N:"+N+"  M:"+M);
//			 Alert.show(arr[0].length+"");
//			 drawBox(XY2grid(mx,my));
			var p:Point=getCellPoint(this.tileWidth,this.tileHeight,mx,my);
//			mx.controls.Alert.show("x:"+p.x+"y:"+p.y);
			switch(color){
				case CountState.startColor:CountState.startNode=arr[p.x][p.y];break;
				case CountState.endColor:CountState.endNode=arr[p.x][p.y];break;
				case CountState.clogColor:arr[p.x][p.y].isClose=true;break;
			}
			drawBox(arr[p.x][p.y].point);
		}
		
		public function drawBox(start:Point):void{
			this.graphics.beginFill(color);
			var fx:int=start.x;
			var fy:int=start.y;
			this.graphics.moveTo(start.x,start.y); //左
			this.graphics.lineTo(fx+tileWidth/2,fy-tileHeight/2); //上
			this.graphics.lineTo(fx+tileWidth,fy);
			this.graphics.lineTo(fx+tileWidth/2,fy+tileHeight/2);
			
			this.graphics.endFill();
			
			trace("fill");
		}
		//返回值是数组下标
//	//根据屏幕像素去得网格坐标 jr的mapEdit方法
	//最重要的方法，没看什么意思
     public function getCellPoint(tileWidth:int, tileHeight:int, px:int, py:int):Point
		{
			var xtile:int = 0;	//网格的x坐标
			var ytile:int = 0;	//网格的y坐标
			
	        var cx:int, cy:int, rx:int, ry:int;
	        cx = int(px / tileWidth) * tileWidth + tileWidth/2;	//计算出当前X所在的以tileWidth为宽的矩形的中心的X坐标
	        cy = int(py / tileHeight) * tileHeight + tileHeight/2;//计算出当前Y所在的以tileHeight为高的矩形的中心的Y坐标
	
	        rx = (px - cx) * tileHeight/2;
	        ry = (py - cy) * tileWidth/2;
	
	        if (Math.abs(rx)+Math.abs(ry) <= tileWidth * tileHeight/4)
	        {
				//xtile = int(pixelPoint.x / tileWidth) * 2;
				xtile = int(px / tileWidth);
				ytile = int(py / tileHeight) * 2;
	        }
	        else
	        {
				px = px - tileWidth/2;
				//xtile = int(pixelPoint.x / tileWidth) * 2 + 1;
				xtile = int(px / tileWidth) + 1;
				
				py = py - tileHeight/2;
				ytile = int(py / tileHeight) * 2 + 1;
			}

			return new Point(xtile - (ytile&1), ytile);
		}
//
//		

}
}

 

package serach
{
 import mx.controls.*;
 import nod.Node;
 import flash.utils.setTimeout;
 import shape.MapShape;
 /**
  * 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:MapShape;//图形
  private var shapeArr:Array=new Array//图形数组
  public var openList:Array=[];
  public var closeList:Array=[];
//  //横向移动一格的路径评分
//  private const COST_HORIZONTAL : int = 20;
////  //竖向移动一格的路径评分
//  private const COST_VERTICAL : int = 5;
////  //斜向移动一格的路径评分
// 
//  private const COST_DIAGONAL : int = 12;

 //根据结果得出 上边和下边的路径评分都 一样
  //横向移动一格的路径评分
  private const COST_HORIZONTAL : int = 10;
  //竖向移动一格的路径评分  
  private const COST_VERTICAL : int = 10;
//  斜向移动一格的路径评分
 
  private const COST_DIAGONAL : int = 14;
  
  public function set Rect(re:MapShape){
   this.rect=re;
  }
  public function Find()
  {
   
  }
  public function init(){
   this.shapeArr=rect.arr;
  }
  
  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){
    trace(i);
    var current:Node=this.openList.shift();
    current.isClose=true;
    current.isOpen=false;
    closeList.push(current);
    
//    Alert.show("findwhile")
//    rect.color=0xf00fff;
//    rect.drawBox(current.point);
    if(current.x==end.x&&current.y==end.y){
     Alert.show(i+"次数");
     drawPath(current);
     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;
//       initNode(n.g,n.h,n.g+n.f,false,true,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;
//       initNode(n.g,n.h,n.g+n.f,false,true,current);
       openList.push(n);
       openList.sortOn("f",Array.NUMERIC);
//       Alert.show("h:"+h);
       
       
     }
    }
//    if(i==0){
//     break out;
//    }
//    break;
   } 
  }
  public function drawPath(node:Node){
   if(node.parentNode!=null){
    rect.color=0x0000ff;
    rect.drawBox(node.point);
    drawPath(node.parentNode);
   }
  }
  
  
  
  /**
   * 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(currentNode:Node,node:Node):int{
   var g:int = 0; 
   if (currentNode.y == node.y)   // 横向  左右
   {
    g = currentNode.g + this.COST_HORIZONTAL;
   }
   else if (currentNode.y+2 == node.y || currentNode.y-2 == node.y)// 竖向  上下    y坐标都差2个
   {
    g = currentNode.g + this.COST_VERTICAL * 2;
   }
   else      // 斜向  左上 左下 右上 右下
   {
    g = currentNode.g + this.COST_DIAGONAL;
   }
   
   return g;
  } 
  public function getH(around:Node,endNode:Node):int{
//   var leh:int=(Math.abs(around.x-end.x)+Math.abs(around.y-end.y))*10
   var dx:int;
   var dy:int;
   //节点到0，0点的x轴距离,判断是否 奇偶，奇数 说明还有半个菱形宽度没加，偶数就不用加
   var dxNodeTo0:int = around.x * this.COST_HORIZONTAL + (around.y&1) * this.COST_HORIZONTAL/2;
   //终止节点到0，0点的x轴距离
   var dxEndNodeTo0:int = endNode.x * this.COST_HORIZONTAL + (endNode.y&1) * this.COST_HORIZONTAL/2; 
   dx = Math.abs(dxEndNodeTo0 - dxNodeTo0);
   dy = Math.abs(endNode.y - around.y) * this.COST_VERTICAL;
   return dx + dy;
   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 checkX:int=x;
   var checkY:int=y;
   checkX = x-1
   checkY = y;
   getNode(checkX,checkY,nodes);
   
   //右
   checkX = x+1;
   checkY = y;
   getNode(checkX,checkY,nodes);
   //上
   checkX = x;
   checkY = y-2;
   getNode(checkX,checkY,nodes);
   //下
   checkX = x;
   checkY = y+2;
   getNode(checkX,checkY,nodes);
   //左上
   checkX = x-1+(y&1); //y&1 y是偶数是0，不属于红色方块某个，x左边-1.奇数是1 意思是，这个节点属于红色方块，说明x坐标不变
   checkY = y-1;
   getNode(checkX,checkY,nodes);
   //左下
   checkX = x-1+(y&1);
   checkY = y+1;
   getNode(checkX,checkY,nodes);
   //右上
   checkX = x+(y&1);
   checkY = y-1;
   getNode(checkX,checkY,nodes);
   //右下
   checkX = x+(y&1);
   checkY = y+1;
   getNode(checkX,checkY,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*2){ //因为横坐标y坐标有左（0，0）右下（0，1）同地图编辑器中一致，所以有row*2行
//  
    return false;
   } 
   trace("x:"+x+"y:"+y)
   if(shapeArr[x][y].isClose){
//    
    return false;
   }
   return true;
  }
  public function updateNode(current:Node,node:Node){
   for each(var ns:Node in this.openList){
    if(ns.point.equals(node.point)){
     ns=node;
     break;
    }
   }
   openList.sortOn("f",Array.NUMERIC);
  }
 }
}

 

 

package util
{
	import nod.Node;
	
	public class CountState
	{
		public static var startColor:uint=0x00ff00;//绿色
		public static var endColor:uint=0x0000ff;//蓝色
		public static var clogColor:uint=000000;//黑色
		public static var startNode:Node;
		public static var endNode:Node;
		public function CountState()
		{
		}

	}
}

 

 

<?xml version="1.0" encoding="utf-8"?>
<mx:Application xmlns:mx="http://www.adobe.com/2006/mxml" layout="absolute" xmlns:shape="shape.*">
	<mx:VBox>
		<shape:MapShape id="sh" height="300">
		
		</shape:MapShape>
	<mx:HBox>
		<mx:Button label="start" click="sh.color=CountState.startColor"> 
			
		</mx:Button>
		<mx:Button label="end" click="sh.color=CountState.endColor">
			
		</mx:Button>
		<mx:Button label="clog" click="sh.color=CountState.clogColor">
			
		</mx:Button>
		<mx:Button label="find" click="start()">
			
		</mx:Button>
		<mx:ColorPicker>
			
		</mx:ColorPicker>
	</mx:HBox>
	</mx:VBox>
	<mx:Script>
		<![CDATA[
			import serach.Find;
			import util.CountState;
			
			import serach.AStarPathFinder;
			import mx.controls.Alert;
			private var f:Find=new Find;
			
			public function start(){
				f.Rect=sh;
				f.init();
				var startTime:int = getTimer();
				f.startfind(CountState.startNode,CountState.endNode);
				var endTime:int = getTimer();
				
				Alert.show("find"+(endTime-startTime));
			}
		]]>
	</mx:Script>
	
</mx:Application>

 

/*
 * author: 白连忱
 * email: [e-mail]
 * vision: v0.1
 */

package serach
{
	import flash.geom.Point;
	import flash.utils.getTimer;
	

	
	public class AStarPathFinder
	{
		//====================================
		//	Constants
		//====================================
		//横向移动一格的路径评分
		private const COST_HORIZONTAL : int = 20;
		//竖向移动一格的路径评分
		private const COST_VERTICAL : int = 5;
		//斜向移动一格的路径评分
		private const COST_DIAGONAL : int = 12;
		
		
//		private var currentUseMap:Maps;	//当前使用的地图
		
		private var xMapStart:int;		//地图起始网格坐标
		private var yMapStart:int;		//地图起始网格坐标
		private var wMap:int;			//地图列数（每行格点数）
		private var hMap:int;			//地图行数（每列格点数）
		private var map:Array;			//与地图行列相同的数组，存放节点

		private var openList:Array = new Array();		//开放列表
		private var closeList:Array = new Array();		//关闭列表
		
		private var isFinded:Boolean = false;		//能否找到路径，true-已找到
		
		public var runTimeInMs:int = 0; 	//寻路时间
		
//		public function AStarPathFinder(useMap:Maps)
//		{
//			this.currentUseMap = useMap;
//			
//			//全图寻路
//			this.xMapStart = 0;
//			this.yMapStart = 0;
//			this.hMap = useMap.getMapHeight();
//			this.wMap = useMap.getMapWidth();
//			
//			//显示范围内寻路
////			this.xMapStart = useMap.getXMapStart();
////			this.yMapStart = useMap.getYMapStart();
////			this.hMap = useMap.getMapDisHeight();
////			this.wMap = useMap.getMapDisWidth();
//			
//			this.initMap();
//		}
		
		public function find(startPoint:Point, endPoint:Point):Array
		{
			///// 运行时间 ////////////
			var startTime:int = getTimer();
			//////////////////////////
			
			var currentNode:Node = map[startPoint.y][startPoint.x];
			var endNode:Node = map[endPoint.y][endPoint.x];
			
			openList.push(currentNode);
			
			var i=0;
			while(openList.length>0){
				//trace("openList.length:"+openList.length);
				//取出并删除开放列表第一个元素
				currentNode = openList.shift();
				
				//加入到关闭列表
				currentNode.isInOpen = false;
				currentNode.isInClose = true;
				this.closeList.push(currentNode);	
				i++;
				trace("寻路次数:"+i);
				trace("openLength.length"+openList.length);
				//当前节点==目标节点
				if(currentNode.x==endPoint.x && currentNode.y==endPoint.y){
					this.isFinded = true;	//能达到终点，找到路径
					break;
				}
				
				//取相邻八个方向的节点，去除不可通过和以在关闭列表中的节点
				var aroundNodes:Array = this.getAroundsNode(currentNode.x, currentNode.y);
				
				for each (var node:Node in aroundNodes) //检测相邻的八个方向的节点
				{
					//trace("node:"+node.x+"||"+node.y);
					//计算 G， H 值   
					var g:int = this.getGValue(currentNode, node);
					var h:int = this.getHValue(currentNode, endNode, node);
					
					if (node.isInOpen)	//如果节点已在播放列表中
					{
						//trace("node.isInOpen");
						//如果该节点新的G值比原来的G值小,修改F,G值，设置该节点的父节点为当前节点
						if (g < node.g)
						{
							node.g = g;
							node.h = h;
							node.f = g + h;
							node.parentNode = currentNode;
							
							this.findAndSort(node);
						}
					} 
					else //如果节点不在开放列表中
					{
						//trace("node.isNO");
						//插入开放列表中，并按照估价值排序
						node.g = g;
						node.h = h;
						node.f = g + h;
						node.parentNode = currentNode;
						
						this.insertAndSort(node);
					}
					
					
				}
				//trace(this+":for each end in find");
			}
			
			//trace("path find end");
			if (this.isFinded)	//找到路径
			{
				var path:Array = this.createPath(startPoint.x, startPoint.y);
				this.destroyLists();
				
				///// 运行时间 ////////////
				this.runTimeInMs = getTimer() - startTime;
				//////////////////////////
			
				return path;
			} else {	//没有找到路径
				this.destroyLists();
				
				///// 运行时间 ////////////
				this.runTimeInMs = getTimer() - startTime;
				//////////////////////////
				
				return null;
			}
		}
		
		/**
		 * 生成路径数组
		 */
		private function createPath(xStart:int, yStart:int):Array
		{
			var path:Array = new Array();
			
			var node:Node = this.closeList.pop();
			
			while (node.x != xStart || node.y != yStart)
			{
				path.unshift(new Point(node.x, node.y));
				node = node.parentNode;
			}
			path.unshift(new Point(node.x, node.y));
			
			return path;
		}
		
		/**
		 * 删除列表中原来的node，并将node放到正确顺序
		 */
		private function findAndSort(node:Node):void
		{
			//trace("findAndSort");
			var listLength:int = this.openList.length;
			
			if (listLength < 1) return;
			for (var i:int=0; i<listLength; i++)
			{
				if (node.f <= this.openList[i].f)
				{
					this.openList.splice(i, 0, node);
				}
				if (node.x == this.openList[i].x && node.y == this.openList[i].y)
				{
					this.openList.splice(i, 1);
				}
			}
			//trace("findAndSort end");
		}
		
		/**
		 * 按由小到大顺序将节点插入到列表
		 */
		private function insertAndSort(node:Node):void
		{
			//trace("insertAndSort");
			node.isInOpen = true;
			
			var listLength:int = this.openList.length;
			
			if (listLength == 0)
			{
				this.openList.push(node);
			} else {
				for (var i:int=0; i<listLength; i++)
				{
					//trace("openList.length:"+openList.length);
					if (node.f <= this.openList[i].f)
					{
						this.openList.splice(i, 0, node);
						return;
					}
				}
				this.openList.push(node);
			}
			//trace("insertAndSort end");
		}
		
		/**
		 * 计算G值
		 */
		private function getGValue(currentNode:Node, node:Node):int
		{
			var g:int = 0; 
			if (currentNode.y == node.y)			// 横向  左右
			{
				g = currentNode.g + this.COST_HORIZONTAL;
			}
			else if (currentNode.y+2 == node.y || currentNode.y-2 == node.y)// 竖向  上下
			{
				g = currentNode.g + this.COST_VERTICAL * 2;
			}
			else						// 斜向  左上 左下 右上 右下
			{
				g = currentNode.g + this.COST_DIAGONAL;
			}
			
			return g;
		}
		
		/**
		 * 计算H值
		 */
		private function getHValue(currentNode:Node, endNode:Node, node:Node):int
		{
			var dx:int;
			var dy:int;
			//节点到0，0点的x轴距离
			var dxNodeTo0:int = node.x * this.COST_HORIZONTAL + (node.y&1) * this.COST_HORIZONTAL/2;
			//终止节点到0，0点的x轴距离
			var dxEndNodeTo0:int = endNode.x * this.COST_HORIZONTAL + (endNode.y&1) * this.COST_HORIZONTAL/2; 
			dx = Math.abs(dxEndNodeTo0 - dxNodeTo0);
			dy = Math.abs(endNode.y - node.y) * this.COST_VERTICAL;
			return dx + dy;
		}
		
		/**
		 * 得到周围八方向节点
		 */
		private function getAroundsNode(x:int, y:int):Array
		{
			var aroundNodes:Array = new Array();
			
			var checkX:int;
			var checkY:int;
			/**
			 * 菱形组合的地图八方向与正常不同
			 */
			//左
			checkX = x-1
			checkY = y;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("左:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//右
			checkX = x+1;
			checkY = y;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("右:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//上
			checkX = x;
			checkY = y-2;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("上:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//下
			checkX = x;
			checkY = y+2;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("下:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//左上
			checkX = x-1+(y&1);
			checkY = y-1;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("左上:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//左下
			checkX = x-1+(y&1);
			checkY = y+1;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("左下:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//右上
			checkX = x+(y&1);
			checkY = y-1;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("右上:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			//右下
			checkX = x+(y&1);
			checkY = y+1;
			if (isWalkable(checkX, checkY) && !this.map[checkY][checkX].isInClose)
			{
				//trace("右下:::"+checkY+"##"+checkX);
				aroundNodes.push(this.map[checkY][checkX]);
			}
			
			return aroundNodes;
		}
		
		/**
		 * 检查点在地图上是否可通过
		 */
		private function isWalkable(x:int, y:int):Boolean
		{
			// 1. 是否是有效的地图上点（数组边界检查）
			if (x < this.xMapStart || x >= this.wMap) 
			{
				return false;
			}
			if (y < this.yMapStart || y >= this.hMap)
			{
				return false;
			}
//			trace("this.currentUseMap.getWalkable("+x+","+y+")"+this.currentUseMap.getWalkable(x, y));
			// 2. 是否是walkable
			return this.currentUseMap.getWalkable(x, y);
		}
		
		
		/**
		 * 使用节点初始化一个行列与地图格点相同的数组
		 */
		private function initMap()	:void
		{
//			trace("***"+this.hMap);
//			trace("***"+this.wMap);
			this.map = [];
			for (var y:int=this.yMapStart; y<this.hMap; y++) {
				if (map[y] == undefined) {
					map[y] = [];
				}
				for (var x:int=this.xMapStart; x<this.wMap; x++) {
					map[y][x] = new Node(x, y);
				}
			}
		}
		
		/**
		 * 销毁数组
		 */
		private function destroyLists():void
		{
			this.closeList = null;
			this.openList = null;
			this.map = null;
		}
		
	}//end class
	
}//end package


class Node
{
	public var x:int;
	public var y:int;
	public var isInOpen:Boolean;
	public var isInClose:Boolean;
	public var g:int;
	public var h:int;
	public var f:int;
	public var parentNode:Node;
	
	public function Node(x:int, y:int)
	{
		this.x = x;
		this.y = y;
		this.isInOpen = false;
		this.isInClose = false;
		this.g = 0;
		this.h = 0;
		this.f = 0;
		this.parentNode = null;
	}
}