寻路

地图建模

寻路的前提是对地图进行建模。

常用的有三种建模方法：

1. 网格。常用于2D地图，分为xy轴的矩形格子。

2. navmesh。常用于3D地图，方便z轴建模。

3. 手动标点。需要人工在地图上标哪些点是可行走的，一般和前两种结合使用。

navmesh&A*&漏斗

使用navmesh对地图建模，使用A* 和漏斗算法寻路，是常用的寻路方式

使用三角剖分来对地图分成三角形网格。

常用的三角剖分算法是 Delaunay trianglations 和 constrained Delaunay trianglations(CDT)

二者生成的三角形都满足”三顶点生成的圆不包含第四个点“，CDT的约束是只会使用给定的点生成三角形

CDT 可以使用 poly2tri 库(github上就有)，接口方便简单。

DT 可以使用 triangle 库，接口不便于理解，我自己封装了个简单的 https://gitee.com/xtlvlv/triangle-lib。

三角剖分

poly2tri库的使用

看github readme就够了，比较简单。

triangle库的使用

运行环境

只能在linux下运行，看makefile，会生成两个可执行文件。

triangle 主要是读 xx.poly文件，生成.ele .node等文件，

showme 程序可以读这些文件生成可视化图形

poly文件的编写

一共分为四个部分

1. node，点。

2. segment，边。

3. hole，内部不想让分割的洞，比如游戏地图中的障碍物。指定hole只需要hole内的一个点就行，hole的边界必须包围着

4. xx ，可忽略

学习使用Triangle库_triangle showme编译-CSDN博客blog.csdn.net

文档

triangle -h 产看帮助，了解都支持那些功能选项

triangle.h 如果想在其他程序中使用，这个文件相当于文档，tricall.c 是使用示例。