J2me Game学习四种寻路算法比较

　　用了两张障碍表，一张是典型的迷宫：

   　char Block[SY][SX] = {
　　{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
　　{1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1},
　　{1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1},
　　{1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1},
　　{1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1},
　　{1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1},
　　{1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1},
　　{1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
　　{1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1},
　　{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
　　};

　　第二张是删掉一些障碍后的:

　  char Block[SY][SX] = {
　　{1,1,1,1,1,1,1,1,1,1,1 },
　　{1,0,1,0,1,0,0,0,0,0,1 },
　　{1,0,1,0,0,0,1,0,1,1,1 },
　　{1,0,0,0,0,0,1,0,0,0,1 },
　　{1,0,0,1,0,0,1,0,0,1,1 },
　　{1,0,1,0,0,1,0,1,0,0,1 },
　　{1,0,0,0,0,0,0,0,1,0,1 },
　　{1,0,1,0,0,0,1,0,1,0,1 },
　　{1,0,0,1,0,0,1,0,0,0,1 },
　　{1,1,1,1,1,1,1,1,1,1,1 }
　　};

　　结果：

　　尝试节点数 合法节点数 步数

　　深度优先 416/133 110/43 19/25

　　广度优先 190/188 48/49 19/15

　　深度+启发 283/39 82/22 19/19

　　广度+启发 189/185 48/49 19/15

　　所以可以看出深度+启发是最好的，效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。

　　附：dfs+heu的源程序，bc++ 3.1通过

　　if ((x == TargetX) && (y == TargetY)) { //已到目标
　　for (int i = 0; i <= Level; i++)
　　cout << (int) Act[i]; //输出结果
　　cout << endl;
　　cout << Level + 1 << " " << sum1 << " " << sum2 << endl;
　　LevelComplete = AllComplete = 1; //完成搜索
　　}
　　}
　　int ActOK() {
　　int tx = x + dx[Act[Level] - 1]; //将到点的x坐标
　　int ty = y + dy[Act[Level] - 1]; //将到点的y坐标
　　if (Act[Level] > MaxAct) //方向错误?
　　return 0;
　　if ((tx >= SX) || (tx < 0)) //x坐标出界?
　　return 0;
　　if ((ty >= SY) || (ty < 0)) //y坐标出界?
　　return 0;
　　if (Table[ty][tx] == 1) //已到过?
　　return 0;
　　if (Block[ty][tx] == 1) //有障碍?
　　return 0;
　　x = tx;
　　y = ty; //移动
　　Table[y][x] = 1; //做已到过标记
　　return 1;
　　}
　　void Back() {
　　x -= dx[Act[Level - 1] - 1];
　　y -= dy[Act[Level - 1] - 1]; //退回原来的点
　　Table[y][x] = 0; //清除已到过标记
　　Act[Level] = 0; //清除方向
　　Level--; //回上一层
　　}
　　int GetNextAct() //找到下一个移动方向。这一段程序有些乱，
　　//仔细看!
　　{
　　int dis[4];
　　int order[4];
　　int t = 32767;
　　int tt = 2;
　　for (int i = 0; i < 4; i++)
　　dis[i] = abs(x + dx[i] - TargetX) + abs(y + dy[i] - TargetY);