关于GPS地图的一些思路与做法

moonlily · 发表于 2014-12-17 10:33:00

难得有北俠这么一个地方可以讨论机器, 更难得这里有很多高手, 有很多教程, 模版可供参考, 获益很多
我用mush做机器就是在北俠学会的, 感谢各路英雄

以下是我做地图的一些思路, 请各位高手指点

1. 地图需要实现的功能
a. 最基本的当然是无拘束的随意行走, 包括任意2点间最短路径, 任意一点为中心, 设定深度范围内遍历
b. goto指令, goto 房间id, goto 房间名字, goto npc名字, goto npc id, 任意给定参数都可以准确无误的抵达目的地.

2. 地图数据需包含的信息
建立数据的时候信息越多越好, 以便使用时候拆分成各种索引表, 比如房间名字索引, npc名字索引等等, 方便查询
房间id是唯一的一个索引值, area是这个房间在什么区域, 区域可以自己定, 比如我这里将白驼山放入yz(扬州)区域

id = 1,
name = "中央广场",
desc= "房间描述ooxx",
area = "yz",
exits = "climb up:421,nw:5,enter:7,d:2,e:6,w:4,n:3,s:8",
npcs = "流氓(Liu mang)|流氓头(Liumang tou)",
mark = ""

复制代码

以上是一个正常的房间信息

id = 11,
name = "客栈",
area = "yz",
desc= "房间描述ooxx",
exits = "w:3,u:1014:blocked::none:give 1 gold to xiao er,e:26", //给钱就可以走u到1014房间
npcs = "店小二(Xiao er)",
mark = ""
id = 883,
name = "后门",
desc= "房间描述ooxx",
area = "yz",
exits = "n:817,s:975:blocked:bt:trendb:门卫+门卫", // 白驼? -> 负神? -> 如都不满足, 杀门卫
npcs = "门卫(Men wei)",
mark = ""

复制代码

这2个是2种不同情况拦路的处理, 拦路分各种情况: 门派, 神值, npc, 特殊指令(比如开门), 程序自会根据不同设定情况做出不同的处理

id = 23,
name = "北门",
desc= "房间描述ooxx",
area = "yz",
exits = "s:9,n:44,w:45,e:53:oneway",
npcs = "官兵(Guan bing)|武将(Wu jiang)|马超兴(Ma chaoxing)",
mark = ""

复制代码

这里有个特殊出口, e:53:oneway,  表示e到达53号房间, 是单向路径, 无法返回, 程序计算路径的时候可以另外处理.

3. 各种路径的获取
我将一些相对独立的地方单独设置区域,  比如神龙岛, 桃花岛, 或者某些有明显入口的区域, 比如少林寺
中原地区连成一片的区域, 可以作为一个大区域, 也可以分成若干小区域来计算路径,  比如扬州区, 华山派区, 等等.

计算路径的时候, 首选判断当前房间区域和目标房间区域是否一样, 如果不一样就调用区域路径走到目标区域某一个固定点, 然后计算这个固定点到目标房间的路径
路径的一些特殊情况处理
   拦路:  根据不同的设置, 采取不同的方式,  比如给钱的, 直接将  give xxx silver 加入路径,  比如 npc拦路的, 将npc按固定格式加入路径, 以便后续行走程序调用清拦路程序清除npc
                  最终形成的路径: e;e;s;s;e;give 50 silver to xiaoer;u    或者 w;w;s;门卫|门卫;s;s
            行走程序会将路径按";"拆分后, 根据内容依次执行
   单向:  表示不能返回, 在计算路径时候, 终点开始的那个循环, 如果碰到单向出口, 则略过. 而起点开始的那个循环, 则可以使用这个单向出口
这些都需要在地图数据中手动设置, 一次性的体力劳动, 问题不大.

a. 两点间的最短路径
   这个貌似有很多算法, 由于我不是专业人士, 只能粗略了解下,  我目前采取的方式是起点房间和终点房间同时进行广度优先计算, 碰到相同id的房间, 表示路径计算成功
                  起始房间 -> 碰面房间的路径 + 终点房间 -> 碰面房间的反路径 = 起点到终点的路径
   可以想象成在平静的水面, 起点和终点同时扔下2块石头,  水波一层层的扩散, 最终交汇.

b.某点任意深度的遍历路径
   这个略简单, 从这个点开始, 走所有出口, 出口房间深度+1, 碰到同名房间深度不变, 计算满设定的深度就行.  关于算法, 我觉得是深度优先比较好, 不用绕来绕去, 路径重复率较低

c. goto指令的各种参数
   这个最简单, 只是根据各种不同参数, 通过各自的索引表, 最终指向到唯一的房间id, 然后计算两点间路径走过去就成了.
   具体到任务, 比如我要杀武将, 会找到很多房间id,这些房间id作为一个列表, 依次行走, 直到发现武将.

4. 丢失位置信息后的处理, 以及确认行走成功的判断
这是我尚未完善的方面, 主要涉及到房间定位的问题
根据littleknife同学的建议, 目前对这方面有了比较清晰的想法

a. 确认行走是否成功
   行走完成后, 判断当前房间名称, 描述, npc等等参数, 是否和目标房间匹配
   行走过程中, 是否出现一定数量的错误信息, 比如"什么","这个方向没有出口"等等

b. 行走不成功重新定位,
   也就是丢失了位置信息的情况下, 获取当前房间名字, 查询地图库获取匹配这个名字的所有房间id, 如不唯一, 继续比对房间描述, 出口信息, npc信息, 如还是不唯一, 随机走出口继续比对, 极端情况下, 比如掉到坑里, 陷阱, 未知区域, 被外星人抓走, 只能quit重连.

北大侠客行MUD，中国最好的MUD

lzkd · 发表于 2014-12-17 11:07:10

　　有点意思，框架看样子搭的差不多了。但核心部分基本木有太大的体现。如果是有心人，根据这个也能琢磨点东西出来了。不过，北侠有句著名的说——你再怎么说，本来懂的，一看就懂；本来不懂的，怎么还是不懂。——这点一直让人比较无语。

moonlily · 发表于 2014-12-17 13:34:42

本帖最后由 moonlily 于 2014-12-17 06:40 AM 编辑

所有地图机器的核心, 寻路算法,
画地图的目的当然就是为了随意走路, 目标是只要指定任意两点, 就可以获得这两点间的路径. 其他如定点定深遍历, 区域遍历都是延伸出来的功能.

从思路到可操作的距离还是很大的, 当然必须要有思路, 才可以考虑算法, 然后实际操作过程中再修改思路, 目的是为了方便程序实现.

目前的寻路算法:
设A, B两点已知, 求两点间的路径

为了减少循环深度, 确定 A, B两点同时开始做广度优先计算, 也就是一个大循环, 其中有2个基本相同的段落

while not meetid do --开始循环
if not meetid then
for i in pairs(sexit) do
//A端循环, 不停将跟A联通的房间id加入sexit表, 已加入的做标记, 每个房间都带有 A 到此房间的路径
if ttflag[i] then --如果此房间号在目标端路径表中，找到路径, ttflag是一个已探索的房间id索引表
meetid = i
break
end
end
end
if not meetid then
for i in pairs(texit) do
//B端循环, 不停将跟B联通的房间id加入texit表, 已加入的做标记, 每个房间都带有 B 到此房间的路径
if stflag[i] then --如果此房间号在开始端路径表中，找到路径，单向出口不对比
meetid = i
break
end
end
end
end

复制代码

借用一张hasea的图片来说明这个过程

假设 A点为16, B点为1, 求 A 到 B的最短路径

第一个循环
A 端已探索房间集合 {16}
循环16的所有出口房间并加入待探索集合, 并将16加入已探索房间
A端待探索集合 {15}
其中15带有16-15的路径为e

B 端已探索房间集合 {1}
B端待探索集合 {2}
其中2带有1-2的路径为w

第二个循环: 探索 "待探索集合中第一个房间,即15"
A 端已探索房间集合 {16,15}
循环15的所有出口房间并加入待探索集合, 并将15加入已探索房间
A端待探索集合 {8}
其中8带有16-8的路径为e;e (15继承下来的路径e, 以及15-8的方向e)

B 端已探索房间集合 {1,2}
B端待探索集合 {3}
其中3带有1-3的路径为w;w

第三个循环: 探索 "待探索集合中第一个房间,即8"
A 端已探索房间集合 {16,15,8}
循环8的所有出口房间并加入待探索集合, 并将8加入已探索房间
A端待探索集合 {7,9}
其中7带有16-7的路径为e;e;n (8继承下来的路径e;e, 以及8-7的方向n)
其中9带有16-9的路径为e;e;e (8继承下来的路径e;e, 以及8-9的方向e)

B 端已探索房间集合 {1,2,3}
B端待探索集合 {4,14}
其中4带有1-4的路径为w;w;w
其中14带有1-14的路径为w;w;s

第四个循环: 探索 "待探索集合中第一个房间,即7"
A 端已探索房间集合 {16,15,8,7}
循环7的所有出口房间并加入待探索集合, 并将7加入已探索房间
A端待探索集合 {9,6}
其中6带有16-6的路径为e;e;n;n (7继承下来的路径e;e;n, 以及7-6的方向n)

B 端已探索房间集合 {1,2,3,4}
B端待探索集合 {14,5}
其中5带有1-5的路径为w;w;w;w

第五个循环: 探索 "待探索集合中第一个房间,即9"
A 端已探索房间集合 {16,15,8,7,9}
循环9的所有出口房间并加入待探索集合, 并将9加入已探索房间
A端待探索集合 {6,10}
其中10带有16-10的路径为e;e;e;e (9继承下来的路径e;e;e, 以及9-10的方向e)

B 端已探索房间集合 {1,2,3,4,14}
其中13带有1-13的路径为w;w;s;s
B端待探索集合 {5,13}

第六个循环: 探索 "待探索集合中第一个房间,即6"
(因图上2个6, 请忽略掉6-6-5中间那个6, 也就是将2个6合并)
A 端已探索房间集合 {16,15,8,7,9,6}
循环6的所有出口房间并加入待探索集合, 并将6加入已探索房间
A端待探索集合 {10,5}
其中5带有16-5的路径为e;e;n;n;e (6继承下来的路径e;e;n;n, 以及6-5的方向e)

B 端已探索房间集合 {1,2,3,4,14,5}
循环5的所有出口房间并加入待探索集合, 并将5加入已探索房间
B端待探索集合 {13,11,6}
其中11带有1-11的路径为w;w;w;w;s
其中6带有1-6的路径为w;w;w;w;w

重点:
当循环5的出口到6时, 发现房间6已经存在于A端已探索房间集合中, 也就是说, 本次路径计算结束, 汇合房间id为6, 循环终止.

最终路径 = 16-6的路径 + 1-6的反向路径
即 16-1的路径为 e;e;n;n + rev(w;w;w;w;w) = e;e;n;n;e;e;e;e;e

至此, 一个寻路的原型已经完成, 关于挡路, 单向等等的特殊情况, 只要添加各种判断然后根据后续程序的需要改变每个房间附带的路径描述就可以

moonlily · 发表于 2014-12-17 13:55:00

本帖最后由 moonlily 于 2014-12-17 07:13 AM 编辑

目前在用的一个完整的寻路函数, 其中错误判断以及挡路部分的判断去掉了, 现在的目的仅是讨论地图寻路算法
请各路高手看看有啥可以改进的地方, 一个人的思维有局限, 容易钻死胡同啊.

如果地图数据没有问题, 理论上是可以很快的速度算出mud这种数量级的任意两点间的路径
比如两点间最短距离是100步, 应该够从扬州中心走到很远的地方, 那么循环几十次或几百次的量对于mush来说, 时间可以忽略不计.

map.getpath = function(startroomid,targetroomid) --获取从开始房间号到目标房间号的路径
local sid = tonumber(startroomid)
local tid = tonumber(targetroomid)
local path = ""
local meetid --两端出现的同一个房间号，找到路径
local st = {sid} --开始端路径表
local tt = {tid} --目标端路径表
local stflag = {[sid] = true} --开始端路径表中房间号对照表，对应房间号=true，同时添加同时删除
local ttflag = {[tid] = true} --目标端路径表中房间号对照表，对应房间号=true，同时添加同时删除
local sidt = {} --开始端已添加房间表
local tidt = {} --目标端已添加房间表
sidt[sid] = {dir = ""}
tidt[tid] = {dir = ""}
local sexit,texit,slastid,tlastid --房间连通表，以及当前房间id
while not meetid do --开始循环
sexit = map.parseexit(mdata[st[1]].exits) --获得开始端第一个房间号的连通表
slastid = st[1]
stflag[st[1]] = nil
table.remove(st, 1) --删除当前房间号
if not meetid then
for i in pairs(sexit) do
i = tonumber(i)
if not sidt[i] then --如果未添加过，添加入路径表末尾，并设置为添加过
table.insert(st, i)
stflag[i] = true
sidt[i] = {
dir = sexit[i].dir,
spcmd = sexit[i].spcmd,
fami = sexit[i].fami,
trend = sexit[i].trend,
cmdt = sexit[i].cmdt,
}
sidt[i].path = additems(sidt[slastid].path, sexit[i].dir, ";") --到此房间路径=到之前房间路径+前房间连通dir
if ttflag[i] then --如果此房间号在目标端路径表中，找到路径
meetid = i
break
end
end
end
end
texit = map.parseexit(mdata[tt[1]].exits) --获得目标端第一个房间号的连通表
tlastid = tt[1]
ttflag[tt[1]] = nil
table.remove(tt, 1) --删除当前房间号
if not meetid then
for i in pairs(texit) do
i = tonumber(i)
if not tidt[i] then --如果未添加过，添加入路径表末尾，并设置为添加过
if texit[i].spcmd ~= "oneway" then --如果房间这个出口是单向路径，出口房间不加入目标端路径表，以免无法返回
table.insert(tt, i)
ttflag[i] = true
tidt[i] = {
dir = texit[i].dir,
spcmd = texit[i].spcmd,
fami = texit[i].fami,
trend = texit[i].trend,
cmdt = texit[i].cmdt,
}
tidt[i].path = additems(tidt[tlastid].path, texit[i].dir, ";") --到此房间路径=到之前房间路径+前房间连通dir
local t_curr = map.parseexit(mdata[i].exits) --获得当前房间的联通表
if stflag[i] then --如果此房间号在开始端路径表中，找到路径，单向出口不对比
meetid = i
break
end
else
table.insert(tt, tlastid)
ttflag[tlastid] = true
end
end
end --for
end
end --while
if meetid ~= 0 then
local backpath = map.revpath(tidt[meetid]["path"])
path = additems(sidt[meetid]["path"], backpath, ";")
end
return path
end

复制代码

moonlily · 发表于 2014-12-17 14:06:33

　　有点意思，框架看样子搭的差不多了。但核心部分基本木有太大的体现。如果是有心人，根据这个也能琢磨点 ...
lzkd 发表于 2014-12-17 03:07 AM

北侠的这句著名的话确实有点道理, 不过不完全正确啊, 对于有想法但不知如何下手, 处于迷惘期的人来说, 从一些比较系统的思路,或者程序上, 可以获得很大的启发, 以至于马上豁然开朗也是有可能的.

我就是翻阅了大量北侠技术区的帖子, 才从0开始学用mush的.

seagate · 发表于 2014-12-17 14:31:23

主要是北侠地图数据量级别太低。。。如果是上万数量级的房间，可能就要优化算法了，现在暴力和非暴力的算法差距不大，精细化花费更多功夫，可能收益没有粗暴做法效率高。

moonlily · 发表于 2014-12-17 14:53:52

主要是北侠地图数据量级别太低。。。如果是上万数量级的房间，可能就要优化算法了，现在暴力和非暴力的算法 ...
seagate 发表于 2014-12-17 06:31 AM

具体情况具体应对嘛, 对于mud这种才几百上千个房间的数量级来说, 简单粗暴的算法足以, 就算是上万数量级,也可以通过分区域来缩小计算规模.
如hasea帖子中提出的优化算法, 感觉反而将程序做复杂了, 只能作为最终闲着没事后的精益求精的改进

mud机器需要完善的地方很多, 比如效率, 容错, 自动化程度, 这些地方更需要花精力去完善. 所以我就没再继续研究寻路算法了. 哈哈

imtt · 发表于 2014-12-17 15:53:19

看样子是可以把player变成类NPC的节奏么？
看来我只能是属于"本来不懂的，怎么还是不懂”这类了，预祝神功早日炼成。

puzzlist · 发表于 2014-12-17 16:41:36

从我使用Tintin++的地图功能经验来看，寻路算法基本不用自己去折腾优化
关键是把图画好，特别是一些特别的房间

littleknife · 发表于 2014-12-17 22:30:12

		自动登录	找回密码
密码			注册