目录
复杂Mud机器人编写指引
作者：Seagate
原帖地址及附件下载：复杂Mud机器人编写指引
开始起的名字不是特别恰当，修改一下本篇文章的题目，再次重申一下写本文的初衷。我写本文不是为了鼓励全自动机器人，仅以此文帮助想要深入Zmud/Cmud系列软件编程的人员提高在这方面的技巧。本文只是不是非常恰当的引用护镖机器人作为例子来讲解。本文的头三章主要是对我附件提供的机器人做一些简单的铺垫，方便大家能够比较容易阅读我写的机器人。后面第四章讲解主流的几种设计思路，第五章对如何设计path进行讲解，第六章讲解护镖出现乱入的时候如何重新定位，第七章讲解小范围区域搜索，第八章讲解大范围区域搜索（没有开发这方面的代码，主要是本人对胡一刀任务和task任务兴趣不是特别大，纯理念上讲讲，觉得不对请补充），第九章讲讲如何设计返回线路，第十章总结。
一、序言
本教程主要目的是如何帮助大家提高自己的护镖机器人的自动化水平。最近有一些人陆续向我索要自动化护镖 机器人，一来这个东西传播出去确实不是特别好，本游戏官方对这个也不是特别鼓励，二来索要人和本人确实不是 特别熟悉，提供出去无法保证传播范围。我仅以写这个系列文章帮助大家提高护镖机器人的自动化水平。本系列文 章估计会有10个左右章节，目标是差不多以一到二周时间写完。
在开始护镖之前首先你要确认的是机器人的编程平台。目前主流的平台有以下几种：Zmud462，Zmud721， Cmudpro237，Mushclient440。我就简单分析一下几个平台的优缺点。Zmud462平台好处是中文支持比较好，缺点是 主流的一些技术都无法支持，包括列表，data record等等，基本上复杂的机器人不建议在这个平台上开发，包括 护镖机器人，实际上你也很难在Zmud462平台开发出一个良好的易于维护和使用的自动护镖机器人。Zmud721平台好 处是目前常用的一些Zscript技术他基本上都能支持，而且稳定性比较好，缺点是对中文支持非常差，对结构化编 程所需要的一些技术包括函数、过程等不支持。如果你的护镖机器人需要使用到区域搜索、位置定位等等技术最好 不要挑选这个平台。Cmudpro237是Zmud系列软件的最新升级版，优点是支持多线程技术性能比较好，中文支持比较 好，支持Xml，提供结构化编程的可能性，支持Lua等等，缺点是平台本身稳定性不是特别良好，对编程人员要求比 较高。Mushclient440平台没有怎么使用过，简单说一下优点吧就是使用Lua开发，语言上比较规范，稳定性非常好， 缺点就是对Mud本身的支持没有Zmud/Cmud系列有非常丰富的内置功能，对开发人员有一定的素质要求。
具体到了自动护镖机器人开发上我建议新入门的选择使用Cmudpro237平台，一来是该平台兼容Zmud使用上难度 比较小，二来是语言比较规范，三来是可以使用内置的Map函数。我下面讲的东西将都是以Cmudpro237为平台的， 就不再特殊说明了。
选好平台以后我讲讲一个自动化护镖机器人的几大挑战。一共有四方面挑战：如何根据林镇南给出的目的地提 示设计出一条良好的护镖线路；如何在乱入的时候回到预设的护镖线路上；如何在到达目的地没有找到伙计的情况 下通过区域搜索找到伙计；在完成任务或者半路被劫匪打晕的情况下如何找到返回路径交镖或者取消任务。
我会在下一个章节以这四个方面一一展开讲解，大体设想是每个方面二个章节，每讲完一个方面提供相应的样 板源代码供大家参考。
附件为护镖机器人样板源代码，包括所有的alias，events，functions，变量定义和部分的护镖机器人代码。 我在以后章节我结合该源代码逐步讲解。本源代码和我自己设计的数据库紧密结合，直接使用是使用不了的。在接 下来讲解之前先把这个xml文件导入的一个新开的cmudpro的session里面。
二、基础环境介绍
本节主要介绍设计相关的一些基础事件、基础函数、基础数据结构。方便大家解读护镖机器人。在本护镖机器 人中地图数据库如何实现以及用什么的方法才能获取房间信息到机器人中有两个开放式接口来实现的。分别是 pubFunc|roomFunc下的函数batch_room_info和函数room_info，这两个函数如何实现需要你们根据自己的地图数据 库特征自己开发。其中room_info是送入一个房间编号输出房间信息结构，batch_room_info是输入一个模糊条件返 回一个房间信息结构列表（SQL语言标准条件）。这里首先要说的本机器人公用的房间信息结构如下：
#new $room_desc {id=0|name=""|direct=""|rel_id=""|rel_name=""|desc=""}
其中id是房间号，name是房间名称，direct是本房间的所有方向（其中自定义命令统一变成commands），rel_id是 相邻房间号，rel_name是相邻房间名称，desc是房间描述（不能存在换行，必须进行trim处理去掉空格）。比如取 中央广场的房间信息命令如下：
#show @room_info(5)
结果如下：
direct=“west|east|north|south|up|commands|down|northwest”|id=5|desc=这里是城市的正中心，一个很宽阔的广场，铺着青石地面。一些游手好闲的 人在这里溜溜达达，经常有艺人在这里表演。中央有一棵大榕树，盘根错节，据 传已有千年的树龄，是这座城市的历史见证。树干底部有一个很大的洞(shudong)。你可以看到北边有来自各地的行人来来往往，南面人声鼎沸，一派繁华景象，东 边不时地传来朗朗的读书声，西边则见不到几个行人，一片肃静。|name=中央广场|rel_id=“4|6|10|13|42|350|1371|2527”|rel_name=“西大街|东大街|北大街|南大街|赏月台|树洞内部|销金窟|北侠饺子馆”
batch_room_info函数返回的房间信息结构列表是一个list，里面的元素是房间信息结构。比如取扬州的所有西大街 的命令如下：
#show @batch_room_info("zoneid=1 and objectname='西大街'")
结果如下：
“direct=”“west|east|south|north”“|id=2|desc=你走在西大街上，感到这里的街面要比别处的干净、整洁。南面是红娘庄，常常有一对对男女来往。北边则是飞龙帮的总部。|name=西大街|rel_id=”“1|3|44|48”“|rel_name=”“西门|西大街|红娘庄大门|飞龙帮总部”““|”direct=”“west|east|north|south”“|id=3|desc=你走在西大街上，感到这里的街面要比别处的干净、整洁。大概因为靠近衙门、兵营可受保护的缘故，富人们都喜欢住在这里。东边静悄悄地没有几个行人，西边是西城门通往郊外。南边是一座镖局，北边是一所富丽堂皇的大宅院。|name=西大街|rel_id=”“2|4|49|53”“|rel_name=”“西大街|西大街|财主大门|福威镖局”““|”direct=”“west|east|south|north”“|id=4|desc=这是一条宽阔的青石板街道，向东西两头延伸。西大街是衙门所在，行人稀少，静悄悄的很是冷清。东边是一个热闹的广场。南边是兵营。北边就是衙门了。|name=西大街|rel_id=”“3|5|55|57”“|rel_name=”“西大街|中央广场|兵营大门|衙门大门”“”
获得三个房间的信息：房间号2，3，4三个房间的信息。
1.基础事件
- ×evtLog事件：位置events|baseEvent，主要作用以事件形式记录日志信息。调用事件记录函数@log_info，具体祥见事件记录函数@log_info
- ×onConnect事件：位置events|baseEvent，实现系统事件onConnect，用以自动登录。
2.基础函数
- ×change_list：位置pubFunc|baseFunc，实现功能是列表中两个元素交换位置，有三个输入参数$list,$locate1,$locate2，其中$list为待交换的列表，$locate1为位置1，$locate2为位置2。返回交换完为止的结果列表。举例：@change_list(“1|2|3”,1,2)，返回“2|1|3”
- ×convChtNum：汉字数字计数变成阿拉伯数字计数。举例：@convChtNum(“一千零五十一”)，返回1051
- *del_list_tail：删除列表中某一位置之后的所有元素。输入参数：$list,$max，其中$list为列表，$max是保留的最后一个列表位置，输出删除后的列表。比如：@del_list_tail(“1|2|3”,2)，返回“1|2”
- *getItemFromRecords：从一个record列表中根据某一个key的值来寻找特定的一个record。输入参数$recordlist,$key,$searchvalue，其中$recordlist为record列表，$key为键名称，$searchvalue为键值。返回record。比如：@getItemFromRecords(“id=1|name=武庙”|“id=2|name=客栈”,id,2)，返回结果“id=2|name=客栈”
- *getKeyList：从一个record列表中取出某一个特定键的键值列表。输入参数$dblist,$key,其中$dblist为record列表，$key为键名称。举例：@getKeyList(“id=1|name=武庙”|“id=2|name=客栈”,id)，返回“1|2”
- *log_info：往特定文件中记录日志信息。（其中特定文件位置在本函数中写死了，需要换位置请修改本函数的日志记录目录位置。）输入参数：$message,$mode，其中$message为日志信息，$mode为日志记录模式，其中0表示即打开日志文件又关闭日志文件，1表示仅打开日志文件不关闭日志文件，2表示不打开日志文件仅关闭日志文件。
- *lowerFirst：将特定字符串的首字母转换为小写后返回结果。举例：@lowerFirst(“Kill”)，返回“kill”。
- ×merge_list：更新指定位置的列表元素，如果该位置有元素这替换该元素，如果该位置在最大位置+1，这添加在末尾，如果该位置在最大位置+N，则中间填空元素后填入该元素。输入参数$list,$item,$locate，其中$list为输入列表，$item是待更新的元素，$locate是更新到的位置。举例：@merge_list(“1|2|3”,4,2)，返回“1|4|3”,@merge_list(“1|2|3”,4,4)，返回“1|2|3|4”,@merge_list(“1|2|3”,4,5)，返回“1|2|3| |4”
三、默认参数介绍
主要介绍一下本例子护镖机器人关键的默认参数，这个章节比较枯燥，有需要可以等到实际章节用到这部分内容 再回过头来查阅。大多数默认参数都需要大家根据自己的地图数据库实际情况重新设计，这个参数设定的质量高低也 是游戏稳定的关键，也不要期望于一次性弄完所有参数，慢慢在实际运行中补充吧。
1.护镖路线设定
在quest|hubiao|clPara|variables|defaults|hubiao_pathset目录下，对应于每一种护镖任务都有一个唯一的变 量hbpath_*，其中*指任务简称，变量存放data record列表，每一个record元素的结构如下
zoneid=2,6,32|id=322|name=青石大道|cmd=gne
其中zoneid指的是该房间所处区域和相邻区域，id是指房间号，name是指房间名称，cmd是指实际推车命令，这个命令 在特殊房间可能不一样，比如北京城门就是命令gn-bj，gn-bj是有gan che to north和ask jiang about 进城组合而成。
2.特殊任务地点定义
在quest|hubiao|clPara|variables|defaults目录下，变量名是hbspec_str，主要存放一些特殊迷宫的特别行镖路 线和返回路线，比如黑沼和太湖的树林。这也是一个record列表，里面record元素的结构如下
questid=taoyuan|targetname=黑沼|backcmd="yinggu|#wa 500|yinggub"|pathlist="2120|2119|2118|2117|2116|2115|2114|567|564|563"|pathid=24
其中questid是指属于哪个任务简称的，targetname表示林镇南给的目的地，backcmd是指返回命令，pathlist是指从该任 务默认线路的一个最近地点以后的预设线路，pathid是指该情况下预设的初始路线转折点位置。比如例子的黑沼中24指的 是2120房间号是接@hbset_taoyuan预设路线的第24号位置-房间号583（桃源驿站）。
3.公共任务头信息
在quest|hubiao|clPara|variables|defaults目录下，包括变量hbpath_list，hbstart_list，hbtarget_list， hbtarget_num_list。这个没有转换成record列表，而是由四个字符串列表组成。其中hbpath_list表示任务英文简称，用 它来查找应该选哪条默认线路、是否有特殊房间需要设置特殊线路等等。hbstart_list是林镇南给出的托镖者名称，有这 个来确定本次护镖是哪个任务。hbtarget_list是默认目的地名称列表。hbtarget_num_list是默认目的地房间号列表。
4.过滤房间号列表
在quest|hubiao|clPara|variables|defaults目录下，变量名maze_list，主要用于区域搜索，列表内的房间将不会搜 索，主要包括迷宫、比较危险的房间、被npc拦截的房间。这个需要大家重新设置了，里面仅存房间号。
5.特殊任务返回设置
在quest|hubiao|clPara|variables|defaults目录下，包括变量back_specpathlist，back_specnumlist， back_speccmdlist，分别指的是特殊返回的任务简称列表，特殊返回的返回命令线路起始点列表，特殊返回的返回命令列表。 主要是考虑到向北京，襄阳，洛阳这三个地方返回的时候不能按照原线路返回（因为要坐船），要用丐帮地道返回。通过 back_specpathlist用任务英文简称找到是否需要用该列表设置特殊返回命令，back_specnumlist是指从那个位置开始执行 特殊命令，back_speccmdlist是指执行的特殊命令。比如北京的bjbiaoju（镖局）任务设置的back_specnumlist值是23， 23在bjbiaoju任务里面是指北京的永安门北面的那个正阳门外大街，也就是说你在该正阳门外大街之后的房间返回你要走到 该房间才能执行back_speccmdlist的beijingb命令，如果在23之前返回则要返回到正阳门外大街才会执行beijingb返回。
6.自动买药设置
这个变量是druglist，里面放着最小药品数量，比这个数量小会自动买药。本教程用不到这个东西就不细讲如何实现的。
7.方向设定
包括direct_type，che_direct_type，mirro_direct_type。分别指方向列表，对应的行镖命令列表，对应的反方向列表。 用来作方向转换用。有一个标准函数实现了这个转换，叫做direct_convert，在目录pubFunc|hbFunc下面。这个函数我会在 用到的时候在具体讲解。
四、设计思想
主流的复杂Mud机器人基本上都要涉及到对地图数据库的操作，在这个方面大体有三种思路，第一种思路是什么样的地图 数据库都不使用，这种护镖机器人当然就不会特别好，编写慕容机器人是一点问题没有，编写胡一刀的机器人就根本没有办法， 更高级的任务更不用说了，这方面比较活跃的现在用zgbl的护镖机器人，我的公开版护镖机器人都在这里，还有就是bugbug的 慕容机器人也是典型。【慕容机器人部分用到了遍历，但是没用到地图数据库搜索之类】这种编写方式比较适合非常简单的机 器人，任务模式比较死板的也合适这个模式，但是具体到护镖机器人有一个大问题就是你怎么知道目的地到底是实际上的具体 位置或者乱入以后你怎么知道乱入到哪里去了？这样的问题不依靠数据库都没法回答。第二种模式就是依靠Zmud/Cmud内置的 map函数来处理房间定位之类问题，实际上系统内置的map函数功能非常丰富，包括选择路线，房间定位，模糊选择诸如此类都 能帮助你完成，而且操作性能也非常好，这方面我就不是特别擅长，主流的代表人物有maper，killunix，oolong。不过maper现在转mushclient，估计在mushclient上就没有这个优势了。第三种模式就是不依靠系统自带的函数和地图数据库，使用自己 的地图数据库和自己的地图操作函数，基本上我一直从事这方面的开发，目前函数上还算比较完善，当然和Zmud/Cmud内置的 地图函数那样子功能强大和高性能是不太可能的。另外如果你要啊在Mushclient上开发基本上也要遵循我这个模式来开发。不 过上面提到的人名肯定只有一部分，这里面藏龙卧虎，比我厉害的有的是，有不到的地方请指教。
要做所有工作之前首先要设计地图数据库的表结构。我这里map数据库的表结构如下：
| 字段 | 字段名 | 类型 | 备注 |
| objectid | 房间号 | 数字 | |
| objectname | 房间名称 | 文本 | |
| relateobject | 相邻房间号 | 文本 | 每个房间号之间用|分割 |
| relateobjname | 相邻房间名称 | 文本 | 每个房间名称之间用|分割 |
| direct | 方向 | 文本 | 每个方向之间用|分割 |
| objectdesc | 房间描述 | 文本 | |
| zoneid | 区域号 | 数字 | |
| zonename | 区域名称 | 文本 | |
| spacex× | 空间x轴 | 数字 | |
| spacey× | 空间y轴 | 数字 | |
| spacez× | 空间z轴 | 数字 | |
| spaceu× | 空间u轴 | 数字 |
具体数据库实现上其实可以仁者见仁，智者见智，我这里只是抛砖引玉，你可以用系统提供给你的map函数操作也是一样，和我 的机器人对接上只要把room_info和batch_room_info函数实现了基本上就可以无缝对接。因为除了那两个函数我其他地方不会 操作数据库。这里面标注为×的是我自己的一个设想，问题就是处在我目前的数据库没有空间坐标轴，导致寻找最优路径的时候 效率特别差，设想将relateobject和direct结合起来转换成spacex-u轴就非常完美了，其中x轴是指东西方向，y轴指南北方向， z轴指上下方向，u轴指enter/out方向。有了这个坐标轴就可以很容易的判定两个房间之间的距离以及最优线路选择了。不用像 我目前选择最优路径往往还需要用到递归操作。当然选择Zmud/Cmud的map函数可以省下那些事情，因为他的内置地图数据库本 身就包含了空间信息。
在开发这类使用数据库的复杂Mud机器人的时候最重要的时候是如何更好的利用Map数据库了。我个人心得是核心的操作有 以下几个方面：路线选择，信息查询，位置定位。路线选择是指给定两个点，一个是初始房间号，一个是目标房间号，给出一 条最优的路线来，路线选择还包括另外一层含义是指我给出一条固定线路，给出距离固定线路一定位置的一个房间号，重新制 作出新的最优线路来，这个设想在护镖的时候非常有用，我在下一章讲护镖线路制作的时候会具体讲我怎么实现的。信息查询 是根据你捕捉的模糊信息或者一个房间号查询出符合条件的所有房间的具体信息，这是为进一步精确定位提供信息基础，乱入 的时候往往需要根据模糊信息提供一个大致的范围，然后再根据方向，名称，描述等等信息进一步定位。位置定位根据捕捉的 实际房间名称，房间描述，房间的方向来确定输入的房间信息或者房间信息列表中符合条件的房间号，这是为了能够精确定位 你目前所处的房间位置使用的。其他人使用系统内置的Map函数实际上也要具体实现符合你实际情况的这三类地图操作功能。
五、路线计算
在路线计算中分为两种情况，一种是两点之间的路线，一种是对已有路线的调整，也就是路线和一个点之间的最优选择。 线路计算解决的两个点之间最优线路的问题，推而广之则有一个点对一个点集合的最优线路选择问题。对于两点之间的最优路 线计算一般来说通过Zmud/Cmud的内置map函数是唯一选择，因为你自己开发首先你要建立每个房间的空间坐标，然后通过坐标 计算两点之间的最优路线，这个开发难度我目前至少没有克服。如果护镖的时候比如计算镖局到北京的线路实际上你大可以预 先设计好线路，然后最后3-5个房间你根据实际情况再微调线路就可以，这样子计算量就不会太大，性能上相对好一点。胡一 刀任务实际上是需要大范围遍历，不涉及到线路计算。在我给出的例子样本中实际上路线计算使用的就是预设路线然后再微调 的办法。
下面我把这部分核心代码贴出来仔细讲解一下。核心代码位于quest|hubiao|clQuest下面，触发条件为：
^??林震南说道：「@me把这批红货送到(%x)那里，他已经派了个伙计名叫(%x)到(%x)附近接你，把镖车送到他那里就行了。」
的脚本里面，代码的26-28行：
#va hb_path %item( @hbpath_list, @quest_id)
#va hb_target %item( @hbtarget_num_list, @quest_id)
#riseevent hbInitPath
就是路线计算部分。@quest_id变量通过第12行
#va quest_id %ismember( @owner, @hbstart_list)
计算获得，就是通过触发条件捕捉的%1查询默认参数@hbstart_list获得当前任务是第几号人物，然后查询@hbpath_list获得任 务英文简称，查询@hbtarget_num_list获得默认目的点的房间号。接着就可以调用事件hbInitPath计算当前行镖路线了。
事件hbInitPath位于Events|hbEvent下面，我行镖路线计算的想法是首先通过预设的行镖路线参数获得初始的当前护镖路线 设置，这部分代码就是hbInitPath的第2-18行：
#if @exp<1000000&&@hb_path="shashoubang" {
hbset_runtime=@hbset_pker
} {
#va hbset_runtime @{%concat("hbset_",@hb_path)}
}
hbdesc_runtime=""
hbcmd_runtime=""
hbnum_runtime=""
hbzone_runtime=""
#loop %numitems(@hbset_runtime),1 {
#local $hbset
$hbset=%item(@hbset_runtime,%i)
#va hbdesc_runtime %push($hbset.name,@hbdesc_runtime)
#va hbcmd_runtime %push($hbset.cmd,@hbcmd_runtime)
#va hbnum_runtime %push($hbset.id,@hbnum_runtime)
#va hbzone_runtime %push($hbset.zoneid,@hbzone_runtime)
}
其中第2-6行是指经验小于1M的玩家杀手帮任务的时候护镖走pker命令从西门出去到杀手帮，大于1M的玩家走南门用shashoubang命 令的行镖线路，其他情况下直接用任务英文简称取路线设置然后展开成字符串列表。
接着判定任务给出的目的地是否已设定好的特殊迷宫，如果是特殊迷宫行镖按照设定规则行镖。这部分代码在27-36行：
#loop %numitems(@hbspec_str) {
#local $hbspec_item
#new $hbspec_item {questid=""|targetname=""|backcmd=""|pathlist=""|pathid=0}
$hbspec_item=%item(@hbspec_str,%i)
#if ($hbspec_item.questid=@hb_path&&$hbspec_item.targetname=@target) {
$target_path.pathsno=$hbspec_item.pathid
$target_path.targetpath=$hbspec_item.pathlist
#break
}
}
主要是根据默认参数@hbspec_str的定义来修改路线，这个参数说明在第三章第二节中，刚刚做了一些修改，以前的表述有些问题。 在这里我要说一下路线调整的结构$target_path，这个结构由两个key组成，键pathsno表示从原路径那个位置以后作调整，键 targetpath表示新的路线设置，举个例子：比如最初的行镖线路设置是1|2|3|4|5，现在我设置$target_path为pathsno=3， targetpath=8|9，也就是说从位置3以后要调整为8|9，新路线就是1|2|3|8|9，并且目的地位置是房间号9。这个结构的作用明白 了吧？这里路线设置的时候只需要填充这个结构的含义也清楚了吧？只要这个结构计算出来了后面可以很容易的通过这个结构 导出完整的行镖线路来。
接下来的代码第38-50行就是一般路线计算了。代码如下：
#if $target_path.pathsno=0 {
#local $condition
$c
$condition=%concat("(zoneid in (",%item( @hbzone_runtime, %ismember( @hb_target, @hbnum_runtime)))
$condition=%concat($condition,") ")
#if @hb_path="taoyuan" {
$condition=%concat($condition," or objectid=1676")
}
$condition=%concat($condition,") and objectname='")
$condition=%concat($condition,@target)
$condition=%concat($condition,"'")
$target_path=@find_targetpath(@batch_room_info($condition),@hbnum_runtime,0,-1)
}
$condition的SQL条件含义是指根据林镇南给出的@target任务地点【就是刚才通过“他已经派了个伙计名叫(%x)到(%x)附近接你” 捕捉的变量】在默认目的地定义的区域范围内寻找符合条件的所有房间号(其中加上or objectid=1676是指桃源任务的山路，因 为桃源任务有时候会给出目的地是杀手帮的山路，而杀手帮并不在桃源任务的搜素区域内，所以特别加上以免路线计算出错）。 然后调用函数@find_targetpath就可以获得路线调整结构的数据。我接下来仔细讲解一下函数@find_targetpath，事件 hbInitPath中剩下的部分就不讲了，剩下的没有什么技术含量了。
函数@find_targetpath是最优路线确定，函数位于pubFunc|hbFunc下面，包括4个参数：$targetlist,$pathlist,$level, $targetpath，其中$targetlist是指目的地房间信息列表，$pathlist是初始线路，$level是递归层级，$targetpath是传给下一 个递归层级上一个层级的计算结果。这个函数的思想是我要寻找出$targetlist和$pathlist之间一条最优线路，这条线路首先 是两点之间距离要最短，举例来说$targetlist中能找到就是$pathlist中的元素（也就是0距离）就用0距离的，没有找距离1的 元素，一直推广下去。距离最短的那些元素中和$pathlist链接的位置一定要尽可能靠后。我的想法是尽可能保留初始路线最 大化并且调整要尽可能少的路线就是最优线路。
下面具体讲解一下这个函数的代码，所以代码一开始，在第15-20行：
#va $temppath %additem($target_room.id,$targetpath)
#loop %numitems($pathlist) {
#if %item($pathlist,%j)=$target_room.id {
$pathid=%j
}
}
先把本次房间号保存到结果列表中供最终出结果或者递归到下一个层级使用。然后寻找房间号在初始路线中最靠后的位置，找 到了这个房间号的寻找旅程就结束了。下面根据本次查找结果进行判定，决定是否替换返回结果，是否做递归等等。这段代码 如下在第22-47行：
#SWITCH ($pathid!=0&&$pathid>=$rtn_struct.pathsno) {
#SWITCH ($rtn_struct.pathsno=0) {
$rtn_struct.pathsno=$pathid
$rtn_struct.targetpath=$temppath
}
(%numitems($rtn_struct.targetpath)>%numitems($temppath)) {
$rtn_struct.pathsno=$pathid
$rtn_struct.targetpath=$temppath
} (%numitems($rtn_struct.targetpath)=%numitems($temppath)&&$pathid>$rtn_struct.pathsno) {
$rtn_struct.pathsno=$pathid
$rtn_struct.targetpath=$temppath
}
} ($pathid=0&&$rtn_struct.pathsno!=0&&%numitems($rtn_struct.targetpath)=1) {
} {
#if $level<=3 {
$condition=%concat("objectid in (",%expandlist($target_room.rel_id,","))
$condition=%concat($condition,")")
$batchlist=@batch_room_info($condition)
$tmp_struct=@find_targetpath($batchlist,$pathlist,$level+1,$temppath)
#if $tmp_struct.pathsno>$rtn_struct.pathsno {
$rtn_struct=$tmp_struct
}
#if ($tmp_struct.pathsno=$rtn_struct.pathsno&&%numitems($tmp_struct.targetpath)<%numitems($rtn_struct.targetpath)) {
$rtn_struct=$tmp_struct
}
}
}
首先如果找到结果了，也就是$pathid>0，并且这个位置比结果里面的pathsno靠后或者相等，则进入下一步判定，有 三种情况下会替换原先的返回结果，第一种情况是返回结果为空，第二种情况是返回结果里面的路线房间数比新结果 的房间数大，第三种情况是两者房间数相等但是$pathid比$rtn_struct.pathsno大。switch中第二个条件 ($pathid=0&&$rtn_struct.pathsno!=0&&%numitems($rtn_struct.targetpath)=1)不作处理是指当你没有找到结果， 但是结果列表里面的结果房间数仅有一个，这时候递归没有任何意义（因为递归找到结果也会比房间数1大）。其他情 况下作递归，递归仅作五层递归（0，1，2，3，4）。将该房间的相邻房间作为源与$pathlist作路线计算，得到的结 果更新到返回结果中。
@find_targetpath函数性能不是特别好，主要原因是每次递归前都要调用@batch_room_info查询房间信息，而这个 查询数据库操作由于我使用ADO技术进行数据库操作，性能实在不是特别好，差不多是100毫秒量级的性能，递归有时候 要做上百次或者更多次递归（比如全真的走廊就是一个例子），后来想改用Lua语言存取数据库，但是由于技术上的 原因没有尝试成功。（Lua语言在Cmud上开发实在不熟悉，而且资料也不多）
六、空间定位
空间定位的问题在于当你处于一个未知房间的时候如何能够准确获得当前位置的正确房间信息和空间定位，来方便 下一步操作。这个问题大概在护镖任务中碰到的比较多，其他任务由于对于目标位置信息不足都需要区域级遍历来确定 任务NPC位置，不涉及到对一个模糊信息的空间位置定位上。空间定位在思想上是根据当前房间捕捉的房间名称、方向 和描述信息从数据库中确定出一个符合实际情况的唯一房间号，根据该房间的相邻信息决定下一步的行动。空间定位在 技术上存在四个审定级别，第一个级别是只要房间名称一样就认为找到符合要求的房间，这个要求最低，适合名称唯一 的那类房间，应用面比较狭窄；第二个级别是房间名称一样，并且实际房间的方向在数据库中该房间的方向中存在，这 个级别的限定相对比较实用，适合大多数情况，但是对于比如西大街、青石大道之类大众化的名称就无法精确定位了； 第三个级别是房间名称一样，房间方向一致，并且房间描述一致，这个定位相对精确，但是你要注意到我们前二个级别 中并不要求房间方向一模一样，只要是数据库定义的房间方向的子集就可以了，这是考虑到要兼容一些秘密房间会有一 些自定义命令来链接隐藏方位，比如ct到丐帮地道，华山舍身崖到紫气台之类都是这种情况，但是前两种的认定在一些 房间名称重复程度特别高，方位比较雷同的房间定位上就会出现问题，这就是第三种定位方式出现的原因，这个程度基 本上是技术上认定的终结，我们原则上认为只要名称、方向、描述都一模一样的房间就是一样的房间，但是实际上存在 很多特例，比如被洗劫以后的襄阳西大街基本上都是一模一样的，但是确实存在多个房间，这就是理论上的第四个级别 存在的基础；第四个级别是要求房间名称一样，房间方向一致，房间描述一致，相邻房间名称一致，这个实现的难度在 于相邻房间的名称捕捉上，这个实现起来难度不是特别小，我个人建议碰到这类情况还不如作一些特殊代码比较好，毕 竟情况不会特别，有问题写死代码的工作量比作通用代码简单多了，当然你的理想是作一个通用平台的话就是另外一回 事了。这里有一个应用上的省略就是我处理房间描述比对上一般只比对第一行描述，不对其他行描述进行比对，这一方 面是为了技术实现的简便起见，另外一方面是由于很难保证地图数据库中的房间描述高质量，而且就是这么处理你在捕 捉房间描述的时候也一定不要把空行捕捉进去，否则一样会出问题。（第一行是空行当然怎么比对都是失败的）
具体在护镖任务上由于存在镖车乱入所以会存在你和镖车随机到一个相邻1到N格的未知位置上，这里面定位分为三 个级别：第一个级别是乱入后的房间在预订行镖线路的房间范围内进行定位上，这时候定位基本上按照第二种方式进行 定位就可以了，特殊的路线上有多个房间符合条件就需要用第三种定位方式了；第二个级别是乱入后的房间在原先位置 的邻居房间中定位，这个定位模式按照第二种定位方式就足够了；第三个级别是乱入后的房间在路线定位的相邻区域范 围内进行定位，对于单一结果按照第二种定位方式进行验证，对于多重结果按照第三种定位方式进行严格验证。
下面简单分析一下我的护镖定位代码，入口代码是quest|hubiao|clWalk下面的id为walk_room_check的那个触发， 这部分代码在子触发2下面的第10-36行：
#if @error_path_flag="ERROR" {
#t- hbWalk
#raiseevent hbRoomCheck @locate_desc @locate_directlist @locate_description
} {
room_desc=@room_info(%item( @hbnum_runtime, %eval( @locate_pathid-1)))
$rtn=@compare_room(@room_desc,@locate_desc,@locate_directlist)
#if $rtn=1 {
#if @locate_pathid>@target_pathid {
#raiseevent hbEndWalk @target_pathid
} {
#t- HbFoundFlag
#t- hbWalkEnd
#SECTION SingleThread {
#va error_path_flag START
}
room_desc=@room_info(%item( @hbnum_runtime, @locate_pathid))
#win hubiao Locate:@locate_desc,Next Room:@room_desc.name,Next Pathid:@locate_pathid
#t+ hbWalk
#raiseevent hbWalk %item( @hbcmd_runtime, @locate_pathid) 1
#alarm almWalk {1} {
#raiseevent hbWalk %item( @hbcmd_runtime, @locate_pathid) 1
}
}
} {
#raiseevent hbRoomCheck @locate_desc @locate_directlist @locate_description
}
}
这里主要是判断是否需要进行重新定位，如果有需要调用定位事件hbRoomCheck，首先是只要error_path_flag这个变量 为ERROR的时候关闭行走事件hbWalk，进行重新定位。其他首先取出本地房间的数据库信息（使用函数@room_info，这 个函数是一个接口函数，需要个人自己实现，具体参见第二章的相关内容），然后进行第二种方式的定位认证（使用函 数@compare_room，这个函数在pubFunc|roomFunc下面，主要是验证名称一致性，实际方向是否是设定方向的子集，成 功返回1，失败返回-1）。如果一致的情况下，下一个目标的序号超过了最大序号，则启用护镖结束事件hbEndWalk，这 个事件就不解释了，否则进行下一步行走，如果比对发现不一致，则启用定位事件hbRoomCheck。
接着我们仔细分析一下定位事件hbRoomCheck，这个事件位于Events|hbEvent下面，首先开始进行护镖定位的第一个 级别认证，也就是和预设路线上的房间进行比较来定位。定位代码为第15-51行，如下：
$condition=%concat("objectid in (",%expandlist(@hbnum_runtime,","))
$condition=%concat($condition,") and objectname='")
$condition=%concat($condition,$locate_name)
$condition=%concat($condition,"'")
$batch_room=@batch_room_info($condition)
#loop %numitems($batch_room) {
#local $rtn,$room,$direct
$direct=""
$room=%item($batch_room,%i)
$rtn=0
//存在多个符合条件的结果的情况下用名字，方向和房间描述来定位
#if %numitems($batch_room)>1 {
$rtn=@compare_room2($room,$locate_name,$locate_direct,$locate_desc)
} {
//仅存在一个结果的情况下用名字和方向定位
$rtn=@compare_room($room,$locate_name,$locate_direct)
}
#if $rtn=1 {
$direct=%item( @hbcmd_runtime, %eval( %ismember( $room.id, @hbnum_runtime) +1))
//确定该位置的行镖路线对应的方向在本地所有方向中是否存在
#if %ismember($direct, @che_direct_type)>0 {
#if %ismember( @direct_convert($direct,2), $locate_direct)=0 {
$rtn=-1
}
}
}
#if $rtn=1 {
#if %ismember( $room.id, $detect_roomlist)=0 {
$detect_roomlist=%push( $room.id, $detect_roomlist)
}
}
}
//如果存在多个结果则进行严格判定，过滤由于方向键非严格判定造成的数据冗余
#if %numitems( $detect_roomlist)>1 {
$detect_roomlist=@detect_room2($detect_roomlist,$locate_name,$locate_direct,$locate_desc,2)
#win hubiao 判定结果：$detect_roomlist
}
首先是用@batch_room_info函数取出路线中和所在房间名称一样的房间列表（@batch_room_info函数说明请见第二章）。 对于有多个结果的情况下首先是按照第三种定位方式的一个变种来进行验证，就是方向哪里不判断一致性，还是仅判断 实际方向是数据库中设定方向的子集就可以了，单一结果的按照第二种定位方式判断名称和方向就可以了。比对成功的 情况下查看下一步行镖方向是否在本房间中实际存在（比如小山村的碎石路、全真的石阶、武当的石阶都可能会出现类 似情况），这个问题是由于第二种认证方式对方向处理的局限性造成的，认证成功的将房间号写入成功列表 $detect_roomlist。如果上面认证的结果还有多个，则通过严格的第三种定位进行进一步认证，去除由于上面对方向处 理的局限性造成的数据冗余。（相关的定位基础函数compare_room,compare_room2,detect_room,detect_room2请查询 pubFunc|roomFunc，相对都比较简单，compare*类是处理单个房间的，detect*类是处理多个房间的，*room2类一般是 实现第三种定位方式或者是第三种定位方式的一种变种，×room类函数一般是实现第二种认证方式。）处理的时候对房 间定位进行从宽处理原则，一方面是考虑到秘密房间的因素，另外一方面是出于对数据库质量不过关的忧虑。下面还有 一大段代码是成功找到正确位置后如何根据一个原则挑选并进行行走的问题，这个很多和实际情况无关，纯粹是个人喜 好问题，就不一一细说了。
接下来进行护镖定位的第二个级别认证，就是根据原先位置的邻居房间范围内进行定位，代码在108-117行，如下：
$room=@room_info(%item(@hbnum_runtime, %eval( @locate_pathid-1)))
#loop %numitems( $room.rel_id) {
#if $locate_name=%item( $room.rel_name, %i) {
$rtn=@compare_room2(@room_info(%item($room.rel_id,%i)),$locate_name,$locate_direct,$locate_desc)
#if $rtn=1 {
$direct=%item( $room.direct, %i)
#break
}
}
}
这部分代码就比较简单了，取出所有邻居房间，循环按照第二种定位方式进行，只有有一个定位成功，则认为找到结果 了，循环中断，进行下一步具体行走处理上。
上一种方式定位失败的情况（这种情况会实际发生的，比如青石大道之类实际上有可能乱入的时候重新定位就定位 错了，但是不影响具体行走，只是下一次行走的时候由于预先的位置并不是你实际乱入前的位置，用那个位置的邻居来 定位乱入后的房间当然找不到想要的结果）下我们就是用第三个级别认证，就是根据预先位置所定义的相邻区域范围内 所有跟乱入房间名称一样的所有房间内进行定位，代码在第137-199行（这部分代码有更新，可能和提供的xml稍微有区 别，以文章所列代码为准：
#switch (@locate_pathid>%numitems(@hbzone_runtime)+1) {
$condition=%concat("zoneid in (",%item( @hbzone_runtime, @target_pathid))
} (@locate_pathid=1) {
$condition=%concat("zoneid in (",%item( @hbzone_runtime, @locate_pathid))
} {
$condition=%concat("zoneid in (",%item( @hbzone_runtime, %eval( @locate_pathid-1)))
}
$condition=%concat($condition,") and objectname='")
$condition=%concat($condition,$locate_name)
$condition=%concat($condition,"'")
$batch_room=@batch_room_info($condition)
#loop %numitems($batch_room) {
#local $position,$rel_roomid,$directid
$room=%item($batch_room,%i)
$rtn=0
#if %numitems($batch_room)>1 {
$rtn=@compare_room2($room,$locate_name,$locate_direct,$locate_desc)
} {
$rtn=@compare_room($room,$locate_name,$locate_direct)
}
$directid=0
$rel_roomid=0
//仅选取匹配的候选对象中邻居在行镖路线或者曾经出错位置列表中的进行出错纠正
#if $rtn=1 {
#loop %numitems( $room.rel_id) {
$rel_roomid=%item($room.rel_id,%j)
$position=@room_position(@hbnum_runtime,$rel_roomid,@locate_pathid-1)
#if $position>0 {
$directid=%j
}
}
#if $directid=0 {
#loop %numitems( $room.rel_id) {
$rel_roomid=%item($room.rel_id,%j)
$position=@room_position(@error_locate_list,$rel_roomid,99)
#if $position>0 {
$directid=%j
}
}
}
#if $directid>0 {
$direct_str.direct=%item($room.direct,$directid)
$direct_str.room=$room
#va $directlist %push($direct_str,$directlist)
}
}
}
#if %numitems($directlist)>1 {
#local $t_str,$flag
#loop %numitems($directlist) {
$t_str=%item($directlist,%i)
$room=$t_str.room
$flag=0
#if (%left($room.desc,%min(%len($locate_desc),60))=%left($locate_desc,%min(%len($locate_desc),60))||(@hb_path="xiangyang"&&%regex($locate_desc,"\s*这里遭受蒙古兵的洗劫后，已经惨不忍睹。尸横遍野，往日的景象已经荡然无存....\s*")=1)) {
$direct_str=$t_str
$flag=1
#break
}
}
#if $flag=1 {
$directlist=$direct_str
}
}
首先从预设房间定义的相邻区域内取出和实际房间名称一致的所有记录（使用@batch_room_info函数），和前面的差不多， 对于有多个结果的情况下首先是按照第三种定位方式的一个变种来进行验证，就是方向哪里不判断一致性，还是仅判断实 际方向是数据库中设定方向的子集就可以了，单一结果的按照第二种定位方式判断名称和方向就可以了。验证通过后用函 数@room_position（这个函数取出一个规定房间号列表中取出传入的房间号与最接近传入的位置数值的那个房间号位置， 如果房间号在规定房间号列表中不存在，则输出0，举例比如我们要在1|2|3|4|3|5这个房间号列表中找到3房间号最解近 序号6的位置，那么结果就是5，最接近序号1的位置就是3，找房间号6最接近1的位置返回结果就是0）来验证该房间所有 邻居中是否有存在预设行镖路线上，如果存在将这个结果写入查找结果结构列表$directlist（这个结构下面会详细说明）， 如果不存在会则查询是否有方向通向乱入结果房间列表@error_locate_list，这个列表会在每次乱入验证成功，将要行走 前将该房间号写入这个列表，供多次乱入使用。$directlist是一个列表，里面包含的元素是record结构，该结构定义如下： 键direct表明乱入房间下一步行走的方向，键room存储乱入房间信息。如果$directlist有多个结果则根据房间描述进行 判断，取出符合条件的第一个结果作为实际结果。接下来的代码则是根据前面的结果如何进行行走的问题了，这里就不 细说了。
七、小范围遍历
遍历一般分为两种：一种是限定步数的遍历，这种遍历一般就称为小范围遍历，另外一种遍历就是区域遍历了， 遍历范围限定在一个区域内部。两种遍历各有各的特点，适合不同场合的需要。小范围遍历对性能要求相对较低，遍 历的房间个数一般来说非常有限，在一个优化比较好的小范围遍历算法中大多数情况下2-3个步深范围内10步以内应 该就能定位一个目标，所以小范围遍历一般来说不需要限定选择区域，不需要仔细优化每秒遍历步数以使自己的性能 达到可实用程度，在服务器反应良好的情况下小范围遍历只要你的性能能够达到5步/秒左右基本上足够使用了。区域 遍历由于要遍历一个区域内部的所有房间，一般来说有以下几种办法来操作：一种办法是固定路线遍历，路线自己设 定好，这个办法的缺点是适应性比较差，地图有变化自己要记得修改路线，好处是行走不容易出问题，自己可以随意 设定，躲避危险房间，被封锁的房间，迷宫等都不需要增加代码，第二种办法是用深度优先原则进行遍历，这种遍历 办法行走步数比较多，但是编码比较简单，第三种办法是用广度优先原则进行遍历，这种遍历办法是遍历步数相对较 少，但是比较考验你的算法，对编码要求也很高，行走前或者每次行走要计算最优遍历方向这不是一般的难，至少我 现在没有好的思路干这个活。（主要是目前我的数据库没有空间坐标，也就没有距离概念，所以无法在一个范围内获 得最短路径概念）后两种自动遍历请参考文章：
http://pkuxkx.net/forum/viewthread.php?tid=7823&page=2&fromuid=6748#pid76003
这篇文章对这方面的相关讨论比较深入。遍历最大的挑战是性能问题，那么区域遍历最大的问题就是性能，设想一下 北京城这样子有上百个房间的地图，如果没有好的遍历办法，你搜索步数达到几百步的时候，如果你按照小范围遍历 的性能要求干活，就要2-3分钟才能遍历完一个城市，那样子的性能要求肯定不能满足你的性能要求的。我觉得范围 遍历要性能良好至少要达到10步/秒以上，这方面下一章再具体讨论一下这方面的理论实践。
小范围遍历一般来说初始点比较随意，遍历房间数比较少，所以固定线路来遍历不太现实，广度优先原则来遍历 实在是大材小用，用的比较多的是深度优先原则，也就是你对每个房间的待遍历方向排个顺序，按照这个顺序一个一 个遍历全了就算完成所有遍历。在这里要考虑的问题是环形线路遍历问题。环形线路的处理是这个遍历算法是否有效 的关键点，处理不好会让你的结果不能满足实际需要。比如下面图所示的环形线路：
A--B--C--D |#####|##| E-----F--G
我们的起始点是A，目标在G点，遍历最大步深是3步，这里会有下面几个问题：
第一个问题是有可能从重复遍历，比如A→E→F→C和A→B→C两种到达C的方式，如果不做限定那么C就会被遍历两遍， 当空间更复杂的情况下，重复遍历情况可能更严重，这里面举个例子就是全真那样子的格子型地图里面，作6步深遍 历，不做限定的情况下很多房间将会被重复遍历多遍，效率非常差。为了防止已遍历过的房间被重复遍历就需要有 一个结构存储历史已遍历房间信息。
第二个问题是上一个问题的解决引出了本问题的产生，就是路线选择有问题的情况下导致部分房间没有遍历到，比如 你首先按照A→B→C→F的路径进行遍历，到达F房间已经是3步达到最大步深，F房间就被记录完成所有遍历，这时候 你走A→E方向遍历的时候，发现下一个房间F已经被遍历过不需要重复遍历，就不会被遍历到，而房间G就被舍弃了。 实际上从路线选择上看来达到F房间的路径有以下几条A→E→F、A→B→C→F、A→B→C→D→G→F，从最优选择看来 我们应该选择A→E→F路径，从而刚好能够遍历到G房间获得结果，其他路径都是不好的路径，但是从深度优先原则看 来他是不需要考虑最短路径问题的，那个问题是广度优先原则要考虑的，而且要计算A到F之间的最短路径首先必须有 空间坐标概念，没有这个概念你就无法获得A和F之间的相对方位，只能通过穷举法来获得最优路径，计算量非常大， 有了空间坐标大致就能获得A和F的相对方位和范围内大致的房间范围，计算最优路径选择上就好不少。从这个例子看 来我们从C点要到F点计算一下A到F的最短路径是2步，而从C到F则从A到F就要走3步，不是最优选择，就不走F房间。 在护镖任务中我的小范围遍历分为几个阶段，第一个阶段是先look起始点当地和所有方向，观察是否有目标以及 进一步确认起始点位置。然后再一个方向一个方向的遍历所有房间直到步深达到规定要求再返回。这部分代码比较多， 第一个阶段look部分代码起始点在quest|hubiao|clSearch下面，
触发条件：设定环境变量：action = “伙计搜索阶段一”
和
触发条件：设定环境变量：action = “精确定位当前位置(*)”
下面的代码就是第一阶段的代码。其中 子触发条件：设定环境变量：action = “邻居搜索结束”$ 中的代码：
#SWITCH (@search_step="locate") {
#raiseevent hbDetectLocate @locate_desc @locate_directlist @locate_description
} {
#if %trigger(HbFoundFlag)=0 {
#raiseevent hbDetectNeighbor @locate_desc @locate_directlist
}
}
就是调用具体处理事件的代码，当look本地的时候调用检测本地房间事件hbDetectLocate，其他情况下调用检测邻居 房间事件hbDetectNeighbor。
其中检测本地房间事件hbDetectLocate和检测邻居房间事件hbDetectNeighbor都在类Events|hbEvent下面，这部分 代码中复杂部分在于定位本地房间一开始要重新检查一下当初认定的起始点是否和捕捉的房间实际情况一致，不一致调 整起始点到实际房间上，其他部分代码大概就是按照顺序查看下一个房间，如果是单方向房间则出去再进行第一阶段搜 索一遍，如果是多方向房间这查完所有邻居没有发现伙计接着进入第二阶段按照深度优先原则进行遍历。本地房间定位 的代码在事件hbDetectLocate的第3-21行：
#SECTION SingleThread {
search_target_room=@room_info(%item( @hbnum_runtime, @target_pathid))
}
$batch_room=@batch_room_info(%format("objectid in (%s)",%expandlist( @search_target_room.rel_id,",")))
$room=@detect_room2($batch_room,$locate_name,$locate_direct,$locate_desc,1)
$detect_flag=0
#if @compare_room2(@search_target_room,$locate_name,$locate_direct,$locate_desc)!=1 {
#if $room!="" {
$room=%item($room,1)
$rtn=@path_change($room.id,%item( @search_target_room.direct, %ismember( $room.id, @search_target_room.rel_id)),%item( @hbzone_runtime, @target_pathid))
#SECTION SingleThread {
#va locate_pathid @target_pathid
search_target_room=$room
}
$detect_flag=1
}
} {
$detect_flag=1
}
首先取出预设出发点房间信息放入变量@search_target_room，将该房间相邻房间的房间信息取出放入内部变量$batch_room， 然后将相邻房间信息和实际房间信息用函数@detect_room2进行检核，将符合条件的那个房间存入$room中。接着首先 检核出发点房间信息@search_target_room是否和实际房间信息一致，使用函数@compare_room2按照第三种定位方式的一个变 种进行定位（这里变种是指这里不验证数据库里面方向是否都在实际方向中存在），如果定位不成功则查找$room是否为空， 不为空则认为该房间是实际起始点房间信息，并用@path_change函数修改预设行镖线路到该点。（这个函数在类 pubFunc|hbFunc下面，主要功能是修改预设行镖线路）
如果上面的第一阶段搜索没有找到伙计则进入第二阶段遍历，这个遍历入口是
触发条件：设定环境变量：action = “伙计搜索阶段二”
和
触发条件：设定环境变量：action = “区域遍历：行走开始”
。遍历事件调用的入口代码在 子触发条件：设定环境变量：action = “区域遍历：行走结束” 中，代码如下：
#if %trigger(HbFoundFlag)=0 {
#raiseevent hbLocateSearch @locate_desc @locate_directlist
}
通过这个触发条件调用遍历事件hbLocateSearch。你们可以看出我这里调用遍历和之前look邻居方向的时候都没有设置任何 等待，获取目标中断遍历都是靠触发来控制的，在伙计触发哪里当你发现伙计的时候会打开HbFoundFlag，这样下一步遍历就 不会被触发了，这样只要服务器性能足够好，遍历算法计算效率足够高，基本上一秒钟5步没问题，更高就比较考验Cmud对触 发的反应灵敏度和数据库处理效率了。
在讲遍历事件hbLocateSearch之前先讲讲关于本遍历算法的一些基础函数。这些函数在目录pubFunc|zoneSearch下面。 ×direct_rearrange函数：这个函数功能是根据一个输入方向对房间方向进行优化，该方向上的房间排在最前面，背该方向的 房间排在最后面。
*direct_rearrange2函数：这个函数功能是上一个函数功能的进一步扩大，首先按照输入方向调用@direct_rearrange进行方 向优化，接着根据传入的单一方向房间列表$singleList，对所有在列表内的房间按照次序排列在最前面。这样子的想法是尽 可能的把最短遍历路径的那些房间先遍历了然后再遍历比较长遍历路径的房间。
*zonesearch_back函数：到达遍历边缘返回一步的时候初始化遍历路径记录结构列表，其中该结构定义如下：
#new $trace {id=0|direct=""|name=""|zoneid=0|directid=0}
其中id是下一步房间的房间号，direct是下一步的方位，name是下一步房间的房间名称，zoneid是下一步房间的预设相邻区 域，directid是下一步方向的方向顺序值。
×zonesearch_traceget函数：根据本地房间信息和方向顺序值获得行走下一步的遍历路径记录结构。
×zonesearch_walkcheck函数：方向检核函数，通过检核本地房间的各个方向的合法性获得下一步行走方向的方向顺序值。 这个函数输入参数遍历路径记录结构列表$tracelist，本地邻居房间号列表$locate_relid，本地方向列表$locate_dir， 下一步的遍历步深$trace_deep。首先获得下一步的初始方向顺序值$directsno和上一个房间到达本房间的方向$trace_dir。 这个函数是一个递归调用，当判断不符合条件的方向的时候调用递归函数zonesearch_walkcheck2，这个函数判断和本函数 一样，区别是入口参数传入下一步的初始方向顺序值和上一个房间爱你到达本房间的方向，省略了本函数对这两个值的计算 过程。在下列情况下认为该方向不合法，方向顺序值+1继续递归判断：下一个房间是@maze_list所包含房间，该房间在已遍 历房间号列表@search_trace_step中存在，该房间在遍历路径记录结构列表的房间号列表@search_trace_highroom中存在的， （也就是说是正在遍历的那个路线是不能返回线路之前的房间），该方向是commands标记的隐藏方向，该方向是上一个房间 行走到本房间所在方向。
遍历事件hbLocateSearch的思想是首先取出本地房间信息，并用方向重排函数对该房间的方向进行重排优化，然后判断 这个房间是否和实际信息一致，一致则进行正式的遍历操作，否则停止遍历。接着就简单了，两种情况下回退一步：到达边 界，该房间所有方向都遍历过以后；否则向未遍历方向行走一步。其中第16-21行是方向优化代码：
$position=@room_position(@hbnum_runtime,$room.id,@target_pathid)
#if $position>0 {
$room=@direct_rearrange2($room,@direct_convert(%item(@hbcmd_runtime,$position),2),@search_direct_single)
} {
$room=@direct_rearrange2($room,"",@search_direct_single)
}
这几行代码相对比较简单，原理是如果本地房间在预设路线上按照预设录像对应方向和本区域唯一方向的房间列表结合起来 对该房间的方向进行按照优先级重排，当然如果你有特殊的重排需求，可以这这部分增加根据按照任务特征进行方向重排以 提高遍历的灵活性和命中率，我这里写的方向优化比较少。接下来是一段房间信息比较失败（这里面排除的两个房间2495和 683分别是武门和海边基地【牙山海战任务】，由于这两个房间在任务开放的时候方向会增多，所以信息比较的时候排除这两 个房间）处理代码。
接下来这一段代码就是遍历代码了：
//到达边界的情况下返回一步
#SWITCH (@search_trace_deep>@search_deep) {
search_trace_list=@zonesearch_back(@search_trace_list)
zone_walk @search_trace_backcmd
//未到达边界的情况下路径判断
} (@search_trace_deep<=@search_deep&&%numitems( @search_trace_list)<=@search_trace_deep) {
$directid=@zonesearch_walkcheck(@search_trace_list,$room.rel_id,$room.direct,@search_trace_deep)
//所有方向都已经遍历则返回一步
#if $directid>%numitems( $room.direct) {
#if @search_trace_deep=1 {
set brief 3
#SECTION SingleThread {
#win hubiao 区域搜索：搜索结束未找到目标
}
#mess 护镖任务：区域搜索结束未找到伙计
#abort all
} {
search_trace_list=@zonesearch_back(@search_trace_list)
zone_walk @search_trace_backcmd
}
} {
//对于还存在未行走合法方向的情况下，再走一步
#if %numitems( @search_trace_list)=@search_trace_deep {
#va search_trace_list %delnitem(@search_trace_list,@search_trace_deep)
}
#va search_trace_list %additem(@zonesearch_traceget($room,$directid),@search_trace_list)
#if %ismember($room.id,@search_trace_highroom)=0 {
#va search_trace_highroom %additem($room.id,@search_trace_highroom)
}
zone_walk %item( $room.direct, $directid)
#if %item( $room.rel_id, $directid)=1680 {
#SECTION SingleThread {
#win hubiao 护镖任务：杀手帮万纶台特殊处理
}
ask liang about pk
}
}
}
实际上可以看出来，遍历代码本身还是比较简单的，边界判定是认为当前步数@search_trace_deep大于设定最大步深 @search_deep就调用返回函数@zonesearch_back，并回走一步。当认为存在未遍历合法方向，往下行走一步分为两种 情况，一种是遍历的时候没有回退过，也就是说没有保留回退信息的，（也就是%numitems( @search_trace_list) <@search_trace_deep）将下一步信息加入遍历路径列表中，接着往下走一步就可以了。另外一种是遍历的时候因为 到达边界或者上一个房间遍历完毕了回退回来的，因为要保留本地房间到达回退前房间的方向序号防止重复行走，所 以遍历结构信息里面在下一步信息里面依然保留一个方向序号，这时候走新一步就要删除该结构信息，然后才能加入 下一步的遍历路径结构信息，这就是代码
#if %numitems( @search_trace_list)=@search_trace_deep {
#va search_trace_list %delnitem(@search_trace_list,@search_trace_deep)
}
出现的缘由。至于万纶台处理在本护镖任务中是被躲避了（因为那个台阶行走有busy，非常讨厌，我在行镖线路上动了 小动作，就不需要遍历万纶台了），所以万纶台特殊处理在这里是可有可无的。
八、区域遍历
区域遍历的关键在于性能，一个比较复杂的区域，比如北京城+紫禁城，房间数高达300多个房间，不管采用 Zmud/Cmud提供的Slowwalk功能或者深度优先算法，广度优先算法，A×算法等等进行遍历，通过我实践经验看来如果 都是一步走完确定没有问题再走下一步，中间夹杂下一步的计算，即使步与步之间你没有加任何延时，由于服务器 来回传输的时间加上每步计算的时间，总的时间差不多不会少于200毫秒，这还是假设服务器网络和性能特别完好的 前提下，这就带来一个问题向上面那么多房间，总的遍历步数不会少于500步的行走中，最理想的情况下你要行走 500步/5（步/秒）=100秒才能遍历完一个区域，如果想胡一刀之类任务有时候往往要遍历多个区域，（比如盗宝人 出现在北京，襄阳和少林寺交界区域，胡一刀报盗宝人出现在少林寺，那么你要寻找少林寺，然后找不到还要找襄 阳和北京）这个时间就更漫长了。一个任务总时间一般要控制在5分钟以内，也就是说遍历一次的时间原则上不能 多余一分钟，多余一分钟的遍历就是一个失败的遍历，这就是区域遍历的挑战。
区域遍历中技术不是问题，技术上和小范围遍历没有本质区别，性能上我的想法是采用批量计算的方法，我一 次不是计算出1步，我一次计算出下20步，行走也是一次性行走20步，举例来说比如我遍历扬州，从ct出发开始遍历 ，采用深度优先算法进行遍历路径计算，那遍历算法和以前稍微不一样的就是，小范围遍历的时候碰到步深极限就 停止搜索，区域搜索是传入参数就带区域所有房间，计算步法的时候忽略不在区域内的所有房间，这样子从ct出发 的前20步可能是：
中央广场→西大街→兵营大门→西大街→西大街→福威镖局→正厅→福威镖局→西大街→西大街→红娘庄大门→ 红娘庄走廊→红娘堂→红娘庄走廊→红娘庄大门→西大街→西门→西大街→飞龙帮总部→西大街→西大街→财主大门→…
我们发出的命令应该如下：
set action 遍历开始;weat;south;north;west;south;south;north;north;west;south;east;east;west;west; north;west;east;north;south;east;north;set action 遍历结束
一次性发出这样子的22个命令，验证触发如下：
#trigger {设定环境变量：action = "遍历开始"} {...}
#cond {(*)-%s$} {...} {LoopLines|Param=20}
#cond {设定环境变量：action = "遍历结束"} {...}
比如你要查找盗宝人，可以增加一个触发
#trigger {盗*宝*人*「*」(%x)~(@dbr_hid~)} {...}
根据触发盗宝人的时候到达的房间名称和行走步数来获得在哪一步碰到盗宝人，然后可以在行走结束的时候计算返回 多少步回到盗宝人所在房间。
我的区域遍历想法就是这个想法，至少按照这个想法来说每秒钟发出一批20步的指令，对于大多数情况在30秒 内能够确认目标，基本上能够适应区域遍历对性能的需求。
九、自动返回
如果你用Zmud/Cmud的自动遍历那么发现目标以后返回是很简单的时候，根据记录的行走痕迹走反方向就能回到出 发点，返回大体上是这个思路，你自己实现遍历算法，只要每次遍历的时候把行走痕迹记录下来返回就不会特别复杂。 具体到护镖任务返回上有几个特殊的地方：第一，行镖线路有渡河的护镖就不能按照正常行镖线路返回，你可以用轻 功或者按照我的返回想法用丐帮暗道返回，第二，迷宫内行镖达到目标以后不能按照行走线路反方向返回，就必须按 照预设的返回线路返回。我的小范围遍历返回在quest|hubiao|clSearch下面的触发：
^%s「店铺伙计」(%x)~(
中，其他涉及返回的代码如下：
#loop @search_trace_deep {
#local $rtn,$trace
$trace=%item(@search_trace_list,%i)
#SECTION SingleThread {
#va search_trace_backcmd %push( @direct_convert($trace.direct,1), @search_trace_backcmd)
}
$rtn=@path_change($trace.id,$trace.direct,$trace.zoneid)
}
代码含义是根据小范围遍历行走记录的搜索记录痕迹变量@search_trace_list，取每次行走的方向反方向（使用路径 转换函数@direct_convert）后压入返回命令列表，就完成了返回命令的获得。
找到伙计以后返回到林镇南哪里就相对比较复杂，这个返回命令收集在pubFunc|hbFunc下面的函数@create_backcmd。 这个命令才用%push压入列表，所以最后执行的命令最先压入。特殊的第一段在15-26行：
#loop %numitems(@hbspec_str) {
#local $hbspec_item
#new $hbspec_item {questid=""|targetname=""|backcmd=""|pathlist=""|pathid=0}
$hbspec_item=%item(@hbspec_str,%i)
#if ($hbspec_item.questid=@hb_path&&$hbspec_item.targetname=@target) {
#loop %numitems($hbspec_item.backcmd),1 {
#va $backlist %push( %item($hbspec_item.backcmd,%j), $backlist)
}
$specflag=1
#break
}
}
这一段含义是如果是特殊地点（一般就是迷宫）中，返回按照@hbspec_str设定的返回线路返回。接下来一段代码是处理 想北京，襄阳，洛阳那样需要渡河的路线情况。代码在27-73行：
#if $specflag=0 {
$specflag=%ismember( @hb_path, @back_specpathlist)
#if @hb_path="shashoubang"&&$pathid<25 {
$specflag=0
}
#if $specflag>=1 {
#if $pathid<%item( @back_specnumlist, $specflag) {
#switch ($pathid>%ismember("wait",@hbcmd_runtime)) {
$pathid=%eval( %item( @back_specnumlist, $specflag)-$pathid)
#va $backlist %push( %item( @back_speccmdlist, $specflag), $backlist)
#loop $pathid {
$speccmd=%item( @hbcmd_runtime, %item( @back_specnumlist, $specflag)-%i+1)
#if $speccmd="gn-bj" {
#va $backlist %push("north",$backlist)
} {
#va $backlist %push( @direct_convert($speccmd,2), $backlist)
}
}
} ($pathid<=%ismember("yb",@hbcmd_runtime)) {
#va $backlist %push( "east", $backlist)
#va $backlist %push( "east", $backlist)
#va $backlist %push( "north", $backlist)
#va $backlist %push( "north", $backlist)
#loop $pathid {
$speccmd=%item( @hbcmd_runtime, %i)
#if @direct_convert($speccmd,3)!="" {
#va $backlist %push( @direct_convert($speccmd,3), $backlist)
}
#if %mod( %i, 5)=0 {#va $backlist %push( "#wa 500", $backlist)}
}
} {
#va error_back_cmd ""
#va $backlist "#mess 在船上！请用小号解救"
}
} {
$pathid=%eval( $pathid-%item( @back_specnumlist, $specflag))
#va $backlist %push( %item( @back_speccmdlist, $specflag), $backlist)
#loop $pathid {
$speccmd=%item( @hbcmd_runtime, %item( @back_specnumlist, $specflag)+%i)
#if $speccmd="gn-bj" {
#va $backlist %push("south",$backlist)
} {
#va $backlist %push( @direct_convert($speccmd,3), $backlist)
}
}
}
}
开始的时候有一个杀手帮的特殊处理，当杀手帮走到杀手帮广场附近的时候用pkerb命令仿照渡河的情况返回，否则 按照行镖过来的线路反方向返回。返回命令执行分两种情况，第一种是当到达目的地的位置在返回定义返回点之前， 则要根据行镖线路走到返回点，然后执行返回点返回到扬州的特殊命令，第二种但到达目的地的位置在返回定义返回 点之后，这要根据行镖线路反方向走回到返回点，然后才执行返回点返回到扬州的特殊命令。第一种情况又分三种情 况，第一种情况是返回起始点在渡完河之后，也就是wait命令之后，wait命令是渡船上执行的特殊命令，按照上述情 况走到返回点，执行预先定义的特殊命令返回，第二种情况是返回起始点在渡完河之前，也就是yell boat（简写yb） 之前，按照普通返回执行，第三种情况是返回起始点在船上，那就没解了，呼叫小号yell boat救你出来吧。其他线路 按照行镖线路正常返回去就可以了，如果晕倒返回的情况下有乱入返回命令在最后乱入返回就可以了。
十、篇后语
写到第九章算是整个指引都写完了，虽然我示例是用护镖任务来做示例的，但是基本上所有复杂机器人所需的技 术80%都齐了，剩下的20%的就是下一步工作的重心了。其实在本篇的讨论中我有所涉及到，不过还没有形成非常完善 的思路，限于技术原因，目前版本的最大问题在于无法计算相对遥远的两点之间的路径和两点之间的最短步数，这两 个技术实际上最大问题是按照现有的深度优先原则或者广度优先原则来设计算法，都没有一个非常好的算法来快速计 算，我的初步想法是先建立一个空间坐标体系，然后用A×算法或者变种A×算法来优化算法。按照这个初步想法来说， 数据库的基础架构需要做一定程度调整，新的数据库应该包括如下表：
房间信息表（字段：房间号（唯一索引）、房间名称、方向、邻居房间号、邻居房间名称、房间描述、区域ID、 区域名称、X轴坐标、Y轴坐标、Z轴坐标、U轴坐标、相对距离、房间标志（C-区域中心房间，N-普通房间， F-受约束房间）、特殊行走命令）
解释：其中XYZU四维坐标轴分别表示东西方向，南北方向，上下方向，里外方向；相对距离是指区域内其他房间相对 区域中心房间的步数；房间标志中受约束房间是指不达到特殊条件不能进入的房间；特殊行走命令是指方向中commands 来替换的隐藏方向对应的命令。
区域信息表（字段：区域ID，区域名称，方向，邻居区域ID，邻居区域名称，相邻区域交接房间号，X坐标，Y坐标， U坐标）
解释：区域关系中不需要上下关系，所有只有XYU三轴，U轴表示该区域是否在另外一个区域里面。相邻区域交接房间号 是指该区域内与邻居区域交界的那个房间，比如扬州区域和星宿区域交接的就是西门，而星宿和扬州交界的就是大道； 方向是一个区域和另外一个区域的相对方位，是在另外一个区域的北面，南面还是里面，外面。
有了上面两个表以后我的想法就是我计算任意两点之间的路线，第一步判断两点是否在一个区域内？是，直接用 坐标和相对距离用A×算法进行计算路线，不是一个区域内，先计算两个区域之间的区域路线，（就用区域信息表按照 A×算法进行计算，实际上算法上和两个房间之间的算法没有区别）然后计算起点到区域交界点的路线，区域交界点到 下一个区域交界点的路线，一直到区域交界点到目的点的路线，计算n次的结果拼接在一起就是一条完整的线路。两 点之间的最短步数其实是上一个计算路线结果统一一下一共走了多少步就能获得结果，所以实际上是一个问题。
当然上面的计算有很多技术问题有待于解决，比如选择线路的时候如何根据受约束房间标志来躲避一条不可行的 线路，优先选择最可行的线路。或者说选择区域连接的时候怎么选择区域连接路径会有利于你的行走。当然解决了所 有这些问题以后你用他来作胡一刀任务的机器人或者task任务的机器人都是非常简单的，胡一刀任务你可以先区域遍 历，如果遍历失败则找vast或者用pp来锁定位置，计算两点之间的线路，达到目标，只要你地图设计的准确性有保证， 不管是迷宫或者隐藏房间都可以自动到达。（当然向梅庄或者少林监狱之类地方就是另外一回事情了，这些房间都属 于受约束房间，或者要特殊判断，或者需要用小号探路，然后手工到达的）
我的计划是在今年夏天之前完成所有这些工作，最近的工作是对已有成果进行性能优化，至少要提高2倍以上，目 前区域搜索性能优化已经完成一个阶段，提高2倍应该没问题，5倍不能保证了，以前每步之间计算量太大，最多 1-2步/秒的搜索速度，还好是小范围遍历，影响不是特别大，修改措施主要是将数据库搜索修改为Record列表（或者 Record嵌套结构）搜索，性能翻倍是起码的（可见ADO数据库连接性能有多差啊），接着就是补全数据库，然后尝试 编写一些标准的A×算法函数，今年夏天如果有好的成果的话再分享吧。
附录
空间集合与空间集合之间最优路径选择
主要场景来源于护镖机器人，一开始的时候林震南给出的伙计位置和预设路径之间最优路径选择。由于伙计位置常常会有10多个重复名字的房间，而预设路径一般来说我的护镖路线是固定死的， 想法就是找离护镖路线最近并且最靠路线后面位置的房间。下面是一个cmud 237开发的递归路线 寻找算法。是一个xml文件。我预设是最大递归层级为4级，大于四级就是寻找失败。
其中$targetlist为林镇南给的信息后找到的房间集合，是一个list，list元素是房间信息的db record， key分别是direct-方向，id-房间号，name-房间名称，relationid-邻居房间号，relationname-邻居房间名称 $pathlist是预设护镖路线的房间号list
$level是递归到多少层级，初始为0
$targetpath是上一层递归找到的路径房间号list
最终返还结果$rtn_struct是一个db record，pathsno为在行镖路线上定位位置，targetpath为从目的地到行镖 指定房间号的list
函数@batch_room_info($condition)为取出指定条件的房间信息集合。一个对地图数据库搜集信息的函数。 实际上你用cmud自带的地图函数一样可以加工出这个返回结构，我使用ado对象对access数据库处理获得的。
<func name="find_targetpath">
<value><![CDATA[//入口参数$targetlist为待确定与设定路线$pathlist关系的目标房间集合，$level为递归层级，$targetpath为目的地到指定地点前路径
#local $target_room,$pathid,$condition,$batchlist,$rtn_struct,$temppath,$tmp_struct
$target_room=""
$c
$rtn_struct=""
$tmp_struct=""
$batchlist=""
$pathid=0
#if ($level=0&&$targetpath=-1) {$targetpath=""}
#addkey $rtn_struct {pathsno=0|targetpath=""}
#new $tmp_struct $rtn_struct
#loop %numitems($targetlist) {
$target_room=%item($targetlist,%i)
#va $temppath %additem($target_room.id,$targetpath)
#loop %numitems($pathlist) {
#if %item($pathlist,%j)=$target_room.id {
$pathid=%j
}
}
--此处为上一步从预设路线成功定位并且这个位置比上一个成功结果更靠后就用这个结果
#if ($pathid!=0&&$pathid>=$rtn_struct.pathsno) {
#if $pathid=$rtn_struct.pathsno {
--当两次结果位置相同，但是本次计算路径更短用本次计算路径
#if %numitems($rtn_struct.targetpath)>%numitems($temppath) {
$rtn_struct.pathsno=$pathid
$rtn_struct.targetpath=$temppath
}
} {
$rtn_struct.pathsno=$pathid
$rtn_struct.targetpath=$temppath
}
} {
#if $level<=4 {
--路径确定失败，用本房间的邻居继续进行下一个递归层级寻找
$condition=%concat("objectid in (",%expandlist($target_room.rel_id,","))
$condition=%concat($condition,")")
$batchlist=@batch_room_info($condition)
$tmp_struct=@find_targetpath($batchlist,$pathlist,$level+1,$temppath)
--递归找到的结果比上一个结果更靠后用本次结果
#if $tmp_struct.pathsno>$rtn_struct.pathsno {
$rtn_struct=$tmp_struct
}
--递归找到的结果和上一个结果同位置，但是递归结果路径更短用本次结果
#if ($tmp_struct.pathsno=$rtn_struct.pathsno&&%numitems($tmp_struct.targetpath)<%numitems($rtn_struct.targetpath)) {
$rtn_struct=$tmp_struct
}
}
}
}
#return $rtn_struct]]></value>
<arglist>$targetlist,$pathlist,$level,$targetpath</arglist>
</func>
护镖：数据库版乱入算法
在之前首先感谢Maper提供了地名验证相关的算法，oolong提高721乱码处理的一些想法，Killunix提供了PKUXKX的地图数据库和地图转换的一些想法，本算法地图数据库来源于721自动生成的Map数据库加工而成，加工方法是通过Oracle的统计函数将邻居的竖列变成了Zmud 721的横列列表形式，方便 将邻居使用Zmud 721的列表进行直接处理。本算法仅在测试环境进行功能测试，未做过完整任务，使用请谨慎。另外本算法用到了ADO，所以如果Zmud 721不支持Com的话，请安装Windows相关插件，具体安装办法请查找Zmud帮助
本人想法就是首先每次行走的时候都要验证地名和预定义的路线当前位置地名是否一致，如果不一致则进行重定位，第二种情况是只要乱入发生直接进 行位置重定位。
可以通过本脚本对我之前发布的机器人进行升级，不过加工后的地图数据库，默认参数中的路线的ID定义hbnum_*，路线中地点的区域定义hbzone_*
需要自己根据自己的地图数据库添加，附件提供演示的加工后的地图数据库模板和通过ORACLE加工的加工语句:
select objectid,objectname,substr(relateobject,2,length(relateobject)-1) relateobject,objectdesc,zoneid,zonename
from (
select objectid, max(objectname) objectname,max(sys_connect_by_path(relateobjectid, '|')) relateobject,
max(objectdesc) objectdesc,max(zoneid) zoneid,max(zonename) zonename
from (select objectid, objectname,relateobjectid, objectdesc,zoneid,zonename,row_number() over(PARTITION BY objectid ORDER BY relateobjectid) l_robj
from world_map)
start with l_robj=1
connect by objectid = prior objectid and prior l_robj+1 = l_robj
group by objectid)
order by objectid
下面就是核心的重定位脚本：
- 本批处理为行走出错重定位批处理，不管何种情况出错首先遍历整个任务路线地点和当前地点匹配，只要地名匹配成功并且方向匹配成功的
- 情况下距离当前出错位置最近的一个地点为本任务正确地点，如果遍历任务路线未找到的情况，接下来根据乱入和非乱入有两种算法，如果
- 是非乱入走到非路线定义地点则根据当前任务地点的邻居和本地地点匹配，只要地名匹配上则取反方向路径返回主线路，如果是乱入走到非
- 路线定义地点则根据当地地点的邻居寻找在主线路上或者上一个乱入地点的匹配值，匹配上则返回到正确线路上（如果是二次乱入则下一次
- 由于标志重置成REDIR-重定位不能使用乱入模式进行定位，这方面算法需要测试）
#if @error_path_flag!="ERROR" {#sa 护镖任务：发现位置错误，正确位置：@locate_vdesc与目前位置：@locate_desc不一致，请等待重定位}
#va loopb ""
#va MapRset %comcreate( "ADODB.Recordset")
#loop %numitems( @hbnum_runtime) {#if %i=1 {#va MapQuery %concat( "select objectname,direct,objectid from objectrelation where objectid in (", %item( @hbnum_runtime, %i))} {#va MapQuery %concat( %concat( @MapQuery, ","), %item( @hbnum_runtime, %i))}}
#va MapQuery %concat( @MapQuery, ")")
#CALL @MapRset.Open(@MapQuery,@MapConnStr,2)
#CALL @MapRset.MoveFirst
#WHILE (not @MapRset.eof) {
#if @MapRset.fields(0).value=%t1 {
#va locate_vdesc @MapRset.fields(1).value
#va loopa 0
#loop %numitems( @locate_directlist) {#if %ismember( %item( @locate_directlist, %i), @locate_vdesc)=0 {#va loopa 1}}
#if @loopa=0 {#va loopb %push( @MapRset.fields(2).value, @loopb)}
}
#CALL @MapRset.MoveNext
}
#call @MapRset.close
#va MapRset ""
#show @loopb
#if %numitems( @loopb)>=1 {
#if %numitems( @loopb)>1 {
#va loopa 0
#va loopc 0
#loop %numitems( @loopb) {
#if @loopa=0 {
#va loopa %abs( %ismember( %item( @loopb, %i), @hbnum_runtime)-@locate_pathid+1)
#va loopc %item( @loopb, %i)
} {
#if %abs( %ismember( %item( @loopb, %i), @hbnum_runtime)-@locate_pathid+1)<@loopa {
#va loopa %abs( %ismember( %item( @loopb, %i), @hbnum_runtime)-@locate_pathid+1)
#va loopc %item( @loopb, %i)
}
}
}
#va loopb @loopc
}
#va locate_pathid %eval( %ismember( @loopb, @hbnum_runtime) +1)
#sa 护镖任务：重定位成功
%item( @hbcmd_runtime, @locate_pathid)
#alarm check_locate {+2} {#sa 护镖任务：位置检查}
} {
#if @error_path_flag="ERROR" {
#va error_locate_buf ""
#va MapQuery %concat( %concat( "select objectname,objectid,relateobject,direct from objectrelation where zoneid in (", %item( @hbzone_runtime, %eval( @locate_pathid-1))), ")")
#va MapRset %comcreate( "ADODB.Recordset")
#CALL @MapRset.Open(@MapQuery,@MapConnStr,2)
#CALL @MapRset.MoveFirst
#va loopb ""
#WHILE (not @MapRset.eof) {
#if (@MapRset.Fields(0).value=%t1 and %abs( %len( @MapRset.Fields(0).value)-%len( %t1))<=1) {
#va loopa 0
#va loopc %numitems( @loopb)
#loop %numitems( @locate_directlist) {#if %ismember( %item( @locate_directlist, %i), @MapRset.Fields(3).value)=0 {#va loopa 1}}
#if @loopa=0 {
#loop %numitems( @MapRset.Fields(2).value) {#if %ismember( %item( @MapRset.Fields(2).value, %i), @hbnum_runtime)>0 {#va loopb %push( %item( @MapRset.Fields(3).value, %i), @loopb)}}
#if @loopb="" {#loop %numitems( @MapRset.Fields(2).value) {#if %ismember( %item( @MapRset.Fields(2).value, %i), @error_locate_list)>0 {#va loopb %push( %item( @MapRset.Fields(3).value, %i), @loopb)}}}
#if %numitems( @loopb)>@loopc {#va error_locate_buf %push( @MapRset.Fields(1).value, @error_locate_buf)}
}
}
#Call @MapRset.MoveNext
}
#Call @MapRset.close
#va MapRset ""
#if %numitems( @loopb)>=1 {
#exec gan che to %item( @loopb, 1)
#va error_locate_list %push( %item( @error_locate_buf, 1), @error_locate_list)
#if %numitems( @error_locate_buf)>1 {#echo 护镖任务：乱入返回路线识别可能有问题！查到多个地点符合要求}
#sa 护镖任务：乱入返回主线路
#va error_path_flag REDIR
}
} {
#va MapQuery %concat( "select relateobject,direct,relateobjname from objectrelation where objectid=", %item( @hbnum_runtime, %eval( @locate_pathid-1)))
#va MapRset %comcreate( "ADODB.Recordset")
#CALL @MapRset.Open(@MapQuery,@MapConnStr,2)
#CALL @MapRset.MoveFirst
#va locate_vdesc @MapRset.fields(0).value
#va loopb ""
#loop %numitems( @locate_vdesc) {#if %t1=%item( @MapRset.fields(2).value, %i) {#va loopb %push( %item( @MapRset.fields(1).value, %i), @loopb)}}
#sus check_locate
#if %numitems( @loopb)>=1 {
#exec gan che to %item( @mirror_direct_type, %ismember( %item( @loopb, 1), @direct_type))
#sa 护镖任务：返回主线路
} {
#sa 护镖任务：路线识别出错，请手工回到主线路然后重启机器人
#va error_path_flag ERROR
}
#call @MapRset.close
#va MapRset ""
}
}
算法相关的一些变量定义：
#CLASS {任务|护镖任务|公共变量|系统变量|运行参数}
#ALIAS hb_next {#t+ 行走;%item( @hbcmd_runtime, @locate_pathid)}
#VAR quest_minute {1162}
#VAR quest_num {13}
#VAR hb_path {yuewangmu}
#VAR owner {岳王墓墓前广场包打听}
#VAR target {墓前广场}
#VAR huoji {龚冕扈}
#VAR quest_id {19}
#VAR hb_target {墓前广场}
#VAR target_pathid {20}
#VAR hbdesc_runtime {福威镖局|西大街|西大街|中央广场|东大街|东大街|东大街|东门|大驿道|大驿道|山路|山路|嘉兴城|嘉兴南门|山路|小道|小道|墓前小道|墓前小道|墓前广场|岳 飞 墓|墓边小道|墓后U地}
#VAR hbcmd_runtime {gn|gn|ge|ge|ge|ge|ge|ge|ge|ge|gse|gs|ge|gs|gs|ge|gn|ge|gne|gn|gn|gnw|gne}
#VAR hbdesc_nums {23}
#VAR locate_pathid {6}
#VAR locate_desc {【闲聊】小希(Littlexi)：刚发现是芸豆-}
#VAR locate_directlist {up|west}
#VAR error_path_flag {REDIR}
#VAR error_pathid {3}
#VAR locate_start_pathid {9}
#VAR loopa {4}
#VAR loopb {}
#VAR loopc {6}
#VAR check_directlist {east|northwest}
#VAR MapConnStr {Provider=Microsoft.Jet.OLEDB.4.0;Data Source=pkuxkx/WorldMap.mdb}
#VAR MapRset {}
#VAR MapQuery {select relateobject,direct,relateobjname from objectrelation where objectid=6}
#VAR hbnum_runtime {53|3|4|5|6|7|8|9|769|768|651|652|653|654|691|692|693|694|695|696|697|698|699}
#VAR locate_vdesc {5|7|70|71|72}
#VAR hbzone_runtime {1|1|1|1|1|1|1|1,10|1,10,52|10|10,16|10,18|10,18|18|18,19,22|18,19|19|19|19|19|19|19|19}
#VAR error_locate_buf {}
#VAR error_locate_list {}
#CLASS 0
原帖地址及附件下载：护镖：数据库版乱入算法
后续讨论
- Seagate：其实我觉得推车这个任务肯定没法纯手工玩的，一定程度的自动化是必须的，这个不是说和大潮流抗拒。我做的工作并不是说为了让大家实现全自动机器人，这个靠这里肯定没办法实现。只是至少提高大家的自动化程度，比如从原先1-2分钟就要操作一次或者说每分钟要操作很多次达到10分钟，30分钟操作一次。推车这个任务相对比较固定，而且操作命令太多了。不像胡一刀和萧峰几分钟内只要杀几个npc就够了，不像task对机器人要求那么高。一次任务推30步你要自己纯手工肯定没有几个新人会玩护镖任务。至少通过本教程能让大家推车基本上走路不用自己操作，交接镖这块自己要操作操作。至少让指令数和其他任务基本上持平。
而且我觉得mud游戏本身肯定要实现一定程度的自动化操作，不提倡全自动，并不表示说不能有机器人存在，没有机器人全都纯手工玩我相信谁都知道这不太现实。通过本教程我觉得如果让有些人能够实现一定程度的自动化推车，对高效遍历机器人有一定思路，从而为实现一定程度的dbr机器人和task机器人提供思路就算达到我的目的了。（本人没有做过dbr机器人和task机器人，这两个机器人不是技术上特别难，而且任务太灵活了，机器人编写需要太多测试功夫，dbr操作上频度不太高，5分钟内找到5个盗宝人就够了，没有机器人不会太麻烦。task实在需要花太多功夫对路径进行设计，本人也不热衷于做task任务）
我觉得很多人有东西自己偷摸用实在没有必要。就像糖果的机器人从现在角度看来我不认为比我的机器人高级哪里去，想那样子的机器人公布出去从影响上看来也不会有什么大不了的。只要你保护好自己的地图数据库问题不会太大。从我的感受看来一个机器人最关键的部分往往是你的地图数据库的质量高低。我的机器人从去年开始写，到现在出问题50%都是处在地图数据库质量太差上。不说了，有人觉得自己的东西特别好捂着不放我反正觉得好东西要大家共享，只要在提高游戏体验和系统活跃度之间取得平衡就可以了。最关键的想我们这些上班族如果没有这种机器人在上班的时候根本没有时间上游戏！这种事情往往是冲突的。
- Lzkd：趁seagate老师还没开讲之前,先提点小要求.
第五章应该是讲遍历吧.
希望seagate讲一下当地图数据库完整的情况下,如果进行小范围遍历(比如说,指定某点的5步之内)和大范围遍范(比如说整个苏州,整个神龙岛)的思路,只要思路就可以,具体代码不需要,先谢谢了.
- Seagate：实际上遍历的要求是效率，如果不需要效率那么问题的解决就非常简单了，要求效率的情况下问题就复杂了。
我的小范围遍历算法的思路是从出发点开始先找一个方向走下去，一直走到规定步数，然后返回走第二个方向，一直把所有方向走完就完成整个遍历了。这里面有几个问题要解决的是：方向优化提高遍历效率，抛弃无法遍历的房间，环形路径遍历去重，环形路径遍历优化（这个没有解决，原因是目前我自己的数据库缺少空间坐标信息，等第二版的复杂Mud编写指引应该会引入空间方面的操作，时间在1-3个月之后吧，目前我在开发数据库过程中，数据库开发完了才会着手编写代码，写标准函数，然后开发机器人）。
简单说一下环形路径优化遇到的麻烦,比如下面的一个A-B-C-D-E-A环：
E--D--C | | A-----B-F
小范围遍历的步深是4步，出发点是A，如果A点遍历第一步是B那么A→B→F，F遍历到了，如果A遍历第一步 是E，那么A→E→D→C→B就达到四步的极限了，F房间就遍历不到了。（原则是完整遍历过的房间不重复遍历《解决环形路径重复遍历问题》，遍历到达规定步深返回）。如果你想要的目标在F房间遍历实际上就是失败的。这个就是需要优化的问题，实际上遍历的时候比如到达D房间你要往C房间遍历的时候你发现A从E到达C要3步，A从B到达C只有2步，不应该从D房间遍历到C，从E出发的遍历到达D房间就应该终止。但是这个问题非常不好解决，不好解决的关键是计算A到达C的最优步数如果没有空间坐标支持效率非常差，因为没有坐标你不知道A和C之间的相对位置，所以只能全区域查找，实际上为了效率问题就把这条路给封死了。
大范围遍历实际上和小范围遍历在实际处理没有本质的不同，同样都是从一个点出发走遍所有房间，只是大范围遍历有几个限制，第一个限制是必须限制区域，第二个限制是区域内起始点是固定的【不固定起始点问题也不大，但是那是给自己找麻烦】。大范围区域遍历需要走的步数太多了，效率的要求比小范围遍历要求更高。我的想法是你不要像小范围遍历那样每走一步计算下一步，比如先计算出下20步，一次性走完，走完再判断已走的房间中有没有自己需要的，有需要的返回到目标房间，没有找到在计算出下20步。这样子基本上能达到20步/秒的性能，而小范围区域搜索在服务器性能良好的情况下也达不到10步/秒，一般来说5步/秒是极限性能。
- Sauron：如果你有各个房间的连通数据，遍历某个房间N步以内的所有房间这个简单，如果没有房间连同数据就比较麻烦了，因为牵扯到一些房间绕圈连接的情况。
- Seagate：房间连通数据肯定有，但是没有距离数据，所以环形选择好解决，但是环形路线要达到最优遍历比较困难，这个版本解决不了，等我写完这个版本开发下一个带距离计算的版本就可以计算最优环线线路遍历。
- Sauron：使用A算法获取房间之间的路径其每个房间相连的g值都可以视为1，所以区域遍历应该是先把指定深度的所有房间寻找出来，然后再遍历，如果在创建地图数据库的时候房间索引如果按一个合理的顺序记录，那会更省时间。
- Seagate：关键是A算法不好弄，评估值就不容易获得，没有特别好的想法做最优路径，我一直想法是是不是可以在一定范围内通过预设一些设定来简化获得路径的处理过程，否则不管什么算法一大顿循环递归之类总是跑不了。最大的问题就是在zmud之类脚本语言环境里面循环处理效率就是大问题，长路径的两个房间计算不做一些简化处理起来如果涉及全地图近3000个房间，肯定会完蛋。首先是区域划分要弄好，这一点疑议应该不大，第二点是做好坐标体系，我想法是建立四维坐标，分别对应南北，东西，上下，里外，刚才想法还有第三点设定每个区域的几何中心，计算每个房间和几何中心之间的相对距离，一次性计算完毕，通过坐标和两个房间与几何中心的相对距离来相对评估这两个房间的评估距离，然后用这个评估距离和坐标相对关系进行距离刷选。具体的东西我对A算法就没弄明白，一切都需要摸索。
- Sauron：
--假设房间数据如下
--[[
后院
|
西厅----衙门正厅----东厅 北门
| |
白莲寺 丽春院 衙门大门 城隍庙---北大街---小酒馆
| | | |
瘦西湖酒楼 小金山 明玉坊 | 天阁斋----北大街---扬州客栈---客栈偏厅
| | | | |
| | | | | 鲜花店
| | | | | |
西门----西大街----西大街----西大街------广场北-------------------北大街---驿站
| | | | |
珠宝店 大明寺 | | | 巫师雕像陈列室
| | | |up
兵营-----兵营大门----广场西-----中央广场-----------------广场东---车马行 书院 药铺 打铁铺
| | | | | |
赌场-----南大街------广场南-------------------东大街-------------东大街-----东大街------ 东大街----东门
| | | | |\ |
| 当铺 乐器店 杂货铺 | \__se_ 兵器铺
| | | \
茶馆-----南大街------扬州盐局---盐局东厅 | 陈列室-----寄卖店 月老亭外
| | |
假山-------个园-----南大街------小盘古 品棋亭------------------------------------月老亭
|
南门
]]
--以上为sj扬州城的大体地图
--地图数据按一下格式记录
yangzhou={
[1]={
roomid=1,
roomname="西门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=2,path="e"}
}
},
[2]={
roomid=2,
roomname="西大街",
roomindex=1,
roomnumber=3,
roomnpc={},
roomexists={
{link=1,path="w"},
{link=3,path="n"},
{link=5,path="n"},
{link=4,path="s"}
}
},
[3]={
roomid=3,
roomname="瘦西湖酒楼",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=2,path="s"}
}
},
[4]={
roomid=4,
roomname="珠宝店",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=2,path="n"}
}
},
[5]={
roomid=5,
roomname="西大街",
roomindex=2,
roomnumber=3,
roomnpc={},
roomexists={
{link=2,path="w"},
{link=6,path="n"},
{link=9,path="e"},
{link=8,path="s"}
}
},
[6]={
roomid=6,
roomname="小金山",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=5,path="s"},
{link=7,path="n"}
}
},
[7]={
roomid=7,
roomname="白莲寺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=6,path="s"}
}
},
[8]={
roomid=8,
roomname="大明寺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=5,path="n"}
}
},
[9]={
roomid=9,
roomname="西大街",
roomindex=3,
roomnumber=3,
roomnpc={},
roomexists={
{link=5,path="w"},
{link=10,path="n"},
{link=12,path="e"},
{link=53,path="s"}
}
},
[10]={
roomid=10,
roomname="名玉坊",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=11,path="n"},
{link=9,path="s"}
}
},
[11]={
roomid=11,
roomname="丽春院",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=10,path="s"}
}
},
[12]={
roomid=12,
roomname="广场北",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=9,path="w"},
{link=13,path="n"},
{link=18,path="e"},
{link=48,path="s"}
}
},
[13]={
roomid=13,
roomname="衙门大门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=14,path="n"},
{link=12,path="s"}
}
},
[14]={
roomid=14,
roomname="衙门正厅",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=15,path="w"},
{link=16,path="n"},
{link=17,path="e"},
{link=13,path="s"}
}
},
[15]={
roomid=15,
roomname="西厅",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=14,path="e"}
}
},
[16]={
roomid=16,
roomname="后院",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=14,path="s"}
}
},
[17]={
roomid=17,
roomname="东厅",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=14,path="w"}
}
},
[18]={
roomid=18,
roomname="北大街",
roomindex=1,
roomnumber=3,
roomnpc={},
roomexists={
{link=12,path="w"},
{link=21,path="n"},
{link=19,path="e"},
{link=29,path="s"}
}
},
[19]={
roomid=19,
roomname="驿站",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=18,path="w"},
{link=20,path="n"}
}
},
[20]={
roomid=20,
roomname="鲜花店",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=20,path="s"}
}
},
[21]={
roomid=21,
roomname="北大街",
roomindex=2,
roomnumber=3,
roomnpc={},
roomexists={
{link=22,path="w"},
{link=18,path="s"},
{link=23,path="n"},
{link=27,path="e"}
}
},
[22]={
roomid=22,
roomname="天阁斋",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=21,path="e"}
}
},
[23]={
roomid=23,
roomname="北大街",
roomindex=3,
roomnumber=3,
roomnpc={},
roomexists={
{link=24,path="w"},
{link=25,path="n"},
{link=26,path="e"},
{link=21,path="s"}
}
},
[24]={
roomid=24,
roomname="城隍庙",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=23,path="e"}
}
},
[25]={
roomid=25,
roomname="北门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=23,path="s"}
}
},
[26]={
roomid=26,
roomname="小酒馆",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=23,path="w"}
}
},
[27]={
roomid=27,
roomname="扬州客栈",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=21,path="w"},
{link=28,path="e"}
}
},
[28]={
roomid=28,
roomname="客栈偏厅",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=27,path="w"},
}
},
[29]={
roomid=29,
roomname="广场东",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=48,path="w"},
{link=18,path="n"},
{link=30,path="e"},
{link=31,path="s"}
}
},
[30]={
roomid=30,
roomname="车马行",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=29,path="w"}
}
},
[31]={
roomid=31,
roomname="东大街",
roomindex=1,
roomnumber=4,
roomnpc={},
roomexists={
{link=49,path="w"},
{link=29,path="n"},
{link=34,path="e"},
{link=32,path="s"}
}
},
[32]={
roomid=32,
roomname="乐器店",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=31,path="n"},
{link=33,path="s"}
}
},
[33]={
roomid=33,
roomname="品棋亭",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=32,path="n"},
{link=43,path="e"}
}
},
[34]={
roomid=34,
roomname="东大街",
roomindex=2,
roomnumber=4,
roomnpc={},
roomexists={
{link=31,path="w"},
{link=35,path="n"},
{link=37,path="s"},
{link=38,path="e"}
}
},
[35]={
roomid=35,
roomname="书院",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=34,path="s"},
{link=36,path="u"}
}
},
[36]={
roomid=36,
roomname="巫师雕像陈列室",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=35,path="d"},
}
},
[37]={
roomid=37,
roomname="杂货铺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=34,path="n"}
}
},
[38]={
roomid=38,
roomname="东大街",
roomindex=3,
roomnumber=4,
roomnpc={},
roomexists={
{link=34,path="w"},
{link=39,path="n"},
{link=44,path="e"},
{link=42,path="se"},
{link=40,path="s"}
}
},
[39]={
roomid=39,
roomname="药铺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=38,path="s"}
}
},
[40]={
roomid=40,
roomname="寄卖店",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=41,path="w"},
{link=38,path="n"}
}
},
[41]={
roomid=41,
roomname="陈列室",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=40,path="e"}
}
},
[42]={
roomid=42,
roomname="月老亭外",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=38,path="nw"},
{link=43,path="s"}
}
},
[43]={
roomid=43,
roomname="月老亭",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=33,path="w"},
{link=42,path="n"}
}
},
[44]={
roomid=44,
roomname="东大街",
roomindex=4,
roomnumber=4,
roomnpc={},
roomexists={
{link=38,path="w"},
{link=45,path="n"},
{link=46,path="e"},
{link=47,path="s"}
}
},
[45]={
roomid=45,
roomname="打铁铺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=44,path="s"}
}
},
[46]={
roomid=46,
roomname="东门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=44,path="w"}
}
},
[47]={
roomid=47,
roomname="兵器铺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=44,path="n"}
}
},
[48]={
roomid=48,
roomname="中央广场",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=53,path="w"},
{link=12,path="n"},
{link=29,path="e"},
{link=49,path="s"}
}
},
[49]={
roomid=49,
roomname="广场南",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=51,path="w"},
{link=48,path="n"},
{link=31,path="e"},
{link=50,path="s"}
}
},
[50]={
roomid=50,
roomname="当铺",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=49,path="n"}
}
},
[51]={
roomid=51,
roomname="南大街",
roomindex=1,
roomnumber=3,
roomnpc={},
roomexists={
{link=52,path="w"},
{link=53,path="n"},
{link=49,path="e"},
{link=56,path="s"}
}
},
[52]={
roomid=52,
roomname="赌场",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=51,path="e"}
}
},
[53]={
roomid=53,
roomname="广场西",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=54,path="w"},
{link=9,path="n"},
{link=48,path="e"},
{link=51,path="s"}
}
},
[54]={
roomid=54,
roomname="兵营大门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=55,path="w"},
{link=53,path="e"}
}
},
[55]={
roomid=55,
roomname="兵营",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=54,path="e"}
}
},
[56]={
roomid=56,
roomname="南大街",
roomindex=2,
roomnumber=3,
roomnpc={},
roomexists={
{link=57,path="w"},
{link=51,path="n"},
{link=58,path="e"},
{link=60,path="s"}
}
},
[57]={
roomid=57,
roomname="茶馆",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=56,path="e"}
}
},
[58]={
roomid=58,
roomname="扬州盐局",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=56,path="w"},
{link=59,path="e"}
}
},
[59]={
roomid=59,
roomname="盐局东厅",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=58,path="w"}
}
},
[60]={
roomid=60,
roomname="南大街",
roomindex=3,
roomnumber=3,
roomnpc={},
roomexists={
{link=61,path="w"},
{link=56,path="n"},
{link=64,path="e"},
{link=63,path="s"}
}
},
[61]={
roomid=61,
roomname="个园",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=62,path="w"},
{link=60,path="e"}
}
},
[62]={
roomid=62,
roomname="假山",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=61,path="e"}
}
},
[63]={
roomid=63,
roomname="南门",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=60,path="n"}
}
},
[64]={
roomid=64,
roomname="小盘古",
roomindex=1,
roomnumber=1,
roomnpc={},
roomexists={
{link=60,path="w"}
}
}
}
local openlist={}
local closedlist={}
--创建节点
function createnode(key,g,path,prevnode,nextnode)
return {key=key,g=g,path=path,prevnode=prevnode,nextnode=nextnode}
end
function checkopenlist(key)
for k,v in pairs(openlist) do
if key==v.key then return true end
end
return false
end
function checkclosedlist(key)
if closedlist[key]~=nil then
return true
else
return false
end
end
--获取路径
function getpathfromlist(sid,did)
local tmp
local path=""
tmp=closedlist[did]
path=tmp.path
while tmp.prevnode~=sid do
tmp=closedlist[tmp.prevnode]
path=tmp.path..";"..path
end
return path
end
--快速行走(A*算法g值为1)
function getroompath(sid,did)
local bestroom,temproom
openlist={}
closedlist={}
if sid==did then return "" end
table.insert(openlist,createnode(sid,0,"",nil,nil))
while table.getn(openlist)~=0 do
table.sort(openlist,function(a,b) return a.g<b.g end)--按g值排序，保证第一个房间为最短的。
bestroom=openlist[1]
if bestroom.key==0 then
print("房间"..bestroom.prevnode.."有出口指向0，请查证")
bestroom=nil
temproom=nil
return ""
end
table.remove(openlist,1)
if not checkclosedlist(bestroom.key) then closedlist[bestroom.key]=bestroom end
if bestroom.key==did then
bestroom=nil
temproom=nil
return getpathfromlist(sid,did)
end
for k,v in pairs(yangzhou[bestroom.key].roomexists) do
if not checkopenlist(v.link) then
if not checkclosedlist(v.link) then table.insert(openlist,createnode(v.link,bestroom.g+1,v.path,bestroom.key,nil)) end
end
end
end
end
function ismember(id,ta)
for i=1,#ta do
if ta==id then return true end
end
return false
end
--这里遍历方法是先按照要求方式按顺序将需要遍历的房间计算出来，然后挨个房间快速行走过去。
--当然如果是不用快速行走也可以，但是需要自己记录已行走的路径，这个就有点麻烦了。
--广度优先遍历
function bft(sid,deep)
local tt={}
local mt={}
local rt={}
local td=deep
table.insert(tt,sid)
repeat
mt={}
for i=1,#tt do
for k,v in ipairs(yangzhou[tt].roomexists) do
if not (ismember(v.link,rt) or ismember(v.link,mt)) then
table.insert(mt,v.link)
end
end
if not ismember(tt,rt) then table.insert(rt,tt) end
end
tt=mt
td=td-1
until td<0
--打印结果
print(yangzhou[sid].roomname..sid.."方圆"..deep.."步广度优先遍历走法为:")
for i=1,#rt do
io.write(yangzhou[rt].roomname..rt.."->")
end
end
bft(48,5)
- Seagate：我知道这个算法，我觉得这个算法效率上似乎有点问题，我的想法是比如起始点A的坐标是（x,y,z,u)，结束点B的坐标是(x2,y2,z2,u2)，（x-东西方向，y-南北方向，z-上下方向，u-enter/out（里外方向）），以(x-x2)^+(y-y2)^2+(z-z2)^2+(u-u2)^2作为h值，g值过小可以忽略，open表以h值从小到大排序，先去最小的进行检查，这样子遍历的节点数才能最小。否则按照上面的算法不考虑h值实际上是一个广度优先算法，而不是A算法。用这个评估值如果起始点邻居中几何坐标最接近目标的会先检查。
- Sauron：刚才开始做的时候地图数据库中我是添加了房间的xyz坐标，以按控件坐标距离作为g值，也是可以算的，但是有个问题
mud中的每个房间的坐标不是想象中的那么好搞定的。至于效率我看没什么问题。sj有50多个区域，上千个房间。 我开了三个mush窗口一共挂了30多个号，cpu使用率在50左右蹦跶(amd4400)
- Seagate：我的想法是这样子的，坐标100%要自己设，自动设和不设置没有区别，因为pkuxkx的房间是变坐标的，比如你大厅到卧室是一格，东大街到打铁铺是一格，南阳到汝州也是一格，但是这三个一格在坐标上长度应该是不一样的，有时候无所谓，有时候很要命， 不考虑周全会导致有些地方坐标重叠，计算就非常不方便了。还有我的想法是坐标计算区域内有效，跨区域要先从本区域计算到区域边缘，然后从区域边缘到另外一个区域，这样一个区域一个区域计算，这个h值相对来说比较准确，而且计算量小了一点。等我写完这个版本，下一个版本的时候仔细考虑考虑吧。我现在的工作目标是写完这个版本，对现有的地图函数进行优化。（优化是尽可能减少读取数据库，一次性读完然后用自己开发的record列表搜索函数来搜索，发现效率提高5倍左右，连接数据库一次差不多在500-1000毫秒之间，ado效率实在太低下了，暂时忍了）
- Killunix：用相对坐标，不要用绝对坐标
- Sauron：恩，用相对坐标好些，在一个区域建立一个坐标系，比如以最左上的房间作为原点，至于区域与区域之间的连接就做一个区域连接地图，直接用广度优先算法计算需要经过的城市。配置坐标是一个很麻烦的事情，正上楼上说的mud中地图画的天马行空，格子长短都不一，相信把坐标配置好后，使用A算法我的cpu使用率可以降低到30左右，哈哈。
- Seagate：我其实也是相对坐标，ct是0，0，0，0。然后从ct往外展开。有些坐标不好协调，比如灵州和普赞广场是相连的，但是灵州是向西走一路过去的，普赞是向南走一路过去，最后估计很难合成相连坐标。还有就是杀手帮，东南西三个方向都可以到，这个更麻烦，实际的杀手帮难道在扬州天上的？否则怎么能够这么天马行空？困惑啊
- Hba：搞坐标要谨慎啊，mud中的坐标是很混乱的，有可能是不同巫师设计的不同区域而导致高度方位的错乱，也有可能是疏忽造成就将错就错。当年我玩风云的时候，搞个task机器人就弄得脑袋都大了。
———-
- Gocold：触发条件：设定环境变量：action = “精确定位当前位置(*)”
这部分比较感兴趣，如何定位准确？
- Seagate：实际上是遍历之前再定位一次当前房间，房子最后一步乱入。没有在look 邻居的时候重新修改locate房间的资料，不是不能做，是比较懒。就是一串命令set action 精确定位当前位置locate;look;set action 结束
或者set action 精确定位当前位置north;look north;set action 结束;
然后作一个多行触发把这个取下来就可以了。
