好奇的探索者,理性的思考者,踏实的行动者。
Table of Contents:
每个mmorpg游戏中都会少不了有寻路模块,且还是开发中的一个难点,涉及到地形资源、客户端、服务器端,涉及到的算法还比较多,还得注意它的性能开销。相信不少游戏开发者都想弄清楚它是怎么实现的。网上讲解这方面的文章也有不少,github上的开源实现也有一些,不过有很大一部分是unity相关的,或者c#实现的。c++的实现也有,但是没几个像俺这样对初级中级程序员这么友好的。友好的原因如下:
了解学习一个东西如果一下子把你带到一个很难很深的level的话,恐怕还多人都是吃不消的。就应该循序渐进,按部登阶,从简入深。俺这个就是遵循这样的精神滴。这个是个入门版的,相信聪明的你很快就能看懂学会,说不定修改就直接用到你们的游戏里面!此项目为入门版,功能少且简单,进阶版的请看这里导航网格寻路C++实现版(进阶版)。
对游戏中需要寻路的场景通常都需要对其进行相应的处理以生成专门针对寻路功能所使用的文件,文件里面包含了地图的信息,比如地图的顶点、边、三角形等。这个文件的生成通常是由专门的生成工具来完成的,比如在unity中,可以通过Unity的插件把场景文件导出为寻路地图文件。
对于寻路地图文件,我们需要对其进行三角剖分,以便后续的寻路算法可以使用。
网格寻路是一种基于网格的寻路算法,它的基本思想是:首先将地图划分为一个个的网格,然后在网格中寻找一条从起点到终点的路径。网格寻路的算法有很多种,比如A*、Dijkstra、BFS、DFS等等,通常可以选择A*
算法来实现。
在网格寻路的过程中,我们只是找到了一条从起点到终点的网格路径,但是这条路径并不是我们想要的最终路径,因为这条路径是由网格组成的,而我们需要的是由顶点组成的路径。所以我们需要根据网格路径生成最终的路径。这个生成算法可以使用拐点算法来实现。
此工程的编译运行环境为windows,需要你的电脑的开发环境有cmake、Visual Studio或make、MinGW
build
目录,用vs打开生成的工程并运行,可执行程序会生成到当前项目根目录的bin
目录下在项目根目录执行make
命令即可,可执行程序同样会生成到bin
目录下
编译成功后再运行你会看到如下的程序运行界面:
界面说明:
* 红色的线是平面多边形,你可以把它看成游戏中的地型。
* 绿色的线表示经三角剖分后构成的线
* 蓝色的线代表寻路的路径
操作说明:
程序运行时在窗口点击第一下为寻路的起点,再点击第二下为寻路的终点。点击第三下会把之前的路径清空。
地图文件是一个自定义格式的文件,可以通过工具由obj模型文件导出生成,而obj模型文件可以通过Unity的插件把场景文件导出,例如这个monitor1394/ExportSceneToObjgithub项目。
在本项目的tools
目录下有一个gen_map_tools的工具,此工具可以将obj模型文件导出成适合本项目的地图文件格式。
这个工具的主要逻辑就是把obj模型的地图文件的外轮廓和内轮廓的多边形识别出来,并按照如下格式生成一个文本文件
childsize,parentlength, parentpoints,[0,child1length,child1points, [0,child2length, child2points]]
内嵌多边形数量,外多边形点的数量,外多边形的点,[0,子多边形1点的数量,子多边形1的点,[0, 子多边形2点的数量,子多边形2的点]]
下面的截图是gen_map_tools/map
目录下的两个地图的例子
其中红色的线为外轮廓,绿色的线为内轮廓。
具体的说明和使用方法请参考gen_map_tools
目录下的说明文档。
这些都可以在网上查的到,在俺的小demo中应该也很容易找的到的
Delaunay三角剖分其实并不是一种算法,而是一种三角剖分的标准,实现它有多种算法。它只是给出了一个“好的”三角网格的定义,它的优秀特性是空圆特性和最大化最小角特性,这两个特性避免了狭长三角形的产生,也使得Delaunay三角剖分应用广泛。
空圆特性其实就是对于两个共边的三角形,任意一个三角形的外接圆中都不能包含有另一个三角形的顶点,这种形式的剖分产生的最小角最大(比不满足空圆特性的最小角大)
// Polygon类,代表寻路多边形的类,主要实现多边形的三角剖分和寻路
Polygon
vector<Point> points;
vector<Triangle> triangles;
vector<Edge> edges;
Grid grid;
// 三角化
Delaunay()
eindexs // k->v (Pindex->edges的index),存放着已经处理过的所有三角形的边
restrains // 存放着所有的约束边,在处理开始就已经知道
// 寻路
FindPath()
// 多边形对应的网格结构类,由纵横的线分割的Cell(格子)组成
Grid
vector<Cell> cells;
int gride;
double minx;
double miny;
double maxx;
double maxy;
int xnum;
int ynum;
//格子类,其中包含构成多边形的顶点链表和边链表
Cell
vector<int> points;
vector<int> edges;
// Triangle类,三角形的表示类
Triangle
int p1;
int p2;
int p3;
int edges[3];
Point icenter;//重心
Point lt;
Point rb;
// Edge类,表示经过剖分后的线段,一条线段可能包含一个或两个三角,包含两个点
Edge
int triangles[2];
int points[2];
// Line类,画网格线的时候用到
Line
Point p1;
Point p2;
// Point类,点的表示类
Point
double x;
double y;
// Circle类,表示圆
Circle
Point center;
double r;
FindCross:向指定的方向寻路
FindPath:向指定的点寻路
客户端寻路
角色寻路
摇杆移动
向摇杆方向FindCross
主要点:摇杆移动每桢渲染,但是FindCross寻路的调用要增加个冷却时间,比如100毫秒,
要不然调用台频繁
屏幕点击某个位置点
FindPath,寻路到指定位置
释放技能(FindCross)
寻路到目标点后释放技能
自动任务(自动打怪、自动采集、自动跟随等)
FindPath,点击需要执行的任务自动寻路到目标点
服务器端寻路
怪物寻路
不存在攻击目标
巡逻
间隔固定时间在营地半径内进行一次巡逻
巡逻时会进行一次寻路(FindCross)
Idle
非巡逻时间idle
存在攻击目标
若在攻击范围内,则进行对攻击目标的一次寻路(FindPath),随后释放相应的技能
宠物寻路
按照规则跟随着主人