天神降临，大家过来膜拜吧! FLASH AS 3.0 A星(A*, A star) 寻路
|
?oh yeah! 转载请声明出处，例子代码可以免费随意使用，但请保留或注明作者信息. ?这里的算法说是终极优化,我挑战了一下, http://eidiot.net/2007/04/17/a-star-pathfinding/ 最终结果比较他快三倍,我站在高高处，藐视了?一下作者.
优化思路: ????????? ?? a.开包(open list)算法优化:? ??????????????? 线性查找--> ??????????????? 二叉堆(binary heap 容器:Array->Vector)-> ??????????????? 二分排序插入/删除(容器:Array) ?????????????????????? dictionary(1维) ->dictionary(2维)--? array(1维)->array(2维)->bitmapdata->bytearray(8位对齐)->byteArrayarray(32位对齐)->vector. <int> ??????????????????? ?dictionary(1维) -> array(1维)->bitmapdata->vector. <int> ?????????????????????????? AS动态对象(Object)->非动态对象(自定义PathNode对象)->使用bytearray自己管理内存分配对象-->使用Vector自已管理内存分配对象. ??????????????????????? 标准（F = G+H,G=Parent.G+DIR_G,H = (ABS(X1-X)+ABS(Y1-Y) )*10 ) ????????????? 上述优化基本上是? 左->右 == 慢->快 ? 测试结果部分 ? 单位:毫秒 地图大小:500x500地图: ?
? 从41条测试线路的平均值结果,? 足足快3倍,比较未优化但是快了25倍以上
? ?
? 代码：FindPathImplVetorMem.as /**
@author aerror
*/
package
{
import flash.utils.ByteArray;
import flash.utils.Endian;
public class FindPathImplVetorMem
{
public static const BLOCK_TYPE_NULL:int = 0;
public static const BLOCK_TYPE_STATIC:int = 1;
public static const BLOCK_TYPE_ENTRY:int = 2;
public static const BLOCK_TYPE_ITEM:int = 4;
private var obstacles:Vector.<int>;
private var iwidth:uint;
private var iheight:uint;
private var nearby:Vector.<int>;
private var nearbyStraight:Vector.<int>;
private var nearbyCross:Vector.<int>;
private static const STATE_NULL:uint = 0;
private static const STATE_CLOSE:uint = 1;
/**
*
*
* */
public function FindPathImplVetorMem()
{
nearbyStraight = new Vector.<int>();
nearbyStraight.push(
-1,-1,14,10,1,10
);
nearbyCross = new Vector.<int>();
nearbyCross.push(
-1,14
);
nearby = nearbyStraight;
}
public function initSys():void
{
}
public function clearBlock():void
{
if(obstacles!=null)
{
//obstacles.dispose();
obstacles = null;
}
}
public function initMap(_mapCol:int,_mapRow:int,bytes:ByteArray):void
{
clearBlock();
this.iwidth = _mapCol;
this.iheight = _mapRow;
obstacles = new Vector.<int>(iwidth*iheight);
var num:int = bytes.length/6;
for(var i:int=0;i<num;i++)
{
var x:int= bytes.readUnsignedShort();
var y:int= bytes.readUnsignedShort();
var t:int = bytes.readUnsignedShort();
obstacles[x+y*_mapRow] = t;
if(t==0)
{
trace("BLOCK_TYPE_NULL inited");
return;
}
}
}
public function checkBlock(cellX:int,cellY:int,cellType:int):Boolean
{
if(obstacles!=null && obstacles[cellX + cellY*iwidth] ==cellType)
{
return true;
}
return false;
}
public function addBlock(cellX:int,blockType:int):void
{
if(obstacles==null)
{
return;
}
obstacles[cellX + cellY*iwidth] = blockType;
}
public function removeBlock(cellX:int,blockType:int):void
{
if(obstacles==null )
{
return;
}
obstacles[cellX + cellY*iwidth] = BLOCK_TYPE_NULL;
}
public function findPath(startX:int,startY:int,endX:int,endY:int,distance:int ):ByteArray
{
var ret:ByteArray = new ByteArray();
ret.endian = Endian.LITTLE_ENDIAN;
var width:uint = iwidth;
var height:uint = iheight;
var nodelist:PathNodeFactoryVector = new PathNodeFactoryVector(width * height);
var key:uint;
var opneListSortedArr:Array = new Array();
var opneNum:int=0;
var minIndex:uint = 0;
var stateMap:Vector.<uint>= new Vector.<uint>(width * height);
var startPoint:uint = nodelist.createNode(startX,startY,PathNodeFactoryVector.NULL);
key = x + width * y;
opneListSortedArr.push(startPoint);
stateMap[key]=startPoint;
opneNum = 1;
minIndex = 0;
var found_end_point:uint = PathNodeFactoryVector.NULL;
var x:int;
var y:int;
var g:int;
var h:Number;
var f:int;
var i:int;
var min:uint = PathNodeFactoryVector.NULL;
while(true)
{
var min_key:uint;
var min_x:uint;
var min_y:uint;
var min_f:uint;
var min_g:uint;
//find the min g+h point
//
if(opneNum >0)
{
//remove from openlist;
min = opneListSortedArr.shift();
min_x = nodelist.getNodeX(min);
min_y = nodelist.getNodeY(min);
min_g = nodelist.getNodeG(min);
min_key = min_x + width * min_y;
opneNum--;
}
else
{
trace("FIND PATH FAILED");
break;
}
//add to close list;
stateMap[min_key] = STATE_CLOSE;// = min;
//add nearby point to openlist
for( i = 0;i<8;i++)
{
x = min_x + nearby[i*3];
y = min_y + nearby[i*3+1];
key = x + width * y;
//calc h
//
h = ((endX<x)?(x-endX):(endX-x)) +
((endY<y)?(y-endY):(endY-y));
//we find the path when openlist contains the endpoint
//
if(h<=distance)
{
found_end_point = nodelist.createNode(x,y,min);
break;
}
h = h*10;
if(x >= width || x < 0 //out of bounds ?
|| y >= height || y < 0//out of bounds ?
|| obstacles[key]!=BLOCK_TYPE_NULL //is obstacle ?
)
{
continue;
}
// if in close list?
var state:uint = stateMap[key];
if(state==STATE_CLOSE)
{
continue;
}
//calc g
//
g = (nearby[i*3+2]+min_g);
f = g+h;
//check if new point or old
//
var newPt:uint;
//the old point
//key key its g value,update if new g is less
//
if(state==STATE_NULL)
{
//the new point
//
newPt = nodelist.createNode(x,g,f,min);
stateMap[key] = newPt;
nodelist.sortInsert(opneListSortedArr,newPt,opneNum);
opneNum++;
}
else if(g<nodelist.getNodeG(state))
{
newPt = nodelist.createNode(x,min);
nodelist.sortRemove(opneListSortedArr,state,opneNum);
stateMap[key] = newPt;
nodelist.sortInsert(opneListSortedArr,opneNum-1);
}
}
//just break the upper loop
//
if(found_end_point !=PathNodeFactoryVector.NULL)
{
break;
}
}
//stateMap.dispose();
//stateMap =null;
//encode it to bytearray. :(
//
if(found_end_point !=PathNodeFactoryVector.NULL)
{
var pt:uint = found_end_point;
var num:int=0;
while(pt!=PathNodeFactoryVector.NULL)
{
num++;
pt =nodelist.getNodeParent(pt);
}
ret.length = num*4;
pt = found_end_point;
i =0;
while(pt!=PathNodeFactoryVector.NULL)
{
ret.position = (num-i-1)*4;
ret.writeShort(nodelist.getNodeX(pt));
ret.writeShort(nodelist.getNodeY(pt));
i++;
pt = nodelist.getNodeParent(pt);
}
ret.position = 0;
}
//clear used memory
//
trace("used length :" + nodelist.getUsedLength() + "open num" + opneListSortedArr.length);
nodelist.clear();
stateMap.length = 0;
opneListSortedArr.length =0;
return ret;
}
}
}
PathNodeFactoryVector.as /**
@author aerror
*/
package
{
public class PathNodeFactoryVector
{
public static const NULL:uint = 0;
private var mem:Vector.<uint>;
private var writePosition:uint =0;
public function PathNodeFactoryVector(max:uint)
{
mem = new Vector.<uint>(max*4+4);
writePosition = 4;
}
public function getNodeX(id:uint):uint
{
return mem[id]&0xffff;
}
public function getNodeY(id:uint):uint
{
return mem[id]>>16 &0xffff;
}
public function getNodeG(id:uint):uint
{
return mem[id+1];
}
public function getNodeF(id:uint):uint
{
return mem[id+2];
}
public function getNodeParent(id:uint):uint
{
return mem[id+3];
}
public function createNode(_x:uint,_y:uint,_g:uint,_f:uint,_linkParent:uint):uint
{
mem[writePosition + 0] = (_x | _y<<16 );
mem[writePosition + 1]= _g;
mem[writePosition + 2]= _f;
mem[writePosition + 3]= _linkParent;
writePosition += 4;
return writePosition-4;
}
public function checkOK(arr:Array):Boolean
{
for(var i:int=0;i < arr.length-1;i++)
{
if(getNodeF(arr[i]) >getNodeF(arr[i+1]))
{
return false;
}
}
return true;
}
public function sortInsert(arr:Array,newPt:uint,begin:int,end:int):void
{
//optimize for empty array
if(arr.length==0)
{
arr.push(newPt);
return;
}
var new_F:uint = getNodeF(newPt);
var cur_F:uint = getNodeF(arr[begin]);
//optimize for sorted inserting with less
if(new_F <= cur_F )
{
arr.splice(0,newPt);
return;
}
//optimize for sorted inserting with larger
cur_F = getNodeF(arr[end-1]);
if(new_F >cur_F)
{
arr.splice(end,newPt);
return;
}
else if(new_F == cur_F)
{
arr.splice(end-1,newPt);
return;
}
while(true)
{
if(begin==end)
{
cur_F = getNodeF(arr[begin]);
if(new_F > cur_F)
arr.splice(begin+1,newPt);
else
arr.splice(begin,newPt);
return ;
}
//find a place
var mid:int = begin+(end-begin)/2;
cur_F =getNodeF(arr[mid]);
if(new_F < cur_F)
{
end = mid;
}
else if(new_F > cur_F)
{
begin = mid +1;
}
else
{
arr.splice(mid,newPt);
return;
}
}
}
public function sortRemove(arr:Array,oldPt:uint,end:int):void
{
var old_f:uint = getNodeF(oldPt);
var i:int;
while(true)
{
//find a place
var mid:int = begin+(end-begin)/2;
var cur_f:uint = getNodeF(arr[mid]);
if(old_f < cur_f)
{
end = mid;
}
else if(old_f > cur_f)
{
begin = mid +1;
}
else
{
for(i =mid; i<end ; i++)
{
if(oldPt==arr[i])
{
arr.splice(i,1);
return ;
}
}
for(i = mid-1; i>=0 ; i--)
{
if(oldPt==arr[i])
{
arr.splice(i,1);
return ;
}
}
return ;
}
}
}
public function clear():void
{
this.mem.length = 0;
}
public function getUsedLength():uint
{
return this.writePosition;
}
public function dumpArray(opneListSortedArr:Array):void
{
for(var j:int =0;j<opneListSortedArr.length;j++)
{
trace(getNodeF(opneListSortedArr[j]));
}
}
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
