spfa四方向自动寻路系统,交通工具,设定速度等 更新v1.1

浮云半仙

RMVA上使用的四方向自动寻路
2016.02.20更新至v1.1版，兼容v1.0功能。新增可设置寻路时移动速度，可以判断不可通行的地形标记（下面有解释）
范例工程，演示了如何使用，以及对寻路功能进行了测试 findpath.zip (1.5 MB, 下载次数: 228)

2016-2-20 17:00 上传

点击文件名下载附件

截图:
在样例工程里面可以使用道具触发自动寻路。如何在事件->脚本中调用，请仔细看脚本开始的说明

npc的自动寻路

npc的自动寻路

地形标记的判断，防止出bug

迷宫寻路

水上寻路

飞艇寻路 飞艇全部可通行


寻路过程中可用任意方向键盘或使用鼠标左键点击停止寻路（鼠标点击停止寻路可以关闭）
执行效率不错，算法本身比较优秀，并且常数优化做得也很到位。大地图不怂。
为什么没有用A*而用了spfa，见脚本前面的说明
↑
以上，祝玩嗨
以下，代码 (spfa四方向寻路系统v1.1) 使用时一定要仔细看前面的用法。
[pre lang="ruby"]=begin
* SPFA 自动寻路系统v1.0 by 浮云半仙  2016.02.19
* 支持小船大船飞行船等交通工具的自动寻路
* 支持寻路过程中，按任意方向键打断寻路。
* 支持寻路过程中，鼠标左键点击游戏窗口中任一点，打断寻路。(往下翻有可选开关)
* 支持特定的地形标记（往下翻，可更改标记的编号）的图块强行判定为不可通行（仅在步行状态下)
    （用途：防止将房顶认为可通行而试图穿越房顶，但实际上又穿越不过去，导致寻路中断)
* 玩家（注意，只是玩家）使用本脚本寻路时，会打开对应的全局开关 （往下翻，有设置开关编号）
* 用法 事件->脚本 FYBX::FindPath.find_path(参数)
  参数以哈希表的形式传入，下列是识别的参数
  start_x,start_y         （可选参数) 起点的x,y坐标，缺省为玩家坐标
  map                      (可选参数) 地图(Game_Map)，缺省为 $game_map
  character                (可选参数) 要移动的对象(Game_Character)
  speed                    (可选参数) 移动速度，注意移动速度的代号如下(与事件 设置移动速度代号相同）：
    代号1:1/8倍速度 代号2:1/4倍速度 代号3:1/2倍速度 代号4:1倍速 代号5:2倍速 代号6:4倍速
                        缺省为移动速度与原来相同，寻路完毕后恢复之前的速度
  target_x, target_y       (必要参数) 目标位置的坐标
  若无法到达，相应的全局变量(注意往下翻，会找到相关设置)会被设置为对应的flag
    flag: 0                  无法到达
          -1                 无需寻路（即起点与终点重合)
          除了0 -1以外的数    起点到终点的最短路径的长度
  *常用用法示例
    玩家以2倍速自动寻路到(20, 15)
      FYBX::FindPath.find_path(:target_x => 20, :target_y => 15, :speed => 5)
    某事件自动寻路到(x,y) (事件->脚本)                  (↑注意这是 => ，不要写成 = )
      FYBX::FindPath(:character => $game_map.events[@event_id], :target_x => x, :target_y => y)
* 若有bug，可以联系qq 1441157749 (作者本人)
* 版权声明：自由使用。使用和转载时请保留声明信息以及作者信息。修改请注明修改自本脚本。
* 一定要注意往下翻，进行设置！
* 常数优化已经做到丧心病狂的地步了！数组避免多次分配空间，大量地实行以空间换时间
* 应该是跑得飞快的
* 题外话：为什么不使用A* （启发式搜索）
    因为种种玄学的原因，事实上，多数情况下A*的实际运行效率低于spfa，why?这是ruby代码
    实现的问题。比如A*算法中，从open_list取出权值最小的元素，用Array做open_list，取
    的时候open_list.min，但是这个min方法，会遍历整个数组，时间复杂度达到O(元素个数)。
    以及，移除权值最小的元素时，很可能导致后面的元素都要向前移动，时间复杂度又高了。
    意思就是说，这些操作在A*算法是常常需要频繁使用的，但是他们实际的工作效率十分低下，
    大大拖慢了A*算法的运行速度！如果想要快速完成取最小元素以及删除元素，需要优先队列
    和链表的数据结构，但是ruby标准库里面并没有。。。我也不想自己手写（懒人+1），因此
    最后决定不使用A*。目前使用的是spfa算法（队列优化的Bellman ford算法)，跑得飞快~
    不过我csdn博客里面有我写的一份A*搜索的c++代码实现。感兴趣的童鞋可以到
    http://blog.csdn.net/u013632138/article/details/50672596 观赏一二
    (博主就是我)
* 扯淡：离开学就剩3天，作业还剩4本，然而我还在淡定地写代码。
* SPFA 自动寻路系统v1.1更新 by 浮云半仙  2016.02.20
  更新内容上面已经写过，增加speed选项，增加对地形标记的判断
=end

module FYBX
  #注意一下这里 寻路结果 全局变量编号。
  FYBX_FINDPATH_NUM_FIND_PATH_RET = 3
  #正在使用本脚本进行寻路的标识的全局开关编号。防止跟事件->设置移动路线的强制移动冲突。
  FYBX_FINDPATH_NUM_FIND_PATH_SWITCH = 10
  #鼠标点击游戏窗口内任一一点，停止寻路的开关。默认打开(=true)，如果需要关闭
  FYBX_FINDPATH_MOUSE_CLICK_STOP = true                        #请赋值false
  #寻路时当作不可通行的图块的地形标记（数据库->图块，右边地形标记)编号，默认为7，
  FYBX_FINDPATH_NOT_PASSABLE_TAG = 7

  #这个是内部使用的。防止被全局开关冲突。。。。
  $fybx_findpath_switch = false
  GetKeyState = Win32API.new("user32", "GetKeyState", "i", "i")

  class SPFAFindPath
    private
    attr_reader :map
    attr_reader :path
    attr_reader :changed_speed
    attr_reader :move_speed

    DIR_TABLE = {:UP => 8, :DOWN => 2, :LEFT => 4, :RIGHT => 6}

    #这里的顺序不要乱改
    DIR = [6, 4, 8, 2]
    DX = [1, -1, 0, 0]
    DY = [0, 0, -1, 1]
    ANTI_DIR = [4, 6, 2, 8]
    ANTI_DIR_BYDIR = [0, 0, 8, 0, 6, 0, 4, 0, 2]


    INF = 0x23333333   #挑个喜庆的数当哨兵
    public
    attr_reader :target_x   #允许修改目标
    attr_reader :target_y
    attr_reader :start_x
    attr_reader :start_y
    attr_reader :character
    attr_reader :is_finding_path
    attr_reader :old_speed
   
    def method_missing(name)
      raise ::NoMethodError, "出错啦！ SPFAFindPath里面可没有叫 #{name.to_s} 的成员方法，请检查拼写"
    end

    def initialize(arg)
      @is_finding_path = false
      @changed_speed = false
      @map = arg[:map]?arg[:map] : $game_map
      if arg[:speed]
        @changed_speed = true
        @move_speed = arg[:speed]
      end
      raise ::ArgumentError, "出错啦！map要求是一个Game_map的实例！" if !@map.is_a?(Game_Map)
      reset_character(arg[:character]?arg[:character]:$game_player)
      raise ::ArgumentError, "出错啦！SPFAFindPath里面的目标的坐标是必填的参数！请补全正确的参数！" if !arg[:target_x] || !arg[:target_y]
      @target_x = arg[:target_x]
      @target_y = arg[:target_y]
      @path = Array.new(@map.width){Array.new(@map.height, nil)}
      @move_speed = (@changed_speed?@move_speed: @character.move_speed)
      @old_speed = @character.move_speed
      #not public
      @in_q = Array.new(@map.width) {Array.new(@map.height) {false}}
      @cost = Array.new(@map.width) {Array.new(@map.height) {INF}}
      @q = Array.new(@map.height * @map.width * 2, 0)
      yield(self) if block_given?
    end

    def reset_target(x, y)
      @target_x = x
      @target_y = y
    end

    def reset_character(c)
      raise ::ArgumentError, "出错啦，character参数要求是Game_CharacterBase的实例" if !c.is_a?(Game_Character)
      @start_x = c.x
      @start_y = c.y
      @character = c
    end
   
    def reset_speed(s)
      @old_speed = @character.move_speed
      @move_speed = s
      @changed_speed = true
    end

    #失败返回false
    def find_path
      @is_finding_path = true
      return 0 if @target_x < 0 || @target_y < 0 || @target_x >= @map.width || @target_y >= @map.height
      return -1 if @start_x == @target_x || @start_y == @target_y
      @in_q.each_with_index {|e, i| @in_q.fill(false)}
      @cost.each_with_index {|e, i| @cost.fill(INF)}
      @path.each_with_index {|e, i| @path.fill(nil)}

      head = 0        #按照左闭右开的惯例
      @q[0] = @start_x
      @q[1] = @start_y
      tail = 2
      @in_q[@start_x][@start_y] = true
      @cost[@start_x][@start_y] = 0
      while head != tail
        cx = @q[head]
        cy = @q[head+1]
        #puts "#{cx} #{cy}"
        head += 2
        for i in 0...4
          dir = DIR
          nx = cx+DX
          ny = cy+DY
          next if !block_passable?(nx, ny, dir)
          #puts "#{nx} #{ny} #{dir}"
          if(@cost[nx][ny] > @cost[cx][cy] + 1)
            @cost[nx][ny] = @cost[cx][cy] + 1
            @path[nx][ny] = ANTI_DIR

            if !@in_q[nx][ny]
              @q[tail] = nx
              @q[tail+1] = ny
              tail += 2
              @in_q[nx][ny] = true
            end
          end
        end
        @in_q[cx][cy] = false
      end

      return 0 if @cost[@target_x][@target_y] == INF  

      note = Array.new(@cost[@target_x][@target_y], 0)
      j = 0
      x = @target_x
      y = @target_y

      #puts cost[x][y]

      #print @path
      while true
        break if !@path[x][y]
        note[j] = ANTI_DIR_BYDIR[@path[x][y]]
        j += 1
        break if x == @start_x && y == @start_y
        case @path[x][y]
          when 2 then
            y += 1
          when 4 then
            x -= 1
          when 6 then
            x += 1
          when 8 then
            y -= 1
        end
      end
      
      $fybx_findpath_switch = true
      $game_switches[FYBX_FINDPATH_NUM_FIND_PATH_SWITCH] = true
      @old_speed = @character.move_speed
      cmds = RPG::MoveRoute.new
      #puts @changed_speed, @move_speed
      cmds.list = (@changed_speed?[RPG::MoveCommand.new(29, [@move_speed])]: [])+note.reverse.map!{|e| RPG::MoveCommand.new(e/2)}+(@changed_speed?[RPG::MoveCommand.new(29, [@old_speed])]: [])
      cmds.list << RPG::MoveCommand.new(0)
      cmds.list << RPG::MoveCommand.new(45, "$fybx_findpath_switch = $game_switches[FYBX_FINDPATH_NUM_FIND_PATH_SWITCH] = false")
      cmds.repeat = false
      @character.force_move_route(cmds)
      
      @is_finding_path = false
      @changed_speed = false
      return @cost[@target_x][@target_y]
    end

    private
    def block_passable?(x, y, dir)
      return false if x < 0 || y < 0 || x >= @map.width || y >= @map.height
      if @character == $game_player
        case $game_player.instance_eval{@vehicle_type}
          when :walk then
            return false if @map.terrain_tag(x,y) ==  FYBX_FINDPATH_NOT_PASSABLE_TAG
            return @map.passable?(x, y, dir) || (@map.ladder?(x, y)&&(dir == 2 || dir == 8))
          when :boat then
            return @map.boat_passable?(x, y)
          when :ship then
            return @map.ship_passable?(x, y)
          when :airship then
            return true
        end
      else
        return @map.passable?(x, y, dir)
      end
    end
  end


  module FindPath
    FINDPATH_ALGORITHM = SPFAFindPath

    def self.find_path(arg)
      @cache ||= {}
      map = arg[:map]? arg[:map]:$game_map
      if @cache[map] == nil
        @cache[map] = FINDPATH_ALGORITHM.new(arg)
      else
        m = @cache[map]
        m.reset_character(arg[:character]? arg[:character]: $game_player)
        m.reset_target(arg[:target_x], arg[:target_y])
        m.reset_speed(arg[:speed]) if arg[:speed]
      end
      return $game_variables[FYBX_FINDPATH_NUM_FIND_PATH_RET] = @cache[map].find_path
    end
   
    def self.read_cache_bymap(map)
      return nil if !@cache
      return @cache[map] if @cache[map]
      return @cache[map] = FINDPATH_ALGORITHM.new(:target_x => 0, :target_y => 0)
    end

    def self.clear_cache
      @cache = {}
    end
  end

end

class Scene_Map
  alias :fybx_update_20160219 :update
  #强制停止角色(player)的自动寻路
  def fybx_force_player_stop_findpath
    $game_player.instance_eval{@move_route_forcing = false}
    #修正速度
    x = FYBX::FindPath.read_cache_bymap($game_map)
    $game_player.instance_eval{@move_speed = x.old_speed}
    $fybx_findpath_switch = $game_switches[FYBX::FYBX_FINDPATH_NUM_FIND_PATH_SWITCH] = false
  end
  def update
    fybx_update_20160219
    if $fybx_findpath_switch && $game_player.move_route_forcing
      if Input.trigger?(:DOWN) || Input.trigger?(:UP) || Input.trigger?(:LEFT) || Input.trigger?(:RIGHT)
        fybx_force_player_stop_findpath
      end
      if FYBX::FYBX_FINDPATH_MOUSE_CLICK_STOP == true
        if FYBX::GetKeyState.call(1) < 0
          fybx_force_player_stop_findpath
        end
      end
    end

  end
end
[/pre]

脚本冲突风险预估：
几率有点大，因为改了Scene_Map的update，很多脚本都会改这里......泥萌懂点脚本的话可以自己协调一下（逃~ )      
高一狗要开学了Orz....{:2_286:}    

hfz521999

先收藏一下  有时间下载下来试试~~~不知道对于武器强化脚本会不会冲突····

_Dot

%%%%%%%神犇
居然用到了SPFA，收下来研究一下，O(∩_∩)O谢谢分享【话说居然才高一被吓到了，果然是人外有人。。

alexncf125

以下，代码 (spfa四方向寻路系统v1.1) 使用时一定要仔细看前面的用法。

请问v1.1在那里???
脚本和范例都是v1.0的说...
啊这...原来是写到下方去了...最新的更新內容不是写在最上方...有点奇怪呢...

alexncf125

Pathfinder.rar (1.42 MB, 下载次数: 67)

2020-9-22 17:39 上传

点击文件名下载附件

附件內的工程有三个问题,
1.玩家的寻路路徑不是最短的
2.女NPC寻路时不会绕过路徑上的障礙物(如图中,要玩家向右移开一步, 女NPC才会移动)
3.女NPC寻路到关口时不知为何会停下
还望LZ有空时能修复完善

MCCF

无权图用A*不香吗

（此图出自NOI2018 D1T1）
感觉SPFA算法还是适合带权图吧，无权图A*因为有启发式函数所以会快很多
另外如果使用二分查找或者直接使用二叉堆，可以将单次加入时间复杂度降为O(logn)，单次取出操作降为O(1)，时间几乎可以忽略不计。
顺便安利一下我的TyPath

浮云半仙

alexncf125 发表于 2020-9-20 13:27
好像有兩个BUG喔及后发现原来第一个和第二个的成因是一样的
1.从黑衣人那领了卷轴后, 馬上使用卷 ...

Wow，感谢fix bug
当初太过naive，这个脚本的架构和算法都不是很优，着实有很多不足，能被选用或者被帮助fix bug实在是荣幸。
---
我已经退坑RM好久了，不过最近搞了一个RMVA实时光线追踪渲染 https://rpg.blue/forum.php?mod=v ... d=482613&page=1 （强行打广告）

浮云半仙

MCCF 发表于 2020-9-20 14:07
无权图用A*不香吗

（此图出自NOI2018 D1T1）

NOI2017退役选手瑟瑟发抖
SPFA是信仰!!!
RM的地图可以使用几何距离作为启发， A*一波确实香

多才不易必自闭

66666666666666