A*算法类
以前写过一篇关于a*算法的文章，由于搬家现在无法访问了。当时也尝试用flash实现，无奈电脑在那时也当机了。似乎是硬盘的原因，一直无法使用了。因为对这个的需求也不是很强烈，所以暂时就搁置了。
又一次偶然的机会，在国外的一个网站上看到了这个算法的实现，于是下载下来，稍加整理，贡献给大家。
Actionscript:
-
/*
-
Class Name:A Star
-
create:2007,3,22
-
last update:2007,3,22
-
coder:Neodroid(http://www.neodroid.tk/)
-
残缺(http://www.rssidea.com)
-
*/
-
//FUNCS FOR A* ---------------------------------
-
//----------------------------------------------
-
//DESCRIPTION:
-
import Tile;
-
class AStar {
-
private var xIni:Number;
-
private var yIni:Number;
-
private var xFin:Number;
-
private var yFin:Number;
-
private var level:Array = new Array();
-
public function AStar(xIni, yIni, xFin, yFin, level) {
-
this.xIni = xIni;
-
this.yIni = yIni;
-
this.xFin = xFin;
-
this.yFin = yFin;
-
this.level = level;
-
}
-
public function findPath():Array {
-
var openList:Array = new Array();
-
var closeList:Array = new Array();
-
//afegim el primer node a la openlist
-
var newTile:Tile = new Tile(this.xIni, this.yIni, 0, 0, 0);
-
newTile.parentTile = "none";
-
openList.push(newTile);
-
//executem per primera vegada la funcio bucle
-
var camino = this.searching(this.xFin, this.yFin, openList, closeList, this.level);
-
return camino;
-
}
-
//----------------------------------------------------------------
-
private function searching(xFin, yFin, openList, closeList, level):Array {
-
while (openList.length != 0) {
-
/*
-
if (openList.length == 0) {
-
//lista buida no shi arriva
-
return false;
-
}
-
*/
-
var tileMenorF = openList[0];
-
var switchIndex = 0;
-
//comprovem agafem el tile de menor F de la openList
-
for (var a:Number = 0; a<openList.length; a++) {
-
if (openList[a].F<tileMenorF.F) {
-
tileMenorF = openList[a];
-
switchIndex = a;
-
}
-
//finalitzaem quan
-
if (openList[a].xPos == xFin) {
-
if (openList[a].yPos == yFin) {
-
//trobem el tile final
-
var camino = new Array();
-
var tileAct = openList[a];
-
camino.push(tileAct);
-
while (tileAct.parentTile != "none") {
-
camino.push(tileAct.parentTile);
-
tileAct = tileAct.parentTile;
-
}
-
return camino;
-
}
-
}
-
}
-
//pasem el tile escollit a la closed list
-
closeList.push(tileMenorF);
-
openList.splice(switchIndex, 1);
-
//
-
//unlock to paint tiles of closedList
-
//_root.attachMovie("closedTile", "closedTile"+tileMenorF.yPos+"_"+tileMenorF.xPos, _root.getNextHighestDepth());
-
//_root["closedTile"+tileMenorF.yPos+"_"+tileMenorF.xPos]._x = tileMenorF.xPos*30;
-
//_root["closedTile"+tileMenorF.yPos+"_"+tileMenorF.xPos]._y = tileMenorF.yPos*30;
-
//
-
//comprovem els 8 tiles adjacents
-
for (var i:Number = -1; i<2; i++) {
-
for (var j:Number = -1; j<2; j++) {
-
//comprovem ke no agafem el mateix tile [0,0]
-
if (i != 0 or j != 0) {
-
var xTile:Number = tileMenorF.xPos+j;
-
var yTile:Number = tileMenorF.yPos+i;
-
//esta een la closed list
-
var existCloseList:Boolean = false;
-
for (var n:Number = 0; n<closeList.length; n++) {
-
if (closeList[n].xPos == xTile and closeList[n].yPos == yTile) {
-
existCloseList = true;
-
}
-
}
-
//es caminable?
-
if (level[yTile][xTile] == 0 and existCloseList == false) {
-
//creamos el tile temporal para poder ver si existe en la lista abierta
-
// G = 10 for tile horiz or vert & 14 for diagonal
-
if (Math.abs(i) == 1 and Math.abs(j) == 1) {
-
var G = tileMenorF.G+14;
-
} else {
-
var G = tileMenorF.G+10;
-
}
-
//H = 10*(abs(currentX-targetX) + abs(currentY-targetY))
-
var H = 10*(Math.abs((xTile-xFin))+Math.abs(yTile-yFin));
-
//F = G+H
-
var F = G+H;
-
var newTile = new Tile(xTile, yTile, G, H, F);
-
newTile.parentTile = tileMenorF;
-
//comprovem si el tile temporal (newTile) esta a la openList
-
var exist:Boolean = false;
-
var indexTemp = 0;
-
for (var n:Number = 0; n<openList.length; n++) {
-
if (openList[n].xPos == newTile.xPos and openList[n].yPos == newTile.yPos) {
-
exist = true;
-
indexTemp = n;
-
}
-
}
-
if (exist == false) {
-
openList.push(newTile);
-
}
-
if (exist == true) {
-
//compare his G
-
if (openList[indexTemp].G<tileMenorF.G) {
-
//recalculem
-
if (Math.abs(i) == 1 and Math.abs(j) == 1) {
-
openList[indexTemp].G = tileMenorF.G+14;
-
} else {
-
openList[indexTemp].G = tileMenorF.G+10;
-
}
-
//H = 10*(abs(currentX-targetX) + abs(currentY-targetY))
-
openList[indexTemp].H = 10*(Math.abs((xTile-xFin))+Math.abs(yTile-yFin));
-
//F = G+H
-
openList[indexTemp].F = openList[indexTemp].G+openList[indexTemp].H;
-
openList[indexTemp].parentTile = tileMenorF;
-
}
-
}
-
}
-
}
-
}
-
}
-
}
-
//launch the functioin again as recursive
-
//return this.searching(xFin, yFin, openList, closeList, level);
-
}
-
//----------------------------------------------------------------
-
//Descripction: returns an array with relative parent direction (x,y based) about tileObj
-
public function returnParentDirection(tileObj):Array {
-
var posArray:Array = [0, 0];
-
var xpos = tileObj.xPos-tileObj.parentTile.xPos;
-
var ypos = tileObj.yPos-tileObj.parentTile.yPos;
-
posArray[0] = xpos*-10;
-
posArray[1] = ypos*-10;
-
return posArray;
-
}
-
}
Actionscript:
-
//Declaración de la clase
-
class Tile {
-
var xPos:Number = 0;
-
var yPos:Number = 0;
-
var G:Number = 0;
-
var H:Number = 0;
-
var F:Number = 0;
-
var parentTile = "none";
-
//---------------------------------------------------------
-
function Tile(myxpos, myypos,myG, myH, myF) {
-
this.xPos = myxpos;
-
this.yPos = myypos;
-
this.G = myG;
-
this.H = myH;
-
this.F = myF;
-
}
-
}
这是已经被我整理成类的版本，核心和原作者的程序基本没有什么差异。但是源程序在寻路的时候使用的是递归，由于flash有256级的限制，所以不能适合稍大的地图。而在这个类中，我用while循环代替了递归，并且规范了部分代码。
这个类可以很轻松的移植到actionScript3.0上。
使用方法：
Actionscript:
-
import AStar;
-
//定义地图，一个二维数组
-
var myLevel = [[0, 0, 0, 0, 1, 0, 0, 0], [1, 1, 1, 0, 1, 0, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 1, 1, 1, 0, 1, 0], [0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 1, 0]];
-
//开始节点
-
var iniTileX = 0;
-
var iniTileY = 0;
-
//结束节点
-
var finTileX = 50;
-
var finTileY = 50;
-
var camino:AStar = new AStar(iniTileX, iniTileY, finTileX, finTileY, myLevel);
-
var path:Array = camino.findPath();
-
//path返回的就是寻路结果
察看演示：http://canque.rssidea.com/wp-content/2007-03-23-astar.swf
参考原文：http://www.gotoandplay.it/_articles/2007/03/pathFinder.php
原作者是Neodroid，一个生长在巴塞罗那的flasher，拥有4年网站开发经验和2年游戏开发经验。
他的网站是：http://www.neodroid.tk/，很遗憾，我这不能访问，所以一直没联系到作者。
谢谢分享!
谢谢。我用这个做了个简单的迷宫寻路程序。
http://blog.nnsky.com/blog_view_107589.html
仍有诸多不完善之处。
欢迎指导。
测试发现,这个类取得的路径不总是最短路径.