北大侠客行MUD论坛

 找回密码
 注册
搜索
热搜: 新手 wiki 升级
查看: 26420|回复: 31

寻路机器人LUA实现

[复制链接]
发表于 2011-2-11 10:18:31 | 显示全部楼层 |阅读模式
先声明这个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[2],w[3],w[4],w[5],w[6])
        local al=alias.new()
         coroutine.resume(map.Search_co,al:opening(c,w[5],w[6]))
         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[1]
      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[1]
         v.direction=values[2]
         v.linkroomno=values[3]
         v.roomtype=values[4]
         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[1]
      --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[1])
            local v={}
            setmetatable(v, {__index = _Vector})
            --setmetatable(v,Vector)
            v.roomno=values[1]
            v.direction=values[2]
            v.linkroomno=values[3]
            v.roomtype=values[4]
            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[n].roomno,Top[n].direction,Top[n].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[1].roomno,Top[1].linkroomno,Top[2].roomno,Top[2].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[1])
    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
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 10:23:03 | 显示全部楼层
高手啊 - -  进我们创意群不
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 10:23:19 | 显示全部楼层
一头雾水
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 11:05:48 | 显示全部楼层
收藏。前辈高手威武!5
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 11:25:13 | 显示全部楼层
胡哥上QQ,有事商量
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 16:20:02 | 显示全部楼层
代码跳过,论坛上看不清。我的mapper.dll是这样的。

一个表,两个stack。
表为代表所有room的bool数组,初始值全false
一个stack代表正向路径,一个stack为反向路径(为了效率优化,不然一个stack也能处理了)
复制stack,逐一弹出储存的上一次遍历的room
遍历room的出口,如果表内为false,代表没走到过,表内设为true,压到新stack内。
复制的stack全走完,开始复制新的stack继续走。
直到stack为空(无路可走),或者room表对应值为true(走同了)

当然,我的mapper.dll里还有步长设置,tag,flylist等,略微复杂点,但基本原理就是这样了。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2011-2-11 16:29:23 | 显示全部楼层
原帖由 jarlyyn 于 2011-2-11 04:20 PM 发表
代码跳过,论坛上看不清。我的mapper.dll是这样的。

一个表,两个stack。
表为代表所有room的bool数组,初始值全false
一个stack代表正向路径,一个stack为反向路径(为了效率优化,不然一个stack也能处理了)
复 ...

很多人都是用的dll com技术开发的 我原来也是这样的
不过现在改写成lua 有好处兼容性好。
dll必须修改 mush sandbox
还会有中文乱码问题,需要经过一次转换
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 16:31:29 | 显示全部楼层
原帖由 ptouch 于 2011-2-11 04:29 PM 发表

很多人都是用的dll com技术开发的 我原来也是这样的
不过现在改写成lua 有好处兼容性好。
dll必须修改 mush sandbox
还会有中文乱码问题,需要经过一次转换


dll 不需要转换,com才需要。
我给的是程序思路,和实现方式没关系……
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
发表于 2011-2-11 16:39:12 | 显示全部楼层
直接用lua写,房间表结构放一table里,最短路经用广度优先算法,区域遍历用递归。这几乎是最有效的编码方式了。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
 楼主| 发表于 2011-2-11 17:02:30 | 显示全部楼层
直接写在table 里面修改起来麻烦。数据一般要和程序分离
我用了sqlite 数据库
最短路径 一般用双向遍历算法比较快
基本上 零点几秒就能算出来了 很快。
北大侠客行Mud(pkuxkx.com),最好的中文Mud游戏!
您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|北大侠客行MUD ( 京ICP备16065414号-1 )

GMT+8, 2024-11-1 03:29 PM , Processed in 0.010926 second(s), 14 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表