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

新手(newbie@tj)

先给个小测试：
做个alias 运行Test()函数，各位看看打印的结果能理解吗

1. function Test()
   
2.         road.id = road.id or "mingjiao/wu1"
   
3.         searchPre()
   
4.         searchStart1()
   
5. end
   
6. 
   
7. function searchStart1()
   
8.         while (#road.rooms>0 ) do
   
9.                 local path, length = map:getPath(road.id, road.rooms[1])
   
10.                 road.id = road.rooms[1]
    
11.                 table.remove(road.rooms,1)
    
12.                 print("【"..road.id.."】:",path)
    
13.         end
    
14. end

复制代码

龙小女(joyce@tj)

一起说完吧，这样搞就变成水坑了。

新手(newbie@tj)

弄清Lua函数具体的作用，有个简单技巧可以理清思路：
1 看是否有return
2 看是否有全局变量，如果有是否被赋值
3 函数是否调用了其他函数，只要发生了函数调用，函数就必须返回，返回值可以是任何值。
开始正题：
首先明确find()函数的作用：在目标房间进行l_distance深度的遍历（默认是6）,遍历行走深度范围内和目标房间相连的所有房间。下面介绍函数调用过程：

1. function find(l_area,l_room)
   
2.     do return search() end
   
3. end

复制代码

1) 有return,调用函数search();

1. function search()       
   
2.     tmp.find = true
   
3.     if flag.find==1 then return end
   
4.     searchPre()
   
5.         cntr1 = countR(15)
   
6.     exe('look;halt')
   
7.         tmpsearch=3
   
8.     return check_halt(searchStart,1)
   
9. end

复制代码

2)有全局变量 tmp.find ,暂时先不管;调用函数searchPre(),这个函数是find()函数的核心

1.         road.rooms={}       
   
2.     local p_room = map.rooms[road.id].name  
   
3.         local p_dest = getLookCity(road.id)
   
4.         local l_distance = 6
   
5.         if p_dest==nil then
   
6.            p_dest=map.rooms[road.id].outdoor
   
7.         end
   
8.         local rooms = getAroundRooms(p_room,p_dest,l_distance,'all')       
   
9.         starttime=os.clock() --测试计算时间
   
10.         newrooms = {}
    
11.         for id in pairs(rooms) do
    
12.                         table.insert(newrooms,id)
    
13.         end

复制代码

发现三个全局变量，其实是两个，很重要。
road.rooms是一个表，最终储存所有需要遍历的房间id,当然现在是空的。
road.id就是前面说的目标房间id，通过函数path_consider()确定。
newrooms等同于road.rooms的另一种存储方式，方便后面处理。

1.         myrt={}
   
2.        
   
3.         for _,roomid in pairs(newrooms) do --插入房间链表
   
4.                         roomV = List.new(roomid)
   
5.                         local node = roomV
   
6.                         for k,v in pairs(newrooms) do --所有的房间id
   
7.                                 for route,link_way in pairs(map.rooms[roomid].ways) do  --当前id的出口
   
8.                                         local routeLength = map.rooms[roomid]:length(route)                                        
   
9.                                         if routeLength then                                               
   
10.                                                 if routeLength ==1 or routeLength >1 and flag.times>1 then
    
11.                                                         if v==link_way then
    
12.                                                                 node = List.addNode(node,List.new(k)) --插入节点生成第一个房间的出口链表
    
13.                                                         end
    
14.                                                 end
    
15.                                         end
    
16.                                 end
    
17.                         end
    
18.                         table.insert(myrt,roomV)
    
19.         end

复制代码

        又发现新的全局变量myrt，中间的循环过程涉及到链表（一种数据结构），不展开讲，记住结论：myrt和newrooms其实是一回事,road.rooms的不同存储方式而已。

1.         for i=1 ,countTab(newrooms) do
   
2.                 if visited[i]==false then--未曾访问的节点测试一下跟第一个起点的连通性，如果能联通，则递归这个节点
   
3.                         local path, len = map:getPath(myrt[1].index,myrt[i].index)
   
4.                         if path then
   
5.                                 FastDFS(myrt,i) --继续遍历指定的myrt[i]这个节点                       
   
6.                         end
   
7.                 end
   
8.         end

复制代码

发现新的函数FastDFS(),控制权交到该函数手上，这个函数是很经典的深度遍历算法。

1. function FastDFS(myrt,i)
   
2.         visited[i] = true          --设置下标为I的顶点为已访问     
   
3.     table.insert(road.rooms,myrt[i].index)
   
4.         local p = myrt[i].pnext --下一个边表结点  
   
5.         if p==nil then return end
   
6.     while p~=nil do   
   
7.       
   
8.         if(not visited[p.index]) then--如果是未访问的则递归
   
9.                         visited[p.index]=true
   
10.             FastDFS(myrt,p.index)
    
11.                 end
    
12.         p = p.pnext
    
13.                
    
14.     end  
    
15. end

复制代码

重点看 table.insert(road.rooms,myrt.index),是不是发现老朋友road.rooms了，饶了一大圈，最后的结论就是searchPre()的作用是给road.rooms这个table赋值了,里面储存所有需要遍历的房间id。
searchPre()函数调用完成，回到search(),继续往下走,发现return了，调用函数searchStart()。
searchStart()和searchFunc(path)、walk_wait()、walk_goon()都是好基友，怎么发生基情后面再说，今天先到这。

新手(newbie@tj)

kkfromch@tj 发表于 2019-4-9 14:36
我就想知道同名房间的搜索怎么提高效率？

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

版主给你段代码，从宋远桥到兰州城大道的遍历路径，你可以琢磨下，

1. function Test()
   
2. name="大道"
   
3. city="兰州城"
   
4. road.id='wudang/sanqing'
   
5. road.rooms=getRooms(name, city)
   
6. searchStart1()
   
7. end
   
8. 
   
9. function searchStart1()
   
10.         while (#road.rooms>0 ) do
    
11.                 local path, length = map:getPath(road.id, road.rooms[1])
    
12.                 road.id = road.rooms[1]
    
13.                 table.remove(road.rooms,1)
    
14.                 print("【"..road.id.."】:",path)
    
15.         end
    
16. end

复制代码

本子(liwei@tj)

听得一头雾水。哈哈

一把龙泉(pinkmoon@tj)

我还是比较关系最后的结论，哈哈            

无法风(kkfromch@tj)

newbie@tj 发表于 2019-4-9 21:41
版主给你段代码，从宋远桥到兰州城大道的遍历路径，你可以琢磨下，

function searchStart()
        if table.getn(getRooms(job.room, job.area))>1 and flag.times==1 then
                road.rooms={}
                road.rooms=getRooms(job.room, job.area)
        end
    if table.getn(road.rooms)==0 then
       return find_nobody()
    end
    local path, length = map:getPath(road.id, road.rooms[1])

无法风(kkfromch@tj)

<!-- Produced by MUSHclient v 4.84 - www.mushclient.com -->

碎石路----碎石路----东村口                                 ｜                                  民房                碎石路 - 碎石路----碎石路----东村口｜民房碎石路     这是一个宁静的小村子，稀稀落落的分布着几十间土坯泥房，看来村中人 家不多，而且大都生活很艰辛。这是一条东西向的碎石路，南面是间普通的民 房。 　　这是一个阳春三月的深夜，夜幕低垂，天上飘着如絮的云朵，星星眨着眼。     这里明显的出口是 east、south 和 west。   华山派风清扬传人「蝶梦楼查询目标中」傲雪(Aoxue)   神龙教第二代弟子「华山任务中」神龙弟子(Archsl) <战斗中>   周栋南(Zhou dongnan) <战斗中>   中原山贼 了岑(Liao cen) > 纤夫四(Qianfud)告诉你：澜沧江渡船到达时间：1554829339。 Ok. > 碎石路 -     这是一个宁静的小村子，稀稀落落的分布着几十间土坯泥房，看来村中人 家不多，而且大都生活很艰辛。这是一条东西向的碎石路，南面是间普通的民 房。 　　这是一个阳春三月的深夜，夜幕低垂，天上飘着如絮的云朵，星星眨着眼。     这里明显的出口是 east、south 和 west。   华山派风清扬传人「蝶梦楼查询目标中」傲雪(Aoxue)   神龙教第二代弟子「华山任务中」神龙弟子(Archsl) <战斗中>   周栋南(Zhou dongnan) <战斗中>   中原山贼 了岑(Liao cen) > 碎石路 - east、north、west > 村中心 - east、northeast、northwest、south、west   女孩(Girl)   男孩(Boy) > 碎石路 - east、north、south > Ok. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 大多数的(Handongb)告诉你：黄河流域 大渡口到达时间：1554829341。 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 纤夫二(Qianf ub)告诉你：长江渡船到达时间：1554829347。 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 笑风云 (Omio)告诉你：城门关闭 月女不捡(Handongc)告诉你：西夏渡口到达时间：1554829351。 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > 黄河一号(Cxihha)告诉你：陕晋渡口出发时间：1554829353。 黄河四号(Cxihhd)告诉你：兰州渡口出发时间：1554829354。 > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >

搞完之后变成这样了！貌似路径不通，哪里有问题呢？这是华山村碎石路，同名房间任务搜索！

无法风(kkfromch@tj)

上次我用这个搞的searchpre

if table.getn(getRooms(job.room, job.area))>1 and flag.times==1 then
local rooms = getAroundRooms(p_room,p_dest,1,'all')
end

用意是，假如任务房间在任务区域内，存在多个，那么就让第一次搜索只对同名房间周围进行半径+1的搜索，结果也失败了！

你可以试试。

现在搞这个路径搜索算法，讲原理的话，我也能讲一大堆，不过就是变现不了实际的，当然我承认我对map和lujing没有钻研得很透彻，只是停留在表面。

我是希望你不要像我一样，而是能真正运用出来，然后抓一个完整的log，告诉大家，如何进行算法优化的？

毕竟对于广大小白，看理论已经很头疼了，能转化为实用才是最厉害的！

无法风(kkfromch@tj)

另外对于自动抓财神机器人，我也有个难题没解决！

每次报的地点，会获取城市名称——

比如报菜地，就是华山村和佛山。

那么再报一个村中心，这第二个地名在先前的城市列表中进行房间遍历，能找到的城市保留，找不到的城市剔除，直到最后剩下唯一的城市名，这样地点就唯一了，可以前往抓财神。

请问这个算法如何实现呢？