北大侠客行MUD论坛

 找回密码
 注册
搜索
热搜: 新手 wiki 升级
查看: 4509|回复: 16

记录和分享GPS寻路方法和算法优化的一些思路

[复制链接]
发表于 2023-4-30 16:16:42 | 显示全部楼层 |阅读模式
本帖最后由 xiaozihe 于 2023-4-30 04:18 PM 编辑

近些天在做北侠GPS,在将北侠地图所有房间全部连通前提下(不进行区域划分),遇到寻路计算耗时较长的问题。
1.对于寻路算法
简单的BFS算法是行不通的,因为BFS算法只能找到最短路线而无法找到最优路线的。即可能找到的是步数最少的路线,但是可能代价(比如路线行走的耗时和交通花费)不是最少的。
我采用的是Dijkstra算法。因为这种算法起码保证了可以获得最优路径,即使寻路耗时长一点又怎么样呢,毕竟玩北侠最不缺的就是时间~~,这是我刚开始的想法。
注:曾看见Q群里有大佬说可以采用A*算法,然而我并不明白在北侠中A*算法中的启发函数h(n)如何确定。如果可以,恳请大佬指教,小弟先在此谢过。
2.寻路算法耗时及优化
一开始,我的路径算法耗时比较长,比如从"黑木崖的黑木崖下"到"平西王府的书房",这个路线的寻路过程基本遍历了地图所有的房间,大约需要耗时1600ms(1.6秒)。
后来我进行了预加载数据库到内存,并在处理table时(如等待处理的房间列表openList和已处理的房间列表closeList),由原来的数组改为采用哈希表形式(key-value)进行保存和比较(哈希表效率比数组高很多),计算速度得到了质的提升。仍然以"黑木崖的黑木崖下"到"平西王府的书房"的路线进行测试,大约只需要130ms(0.13秒),其他的短路线的计算耗时就更快了,一般都在100ms以内。
上述功能已测试了几天,目前运行良好
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-4-30 16:21:30 | 显示全部楼层

11

本帖最后由 ppmm 于 2023-4-30 04:25 PM 编辑

求分享
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-4-30 16:23:16 | 显示全部楼层
非常不幸的是别人是他的1/10
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-4-30 17:04:29 | 显示全部楼层
北侠的房间的数量级完全不需要优化吧……

当年我记得搞过双向逼近的,但发现完全没必要的。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-4-30 17:12:50 | 显示全部楼层
man 发表于 2023-4-30 04:23 PM
非常不幸的是别人是他的1/10


试验了下,的确……

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-4-30 18:19:53 | 显示全部楼层
支持楼主,我也是写了一堆各种寻路算法,再慢慢选择合适的。
楼主的这段路,我这里是 0.02s,还有优化空间,加油努力~
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2023-5-1 02:19:06 | 显示全部楼层
本帖最后由 xiaozihe 于 2023-5-1 02:48 AM 编辑

谢谢各位大佬的提示。晚上对算法进行了优化,仍然以上面的路径进行测试,计算耗时一般在稳定在35ms以内。现在是休假在家,用的是5年前配的旧电脑,不知道新电脑对速度有没有提升,待收假回去后再进行测试。

我的地图还不是很完善,所以计算路径上可能有差异。另外,如果采用坐车的方式,则会少走一些路,计算路径应该会快一些。我是刚玩不久,号上缺钱,目前是能省则省,所以一般都不坐车。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2023-5-3 11:15:35 | 显示全部楼层
本帖最后由 xiaozihe 于 2023-5-3 11:24 AM 编辑

今天回到家,用家里的电脑测试了一下,计算耗时一般在25ms以内:

我的电脑硬件配置如下:

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-5-3 21:11:27 | 显示全部楼层
能分享一个哇?
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2023-5-3 21:22:09 | 显示全部楼层
你这个使用mudlet平台,还是跨平台的啊?
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|北大侠客行MUD ( 京ICP备16065414号-1 )

GMT+8, 2024-11-24 09:58 AM , Processed in 0.010121 second(s), 15 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

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