文件類別 (Document Class)
TestAstar.as
package
{
import flash.display.Sprite;
import flash.display.StageAlign;
import flash.display.StageScaleMode;
import flash.events.Event;
import flash.events.MouseEvent;
import flash.geom.Point;
import net.eidiot.map.AStar;
import test.map.MapTileModel;
import test.map.Tile;
import flash.text.TextField;
import flash.text.TextFieldAutoSize;
[SWF(width = 1024, height = 768, frameRate = 12)]
/**
* A* 尋路測試類別
*
* @author chugo
* @
* @date 09212009
*/
public class TestAstar extends Sprite
{
//====================================
// Member Variables
//====================================
private var m_player : Tile;
private var m_map : Array;
private var m_AStar : AStar;
private var m_mapTileModel : MapTileModel;
private var m_mapW : int = 20;
private var m_mapH : int = 10;
private var m_mapX : int = 10;
private var m_mapY : int = 40;
private var m_m_clogRate : Number = 0.3;
private var m_path : Array;
private var m_outTxt : TextField;
//====================================
// Constructor
//====================================
public function TestAstar()
{
stage.align = StageAlign.TOP_LEFT;
stage.scaleMode = StageScaleMode.NO_SCALE;
stage.doubleClickEnabled = true;
stage.addEventListener(MouseEvent.DOUBLE_CLICK, resetHandle);
this.m_outTxt = new TextField();
addChild(this.m_outTxt);
with (this.m_outTxt)
{
x = y = 20;
selectable = false;
autoSize = TextFieldAutoSize.LEFT;
}
this.m_mapTileModel = new MapTileModel();
this.m_AStar = new AStar(this.m_mapTileModel);
this.reset();
}
//====================================
// Private Methods
//====================================
private function reset() : void
{
var tile : Tile;
var isClog : Boolean;
this.m_map = new Array();
for (var i : int = 0; i < m_mapW; i++)
{
m_map[i] = new Array();
for (var j : int = 0; j < m_mapH; j++)
{
isClog = Math.random() < 0.3;
tile = new Tile(isClog ? 0x000000 : 0xCCCCCC);
tile.addEventListener(MouseEvent.CLICK, clickHandle);
addChild(tile);
tile.x = m_mapX + i * 30;
tile.y = m_mapY + j * 30;
m_map[i][j] = isClog ? 0 : 1;
}
}
m_player = new Tile(0xFF0000);
addChild(m_player);
m_player.x = m_mapX;
m_player.y = m_mapY;
this.m_mapTileModel.map = this.m_map;
output("單擊白色方塊區域測試尋路，雙擊空白區域重新排列地圖");
}
private function getPoint(p_x : Number, p_y : Number) : Point
{
p_x = Math.floor((p_x - this.m_mapX) / 30);
p_y = Math.floor((p_y - this.m_mapY) / 30);
return new Point(p_x, p_y);
}
private function output(p_info : String) : void
{
this.m_outTxt.htmlText = "A* 尋路徑演算法\t\t\t" + p_info;
}
//====================================
// Event Handles
//====================================
private function resetHandle(event : MouseEvent) : void
{
while (this.numChildren > 1)
{
var tile : Tile = this.getChildAt(1) as Tile;
if (tile.hasEventListener(MouseEvent.CLICK))
{
tile.removeEventListener(MouseEvent.CLICK, clickHandle);
}
this.removeChild(tile);
}
this.reset();
}
private function clickHandle(event : MouseEvent) : void
{
var findPiont : Point = getPoint(this.mouseX, this.mouseY);
var playerPoint : Point = getPoint(this.m_player.x, this.m_player.y);
this.m_path = this.m_AStar.find(playerPoint.x, playerPoint.y, findPiont.x, findPiont.y);
if (this.m_path != null && this.m_path.length > 0)
{
output("路徑已經找到，正在移動");
this.addEventListener(Event.ENTER_FRAME, enterframeHandle);
} else
{
output("無法到達");
}
}
private function enterframeHandle(event : Event) : void
{
if (this.m_path == null || this.m_path.length == 0)
{
output("單擊白色方塊區域測試尋路，雙擊空白區域重新排列地圖");
this.removeEventListener(Event.ENTER_FRAME, enterframeHandle);
return;
}
var note : Array = this.m_path.shift() as Array;
this.m_player.x = this.m_mapX + note[0] * 30;
this.m_player.y = this.m_mapY + note[1] * 30;
}
}
}
============================================================================================
AStar.as
package net.eidiot.map
{
/**
* A* 尋路徑演算法
*
* @author chugo
* @version 1.0
* @date 09212009
*/
public class AStar
{
//====================================
// Constants
//====================================
//橫向或豎向移動一格路徑評分
private const COST_STRAIGHT : int = 10;
//斜向移動一格路徑評分
private const COST_DIAGONAL : int = 14;
//（單個）節點數組 節點ID 索引
private const NOTE_ID : int = 0;
//（單個）節點數組 是否在開啟列表中 索引
private const NOTE_OPEN : int = 1;
//（單個）節點數組 是否在關閉列表中 索引
private const NOTE_CLOSED : int = 2;
//====================================
// Member Variables
//====================================
//地圖模型
private var m_mapTileModel : IMapTileModel;
//最大尋路徑步數，限制超時返回
private var m_maxTry : int;
//開放列表，存放節點ID
private var m_openList : Array;
//開放列表長度
private var m_openCount : int;
//節點加入開放列表時分配的唯一ID(從0開始)
//根據此ID(從下面的列表中)存取節點數據
private var m_openId : int;
//節點x座標列表
private var m_xList : Array;
//節點y座標列表
private var m_yList : Array;
//節點路徑評分列表
private var m_pathScoreList : Array;
//(從起點移動到)節點的移動耗费列表
private var m_movementCostList : Array;
//節點的父節點(ID)列表
private var m_fatherList : Array;
//節點(數組)地圖,根據節點座標記錄節點開啟關閉狀態和ID
private var m_noteMap : Array;
//====================================
// Constructor
//====================================
/**
* Constructor
*
* @param p_mapTileModel 地圖模型，實現 IMapTileModel 接口
* @param p_maxTry 最大尋路徑步數，限制超時返回
*/
public function AStar(p_mapTileModel : IMapTileModel, p_maxTry : int = 500)
{
this.m_mapTileModel = p_mapTileModel;
this.m_maxTry = p_maxTry;
}
//====================================
// Properties
//====================================
/**
* 最大尋路徑步數，限制超時返回
*/
public function get maxTry() : int
{
return this.m_maxTry;
}
/**
* @private
*/
public function set maxTry(p_value : int) : void
{
this.m_maxTry = p_value;
}
//====================================
// Public Methods
//====================================
/**
* 開始尋找路徑
*
* @param p_startX 起點X座標
* @param p_startY 起點Y座標
* @param p_endX 終點X座標
* @param p_endY 終點Y座標
*
* @return 找到的路徑(二維數組 : [p_startX, p_startY], ... , [p_endX, p_endY])
*/
public function find(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : Array
{
this.initLists();
this.m_openCount = 0;
this.m_openId = -1;
this.openNote(p_startX, p_startY, 0, 0, 0);
var currTry : int = 0;
var currId : int;
var currNoteX : int;
var currNoteY : int;
var aroundNotes : Array;
var checkingId : int;
var cost : int;
var score : int;
while (this.m_openCount > 0)
{
//超時返回
if (++currTry > this.m_maxTry)
{
this.destroyLists();
return null;
}
//每次取出開放列表最前面的ID
currId = this.m_openList[0];
//將編碼為此ID的元素列入關閉列表
this.closeNote(currId);
currNoteX = this.m_xList[currId];
currNoteY = this.m_yList[currId];
//如果終點被放入關閉列表尋路結束，返回路徑
if (currNoteX == p_endX && currNoteY == p_endY)
{
return this.getPath(p_startX, p_startY, currId);
}
//獲取周圍節點，排除不可通過和已在關閉列表中的
aroundNotes = this.getArounds(currNoteX, currNoteY);
//對於周圍的每一個節點
for each (var note : Array in aroundNotes)
{
//計算F和G值
cost = this.m_movementCostList[currId] + ((note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL);
score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
if (this.isOpen(note[0], note[1])) //如果節點已在播放列表中
{
checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
//如果新的G值比節點原來的G值小,修改F,G值，換父節點
if(cost < this.m_movementCostList[checkingId])
{
this.m_movementCostList[checkingId] = cost;
this.m_pathScoreList[checkingId] = score;
this.m_fatherList[checkingId] = currId;
this.aheadNote(this.getIndex(checkingId));
}
} else //如果節點不在開放列表中
{
//將節點放入開放列表
this.openNote(note[0], note[1], score, cost, currId);
}
}
}
//開放列表已空，找不到路径
this.destroyLists();
return null;
}
//====================================
// Private Methods
//====================================
/**
* @private
* 將節點加入開放列表
*
* @param p_x 節點在地圖中的x座標
* @param p_y 節點在地圖中的y座標
* @param P_score 節點的路徑評分
* @param p_cost 起始點到節點的移動成本
* @param p_fatherId 父節點
*/
private function openNote(p_x : int, p_y : int, p_score : int, p_cost : int, p_fatherId : int) : void
{
this.m_openCount++;
this.m_openId++;
if (this.m_noteMap[p_y] == null)
{
this.m_noteMap[p_y] = [];
}
this.m_noteMap[p_y][p_x] = [];
this.m_noteMap[p_y][p_x][NOTE_OPEN] = true;
this.m_noteMap[p_y][p_x][NOTE_ID] = this.m_openId;
this.m_xList.push(p_x);
this.m_yList.push(p_y);
this.m_pathScoreList.push(p_score);
this.m_movementCostList.push(p_cost);
this.m_fatherList.push(p_fatherId);
this.m_openList.push(this.m_openId);
this.aheadNote(this.m_openCount);
}
/**
* @private
* 將節點加入關閉列表裡
*/
private function closeNote(p_id: int) : void
{
this.m_openCount--;
var noteX : int = this.m_xList[p_id];
var noteY : int = this.m_yList[p_id];
this.m_noteMap[noteY][noteX][NOTE_OPEN] = false;
this.m_noteMap[noteY][noteX][NOTE_CLOSED] = true;
if (this.m_openCount <= 0)
{
this.m_openCount = 0;
this.m_openList = [];
return;
}
this.m_openList[0] = this.m_openList.pop();
this.backNote();
}
/**
* @private
* 將(新加入開放列表或修改了路徑評分的)節點向前移動
*/
private function aheadNote(p_index : int) : void
{
var father : int;
var change : int;
while(p_index > 1)
{
//父節點的位置
father = Math.floor(p_index / 2);
//如果該節點的F值小於父節點的F值則和父節點交換
if (this.getScore(p_index) < this.getScore(father))
{
change = this.m_openList[p_index - 1];
this.m_openList[p_index - 1] = this.m_openList[father - 1];
this.m_openList[father - 1] = change;
p_index = father;
} else
{
break;
}
}
}
/**
* @private
* 将(取出开启列表中路径评分最低的节点后从队尾移到最前的)节点向后移动
*/
private function backNote() : void
{
//尾部的節點被移到最前面
var checkIndex : int = 1;
var tmp : int;
var change : int;
while(true)
{
tmp = checkIndex;
//如果有子節點
if (2 * tmp <= this.m_openCount)
{
//如果子節點的F值更小
if(this.getScore(checkIndex) > this.getScore(2 * tmp))
{
//記節點的新位置為子節點位置
checkIndex = 2 * tmp;
}
//如果有兩個子節點
if (2 * tmp + 1 <= this.m_openCount)
{
//如果第二個子節點F值更小
if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
{
//更新節點新位置為第二個子節點位置
checkIndex = 2 * tmp + 1;
}
}
}
//如果節點位置没有更新結束排序
if (tmp == checkIndex)
{
break;
}
//反之和新位置交換，繼續和新位置的子節點比較F值
else
{
change = this.m_openList[tmp - 1];
this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
this.m_openList[checkIndex - 1] = change;
}
}
}
/**
* @private
* 判斷某節點是否在開放列表
*/
private function isOpen(p_x : int, p_y : int) : Boolean
{
if (this.m_noteMap[p_y] == null) return false;
if (this.m_noteMap[p_y][p_x] == null) return false;
return this.m_noteMap[p_y][p_x][NOTE_OPEN];
}
/**
* @private
* 判斷某節點是否在關閉列表中
*/
private function isClosed(p_x : int, p_y : int) : Boolean
{
if (this.m_noteMap[p_y] == null) return false;
if (this.m_noteMap[p_y][p_x] == null) return false;
return this.m_noteMap[p_y][p_x][NOTE_CLOSED];
}
/**
* @private
* 獲取某節點的周圍節點，排除不能通過和已在關閉列表中的
*/
private function getArounds(p_x : int, p_y : int) : Array
{
var arr : Array = [];
var checkX : int;
var checkY : int;
var canDiagonal : Boolean;
//右
checkX = p_x + 1;
checkY = p_y;
var canRight : Boolean = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canRight && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//下
checkX = p_x;
checkY = p_y + 1;
var canDown : Boolean = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canDown && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//左
checkX = p_x - 1;
checkY = p_y;
var canLeft : Boolean = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canLeft && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//上
checkX = p_x;
checkY = p_y - 1;
var canUp : Boolean = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canUp && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//右下
checkX = p_x + 1;
checkY = p_y + 1;
canDiagonal = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canDiagonal && canRight && canDown && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//左下
checkX = p_x - 1;
checkY = p_y + 1;
canDiagonal = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canDiagonal && canLeft && canDown && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//左上
checkX = p_x - 1;
checkY = p_y - 1;
canDiagonal = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canDiagonal && canLeft && canUp && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
//右上
checkX = p_x + 1;
checkY = p_y - 1;
canDiagonal = this.m_mapTileModel.isBlock(p_x, p_y, checkX, checkY) == 1;
if (canDiagonal && canRight && canUp && !this.isClosed(checkX, checkY))
{
arr.push([checkX, checkY]);
}
return arr;
}
/**
* @private
* 獲取路徑
*
* @param p_startX 起始點X座標
* @param p_startY 起始點Y座標
* @param p_id 終點的ID
*
* @return 路徑座標(Point)數組
*/
private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
{
var arr : Array = [];
var noteX : int = this.m_xList[p_id];
var noteY : int = this.m_yList[p_id];
while (noteX != p_startX || noteY != p_startY)
{
arr.unshift([noteX, noteY]);
p_id = this.m_fatherList[p_id];
noteX = this.m_xList[p_id];
noteY = this.m_yList[p_id];
}
arr.unshift([p_startX, p_startY]);
this.destroyLists();
return arr;
}
/**
* @private
* 獲取某ID節點在開放列表中的索引(從1开始)
*/
private function getIndex(p_id : int) : int
{
var i : int = 1;
for each (var id : int in this.m_openList)
{
if (id == p_id)
{
return i;
}
i++;
}
return -1;
}
/**
* @private
* 獲取某節點的路徑評分
*
* @param p_index 節點在開啟列表中的索引(從1開始)
*/
private function getScore(p_index : int) : int
{
return this.m_pathScoreList[this.m_openList[p_index - 1]];
}
/**
* @private
* 初始化數組
*/
private function initLists() : void
{
this.m_openList = [];
this.m_xList = [];
this.m_yList = [];
this.m_pathScoreList = [];
this.m_movementCostList = [];
this.m_fatherList = [];
this.m_noteMap = [];
}
/**
* @private
* 銷毀數組
*/
private function destroyLists() : void
{
this.m_openList = null;
this.m_xList = null;
this.m_yList = null;
this.m_pathScoreList = null;
this.m_movementCostList = null;
this.m_fatherList = null;
this.m_noteMap = null;
}
}
}
=============================================================================================
MapTileModel.as
package test.map
{
import net.eidiot.map.IMapTileModel;
/**
* 地圖模型類別
*
* @author chugo
* @version 1.0
* @date 09212009
*/
public class MapTileModel implements IMapTileModel
{
private var m_map : Array;
public function MapTileModel()
{
}
public function get map() : Array
{
return this.m_map;
}
public function set map(p_value : Array) : void
{
this.m_map = p_value;
}
/**
* 是否為障礙
* @param p_startX 起始點X座標
* @param p_startY 起始點Y座標
* @param p_endX 終點X座標
* @param p_endY 終點Y座標
* @return 0為障礙 1為通路
*/
public function isBlock(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : int
{
var mapWidth : int = this.m_map.length;
var mapHeight : int = this.m_map[0].length;
if (p_endX < 0 || p_endX == mapWidth || p_endY < 0 || p_endY == mapHeight)
{
return 0;
}
return this.m_map[p_endX][p_endY];
}
}
}
==============================================================================================
Tile.as
package test.map
{
import flash.display.Sprite;
/**
* 瓷磚類別
*
* @author chugo
* @version 1.0
* @date 09212009
*/
public class Tile extends Sprite
{
public function Tile(p_color : uint = 0xCCCCCC, p_w : int = 30, p_h : int = 30)
{
with (this.graphics)
{
lineStyle(1, 0x666666);
beginFill(p_color);
drawRect(0, 0, p_w, p_h);
endFill();
}
}
}
}
=============================================================================================
IMapTileModel.as
package net.eidiot.map
{
/**
* 地圖模型接口
*
* @author chugo
* @version 1.0
* @date 09212009
*/
public interface IMapTileModel
{
/**
* 判斷是否為障礙
* @param p_startX 起始點X座標
* @param p_startY 起始點Y座標
* @param p_endX 起始點X座標
* @param p_endY 起始點Y座標
* @return 0為障礙 1為通路
*/
function isBlock(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : int;
}
}
==============================================================================================
