活跃下气氛，对公版机器遍历函数find()的一点看法

新手(newbie@tj)

今日拜读坛内大神们的帖子，发现基本是基于如何提高job速度的，在各个细节方面基本做到极致，但是少有对遍历函数本身的讨论。当然大神的私人订制版肯定对该函数是优化过的。今日通过对公版机器的研究，发现该机器的核心其实就是rooms.lua和lujing.lua两个文件，其他文件都是有效的补充和完善。要想做到完美提速，对遍历函数的探讨是必不可少的，但是遗憾的是，公版机器的遍历函数find()，简单粗暴，处理简单区域还行，遇到房间多或者迷宫多的区域，无效的遍历太多，导致任务搜索失败几率增加，严重影响效率。小弟不才，对find()函数的实现过程做个简单解释说明，结合实例，帮助兄弟们更好的理解遍历过程。
整天挂机很无趣的。
（未完待续，先开个头水一贴）

新手(newbie@tj)

前面讲了那么多，强调了road.rooms的重要性，那怎么用呢？下面以华山村碎石路为例做个说明
华山村地图】其中■■■表示你所在房间位置，■■■表示目标Npc位置
2: ─────────────────────────────────────────────────
3:
4:                           ※※※※※
5:    ┏━━━━━━━┓     ※ 菜地 ※
6:    ┃【长安】南城门┃     ※※※※※
7:    ┗━━━━━━━┛酒肆  \     /  杂货铺
8:               \       |     \   /     |                     ┏━━━━━━━━┓
9:             碎石路─碎石路─村中心─碎石路─碎石路─东村口─┃【华山】华山脚下┃
10:               |               |                             ┗━━━━━━━━┛
11:             玄坛庙          碎石路─铁匠铺
12:                               |
13:                      民房─碎石路
14:                               |
15:                             南村口
16:                               |
17:                             黄土路
18:                               |
19:                       ┏━━━━━━━┓
20:                       ┃【襄阳】土路①┃
21:                       ┗━━━━━━━┛

华山村地图】其中■■■表示你所在房间位置，■■■表示目标Npc位置
2: ─────────────────────────────────────────────────
3:
4:                           ※※※※※
5:    ┏━━━━━━━┓     ※ caidi ※
6:    ┃【长安】南城门┃     ※※※※※
7:    ┗━━━━━━━┛jiusi  \     /  zahuopu
8:               \       |     \   /     |                     ┏━━━━━━━━┓
9:             shilu5─shilu3─zhongxin─shilu4─shilu6─eexit─┃【华山】华山脚下┃
10:               |               |                             ┗━━━━━━━━┛
11:             miaoyu          shilu2─tiejiangpu
12:                               |
13:                   minfang1─shilu1
14:                               |
15:                             sexit
16:                               |
17:                             hsroad3
18:                               |
19:                       ┏━━━━━━━┓
20:                       ┃【襄阳】土路①┃
21:                       ┗━━━━━━━┛

1. rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
   
2. 
   
3. for id in pairs(rooms) do
   
4.         table.insert(newrooms,id)
   
5. end

复制代码

这是公版机器代码，作用是得到以road.id为中心，范围6格内所有相邻房间，转换下格式储存在newsrooms这个表里
下面结合华山村碎石路分析，road.id="village/shilu1",newrooms这个表的实际内容如下：
1="huashan/shanhong"
2="group/entry/caeroad3"
3="changan/eastroad1"
4="village/shilu5"
5="village/zhongxin"
6="huashan/qianchi"
7="village/caidi"
8="village/minfang1"
9="gumu/xiaolu1"
10="changan/eastroad2"
11="changan/neijie7"
12="changan/bingying"
13="village/shilu2"
14="huashan/shaluo"
15="xiangyang/caiyongmanor"
16="xiangyang/henanroad1"
17="huashan/shulinn1"
18="village/hsroad3"
19="huashan/yuquan"
20="huashan/path1"
21="changan/eastjl2"
22="huashan/shulinn2"
23="xiangyang/hanshui1"
24="village/shilu3"
25="village/zahuopu"
26="changan/eastjie3"
27="changan/southroad2"
28="huashan/baichi"
29="huashan/shulinn"
30="changan/eastjie4"
31="village/shilu4"
32="village/minfang2"
33="changan/eastmen"
34="changan/southroad3"
35="changan/eastchl"
36="village/shilu1"
37="huashan/v-road-1"
38="xiangyang/shanxiroad1"
39="xiangyang/outnroad2"
40="huashan/qingke"
41="village/shilu6"
42="village/eexit"
43="huashan/kongdi"
44="huashan/shulin1"
45="village/jiusi"
46="gumu/fchuan"
47="village/miaoyu"
48="changan/eastjl1"
49="xiangyang/shanxiroad2"
50="xiangyang/outnroad3"
51="village/tiejiangpu"
52="xiangyang/lantian"
53="huashan/shulin"
54="village/sexit"

记住这时候是newrooms是没有经过排序的，公版机器同时也给出了FastDFS这个函数进行了排序，排序结果储存在road.rooms这个表，
里面的实际内容如下：
1="huashan/shanhong"
2="huashan/shaluo"
3="huashan/path1"
4="huashan/yuquan"
5="village/eexit"
6="village/shilu6"
7="village/shilu4"
8="village/zhongxin"
9="village/shilu2"
10="village/shilu1"
11="village/minfang1"
12="village/sexit"
13="village/hsroad3"
14="xiangyang/shanxiroad2"
15="xiangyang/shanxiroad1"
16="gumu/fchuan"
17="gumu/xiaolu1"
18="xiangyang/outnroad3"
19="xiangyang/henanroad1"
20="xiangyang/hanshui1"
21="xiangyang/outnroad2"
22="xiangyang/lantian"
23="changan/southroad3"
24="xiangyang/caiyongmanor"
25="changan/southroad2"
26="village/tiejiangpu"
27="village/shilu3"
28="village/shilu5"
29="group/entry/caeroad3"
30="changan/eastroad2"
31="changan/eastroad1"
32="changan/eastmen"
33="changan/eastjie4"
34="changan/neijie7"
35="changan/bingying"
36="changan/eastjie3"
37="changan/eastchl"
38="changan/eastjl2"
39="changan/eastjl1"
40="village/miaoyu"
41="village/jiusi"
42="village/zahuopu"
43="village/minfang2"
44="huashan/shulin"
45="huashan/shulinn"
46="huashan/shulinn1"
47="huashan/shulinn2"
48="huashan/shulin1"
49="huashan/kongdi"
50="huashan/v-road-1"
51="huashan/qingke"
52="huashan/qianchi"
53="huashan/baichi"
54="village/caidi"
结合上面的华山村的地图，显然这个搜索次序和我们的预期不符合，如果是手动走路的话，第一反应当然是先把所有的碎石路遍历一遍，然后再走剩余的房间，
我们根据这个思路对 searchPre做个小改动，在哪里动手术，简单的办法是在排序前对newrooms预先进行处理，然后再用FastDFS函数进行排序，
当然有能力的话也可以自己写个排序算法，这个不在讨论范围内。
下面讲下步骤：
1 把遍历路径分成两部分，一是华山村所有碎石路的id，二是以road.id为中心，范围6格内所有相邻房间
2 把两部分遍历路径分别放进newrooms，然后用DFS()函数进行排序（DFS函数是原searchPre的一部分，这里进行了封装处理，因为要调用两次）
我们看看调整后的结果：
1="village/shilu1"
2="village/shilu2"
3="village/shilu6"
4="village/shilu4"
5="village/shilu3"
6="village/shilu5"
7="huashan/shanhong"
8="huashan/shaluo"
9="huashan/path1"
10="village/eexit"
11="village/shilu6"
12="village/shilu4"
13="village/zhongxin"
14="village/shilu2"
15="village/shilu1"
16="village/minfang1"
17="village/sexit"
18="village/hsroad3"
19="xiangyang/shanxiroad2"
20="xiangyang/shanxiroad1"
21="gumu/fchuan"
22="gumu/xiaolu1"
23="xiangyang/outnroad3"
24="xiangyang/henanroad1"
25="xiangyang/hanshui1"
26="xiangyang/outnroad2"
27="xiangyang/lantian"
28="changan/southroad3"
29="xiangyang/caiyongmanor"
30="changan/southroad2"
31="village/tiejiangpu"
32="village/shilu3"
33="village/shilu5"
34="group/entry/caeroad3"
35="changan/eastroad2"
36="changan/eastroad1"
37="changan/eastmen"
38="changan/eastjie4"
39="changan/neijie7"
40="changan/bingying"
41="changan/eastjie3"
42="changan/eastchl"
43="changan/eastjl2"
44="changan/eastjl1"
45="village/miaoyu"
46="village/jiusi"
47="village/zahuopu"
48="village/minfang2"
49="huashan/shulin"
50="huashan/shulinn"
51="huashan/shulinn1"
52="huashan/shulinn2"
53="huashan/shulin1"
54="huashan/kongdi"
55="huashan/v-road-1"
56="huashan/yuquan"
57="huashan/qingke"
58="huashan/qianchi"
59="huashan/baichi"
60="village/caidi"

显然，调整后的次序最先遍历的就是6个碎石路房间，初步达到了目的，当然这只是初步方案，
碎石路房间遍历完后的第二部分路径同样是可以进行优化的，这个后面在讨论。

给出测试代码，有兴趣的同学可以试试

1. function searchPre()
   
2.         if flag.times then
   
3.         print(road.id)       
   
4.         print("第"..flag.times.."次遍历")
   
5.         end
   
6.         road.rooms={}
   
7.     local p_room = map.rooms[road.id].name
   
8.         local p_dest = getLookCity(road.id)
   
9.         local l_distance = 6
   
10.   if job.name and (job.name=="clb" or job.name=='tdh' or job.name=='tmonk') and flag.times==1 then
    
11.            l_distance = 2
    
12.         end
    
13.         if job.name and job.name=='xueshan' and flag.times==1 then
    
14.        l_distance = 3
    
15.   end
    
16.         if p_dest==nil then
    
17.            p_dest=map.rooms[road.id].outdoor
    
18.         end
    
19.         newrooms = {}
    
20.         local rooms ={}       
    
21.         rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
    
22.         local SN_rooms={}
    
23.         if job.name=='huashan' then
    
24.                 job.room=dest.room
    
25.                 job.area=dest.area
    
26.         end
    
27.         if job.room and job.area then SN_rooms=getRooms(job.room, job.area) end
    
28.         if #SN_rooms>1 then        
    
29.                 print('找到'..#SN_rooms..'个同名房间')
    
30.                 local Firstroom=getNearRoom({road.id},SN_rooms)
    
31.                 table.insert(newrooms,Firstroom)
    
32.                 for _,v in pairs(SN_rooms) do
    
33.                         if v~=Firstroom then                        
    
34.                                 table.insert(newrooms,v)
    
35.                         end
    
36.                 end       
    
37.         DFS()               
    
38.         newrooms = {}
    
39.         end
    
40.        
    
41.         for id in pairs(rooms) do                       
    
42.                 table.insert(newrooms,id)
    
43.         end       
    
44.         DFS()
    
45. end
    
46. function DFS()
    
47.                 myrt={}
    
48.        
    
49.         for _,roomid in pairs(newrooms) do --插入房间链表
    
50.                         roomV = List.new(roomid)
    
51.                         local node = roomV
    
52.                         for k,v in pairs(newrooms) do --所有的房间id
    
53.                                 for route,link_way in pairs(map.rooms[roomid].ways) do  --当前id的出口
    
54.                                         local routeLength = map.rooms[roomid]:length(route) --获取路径方向是否可达，返回false标示此路不通，那么这个方向的路就不插入出口链表
    
55.                                         --print("k="..k.."|link_way="..link_way.."|v="..v)
    
56.                                         if routeLength then
    
57.                                                 ---by fqyy 20170429 加入room.lengths的数值判断
    
58.                                                 if routeLength ==1 or routeLength >1 and flag.times>1 then
    
59.                                                         if v==link_way then
    
60.                                                                 node = List.addNode(node,List.new(k)) --插入节点生成第一个房间的出口链表
    
61.                                                         end
    
62.                                                 end
    
63.                                         end
    
64.                                 end
    
65.                         end
    
66.                         table.insert(myrt,roomV)
    
67.         end
    
68.         visited={}
    
69. 
    
70.         for i=1 ,countTab(newrooms) do
    
71.                 visited[i]=false --初始化所有节点未曾访问
    
72.         end
    
73.        
    
74.         if not visited[1] then
    
75.                 FastDFS(myrt,1) --计算起点的连通图
    
76.         end
    
77.         for i=1 ,countTab(newrooms) do
    
78.                 if visited[i]==false then--未曾访问的节点测试一下跟第一个起点的连通性，如果能联通，则递归这个节点
    
79.                         local path, len = map:getPath(myrt[1].index,myrt[i].index)
    
80.                         if path then
    
81.                                 FastDFS(myrt,i) --继续遍历指定的myrt[i]这个节点
    
82.                                 --messageShow("发现通路，遍历下一个节点！通路长度="..len,"red")
    
83.                         end
    
84.                 end
    
85.         end                       
    
86. end

复制代码

新手(newbie@tj)

这段代码没有调用newrooms，我就是用getrooms返回所有同名房间列表而已，然后赋值给road.rooms，再用程序自带的getpath来处理，肯定是路径生成出错了，但跟newrooms没有丝毫关系！

请仔细思考经过searchPre（）处理过的road.rooms和你自己加的road.rooms之间的区别，我打个比方，经过searchPre（）处理过的road.rooms是你的档案，上面写满了关于你的一切，你自己加的road.rooms，也是你的档案，不过上面就只有一个名字，除此之外确定不了任何事，getpath（）需要的是前者

新手(newbie@tj)

给一个初级版本，供大家参考，

1. function searchPre()
   
2.         road.rooms={}
   
3.         --print(road.id)
   
4.     local p_room = map.rooms[road.id].name
   
5.         local p_dest = getLookCity(road.id)
   
6.         local l_distance = 6
   
7.   if job.name and (job.name=="clb" or job.name=='tdh' or job.name=='tmonk') and flag.times==1 then
   
8.            l_distance = 2
   
9.         end
   
10.         if job.name and job.name=='xueshan' and flag.times==1 then
    
11.        l_distance = 3
    
12.   end
    
13.         if p_dest==nil then
    
14.            p_dest=map.rooms[road.id].outdoor
    
15.         end
    
16.     --local rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
    
17. 
    
18.        
    
19.         ----------------------------------
    
20.         local rooms ={}
    
21.        
    
22.                 if table.getn(getRooms(job.room, job.area))>1 and flag.times==1 then              
    
23.            rooms=getRooms(job.room, job.area)
    
24.                    require "tprint"
    
25.                   -- tprint(rooms)
    
26.                    print("第一次遍历，找到"..countTab(rooms).."个同名房间")
    
27.                 else
    
28.                         rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
    
29.         end
    
30.                  tprint(rooms)
    
31.         -----------------------------------
    
32.         --local roomsnum=countTab(rooms)
    
33.         local roomsnum=#rooms
    
34.         --构造邻接表，用于递归搜索
    
35.         --插入起始road.id
    
36.         starttime=os.clock() --测试计算时间
    
37.         newrooms = {}
    
38.        
    
39.         if roomsnum > 1 and flag.times==1 then
    
40.                 newrooms=rooms       
    
41.         else
    
42.                 for id in pairs(rooms) do
    
43.                         table.insert(newrooms,id)
    
44.                 end       
    
45.         end
    
46. 
    
47.         myrt={}

复制代码

我发这篇帖子的起因是没看到论坛有相关内容讨论，不是为灌水，也不是为了通宝，纯粹是出于兴趣研究公版机器，我也没什么兴趣挂机练级，弄几个号仅仅是为了测试而已

渡雪(lovecold@tj)

感觉是专业人士,洗耳恭听.

风小小(zhubang@tj)

好久没人讲课了，这个好专业的感觉，仔细听讲                                             

无法风(kkfromch@tj)

我就想知道同名房间的搜索怎么提高效率？

比如兰州城，三面的大道，而且那里是个环形地图，有办法优化吗？

例如：任务地点是兰州城大道。

云妮儿(yunny@tj)

这个厉害了  等待大神讲解

奥特慢(outm@tj)

厉害了我的哥,  笔记本拿出来准备开始哦

风小小(zhubang@tj)

咋开个头，人没影了                                                

大象无形(xlang@tj)

大神还在赶稿吗？                     

傲雪(aoxue@tj)

搬个小板凳，后来的同学别插队

新手(newbie@tj)

热心同学好多，出差中，晚上更新