基础 | 图与路径查找----地图分割
本系列为笔者初学c/c++和游戏AI开发的学习过程，算法为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),若有错误请在评论区留下批评意见。
语言：c/c++ (11及以上)
平台：macOS mojave
编辑器/编译器：vs Code / g++
图与路径查找
二、地图
2.1 地图
在做路径查找之前，我们首先需要对地图进行划分，也就是将地图分割成便于计算的一系列节点。
通常地图分割的方法有两种：Grid（或Tile，方格）和Navmesh（导航网格）。
2.1.1 Grid 方格：
Grid指的是将地图离散化一个个相互独立的方格，这样每个方格代表了地图上的一种资源，可能是道路、山体或者树木等。
游戏中的角色根据每个方格属性的不同，可以自动判断是否可以通过这个方格前往下一个。
绘制方格地图是相对比较简单的，在我们项目中，只需要用一个二维数组就可以表达出一个地图的方格。
如上图，Tile类是我们自定义的方格类，存储方格的位置、大小和标签ID。
在地图里，高height对应矩阵的行y，宽width对应列x。为了便于渲染，我们用一个动态数组tiles来存储这些方格。
可见只要知道地图的宽高，和方格的大小，就能够定义方格在世界坐标中的中心位置，并将其表示为数学模型中的节点。
方格地图的优点在于简单，且跟A*算法十分的契合。缺点是角色移动会不够连续自然，十分僵硬，且在地图大、路径长的情况下十分耗费计算资源。
2.1.1 Navmesh 导航网格：
导航网格是一种用于在复杂空间中导航寻路、标记哪些地方可行走的多边形网格数据结构 。
一个导航网格是由多个凸多边形（Convex Polygon, Poly Mesh）组成的。
这里主要应用了凸多边形的性质：在凸多边形边上的一个点走到另外一点，不管怎么走都不会走出这个多边形。（https://mathworld.wolfram.com/ConvexPolygon.html）
因此，我们在游戏地图上，只要在空地上绘制好凸多边形，角色在这个凸多边形上无论怎么走都不会碰到障碍物。
导航网格的构建相对更麻烦，笔者在这个项目中并未采用这种方法，因此只简单介绍一下在2D地图上如何绘制一个Navmesh。
连接地图的边界点和障碍物的边界点， 将地图分割成多个三角形区域。
清除多余的三角形区域。
在网格的每条边上放置节点（路径点），将路径点连接起来，就形成了导航网格。
Navmesh导航网格的优点是减少节点和搜寻的计算量，使角色移动更自然。缺点是计算三角形和合并相邻的凸多边形需要很大的计算量，且实现十分复杂。
2.2 用SFML绘制方格地图
为了便于地图分割，我们将地图的大小设置为 1280x720，方格大小40x40，且地图上有一个起始节点和一个目标节点，表示算法的开始和结束。
黑色方格是墙壁，表示无法通过的节点。
2.2.1 Tile类
我们用Tile类来表示一个方格，相当于每个tile是一个贴图。在SFML中，贴图是可以直接在窗口中绘制的子类，需要继承sf::Drawble类和sf::Transformable类。
Tile类存储方格在地图上的基础信息，包括位置、颜色和ID（方格标签）。
其中有几个比较特殊的类：
RectangleShape：特殊表示的矩形，用来绘制方格，可随意变换属性。
IntRect：操纵2D轴对齐的矩形的类，输入为方格左上角顶点的坐标和方格宽高，转化为 标准格式。
draw()：该虚函数用来绘制图形，按照官方的方法写就好
2.2 Game类
我们的项目主体是一个Game类，在这个类中定义地图（世界）拥有的一些功能。
handleInput（）：处理键盘输入。
S：source，绘制起始节点
T：target，绘制目标节点
W：wall，绘制墙壁节点
R：run，启动路径查找算法
C：clear，清除内存，重置地图
A：A*算法，选择A*算法作为路径查找算法
B：BFS算法，选择BFS算法作为路径查找算法
render（）：渲染，由于我们需要展示路径查找的过程，因此分开渲染路径节点。通过延迟算法来控制渲染时间。
整个项目的逻辑设计：
启动程序，初始化地图。
键盘输入R，选择路径查找算法。
按住S键或T键，鼠标点击地图，重置起始节点和目标节点的位置。
按住W键，鼠标点击地图，在地图上绘制墙壁节点。
按R键，启动路径查找算法。
按C键，清除内存，重置地图。
到这里，就能够绘制出方格地图，接受键盘输入，选择路径查找算法，并运行算法展示查找路径。
更详细的工程实现，读者可以下载代码阅读，笔者一直相信阅读代码是最好的学习方式。
2.3 结果展示
参考：
《游戏人工智能编程案例精粹》
https://en.wikipedia.org/wiki/Navigation_mesh#Advantages Navmesh介绍
https://mathworld.wolfram.com/ConvexPolygon.html 凸多边形数学定义
https://www.sfml-dev.org/tutorials/2.5/
相关代码下载 https://github.com/linpeijie/GameToy
