2.2　用网格表示世界

网格是游戏中用于表示世界用得最多的结构，因为它容易实现且直观。然而，需要通过学习图论及其特性为高级图表示法打下基础。

准备工作

首先，需要创建一个抽象类Graph，声明每个图表示实现的虚方法。无论在内部如何表示顶点和边，寻路算法都保持在上层实现，这样就避免了为各种类型的图表示实现算法。

这个类是本章中要学习的各种不同图表示法的父类，而且如果你想要实现本书中没有涵盖的图表示法，也可以将这个类作为一个不错的开端。

然后，我们将实现一个图的子类，它在内部将自己作为网格处理。

操作步骤

下面的代码是用于Graph类的：

1. 创建类的骨架以及其成员变量：

2. 定义Start函数：

3. 定义之前提到的Load虚函数：

4. 实现用于取得图的顶点个数的虚函数：

5. 定义用于获取给定点位最邻近的顶点的虚函数：

6. 实现用于根据顶点的ID获取顶点的函数：

7. 实现用于获取一个顶点的邻接顶点的函数：

还需要一个Vertex类，代码如下：

接下来，需要创建一个Edge类，用于存储顶点的邻接点及它们的成本，下面来实现它：

1. 创建Edge类，继承自IComparable：

2. 实现其构造函数：

3. 实现比较成员函数：

4. 实现用于比较两条边的函数：

5. 重写比较两个对象的函数：

6. 重写用于获取哈希值的函数，这在重写Equals函数时要用到：

除了创建前面的类之外，定义一些基于立方体（可以是一个高度比较低的立方体）控件的预制件也很重要，以便将地面和墙体或障碍物可视化。用于地面的预制件被赋值给vertexPrefab变量，而墙体预制件被赋值给下一段中声明的obstaclePrefab变量。

最后，创建一个Maps目录，保存用于定义地图的文本文件。

现在是时候深入理解并具体实现基于网格的图了。首先，实现所有操作图的函数，留一些空间用于保存你自己的文本文件，然后我们将学习如何读取.map文件，这是一种被很多游戏使用的开放格式：

1. 创建继承自Graph的GraphGrid类：

2. 定义GridToId和IdToGrid函数，用于把网格中的位置点转换成顶点索引，以及反向转换：

3. 定义LoadMap函数，用于读取文本文件：

4. 重写LoadGraph函数：

5. 重写GetNearestVertex函数。这是一种传统的方式，不需要考虑返回的顶点是不是障碍物。下一步我们将学习如何改进：

6. 重写GetNearestVertext函数，它基于广度优先算法，后面会深入学习：

7. 定义搜索的位置（顶点）列表和要搜索的位置队列：

8. 当队列中还有未搜索过的元素时，执行下面的代码，否则，返回null：

9. 如果是一个有效的顶点则立即返回它：

10. 如果已经不在列表中了，则将这个位置添加到搜索过的顶点列表中：

11. 假如位置有效，将它所有有效的邻接点添加到队列中：

运行原理

此算法利用私有函数去适配继承自父类的通用函数，依靠简单的数学函数把二维向量位置转换成一维向量，或者说顶点索引。如图2-1所示。

你可以使用自己的地图文件实现LoadMap函数，但是下一节我们要学习如何实现和读取某种类型的文本文件，这种文本文件包含基于网格的地图。这将使你了解如何处理文件，甚至对文件使用相同的格式。

延伸阅读

还要学习另一种使用.map文件格式实现LoadMap函数的方法：

1. 定义函数，创建一个StreamReader对象，用于读取文件：

2. 声明并初始化需要用到的变量：

3. 读取包含高度和宽度的文件头：

4. 初始化成员变量，同时申请内存：

5. 声明用于迭代读取字符的for循环：

6. 根据读取的字符，把逻辑表达式赋值为true或false：

7. 实例化合适的预制件：

8. 把新的游戏对象赋值为图的子节点，并清除其名称：

9. 在上一个循环之后创建一对嵌套循环，用于设置每个顶点的邻接顶点：

10. 定义上一步调用的SetNeighbours函数：

11. 当我们需要八个邻域（上下左右以及4个角）时计算出合适的值：

12. 初始化四个邻域（不含4个角）：

13. 将邻接点添加到列表中，与邻域的过程相同：

其他参考

关于用到的地图格式以及获取免费地图的更多信息，请参阅由Sturtevant教授领导的Moving AI Lab的网站，网址是：http://movingai.com/benchmarks/。