|
|
我们在在做一款游戏,设计上战斗是在一个带有障碍的场景内放置大概50个角色自动战斗.然后考虑到反外挂,整个战斗系统包括寻路等都是在后端做,前端只负责播放战斗记录.
考虑了几种比较常用的寻路算法.
1. 基于GRID的地图划分, 这个算法有个很大的问题就是精度不够,比如说我们想做一个细墙,那么精度就要做到墙那么细,然后整个场景就会有太多GRID, 类似5000*5000, 后台有点扛不住.
2. 用navmesh来划分地图, 吧地图分成很多凸多边形,然后在多边形之间做寻路,这套方案还算成熟,可以做到很高的精度.
基本上是考虑用navmesh来做了, 突然我想到如果我们场景的所有障碍物都是 平行或垂直 X轴 的边组成的矩形(这点可以让策划妥协), 那么我们可以搞一个矩形划分的navmesh,基本上是把地图划分成n个矩形, 部分矩形是障碍,部分矩形是通路, 然后就可以用navmesh上的寻路算法来搞了, 这有点类似离散化的grid地图划分,不过矩形少很多.
存储很简单,就是一堆障碍的矩形, 序列化也很简单.
然后我们就开搞了,写着写着发现一个问题,,如果我们在生成这种rect navmesh的过程中保持一个特性,那么生成的矩形划分就是天然有序的,可以o(logN)的时间判断角色在哪个矩形内, 然后发现这样有一个很大的优点就是地图划分load进内存就可以直接用了, 不需要创建数据结构开销.
然后我们用这种算法测了一下寻路, 很符合我们的要求, 地图划分直接二进制丢到mongodb也很方便.
上面说的让矩形划分保持有序的特性就留给读者思考了
|
|
发表于 2019-9-7 20:58:57