当前页面: 开发资料首页 → J2ME 专题 → 手机游戏寻路算法之广度优先
手机游戏寻路算法之广度优先
摘要: 手机游戏寻路算法之广度优先
http:///tech/article1031.html
[转载于开发视界]
作者：许伟东
昨天写的那篇只能算是导读,而真正让人感兴趣的莫过于一睹代码风采了。虽然我的代码有些粗制滥造的感觉，但只要稍加改造，能实现功能才是首要的，至于速度和其他优化问题，只能用者自己解决了。
[]下面给出的类就是被命名为广度优先的寻路算法，我使用的是标准的广度优先算法，并且已经给最终使用者留好了接口。如果你和我一样，刚刚开始研究这方面，那就好好看下结构。如果没有理解代码中的结构就使用，对你的帮助或许并不太大，而这种人也不会有什么发展前途。（至少我这么认为）
与以往一样，我会在代码中给出详细的注释以便于读者理解，如果还有什么问题需要一起讨论的话，就加我的QQ：70705327
[]代码如下：
public class GuangDuSouSuo
{
private int iSX; //宽
private int iSY; //长
private int[] iDx = {0, 0, -1, 1}; //四种移动方向对x和y坐标的影响
private int[] iDy = {-1, 1, 0, 0};
private int[][] Block;//障碍表
private boolean AllComplete = false; //全部完成标志
private int LevelNow = 1; //搜索到第几层
private int Act; //现在的移动方向
private int ActBefore; //现在的节点的父节点
private int MaxAct = 4; //移动方向总数
private int ActNow; //现在的节点
private int tx = 10, ty = 10; //当前坐标
private int[] LevelFoot = new int[1000]; //每一层最后的节点
private int[] ActHead = new int[1000]; //每一个节点的父节点
private int[] AllAct = new int[1000]; //每一个节点的移动方向
private int[] ActX = new int[1000];
private int[] ActY = new int[1000]; //按节点移动后的坐标
private int[][] Table; //已到过标记
private int TargetX = 22, TargetY = 22; //目标点
public GuangDuSouSuo()
{
this.InitBlock();
}
private void InitBlock()
{
iSX = GameBackground.mapW;
iSY = GameBackground.mapH;
Block = new int[iSX][iSY];
Table = new int[iSY][iSX];
[] int iCon = 0;
for (int i = 0; i < iSX; i++)
{
for (int j = 0; j < iSY; j++)
{
Block[i][j] = GameBackground.aCon4[iCon];
iCon += 1;
}
}
}
[]
private int ActOK()
[] {
tx = ActX[ActBefore] + iDx[Act - 1]; //将到点的x坐标
ty = ActY[ActBefore] + iDy[Act - 1]; //将到点的y坐标
if ((tx >= iSX) || (tx < 0)) //x坐标出界？
return 0;
if ((ty >= iSY) || (ty < 0)) //y坐标出界？
return 0;
if (Table[ty][tx] == 1) //已到过？
return 0;
if (Block[ty][tx] == 1) //有障碍？
return 0;
return 1;
}
[]
private int Test()
{
if ((tx == TargetX) && (ty == TargetY)) //已到目标
{
[] int act = ActNow;
while (act != 0)
{
// cout << (int)AllAct[act]; //一步步向前推出所有移动方向
act = ActHead[act]; //所以输出倒了过来
}
return 1;
[] }
[] return 0;
}
/**
* 寻径
* @param tx int 起始X坐标点
[] * @param ty int 起始Y坐标点
[] * @param TargetX int 目标X坐标点
* @param TargetY int 目标Y坐标点
*/
public void RunPathFinder()
[] {
LevelNow = 1;
LevelFoot[1] = 0;
LevelFoot[0] = -1;
ActX[0] = 0;
ActY[0] = 0;
[] while (!AllComplete)
{
[] LevelNow++; //开始搜索下一层
[] LevelFoot[LevelNow] = LevelFoot[LevelNow - 1];
//新一层的尾节点先设为与上一层相同
[] for (ActBefore = LevelFoot[LevelNow - 2] + 1;
[] ActBefore <= LevelFoot[LevelNow - 1];
ActBefore++) //对上一层所有节点扩展
{
for (Act = 1; Act <= MaxAct; Act++) //尝试所有方向
{
if ((ActOK() == 0) && (!AllComplete)) //操作可行?
{
LevelFoot[LevelNow]++; //移动尾指针准备加入新节点
ActNow = LevelFoot[LevelNow]; //找到加入新节点位置
ActHead[ActNow] = ActBefore; //置头指针
AllAct[ActNow] = Act; //加入新节点
ActX[ActNow] = tx;
ActY[ActNow] = ty; //存储移动后位置
Table[ty][tx] = 1; //做已到过标记
if (Test() == 1)
AllComplete = true; //完成
}
}
[] }
}
}
}
[]
在程序中，我给出了vDirect这个Vector向量类保存需要移动的方向。至于构造函数的参数，相信并不难。
好了，相信现在你对广度优先有了一些了解，但正像我在本系列文章的第一篇中所说的，直接使用会有一些意想不到的问题发生，而下一章就是为解决这些问题而写的。如果你依然关注，就请期待本人的下一篇拙作。
如果文章有错字，请谅解，因为我一般都是在原有文章基础上即兴发挥，错误之处在所难免。
http:///tech/article1031.html
</td></tr></table></td> </tr> <tr> <td background="/pic/split.gif" height=1></td> </tr> <tr> <td class="tdMargin1">
↑返回目录
前一篇: 在移动设备上使用M3G编程教程
后一篇: 手机游戏开发的一点心得（二）