Archive for May, 2006

flash的AStar寻路类 应该对研究tile的同学有帮助

Wednesday, May 3rd, 2006

具体用法需要研究的同学看三个public入口就知道了。

  1. /**
  2. * @author hirokimo
  3. * @data 2006-05-03
  4. * @usage A*path searching
  5. */
  6. class Astar {
  7.     private static var cost:Number = 10;
  8.     private static var isSearching:Boolean = false;
  9.     private static var broadcastInit = AsBroadcaster.initialize(Astar.prototype);
  10.     public var addListener:Function;
  11.     public var removeListener:Function;
  12.     private var broadcastMessage:Function;
  13.     private var path:Array;
  14.     private var openList:Array;
  15.     private var closeList:Array;
  16.     private var map:Array;
  17.     private var pointType:Array;
  18.     private var directData:Array;
  19.     //
  20.     public function Astar() {
  21.         path = new Array();
  22.         pointType = new Array();
  23.         openList = new Array();
  24.         closeList = new Array();
  25.         directData = new Array();
  26.         map = new Array();
  27.         initDirectData();
  28.     }
  29.     public function setMap(map_t:Array) {
  30.         map = map_t;
  31.         setPointType(map);
  32.     }
  33.     public function findPath(startX:Number, startY:Number, endX:Number, endY:Number) {
  34.         initData();
  35.         isSearching = true;
  36.         var startPoint:Object = new Object();
  37.         var endPoint:Object = new Object();
  38.         var prePoint:Object = new Object();
  39.         startPoint.X = startX;
  40.         startPoint.Y = startY;
  41.         endPoint.X = endX;
  42.         endPoint.Y = endY;
  43.         startPoint.parent = null;
  44.         startPoint.G = 0;
  45.         startPoint.H = manhattanDis(startPoint, endPoint);
  46.         startPoint.F = startPoint.G+startPoint.H;
  47.         prePoint = startPoint;
  48.         //send2List(startPoint, openList);
  49.         send2List(startPoint, closeList);
  50.         while (isSearching == true) {
  51.             for (var i = 0; i<directData.length; i++) {
  52.                 var tempPoint:Object = new Object();
  53.                 tempPoint.X = prePoint.X+directData[i][0];
  54.                 tempPoint.Y = prePoint.Y+directData[i][1];
  55.                 if (isOut(tempPoint) == true) {
  56.                 } else {
  57.                     if (tempPoint.Y == endPoint.Y && tempPoint.X == endPoint.X) {
  58.                         //found
  59.                         isSearching = false;
  60.                         send2List(tempPoint, closeList);
  61.                         tempPoint.parent = prePoint;
  62.                         tempPoint.G = prePoint.G+directData[i][2];
  63.                         tempPoint.H = manhattanDis(tempPoint, endPoint);
  64.                         tempPoint.F = tempPoint.G+tempPoint.H;
  65.                         //trace(closeList[closeList.length-1].X+" "+closeList[closeList.length-1].Y);
  66.                         //trace("path found!");
  67.                         drawPath();
  68.                         broadcastMessage("onPathFound");
  69.                         return;
  70.                     }
  71.                     if (getPointType(tempPoint) == "road" && isInList(tempPoint, closeList) == false) {
  72.                         //trace("四向之"+i+" tempPoint:"+tempPoint.X+" "+tempPoint.Y);
  73.                         //目标格不在关闭列表且是road
  74.                         if (isInList(tempPoint, openList) == false) {
  75.                             //目标格尚未开启
  76.                             send2List(tempPoint, openList);
  77.                             //trace("ol:"+openList[0].X+"=="+openList[0].Y);
  78.                             tempPoint.parent = prePoint;
  79.                             tempPoint.G = prePoint.G+directData[i][2];
  80.                             tempPoint.H = manhattanDis(tempPoint, endPoint);
  81.                             tempPoint.F = tempPoint.G+tempPoint.H;
  82.                         } else {
  83.                             //已经在开启列表中
  84.                             var tempG:Number = prePoint.G+directData[i][2];
  85.                             for (var j = 0; j<openList.length; j++) {
  86.                                 if (tempPoint.X == openList[j].X && tempPoint.Y == openList[j].Y) {
  87.                                     if (tempG<openList[j].G) {
  88.                                         //现在的路径G更好
  89.                                         openList[j].G = tempG;
  90.                                         openList[j].F = openList[j].G+openList[j].H;
  91.                                         openList[j].parent = prePoint;
  92.                                     }
  93.                                     break;
  94.                                 }
  95.                             }
  96.                         }
  97.                     }
  98.                 }
  99.             }
  100.             if (openList.length == 0) {
  101.                 isSearching = false;
  102.                 broadcastMessage("onPathBlock");
  103.                 return;
  104.             }
  105.             sortList(openList);
  106.             prePoint = openList.shift();
  107.             send2List(prePoint, closeList);
  108.             //trace(closeList[closeList.length-1].X+" "+closeList[closeList.length-1].Y);
  109.         }
  110.     }
  111.     public function getPath():Array {
  112.         path.reverse();
  113.         trace("==========Path start===========");
  114.         for (var i = 0; i<path.length; i++) {
  115.             trace("path:"+path[i].X+path[i].Y);
  116.         }
  117.         trace("==========Path  end ===========");
  118.         return path;
  119.     }
  120.     private function initData():Void {
  121.         openList = [];
  122.         closeList = [];
  123.         path = [];
  124.     }
  125.     private function drawPath() {
  126.         //trace("set path");
  127.         closeList.reverse();
  128.         var currentPathPoint:Object = new Object();
  129.         currentPathPoint = closeList[0];
  130.         send2List(currentPathPoint, path);
  131.         //trace(currentPathPoint.X+" "+currentPathPoint.Y);
  132.         for (var i = 1; i<closeList.length; i++) {
  133.             if (currentPathPoint.parent == null) {
  134.                 break;
  135.             }
  136.             //trace(currentPathPoint.parent.X+" "+currentPathPoint.parent.Y);                                                           
  137.             send2List(currentPathPoint.parent, path);
  138.             currentPathPoint = currentPathPoint.parent;
  139.         }
  140.     }
  141.     private function getPointType(point_t:Object):String {
  142.         return pointType[point_t.X][point_t.Y];
  143.     }
  144.     private function setPointType(map_t:Array) {
  145.         for (var i = 0; i<map_t.length; i++) {
  146.             pointType[i] = new Array();
  147.             for (var j = 0; j<map_t[0].length; j++) {
  148.                 if (map_t[i][j] == 1) {
  149.                     pointType[i].push("wall");
  150.                 } else if (map_t[i][j] == 0) {
  151.                     pointType[i].push("road");
  152.                 }
  153.             }
  154.         }
  155.         //trace("第一行:"+pointType[0]);
  156.     }
  157.     private function initDirectData():Void {
  158.         //下，右，上，左
  159.         directData[0] = [1, 0, 10];
  160.         directData[1] = [0, 1, 10];
  161.         directData[2] = [-1, 0, 10];
  162.         directData[3] = [0, -1, 10];
  163.     }
  164.     private function sortList(list_t:Array):Void {
  165.         list_t.sortOn("F", Array.NUMERIC);
  166.     }
  167.     private function isOut(point_t:Object):Boolean {
  168.         if (point_t.X<0 || point_t.Y<0 || point_t.X>16 || point_t.Y>16) {
  169.             return true;
  170.         } else {
  171.             return false;
  172.         }
  173.     }
  174.     private function isInList(point_t:Object, list_t:Array):Boolean {
  175.         if (list_t.length == 0) {
  176.             return false;
  177.         }
  178.         for (var i = 0; i<list_t.length; ) {
  179.             if (list_t[i].X == point_t.X && list_t[i].Y == point_t.Y) {
  180.                 return true;
  181.                 break;
  182.             }
  183.             i++;
  184.             if (i == list_t.length) {
  185.                 return false;
  186.             }
  187.         }
  188.     }
  189.     private function manhattanDis(start_t:Object, end_t:Object):Number {
  190.         var dis:Number;
  191.         dis = Math.abs(start_t.X-end_t.X)+Math.abs(start_t.Y-end_t.Y);
  192.         return dis*cost;
  193.     }
  194.     private function send2List(point_t:Object, list_t:Array):Void {
  195.         list_t.push(point_t);
  196.     }
  197. }

Posted in flash | No Comments »