游戏开发技术论坛

 找回密码
 立即注册
搜索
查看: 1032|回复: 1

精简的场景内寻路算法思路

[复制链接]

0

主题

0

帖子

8

积分

新手上路

Rank: 1

积分
8
发表于 2019-9-7 20:58:57 | 显示全部楼层 |阅读模式
我们在在做一款游戏,设计上战斗是在一个带有障碍的场景内放置大概50个角色自动战斗.然后考虑到反外挂,整个战斗系统包括寻路等都是在后端做,前端只负责播放战斗记录.
考虑了几种比较常用的寻路算法.
1. 基于GRID的地图划分, 这个算法有个很大的问题就是精度不够,比如说我们想做一个细墙,那么精度就要做到墙那么细,然后整个场景就会有太多GRID, 类似5000*5000, 后台有点扛不住.
2. 用navmesh来划分地图, 吧地图分成很多凸多边形,然后在多边形之间做寻路,这套方案还算成熟,可以做到很高的精度.

基本上是考虑用navmesh来做了, 突然我想到如果我们场景的所有障碍物都是 平行或垂直 X轴 的边组成的矩形(这点可以让策划妥协), 那么我们可以搞一个矩形划分的navmesh,基本上是把地图划分成n个矩形, 部分矩形是障碍,部分矩形是通路, 然后就可以用navmesh上的寻路算法来搞了, 这有点类似离散化的grid地图划分,不过矩形少很多.

存储很简单,就是一堆障碍的矩形, 序列化也很简单.

然后我们就开搞了,写着写着发现一个问题,,如果我们在生成这种rect navmesh的过程中保持一个特性,那么生成的矩形划分就是天然有序的,可以o(logN)的时间判断角色在哪个矩形内, 然后发现这样有一个很大的优点就是地图划分load进内存就可以直接用了, 不需要创建数据结构开销.

然后我们用这种算法测了一下寻路, 很符合我们的要求, 地图划分直接二进制丢到mongodb也很方便.

上面说的让矩形划分保持有序的特性就留给读者思考了

0

主题

1

帖子

13

积分

新手上路

Rank: 1

积分
13
发表于 2020-5-19 16:45:00 | 显示全部楼层
亮出你们的寻路速度看看?
我也做的是四边形导航寻路,640*640的主城地图,对线两端寻个路0.02ms
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2023-2-4 11:03

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表