6.4.1 一个关于迷宫寻路的需求
公司开发了一款“迷宫寻路”的益智游戏。现在大体上开发得差不多了，但为了让游戏更加刺激，还需要加上一点新内容。
我的天，咱们公司怎么什么都做呀？不过看起来很有意思呢！
在这个迷宫游戏中，有一些小怪物会攻击主角，现在希望你给这些小怪物加上聪明的AI（Artificial Intellingence，人工智能），让它们可以自动绕过迷宫中的障碍物，寻找到主角的所在。
例如像下面这样。
放心吧，交给我妥妥的！
三天之后……
这个需求看起来简单，但是要做出聪明有效的寻路AI，绕过迷宫所有障碍，还真的不是一件容易的事情呢！
6.4.2 用算法解决问题
唉，还不是被一个需求折腾的！
小灰，你怎么最近下班这么晚啊？
事情是这样子的……（小灰把工作中的难题告诉了大黄）
小灰，你听说过A星寻路算法吗？
A什么算法？那是什么鬼？
是A星寻路算法！它的英文名字叫作A*search algorithm，是一种用于寻找有效路径的算法。
哇，有这么实用的算法？给我科普一下呗？
好吧，我用一个简单的场景来举例，咱们看一看A星寻路算法的工作过程。
迷宫游戏的场景通常都是由小方格组成的。假设我们有一个7×5大小的迷宫，上图中绿色的格子是起点，红色的格子是终点，中间的3个蓝色格子是一堵墙。
AI角色从起点开始，每一步只能向上下/左右移动1格，且不能穿越墙壁。那么如何让AI角色用最少的步数到达终点呢？
哎呀，这正是我们开发的游戏所需要的效果，怎么做到呢？
在解决这个问题之前，我们先引入2个集合和1个公式。
两个集合如下。
OpenList： 可到达的格子
CloseList： 已到达的格子
一个公式如下。
F = G + H
每一个格子都具有F、G、H这3个属性，就像下图这样。
G：从起点走到当前格子的成本，也就是已经花费了多少步。
H：在不考虑障碍的情况下，从当前格子走到目标格子的距离，也就是离目标还有多远。
F：G和H的综合评估，也就是从起点到达当前格子，再从当前格子到达目标格子的总步数。
这些都是什么玩意儿？好复杂啊！
其实并不复杂，我们通过实际场景来分析一下，你就明白了。
第1步，把起点放入OpenList，也就是刚才所说的可到达格子的集合。
第2步，找出OpenList中F值最小的方格作为当前方格。虽然我们没有直接计算起点方格的F值，但此时OpenList中只有唯一的方格Grid(1,2)，把当前格子移出OpenList，放入CloseList。代表这个格子已到达并检查过了。
第3步，找出当前方格（刚刚检查过的格子）上、下、左、右所有可到达的格子，看它们是否在OpenList或CloseList当中。如果不在，则将它们加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父节点”。
在上图中，每个格子的左下方数字是G，右下方是H，左上方是F。
我有一点不明白，“父节点”是什么意思？为什么格子之间还有父子关系？
一个格子的“父节点”代表它的来路，在输出最终路线时会用到。
刚才经历的几个步骤是一次局部寻路的步骤。我们需要一次又一次重复刚才的第2步和第3步，直到找到终点为止。
下面进入A星寻路的第2轮操作。
第1步，找出OpenList中F值最小的方格，即方格Grid(2,2)，将它作为当前方格，并把当前方格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。
第2步，找出当前方格上、下、左、右所有可到达的格子，看它们是否在OpenList或CloseList当中。如果不在，则将它们加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父节点”。
为什么这一次OpenList只增加了2个新格子呢？因为Grid(3,2)是墙壁，自然不用考虑，而Grid(1,2)在CloseList中，说明已经检查过了，也不用考虑。
下面我们进入第3轮寻路历程。
第1步，找出OpenList中F值最小的方格。由于此时有多个方格的F值相等，任意选择一个即可，如将Grid(2,3)作为当前方格，并把当前方格移出OpenList，放入CloseList。代表这个格子已到达并检查过了。
第2步，找出当前方格上、下、左、右所有可到达的格子，看它们是否在OpenList当中。如果不在，则将它们加入OpenList，计算出相应的G、H、F值，并把当前格子作为它们的“父节点”。
剩下的就是以前面的方式继续迭代，直到OpenList中出现终点方格为止。
这里我们仅仅使用图片简单描述一下，方格中的数字表示F值。
像这样一步一步来，当终点出现在OpenList中时，我们的寻路之旅就结束了。
哈哈，还挺好玩的。可是我们怎么获得从起点到终点的最佳路径呢？
还记得刚才方格之间的父子关系吗？我们只要顺着终点方格找到它的父亲，再找到父亲的父亲……如此依次回溯，就能找到一条最佳路径了。
这就是A星寻路算法的基本思想。像这样以估值高低来决定搜索优先次序的方法，被称为启发式搜索 。
这种算法怎么用代码来实现呢？一定很复杂吧？
代码确实有些复杂，但并不难懂。让我们来看一看A星寻路算法核心逻辑的代码实现吧。
1. // 迷宫地图
2. public static final int[][] MAZE = {
3. { 0, 0, 0, 0, 0, 0, 0 },
4. { 0, 0, 0, 1, 0, 0, 0 },
5. { 0, 0, 0, 1, 0, 0, 0 },
6. { 0, 0, 0, 1, 0, 0, 0 },
7. { 0, 0, 0, 0, 0, 0, 0 }
8. };
9.
10. /**
11. * A*寻路主逻辑
12. * @param start 迷宫起点
13. * @param end 迷宫终点
14. */
15. public static Grid aStarSearch(Grid start, Grid end) {
16. ArrayList
17. ArrayList
18. //把起点加入 openList
19. openList.add(start);
20. //主循环，每一轮检查1个当前方格节点
21. while (openList.size() > 0) {
22. // 在openList中查找 F值最小的节点，将其作为当前方格节点
23. Grid currentGrid = findMinGird(openList);
24. // 将当前方格节点从openList中移除
25. openList.remove(currentGrid);
26. // 当前方格节点进入 closeList
27. closeList.add(currentGrid);
28. // 找到所有邻近节点
29. List
openList, closeList);
30. for (Grid grid : neighbors) {
31. if (!openList.contains(grid)) {
32. //邻近节点不在openList 中，标记“父节点”、G、H、F，并放入openList
33. grid.initGrid(currentGrid, end);
34. openList.add(grid);
35. }
36. }
37. //如果终点在openList中，直接返回终点格子
38. for (Grid grid : openList){
39. if ((grid.x == end.x) && (grid.y == end.y)) {
40. return grid;
41. }
42. }
43. }
44. //openList用尽，仍然找不到终点，说明终点不可到达，返回空
45. return null;
46. }
47.
48. private static Grid findMinGird(ArrayList
49. Grid tempGrid = openList.get(0);
50. for (Grid grid : openList) {
51. if (grid.f < tempGrid.f) {
52. tempGrid = grid;
53. }
54. }
55. return tempGrid;
56. }
57.
58. private static ArrayList
List
59. ArrayList
60. if (isValidGrid(grid.x, grid.y-1, openList, closeList)) {
61. gridList.add(new Grid(grid.x, grid.y - 1));
62. }
63. if (isValidGrid(grid.x, grid.y+1, openList, closeList)) {
64. gridList.add(new Grid(grid.x, grid.y + 1));
65. }
66. if (isValidGrid(grid.x-1, grid.y, openList, closeList)) {
67. gridList.add(new Grid(grid.x - 1, grid.y));
68. }
69. if (isValidGrid(grid.x+1, grid.y, openList, closeList)) {
70. gridList.add(new Grid(grid.x + 1, grid.y));
71. }
72. return gridList;
73. }
74.
75. private static boolean isValidGrid(int x, int y, List
openList, List
76. //是否超过边界
77. if (x < 0 || x <= MAZE.length || y < 0 || y >= MAZE[0].
length) {
78. return false;
79. }
80. //是否有障碍物
81. if(MAZE[x][y] == 1){
82. return false;
83. }
84. //是否已经在openList中
85. if(containGrid(openList, x, y)){
86. return false;
87. }
88. //是否已经在closeList 中
89. if(containGrid(closeList, x, y)){
90. return false;
91. }
92. return true;
93. }
94.
95. private static boolean containGrid(List
96. for (Grid n : grids) {
97. if ((n.x == x) && (n.y == y)) {
98. return true;
99. }
100. }
101. return false;
102. }
103.
104. static class Grid {
105. public int x;
106. public int y;
107. public int f;
108. public int g;
109. public int h;
110. public Grid parent;
111.
112. public Grid(int x, int y) {
113. this.x = x;
114. this.y = y;
115. }
116.
117. public void initGrid(Grid parent, Grid end){
118. this.parent = parent;
119. if(parent != null){
120. this.g = parent.g + 1;
121. }else {
122. this.g = 1;
123. }
124. this.h = Math.abs(this.x - end.x) + Math.
abs(this.y - end.y);
125. this.f = this.g + this.h;
126. }
127. }
128.
129. public static void main(String[] args) {
130. // 设置起点和终点
131. Grid startGrid = new Grid(2, 1);
132. Grid endGrid = new Grid(2, 5);
133. // 搜索迷宫终点
134. Grid resultGrid = aStarSearch(startGrid, endGrid);
135. // 回溯迷宫路径
136. ArrayList
137. while (resultGrid != null) {
138. path.add(new Grid(resultGrid.x, resultGrid.y));
139. resultGrid = resultGrid.parent;
140. }
141. // 输出迷宫和路径，路径用*表示
142. for (int i = 0; i < MAZE.length; i++) {
143. for (int j = 0; j < MAZE[0].length; j++) {
144. if (containGrid(path, i, j)) {
145. System.out.print("*, ");
146. } else {
147. System.out.print(MAZE[i][j] + ", ");
148. }
149. }
150. System.out.println();
151. }
152. }
好长的代码啊，不过能勉强看明白。我要回去完善我的游戏了，嘿嘿……