|
|
楼主 |
发表于 2019-4-15 23:58:08
|
显示全部楼层
前面讲了那么多，强调了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: ┗━━━━━━━┛
- rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
- for id in pairs(rooms) do
- table.insert(newrooms,id)
- 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个碎石路房间，初步达到了目的，当然这只是初步方案，
碎石路房间遍历完后的第二部分路径同样是可以进行优化的，这个后面在讨论。
给出测试代码，有兴趣的同学可以试试
- function searchPre()
- if flag.times then
- print(road.id)
- print("第"..flag.times.."次遍历")
- end
- road.rooms={}
- local p_room = map.rooms[road.id].name
- local p_dest = getLookCity(road.id)
- local l_distance = 6
- if job.name and (job.name=="clb" or job.name=='tdh' or job.name=='tmonk') and flag.times==1 then
- l_distance = 2
- end
- if job.name and job.name=='xueshan' and flag.times==1 then
- l_distance = 3
- end
- if p_dest==nil then
- p_dest=map.rooms[road.id].outdoor
- end
- newrooms = {}
- local rooms ={}
- rooms = getAroundRooms(p_room,p_dest,l_distance,'all')
- local SN_rooms={}
- if job.name=='huashan' then
- job.room=dest.room
- job.area=dest.area
- end
- if job.room and job.area then SN_rooms=getRooms(job.room, job.area) end
- if #SN_rooms>1 then
- print('找到'..#SN_rooms..'个同名房间')
- local Firstroom=getNearRoom({road.id},SN_rooms)
- table.insert(newrooms,Firstroom)
- for _,v in pairs(SN_rooms) do
- if v~=Firstroom then
- table.insert(newrooms,v)
- end
- end
- DFS()
- newrooms = {}
- end
-
- for id in pairs(rooms) do
- table.insert(newrooms,id)
- end
- DFS()
- end
- function DFS()
- myrt={}
-
- for _,roomid in pairs(newrooms) do --插入房间链表
- roomV = List.new(roomid)
- local node = roomV
- for k,v in pairs(newrooms) do --所有的房间id
- for route,link_way in pairs(map.rooms[roomid].ways) do --当前id的出口
- local routeLength = map.rooms[roomid]:length(route) --获取路径方向是否可达，返回false标示此路不通，那么这个方向的路就不插入出口链表
- --print("k="..k.."|link_way="..link_way.."|v="..v)
- if routeLength then
- ---by fqyy 20170429 加入room.lengths的数值判断
- if routeLength ==1 or routeLength >1 and flag.times>1 then
- if v==link_way then
- node = List.addNode(node,List.new(k)) --插入节点生成第一个房间的出口链表
- end
- end
- end
- end
- end
- table.insert(myrt,roomV)
- end
- visited={}
- for i=1 ,countTab(newrooms) do
- visited[i]=false --初始化所有节点未曾访问
- end
-
- if not visited[1] then
- FastDFS(myrt,1) --计算起点的连通图
- end
- for i=1 ,countTab(newrooms) do
- if visited[i]==false then--未曾访问的节点测试一下跟第一个起点的连通性，如果能联通，则递归这个节点
- local path, len = map:getPath(myrt[1].index,myrt[i].index)
- if path then
- FastDFS(myrt,i) --继续遍历指定的myrt[i]这个节点
- --messageShow("发现通路，遍历下一个节点！通路长度="..len,"red")
- end
- end
- end
- end
|
|
闽公网安备 35050202000162号 )
发表于 2019-4-10 18:20:21
