【原创】事件寻路脚本(基于广度优先搜索和RGSS1)

myownroc

旧版本

以下为最新版本
用法：在事件页中使用脚本，输入以下内容。

RUBY 代码复制

BFS.find_path(character, target_x, target_y)

BFS.find_path(character, target_x, target_y)

说明：
如果想要移动主角，character为$game_player;若想移动事件，character为$game_map.events[n] (注：n为相应事件的ID)
注意：该脚本适用于较小的地图（推荐不超过100*100）且工程的系统应基于默认的RGSS。

RUBY 代码复制下载

module BFS
  def self.find_path(character, tx, ty)
    ox, oy = character.x, character.y
    return if (tx > $game_map.width - 1) || (ty > $game_map.height - 1)
    return if !($game_map.passable?(tx, ty, 0, character))
    return if (tx == ox) && (ty == oy)
    checked = []
    father = []
    for i in 0...$game_map.width
      checked << []
      father << []
      for j in 0...$game_map.height
        checked[-1] << 0
        father[-1] << nil
      end
    end
    path = []
    found = false
    checked[ox][oy] = 1
    empty = false
    loop do
      empty = true
      for i in 0...$game_map.width
        for j in 0...$game_map.height
          if checked[i][j] == 1
            checked[i][j] = 2
            if $game_map.passable?(i, j + 1, 2, character) &&
              checked[i][j + 1] == 0
              checked[i][j + 1] = 1
              father[i][j + 1] = [i, j]
            end
            if $game_map.passable?(i - 1, j, 4, character) &&
              checked[i - 1][j] == 0
              checked[i - 1][j] = 1
              father[i - 1][j] = [i, j]
            end
            if $game_map.passable?(i, j - 1, 8, character) &&
              checked[i][j - 1] == 0
              checked[i][j - 1] = 1
              father[i][j - 1] = [i, j]
            end
            if $game_map.passable?(i + 1, j, 6, character) &&
              checked[i + 1][j] == 0
              checked[i + 1][j] = 1
              father[i + 1][j] = [i, j]
            end
          end
          if checked[tx][ty] == 1
            found = true
            break
          end
        end
      end
      for i in 0...$game_map.width
        empty = false if checked[i].include?(1)
      end
      if found || empty
        break
      end
    end
    return if !found
    if found
      x, y = tx, ty
      while [x, y] != [ox, oy]
        dx, dy = father[x][y][0] - x, father[x][y][1] - y
        step = 2 if dy == -1
        step = 4 if dx == 1
        step = 8 if dy == 1
        step = 6 if dx == -1
        path << step
        x, y = father[x][y][0], father[x][y][1]
      end
      path.reverse!
    end
    list = []
    path.each{|e|
      code = 1 if e == 2
      code = 2 if e == 4
      code = 4 if e == 8
      code = 3 if e == 6
      list << RPG::MoveCommand.new(code)
    }
    list << RPG::MoveCommand.new(0)
    skippable = false
    repeat = false
    commands = RPG::MoveRoute.new
    commands.skippable = skippable
    commands.repeat = repeat
    commands.list = list
    if character == nil
      return true
    end
    character.force_move_route(commands)
    return true
  end
end

module BFS


  def self.find_path(character, tx, ty)


    ox, oy = character.x, character.y


    return if (tx > $game_map.width - 1) || (ty > $game_map.height - 1)


    return if !($game_map.passable?(tx, ty, 0, character))


    return if (tx == ox) && (ty == oy)


    checked = []


    father = []


    for i in 0...$game_map.width


      checked << []


      father << []


      for j in 0...$game_map.height


        checked[-1] << 0


        father[-1] << nil


      end


    end


    path = []


    found = false


    checked[ox][oy] = 1


    empty = false


    loop do


      empty = true


      for i in 0...$game_map.width


        for j in 0...$game_map.height


          if checked[i][j] == 1


            checked[i][j] = 2


            if $game_map.passable?(i, j + 1, 2, character) &&


              checked[i][j + 1] == 0


              checked[i][j + 1] = 1


              father[i][j + 1] = [i, j]


            end


            if $game_map.passable?(i - 1, j, 4, character) &&


              checked[i - 1][j] == 0


              checked[i - 1][j] = 1


              father[i - 1][j] = [i, j]


            end


            if $game_map.passable?(i, j - 1, 8, character) &&


              checked[i][j - 1] == 0


              checked[i][j - 1] = 1


              father[i][j - 1] = [i, j]


            end


            if $game_map.passable?(i + 1, j, 6, character) &&


              checked[i + 1][j] == 0


              checked[i + 1][j] = 1


              father[i + 1][j] = [i, j]


            end


          end


          if checked[tx][ty] == 1


            found = true


            break


          end


        end


      end


      for i in 0...$game_map.width


        empty = false if checked[i].include?(1)


      end


      if found || empty


        break


      end


    end


    return if !found


    if found


      x, y = tx, ty


      while [x, y] != [ox, oy]


        dx, dy = father[x][y][0] - x, father[x][y][1] - y


        step = 2 if dy == -1


        step = 4 if dx == 1


        step = 8 if dy == 1


        step = 6 if dx == -1


        path << step


        x, y = father[x][y][0], father[x][y][1]


      end


      path.reverse!


    end


    list = []


    path.each{|e|


      code = 1 if e == 2


      code = 2 if e == 4


      code = 4 if e == 8


      code = 3 if e == 6


      list << RPG::MoveCommand.new(code)


    }


    list << RPG::MoveCommand.new(0)


    skippable = false


    repeat = false


    commands = RPG::MoveRoute.new


    commands.skippable = skippable


    commands.repeat = repeat


    commands.list = list


    if character == nil


      return true


    end


    character.force_move_route(commands)


    return true


  end


end

如果还不能理解以上所述，可以下载附件进行考察。 FindPath.rar (192.79 KB, 下载次数: 389)

2014-8-5 16:53 上传

点击文件名下载附件

冲突评估（欢迎讨论）：
双远景/三远景系统（预测，没有实验证据）
鼠标系统（预测，没有实验证据）
八方行走系统（预测，没有实验证据）
更新记录：
当前新版本比之前一个版本修正了绕路的bug。
提高了算法的效率。

yang1zhi

用条件分歧来设置多个目标点轮流走动时。
每当经过目标点，都会变卡

OCTSJimmy

寻路算法也，楼主好牛！
记得原来有个whbm出的寻路算法，用了下也感觉好牛X。

jiahui5592986

LZ继续加油，争取把八方向的写好

end55rpg

不太懂算法。。理解错误请见谅：
刚刚想了想这个算法，能否考虑
把不可通行标记为3或其他，交换
PASSABLE和标记==0的位置，在判断过的障碍那里就不必2次PASSABLE判断了
最主要,交换之后对于之前搜索过已经变为2标记的位置，将减少一次passable判断的多余
虽然到后面标记为2的已经减少了，但加起来的多余passble就很多了

另外初始化标记为0非要用循环吗- -b

end55rpg

效率能说一下提高的量吗（貌似0.01s一张小地图）
，记得原来有个是障碍越多效率越快，不知LZ您的是不是这样（不清楚算法）

羁绊的守望者

哇哇，广度优先算法出来啦！
我准备写一个深度优先算法~

taroxd

不直接整合进事件的移动路线-接近吗？

其实我挺喜欢禾西的A*脚本的，只给一个寻路的算法核心，整合这种东西交给用户。

shy

还不错~帮了大忙了~