记录和分享mush遍历查找NPC的思路

xiaozihe

    因为近来做萧峰任务比较多，常常遇到一个很头疼的问题，就是杀手随机走路很快，有时候跑到非常远的地方，找到脑壳疼都找不着，最后只能无奈放弃任务。如果找杀手的时间太久，这货能跑到另外一个城市。于是这几天开始折腾如何自动查找NPC的问题。
    查了下论坛里大佬们的文章，关于遍历的思路，一般都是预先将区域内的所有路径录好（如扬州），然后再按照已录好的路径step by step。
    然而我并不想录这些路径，我的出发点是以某个房间为中心，围绕着这个中心，在一定范围内的区域进行查找。
    目前已完成功能，测试通过。算法采用的是深度遍历中的递归算法。
    其中有几个关键问题必须处理好：
    1.能够准确地捕捉和记录房间信息是算法正确的数据保障。因为有些房间是必须重复走的，经常需要比较当前的房间和已经走过的房间是否是相同。
    2.因为我面对的情况是没有预定路径的，地图需要边走边动态生成。
    3.为了少重复并且不漏走房间，必须对走过的走过的房间进行辨认并记录其离中心点的步数（步长）。举个例子，围绕信阳的小广场进行深度为3的遍历，往南遍历时，会走到西市。之后往西遍历，发现即是西市是已经访问过的，但是由于其离小广场的步长只有1，则仍然要走下去。否则会漏掉西市1、官道、中原马车行这3个房间。这点处理起来是比较复杂的。

    4.有些地方直接走过去是无法进去的，如扬州客店二楼，不给钱不给进。如果要快速遍历，这些地方可以不进，要进行特别处理。我的做法是略过这些房间不进去。
    5.必须准确的记录自己目前的位置（所在的房间），包括正常走的、走失败的、进不去的、退回的这几种情况都必须处理好。
    6.必须等上一步走完，才能走下一步，否则肯定会走乱。
    7.由于muchclient目前使用的lua版本是5.1，不支持goto语句，在循环时要实现其他语言的continue语句功能，处理起来略为麻烦一些。
    以上程序写好后，实际上可以很方便查找NPC、物品、房间。今天下午完成后，实测了半天萧峰任务，和原来比起来，感觉丝般顺滑，省心快捷还少失败。
    上个效果图给大家乐一乐：

此处略过几幅遍历效果图片

    注：如果不怕重复走的太多，其实上述第3点可以不必处理。

jarlyyn

你这就是个深度优先遍历啊。

北侠用深度遍历的问题是不是所有房间都能返回的，甚至某个房间se过去，nw返回的是另一个房间 。

还有迷宫也解决不了。

xiaozihe

jarlyyn 发表于 2023-2-17 05:56 PM
你这就是个深度优先遍历啊。

北侠用深度遍历的问题是不是所有房间都能返回的，甚至某个房间se过去，nw返回 ...

是的。对于迷宫，乱走就可以了，不需要什么算法。因为在做任务时，一般属于小范围内查找，所以没处理走过去了走不回来的情况，遇到这些地方需要重新执行一次遍历继续查找即可。

xfox

赞~

能处理环就更牛逼了

kkena

北侠一卡通了解下，付啥钱，刷卡……