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

myownroc

[fold=旧版本]用法：在事件页中使用脚本，输入以下内容。
[pre lang="ruby" line="1"]f = BFS.new
f.find_path(character, tx, ty)[/pre]
说明：
如果想要移动主角，character为$game_player;若想移动事件，character为$game_map.events[n] (注：n为相应事件的ID)
注意：该脚本适用于较小的地图（推荐不超过50*50）且工程的系统应基于默认的RGSS。
[pre lang="ruby" line="1" file="BFS"]# This algorithm is based on Breadth-First-Search.
# Due to BFS algorithm, we suggest your map's area be below 50*50.
# In a word, this algorithm is suitable for small map.
# If you want to use this method, please write following codes
# in the events pages:
#
# f = BFS.new
# f.find_way(character, target_x, target_y)
#
# If you want to move your own player, 'character' would be '$game_player'
# If you want to move a event(ID :n), 'character' would be '$game_map.events[n]'
# Once you finish what we had said above, the selected character would move to
# the target point.
class BFS
  def find_path(character, target_x, target_y)
    origin_x, origin_y = character.x, character.y
    # exit when it's out of map
    return if ((target_x > $game_map.width - 1) ||
    (target_y > $game_map.height - 1))
    # exit when it is not accessable
    return if (!$game_map.passable?(target_x, target_y, 0, character))
    # exit when target is where character is.
    return if (target_x == character.x and target_y == character.y)
    # find the path
    openlist = []
    closelist = []
    father = []
    for i in 0...$game_map.width
      father << []
      for j in 0...$game_map.height
          father[-1] << nil
      end
    end
    path = []
    found = false
    openlist << [character.x, character.y]
    while !openlist.empty? and !found
      openlist.each{|e|
        # delete & move
        openlist.delete(e)
        closelist << e
        # down
        if $game_map.passable?(e[0], e[1] + 1, 2, character) &&
          !closelist.include?([e[0], e[1] + 1]) &&
          !openlist.include?([e[0], e[1] + 1])
          openlist << [e[0], e[1] + 1] if !openlist.include?([e[0], e[1] + 1])
          father[e[0]][e[1] + 1] = [e[0], e[1]] if !closelist.include?([e[0], e[1] + 1])
        end
        # left
        if $game_map.passable?(e[0] - 1, e[1], 4, character) &&
          !closelist.include?([e[0] - 1, e[1]]) &&
          !openlist.include?([e[0] - 1, e[1]])
          openlist << [e[0] - 1, e[1]] if !openlist.include?([e[0] - 1, e[1]])
          father[e[0] - 1][e[1]] = [e[0], e[1]] if !closelist.include?([e[0] - 1, e[1]])
        end
        # up
        if $game_map.passable?(e[0], e[1] - 1, 8, character) &&
          !closelist.include?([e[0], e[1] - 1]) &&
          !openlist.include?([e[0], e[1] - 1])
          openlist << [e[0], e[1] - 1] if !openlist.include?([e[0], e[1] - 1])
          father[e[0]][e[1] - 1] = [e[0], e[1]] if !closelist.include?([e[0], e[1] - 1])
        end
        # right
        if $game_map.passable?(e[0] + 1, e[1], 6, character) &&
          !closelist.include?([e[0] + 1, e[1]]) &&
          !openlist.include?([e[0] + 1, e[1]])
          openlist << [e[0] + 1, e[1]] if !openlist.include?([e[0] + 1, e[1]])
          father[e[0] + 1][e[1]] = [e[0], e[1]] if !closelist.include?([e[0] + 1, e[1]])
        end
        # get target?
        if openlist.include?([target_x, target_y])
          found = true
          break
        end
      }
    end
    # exit when we can't find a path
    return if !found
    # create move command & carry out
    if found
      x, y = target_x, target_y
      while [x, y] != [origin_x, origin_y]
        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
    # move
    if character == nil
      # continue
      return true
    end
    # force_move
    character.force_move_route(commands)
    # continue
    return true
  end
end[/pre]
[pre lang="ruby" line="1" file="BFS"]class BFS
  def 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[j] == 1
            checked[j] = 2
            if $game_map.passable?(i, j + 1, 2, character) &&
              checked[j + 1] == 0
              checked[j + 1] = 1
              father[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[j - 1] == 0
              checked[j - 1] = 1
              father[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.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[/pre][/fold]
以下为最新版本
用法：在事件页中使用脚本，输入以下内容。
[pre lang="ruby" line="1"]BFS.find_path(character, target_x, target_y)[/pre]
说明：
如果想要移动主角，character为$game_player;若想移动事件，character为$game_map.events[n] (注：n为相应事件的ID)
注意：该脚本适用于较小的地图（推荐不超过100*100）且工程的系统应基于默认的RGSS。
[pre lang="ruby" line="1" file="BFS"]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[j] == 1
            checked[j] = 2
            if $game_map.passable?(i, j + 1, 2, character) &&
              checked[j + 1] == 0
              checked[j + 1] = 1
              father[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[j - 1] == 0
              checked[j - 1] = 1
              father[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.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[/pre]
如果还不能理解以上所述，可以下载附件进行考察。 FindPath.rar (192.79 KB, 下载次数: 389)

2014-8-5 16:53 上传

点击文件名下载附件

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

shy

还不错~帮了大忙了~

taroxd

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

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

羁绊的守望者

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

end55rpg

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

end55rpg

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

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

jiahui5592986

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

OCTSJimmy

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

yang1zhi

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