寻路机器人LUA实现
先声明这个lua 代码是书剑不是北大侠客行(避免被和谐)基本原理都相同，有兴趣可以自己改下。
map 基本目标归纳起来只有 2点
1 定位(给定房间信息，找到对应房间号)
2 路径生成(给出开始房间号和结束房间号，生成两点之间最短路径)
房间描述格式
【区域】
【相对关系】
【房间名称】
【房间描述】
【天气描述】
【出口描述】
书剑mud特殊地方
有些房间 出口数目 房间描述会根据时间变化
所以一个房间号同时可以对应多个房间信息
mud_room 表基本结构
roomno , int
zone, string
relation, string
roomname, string
description, string
exits, string
roomtype , string roomtype 用来记录房间类型 我的应用里面有 D =danger 有auto kill npc，C 集群 下面对应多个子房间 迷宫处理时候用到，V 虚拟房间用来处理有些房间随时间变化出口变化情况，比如夜晚城门关闭，房间通路没有了，根据条件来生成不同路径
两点路径生成(图的遍历)
详情可以去看看清华版的数据结构的图的遍历。
我这里简单介绍下基本思想
1 从开始点 把所有和开始点 有连接的房间号 加入 开始队列(top)
2 从结束点 把所有和结束点 有连接的房间号 加入 结束队列(bottom)
3 比较两个队列的数目，选取小的队列(双头选择) 设置为当前队列(current)
4 current 出队列获得 current_roomno (获取第一个房间号，并从队列删除)，把所有和current_roomno 有连接的房间号加入 current
5 重复 3,4 步骤直到 top 和 bottom 队列中有重合房间号出现(seed_roomno)
6 最后根据seed_roomno 到 top ，bottom 反向推导出路径
mud_entrance 表
roomno ,int
linkroomno,int
direction,string
代码部分
--数据结构 向量
local vector={
roomno=nil,--当前节点房间号
direction="", --方向
linkroomno=nil, --接连节点房间号
roomtype="", --房间类型
}
local Bottom={}
local Bottom_buffer={} --底部检索队列
local Bottom_buffer_len=0
local Bottom_pre_existing={}
local Top={}
local Top_buffer={} --顶部检索队列
local Top_buffer_len=0
local Top_pre_existing={}
local map={
new=function()
local mp={}
setmetatable(mp,{__index=map})
return mp
end,
Search_co={},
opentime=nil,
}
function map:Search_end(path,room_type)--
end
--检查正向有重合节点
local function T_Contain(roomno)
--print("T目标",roomno)
for i,t in ipairs(Top) do
if t.linkroomno==roomno then
return true
end
end
return false
end
--检查反向有重合节点
local function B_Contain(roomno)
--print("B目标",roomno)
for i,b in ipairs(Bottom) do
if b.roomno==roomno then
return true
end
end
return false
end
--检查是否存在
local function pre_existing(existing_rooms,roomno)
for i,e in ipairs(existing_rooms) do
if e==roomno then
return true
end
end
return false
end
local function opening(c)--确定开放时间
wait.make(function()
world.Send("time")
local l,w=wait.regexp("^(> |)现在是书剑(.*)年(.*)月(.*)日(.*)时(.*)。$",15)
if l==nil then
opening(c)
return
end
if string.find(l,"现在是书剑") then
print(w,w,w,w,w)
local al=alias.new()
coroutine.resume(map.Search_co,al:opening(c,w,w))
return
end
wait.time(15)
end)
end
local function virtual(v)--虚拟房间
--通过
local cond
if map.opentime==true then
cond=true
else
local condition= v.direction
opening(condition)
cond=coroutine.yield()
map.opentime=cond --记忆
end
--print("结果:",cond)
if cond then
for _,pre in ipairs(Bottom) do
--print(pre.roomno," ",pre.direction," ",pre.linkroomno)
if pre.linkroomno==v.roomno then
v.roomno=pre.roomno
v.direction=pre.direction
break
end
end
--print("top")
for _,pre in ipairs(Top) do
--print(pre.roomno," ",pre.direction," ",pre.linkroomno)
if pre.linkroomno==v.roomno then
v.roomno=pre.roomno
v.direction=pre.direction
break
end
end
else
--print("不通")
v.roomno="-10"
v.linkroomno="0"
end
v.roomtype=''
--print("test3333")
end
--从结束节点开始搜索
local function Bottom_Start()
--print("BOTTOM------------------------------")
while true do
--buffer 长度
Bottom_buffer_len=table.getn(Bottom_buffer)
if Bottom_buffer_len>Top_buffer_len then
break
end
--循环读取
local linkroomno
linkroomno=Bottom_buffer
table.remove(Bottom_buffer,1)
--print("Bottom_LENGth",table.getn(Bottom_buffer))
--print("TOP_LENGth",table.getn(Top_buffer))
local sql="SELECT MUD_Entrance.roomno,MUD_Entrance.direction,MUD_Entrance.linkroomno,MUD_Room.roomtype from MUD_Entrance,MUD_Room where MUD_Room.roomno=MUD_Entrance.roomno and linkroomno=" ..linkroomno
--print(sql)
DatabasePrepare ("db", sql)
rc = DatabaseStep ("db")
while rc == 100 do
--print("row",i)
local values=DatabaseColumnValues ("db")
local v={}
setmetatable(v, {__index = _Vector})
--setmetatable(v,Vector)
v.roomno=values
v.direction=values
v.linkroomno=values
v.roomtype=values
if v.roomtype==nil then
v.roomtype=""
end
if v.roomtype=="V" then
virtual(v)
--print("virtual" ," roomtype ",v.roomtype," roomno ",v.roomno)
end
--print("vector2",v.roomno,v.direction,v.linkroomno,v.roomtype)
--读取数据库 检查top 没有插入 Bottom & Bottom_buffer
if T_Contain(v.roomno)==true then
-- print("true","Bottom",v.roomno)
table.insert(Bottom,v)
DatabaseFinalize ("db")
return true,v.roomno--找到重合点
elseif pre_existing(Bottom_pre_existing,v.roomno)==false then
--print("false")
table.insert(Bottom_buffer,v.roomno)
table.insert(Bottom_pre_existing,v.roomno)
table.insert(Bottom,v)
--print("Bottom_LENGth",table.getn(Bottom_buffer))
-- print("TOP_LENGth",table.getn(Top_buffer))
end
rc = DatabaseStep ("db")
end
DatabaseFinalize ("db")
end
--for i,v in ipairs(Bottom) do print(v.roomno,v.linkroomno,v.direction) end
--print("------------------------------BOTTOM")
--DatabaseClose ("db")-- close it
return false,nil
end
--从开始节点开始搜索
local function Top_Start()
--print("Top------------------------------------------")
--co=coroutine.create(function()
while true do
--buffer 长度
Top_buffer_len=table.getn(Top_buffer)
--print("长度",Top_buffer_len,Bottom_buffer_len)
if Top_buffer_len > Bottom_buffer_len then
break
end
--循环读取
local roomno
roomno=Top_buffer
--print(roomno)
table.remove(Top_buffer,1)
local sql="SELECT MUD_Entrance.roomno,MUD_Entrance.direction,MUD_Entrance.linkroomno,MUD_Room.roomtype from MUD_Entrance,MUD_Room where MUD_Room.roomno=MUD_Entrance.roomno and MUD_Entrance.roomno=" ..roomno
--print(sql)
DatabasePrepare ("db", sql)
rc = DatabaseStep ("db")
while rc == 100 do
local values=DatabaseColumnValues ("db")
-- tprint (values)
--print(values)
local v={}
setmetatable(v, {__index = _Vector})
--setmetatable(v,Vector)
v.roomno=values
v.direction=values
v.linkroomno=values
v.roomtype=values
if v.roomtype==nil then
v.roomtype=""
end
if v.roomtype=="V" then
virtual(v)
--print("virtual" ," roomtype ",v.roomtype," roomno ",v.roomno)
end
--print("vector1",v.roomno,v.direction,v.linkroomno,v.roomtype)
--读取数据库 检查top 没有插入 Bottom & Bottom_buffer
if B_Contain(v.linkroomno)==true then
--print("true","Top",v.linkroomno)
table.insert(Top,v)
DatabaseFinalize ("db")
return true,v.linkroomno--找到重合点
elseif pre_existing(Top_pre_existing,v.linkroomno)==false then
--print("false")
--print("vector2",v.roomno,v.direction,v.linkroomno)
table.insert(Top_buffer,v.linkroomno)
table.insert(Top_pre_existing,v.linkroomno)
table.insert(Top,v)
--local n
--n=table.getn(Top)
--print("TOP",Top.roomno,Top.direction,Top.linkroomno)
--tprint(Top)
--print("Bottom_LENGth",table.getn(Bottom_buffer))
--print("TOP_LENGth",table.getn(Top_buffer))
end
rc = DatabaseStep ("db")
end
DatabaseFinalize ("db")
end
return false,nil
--end)
--print(Top.roomno,Top.linkroomno,Top.roomno,Top.linkroomno)
--print("-------------------------------------Top")
--return coroutine.resume(co)
end
local function top_serialize(linkroomno)
local v={}
for i,v in ipairs(Top) do
if v.linkroomno==linkroomno then
--print(v.roomno,v.linkroomno,v.direction)
return v.roomno,v.direction,v.roomtype
end
end
return
end
local function bottom_serialize(roomno)
local v={}
for i,v in ipairs(Bottom) do
if v.roomno==roomno then
--print(v.roomno,v.linkroomno,v.direction)
return v.linkroomno,v.direction,v.roomtype
end
end
end
local function Serialize(seed)
local T_Serialize=""
local B_Serialize=""
local T_room_type=""
local B_room_type=""
local roomno
local direction
local roomtype
roomno,direction,roomtype=top_serialize(seed)
while roomno~=nil do
T_Serialize=direction .. ";" .. T_Serialize
T_room_type=roomtype .. ";" .. T_room_type
--print("roomno:",roomno,"dx:",direction)
roomno,direction,roomtype=top_serialize(roomno)
--print("ss2",roomno,direction)
end
--print("T_Serialize",T_Serialize)
roomno,direction,roomtype=bottom_serialize(seed)
while roomno~=nil do
B_Serialize=B_Serialize .. direction .. ";"
B_room_type=B_room_type .. roomtype .. ";"
roomno,direction,roomtype=bottom_serialize(roomno)
--print("roomno:",roomno,"dx:",direction)
end
local path
path=T_Serialize .. B_Serialize
local room_type
room_type=T_room_type .. B_room_type
print(path)
print(room_type)
return path,room_type
end
function map:Search(StartRoomNo,EndRoomNo,opentime)--异步 开始房间 结束房间 时间 白昼 或 夜晚
map.opentime=opentime
Bottom_buffer_len=1
Top_buffer_len=1
Top={}
Bottom={}
Top_buffer={}
Bottom_buffer={}
Top_pre_existing={}
Bottom_pre_existing={}
--print("BF",Bottom_buffer)
table.insert(Top_buffer,StartRoomNo)
table.insert(Top_pre_existing,StartRoomNo)
table.insert(Bottom_buffer,EndRoomNo)
table.insert(Bottom_pre_existing,EndRoomNo)
local h={}
setmetatable(h, {__index = _Vector})
--setmetatable(h,Vector)
h.roomno=nil
h.linkroomno=StartRoomNo
h.direction=nil
local e={}
e.roomno=EndRoomNo
e.linkroomno=nil
e.direction=nil
setmetatable(e, {__index = _Vector})
--setmetatable(e,Vector)
table.insert(Top,h)
table.insert(Bottom,e)
local result
local roomno
map.Search_co={}
map.Search_co=coroutine.create(function()
while true do
if Bottom_buffer_len==0 or Top_buffer_len==0 then
print("没有通路")
break
end
result,roomno = Top_Start()
if result==true then
break
else
result, roomno=Bottom_Start()
if result==true then
break
end
end
end
--print("roomno:",roomno)
local path
local room_type
path,room_type=Serialize(roomno)
--[[print("search: ----start---------")
print(path,room_type)
print("search: ----end---------")]]
self.Search_end(path,room_type)
end)
--print(coroutine.resume(co))
coroutine.resume(map.Search_co)
--return _path,_roomtype
end 高手啊 - -进我们创意群不 一头雾水ttk_01 收藏。前辈高手威武！yct15 胡哥上QQ，有事商量 代码跳过，论坛上看不清。我的mapper.dll是这样的。
一个表，两个stack。
表为代表所有room的bool数组，初始值全false
一个stack代表正向路径，一个stack为反向路径(为了效率优化，不然一个stack也能处理了)
复制stack,逐一弹出储存的上一次遍历的room
遍历room的出口，如果表内为false,代表没走到过，表内设为true,压到新stack内。
复制的stack全走完，开始复制新的stack继续走。
直到stack为空(无路可走)，或者room表对应值为true(走同了)
当然，我的mapper.dll里还有步长设置，tag,flylist等，略微复杂点，但基本原理就是这样了。 原帖由 jarlyyn 于 2011-2-11 04:20 PM 发表 http://pkuxkx.com/forum/images/common/back.gif
代码跳过，论坛上看不清。我的mapper.dll是这样的。
一个表，两个stack。
表为代表所有room的bool数组，初始值全false
一个stack代表正向路径，一个stack为反向路径(为了效率优化，不然一个stack也能处理了)
复 ...
很多人都是用的dll com技术开发的 我原来也是这样的
不过现在改写成lua 有好处兼容性好。
dll必须修改 mush sandbox
还会有中文乱码问题，需要经过一次转换 原帖由 ptouch 于 2011-2-11 04:29 PM 发表 http://www.pkuxkx.com/forum/images/common/back.gif
很多人都是用的dll com技术开发的 我原来也是这样的
不过现在改写成lua 有好处兼容性好。
dll必须修改 mush sandbox
还会有中文乱码问题，需要经过一次转换
dll 不需要转换，com才需要。
我给的是程序思路，和实现方式没关系…… 直接用lua写，房间表结构放一table里，最短路经用广度优先算法，区域遍历用递归。这几乎是最有效的编码方式了。 直接写在table 里面修改起来麻烦。数据一般要和程序分离
我用了sqlite 数据库
最短路径 一般用双向遍历算法比较快
基本上 零点几秒就能算出来了 很快。