在之前的广度优先算法上加了对每个节点的估价函数变成了A*
,有兴趣的可以看看代码,没写注释,有不懂的联系我,呵呵。
不知道怎么回事,5d居然不能显示上传的swf了,演示地址http://blog.5d.cn/user10/Billows/upload/2006-010/20061027162236094.swf这样吧
/**
* @author Billow
*/
class AStar {
private var pathTime:Number;
private var path:Object;
private var root:MovieClip;
private var openA:Array;
private var closeA:Array;
private var mapArray:Array;
private var pathArray:Array;
private var colID:Number = 50;
private var rowID:Number = 50;
private var startColID:Number;
private var startRowID:Number;
private var isPathFind:Boolean = false;
private var endRowID, endColID:Number;
//private var nodeArray:Array;
private var indexNum:Number = 0;
private var preNum:Number = 0;
//private var blockArray:Array;
public function AStar(root:MovieClip) {
//trace(root);
init(root);
attachTile();
//attachBlock();
}
private function init(root:MovieClip):Void {
this.root = root;
startRowID = 5;
startColID = 5;
this.mapArray = new Array();
//this.pathArray = new Array();
}
public function attachTile():Void {
//trace("attachTile");
var self = this;
for (var i:Number = 0; i<rowID; i++) {
mapArray[i] = new Array();
for (var j:Number = 0; j<colID; j++) {
var depth:Number = i*colID+j;
var tile_mc = root.attachMovie("mc_tile", "mc_tile"+depth, depth);
tile_mc._x = j*tile_mc._width;
tile_mc._y = i*tile_mc._height;
//trace(tile_mc);
var type:String;
var randomNum = Math.floor(Math.random()*3);
if (randomNum == 0) {
//mapArray[i][j].graphic.gotoAndStop(4);
type = "block";
} else if (randomNum>0) {
type = "common";
//mapArray[i][j].graphic.gotoAndStop(3);
}
if (i == startColID && j == startRowID) {
//mapArray[i][j].graphic.gotoAndStop(2);
type = "start";
}
mapArray[i][j] = new Tile(this, tile_mc, i, j, false, type);
}
}
}
public function onPressHandle(pressRowID:Number, pressColID:Number):Void {
//trace("the start point is:"+startRowID+","+startColID);
//trace("the end point is:"+pressRowID+","+pressColID);
//trace("mapArray[pressRowID][pressRowID].type="+mapArray[pressRowID][pressColID].type);
if (mapArray[pressRowID][pressColID].type != "common") {
//trace("can't press");
return;
} else {
//this.endRowID = pressRowID;
//this.endColID = pressColID;
initMapData();
//searchPath(startRowID, startColID, pressRowID, pressColID);
findPath(startRowID, startColID, pressRowID, pressColID);
//pushPathArray(pressRowID, pressColID);
attachPath();
}
}
private function initMapData():Void {
resetAllIsChecked();
preNum = 0;
indexNum = 0;
closeA.splice(0);
pathArray.splice(0);
}
private function attachPath():Void {
for (var i:Number = 0; i<pathArray.length; i++) {
var rowNum = pathArray[i].x;
var colNum = pathArray[i].y;
//trace("x,y="+rowNum+","+colNum);
mapArray[rowNum][colNum].graphic.gotoAndStop("move");
}
}
private function resetAllIsChecked():Void {
for (var i:Number = 0; i<rowID; i++) {
for (var j:Number = 0; j<colID; j++) {
mapArray[i][j].setIsChecked(false);
mapArray[i][j].graphic.gotoAndStop(mapArray[i][j].type);
}
}
}
private function pushPathArray(ex, ey:Number) {
pathArray.push({x:ex, y:ey});
var curIndexNum:Number = closeA[closeA.length-1].preNum;
while (curIndexNum>0) {
pathArray.push({x:closeA[curIndexNum-1].sx, y:closeA[curIndexNum-1].sy});
curIndexNum = closeA[curIndexNum-1].preNum;
}
}
function make_path(ob) {
// create path array
pathArray = new Array();
// loop until no more parents
while (ob.parentx != null) {
// add the x and y
//pathArray[pathArray.length] = ob.x;
//pathArray[pathArray.length] = ob.y;
pathArray.push({x:ob.x, y:ob.y});
// mark the tile
//game.clip["t_"+ob.y+"_"+ob.x].mark.gotoAndStop(2);
// make its parent new object
ob = path["node_"+ob.parenty+"_"+ob.parentx];
}
// show time it took to find path
trace(getTimer()-pathTime+" ms");
}
function findPath(startx, starty, targetx, targety:Number) {
// start timer
pathTime = getTimer();
// make new path object
path = {};
// make new array for unchecked tiles
path.Unchecked_Neighbours = [];
// not done yet
path.done = false;
// initialize
path.name = "node_"+starty+"_"+startx;
// create first node
var cost = Math.abs(startx-targetx)+Math.abs(starty-targety);
path[path.name] = {x:startx, y:starty, visited:true, parentx:null, parenty:null, cost:cost};
// add node to array
path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
// loop
while (path.Unchecked_Neighbours.length>0) {
// get the next node
var N = path.Unchecked_Neighbours.shift();
// we've finished
if (N.x == targetx and N.y == targety) {
// done
make_path(N);
path.done = true;
break;
} else {
N.visited = true;
// right neighbour
addNode(N, N.x+1, N.y, targetx, targety);
// left neighbour
addNode(N, N.x-1, N.y, targetx, targety);
// up neighbour
addNode(N, N.x, N.y+1, targetx, targety);
// down neighbour
addNode(N, N.x, N.y-1, targetx, targety);
// rightUp neighbour
addNode(N, N.x+1, N.y-1, targetx, targety);
// leftUp neighbour
addNode(N, N.x-1, N.y-1, targetx, targety);
// rightDown neighbour
addNode(N, N.x+1, N.y+1, targetx, targety);
// leftDown neighbour
addNode(N, N.x-1, N.y+1, targetx, targety);
}
}
// remove path object
delete path;
// check if path was found
if (path.done) {
// we reached the goal
return true;
} else {
// we couldn't get there;
return false;
}
}
function addNode(ob, x, y, targetx, targety) {
// name of the new node
path.name = "node_"+y+"_"+x;
// add to the unchecked neighbours, if its walkable
//if (game["t_"+y+"_"+x].walkable) {
if (mapArray[x][y].type == "common") {
// find estimated cost to the target
var cost = Math.abs(x-targetx)+Math.abs(y-targety);
// and if its not visited yet
if (path[path.name].cost>cost || path[path.name].cost == undefined) {
// make new node
path[path.name] = {x:x, y:y, visited:false, parentx:ob.x, parenty:ob.y, cost:cost};
// add to the array
for (var i = 0; i<path.Unchecked_Neighbours.length; i++) {
if (cost<path.Unchecked_Neighbours[i].cost) {
path.Unchecked_Neighbours.splice(i, 0, path[path.name]);
break;
}
}
// didnt add it yet, too much cost, add to the end
if (i>=path.Unchecked_Neighbours.length) {
path.Unchecked_Neighbours[path.Unchecked_Neighbours.length] = path[path.name];
}
}
}
}
public static function main(root:MovieClip) {
new AStar(root);
}
}
