在我做的一个小游戏中，经常遇到要计算最短路径的问题。从一个格子走到另外一个格子，不过中间有很多障碍物(就是一些格子不能走上去),计算最短路径是个比较困难的问题。
如果使用著名的A*算法，那么消耗的内存太多，不可取.我需要搜索的范围很小，最大也是14*14的矩阵格子，最佳的算法就是一个SLG游戏中常用的小范围寻路算法。
小范围寻路法的核心就是在于计算距离.把14x14的格子里面每个点到目的点的距离计算出来后，人物只要一直按距离最小的格子走，那么一定可以走到目的地。这个算法可以很容易证明，只要计算的格子范围足够大，人物是一定可以走到目的点的，而且所走的路径是最短的。
而计算距离的方法也很简单，我们只要把目的点的距离设置成0,然后再计算它周围的点的距离，如果是不能走的格子，那么距离值设置成无穷大，如果可以走，它的距离就是它附近的格子加1.
计算距离的算法我已经写在下面了.
算法的时间复杂度等于 O(n*n*(n/2-1)+n^2),在小范围内，速度比较快,最大的优点就是很简单,不依靠其它数据结构,所有操作都在数组内完成。
//***********************************************************
/**
* 计算以某点为中心的矩型区域的每个Tile到中心的距离
* @param MapPoint int[] 中心点的Tile地图坐标
* @param Move int 范围值
* @param bIngnoreNpc boolean 是否需要忽略Npc的阻挡
* @return int[][] 以某点为中心的矩型区域的每个Tile到中心的距离
*/
protected int[][] Game_Calulate_Distance(int []MapPoint, int Move, boolean bIngnoreNpc) {
int i,j;
int[][] Dst = new int[2*Move+1][2*Move+1];
int step;
// 设置初试距离都为无穷大
for(i=0;i<2*Move+1;i++)
for(j=0;j<2*Move+1;j++)
Dst[i][j]= Integer.MAX_VALUE;
// 设置目标点的距离为0
Dst[Move][Move] = 0;
for(step=0; step<=Move-1;step++)
for(i = Move-step; i<= Move+step; i++) {
for (j = Move - step; j <= Move + step; j++) {
if (Game_Tile_Test_CanWalk(new int[] {MapPoint[0] - Move + i - 1,
MapPoint[1] - Move + j}, bIngnoreNpc)) {
if (Dst[i - 1][j] > Dst[i][j])
Dst[i - 1][j] = Dst[i][j] + 1;
}
if (Game_Tile_Test_CanWalk(new int[] {MapPoint[0] - Move + i + 1,
MapPoint[1] - Move + j}, bIngnoreNpc)) {
if (Dst[i + 1][j] > Dst[i][j])
Dst[i + 1][j] = Dst[i][j] + 1;
}
if (Game_Tile_Test_CanWalk(new int[] {MapPoint[0] - Move + i,
MapPoint[1] - Move + j - 1}, bIngnoreNpc)) {
if (Dst[i][j - 1] > Dst[i][j])
Dst[i][j - 1] = Dst[i][j] + 1;
}
if (Game_Tile_Test_CanWalk(new int[] {MapPoint[0] - Move + i,
MapPoint[1] - Move + j + 1}, bIngnoreNpc)) {
if (Dst[i][j + 1] > Dst[i][j])
Dst[i][j + 1] = Dst[i][j] + 1;
}
}
}
return Dst;
}
打印 | 张贴于 2004-03-16 23:30:00 | Tag:暂无标签