RGSS3下A星寻路的解说与实现

余烬之中

写在前面

[fold]

RM中，事件的移动模式有三种：随机、接近、自定义（事实上这是前几天我帮忙翻译F1的时候才注意到的），其中的接近常用于各种各样的追逐战……但是事件的接近模式似乎有些傻？


像这样，对面的姐姐敌人毫无疑问地被一条大河噗挡住了。

事实上不仅是RM游戏，各种各样的RPG都面临这样的问题。也正是因此诞生了各种各样的寻路算法，让NPC的移动看上去更加智能化。我们今天要介绍的就是A星（A*）算法。

其实，一定有很多人已经在VA平台上实现过了这个算法，这里只是向大家介绍这个算法的原理，以及在RGSS3上的实现过程，以供参考和学习，算是个教程式的发布，当然在最后也会贴出成品和使用方法。

如果大家发现本文的错误，请一定要指出，毕竟不能误人子弟；有不足之处，也请不吝赐教。

用语尽量易于理解（也只能这样，毕竟我是根据记忆来写），所用的图形素材全部自制。

要注意的是，虽然我告诉了你算法和实现步骤及它们的解说，但是我还是不允许你把我的东西直接搬走然后说是你的。

废话到此为止。

[/fold]

A星寻路算法

[fold]

A星寻路算法是一种寻路算法（这当然是不可不说的废话），让我们直入主题。在讨论算法本身的时候，我们首先只需要考虑最简单的情况：

• 一个地图，由图块组成
• 图块分为可以通行（黑色）的和不可通行的（白色）
• 一个出发点（红色）
• 一个终止点（蓝色）
  

我们的地图就像这样：


我们把地图分为正方形的小块，每个小块叫做一个节点。

现在，既然我们需要找到一条从红色到蓝色的路径，基本思想是很明确的：让程序搜索整个区域，找到一条无障碍而总长度最短的路径。拆开来看，我们需要程序做这些事情：

搜索区域，直到找到目标；
模拟路径，并能判断路径的“好坏”且依此更改路径。

好，现在继续分析。

“搜索路径”，这是很简单的，我们只需要确定一个“当前节点”，然后搜索它的八个方向的相邻节点，然后把“当前格”标记为“已被搜索”，然后把它的八个子节点依次当做“当前节点”，重复这样的操作就可以了。

再想想，这个想法还可以细化：如果某一个子节点是不可通行的，我们就没有必要去考虑它了，这样，我们就减少了很多的工作量。

而且我们可以从目标开始搜寻，一直找到出发点，就像我们走迷宫时从出口找入口一样。

初步思路的图示：
（当前节点用渐变色表示，子节点用灰色表示，已被搜索的用深红褐色表示）


但是，如果我们从子节点中选择“当前节点”的顺序是不分先后的，我们会面临这样的窘境：明明向左多搜索几个节点就可以完成的工作，却无谓的向右搜索的同样的距离。

因此，我们需要一个用来表示一个节点“是否有利于向出发点靠近”的参数，我们把它称为F，这是A星算法的一个重要概念。

我们需要让F值能够衡量当前节点的有利程度，这个程度应该由两个值来影响：它距离目标的距离G，以及它距离出发点的估计距离H（为什么是估计距离？）。

它距离目标的距离是可以知道的，因为我们是从目标开始搜寻，找到当前点的，我们可以记录下沿途的距离，这就是当前点距离目标的距离G。

计算G的方法多样，我们这样来：每两个水平或竖直相邻节点间的距离为10，对角线方向相邻节点间的距离为14，这个数字代表着在节点间移动的代价，可以根据实际更改一下，比如，假设你想要让对角线方向移动的代价更高，你可以让它比纵横方向代价的1.414倍更多。

但是它距离出发点的距离是未知的，因为我们还没有去那里，只能估计。根据A星算法的具体用途，估计的方法多种多样，我们采用最简单的：把当前点和目标点的水平距离和竖直距离加起来，不管有没有障碍，得到H：


好了，现在我们可以得到某个节点的有利程度F（计算F的方式多样，我们同样采用最简单的F=G+H），我们再选取子节点作为当前节点的时候，就选择这个值最小的，因为F值代表着“采用这条路径所花的代价”。如果这条路径走下去发现不幸被堵死了，我们还是可以退而求其次走其它的路：


我们现在打算把每个节点的F、G、H全部标记在节点上，同时让子节点记住它老子是谁保存一个指向父节点的指针：
（初始节点的G为零，H值按上述方法估算）


然后选择F值最小的为父节点，继续搜索，这时我们发现：它的子节点也同时作为其它节点的子节点，而且根节点（也就是目标点）也是它的一个子节点，这时我们这样处理：

• 如果子节点是根节点，那么不去理会，没有必要走回头路；
• 如果子节点是未被搜索过的节点，那么搜索它，计算F值；
• 如果子节点是已被搜索过的节点，且不是根节点，那么计算“将该节点作为自己子节点后，该节点的F值”，并与原F值比较，如果新的值更小，则将其作为自己的子节点，也就是让子节点那个指向父节点的指针指向自己，否则什么都不做（为什么？）。
  

前两点很好理解，我们重点说明第三点。

如果有一个节点A，它在节点B与节点C的公共子节点范围中，它作为B的子节点时，F值为30，作为C的子节点时，F值为28，比30小，这意味着：通过C节点到达A节点，所花费的代价更小，所以我们走这条路。还不是很理解？不要紧，后面就清楚了。

既然已经有了处理办法，我们就继续我们的搜索：




好，在进行下一步搜索时，别想当然地往下画，牢记我们的规则，选取F值最小的，现在的情况是这样：


我们看到有两个F为17的节点，分别在目标点的左边和下边，我们还要搜索下边的那个吗？当然不需要，因为我们已经将它作为父节点搜索过了。我们应该做个标记。


现在，我们可以很轻易的知道，开始搜索谁了，叛徒就是你！来人！拿下！开始搜索它吧。






………………等等！发生了什么！已经进展到了这个程度了吗！！

当然了，既然已经有了处理方法，重复处理就可以了。

现在我们正准备完成关键性的一步……




好了！完成！还没有完成……

事实上，在以前的A星算法中，到达这一步（找到了出发点）就已经成功了，但是有时候，这样找到的路径可能比最路径长那么一步两步。具体例子我就不再举了，反正记得：要在将出发点搜索完以后再宣告成功，比如这样：


现在生成路径，有些朋友已经看出来了：


跟着指向父节点的指针走就行了

好，现在整理我们的算法：

1. 首先，获取出发点和终止点;
   
2. 
   
3. 初始化两个数组：名字叫open和close,
   
4. 
   
5. open中存放我们已经知道，但是还没有搜索的节点；
   
6. 
   
7. close中是已经被搜索了的节点。
   
8. 
   
9. 一开始两个数组都是空的。
   
10. 
    
11. 初始化终止点的F值，并把终止点放到open里，准备搜索；
    
12. 
    
13. 循环：
    
14.   从open表中抽取F值最小的节点 并把它从open中删去
    
15.   遍历它的子节点：
    
16.     如果 子节点在open中（说明它已经是其它节点的子节点）
    
17.       就判断如果走这条路 它的F值是否更小 是的话把它的父节点改为自己 并更新F值 否的话什么都不做
    
18.     如果不在open中
    
19.       如果在close中（说明它已经被搜索过了）
    
20.         就看下一个子节点
    
21.       否则（是一个全新的节点）
    
22.         把它的父节点改为自己 计算F值
    
23.         把它添加到open表中
    
24.       条件结束
    
25.     条件结束
    
26.   遍历结束
    
27.   （这个节点已经搜索完了）
    
28.   把这个节点放入close中
    
29.   如果出发点在close表中（找到了路径） 那么跳出循环
    
30.   如果open表已经空了 那么跳出循环
    
31. 回到循环
    
32. 
    
33. 如果出发点在close表中 那么找到了路径 继续下去 否则返回“没有找到路径”
    
34. 
    
35. 从出发点出发，依次寻找父节点，即生成了路径。

复制代码

以上就是简单的A星算法。

现在，准备看看A星算法在RGSS3的实现吧。

[/fold]

在RGSS3的实现

[fold]

实现之前，先了解一些事实：

RGSS3中，事件的移动都是有方向的（废话），在Game_Character类中的move_straight等一系列方法中都用数字表示方向，具体对应如下图：


判断某个位置是否可以通行可以通过$game_map.passable?(x, y, dir)（？）来做到，大约是这个意思：当某角色站在(x, y)这个点的时候 向dir方向是否可以行走

这是一点 另外 如果要判断“某一个点(x, y)是否可以*抵达*” 就需要稍微处理一下：

1. 4个方向都试一试
   
2. d = 方向
   
3. x = x + (d == 4 ? -1 : d == 6 ? 1 : 0)
   
4. y = y + (d == 8 ? -1 : d == 2 ? 1 : 0)
   
5. $game_map.passable?(x, y, 10 - d)

复制代码

拿上面的图打比方，我要判断5这个位置是否可以抵达，我就先退到8，然后朝2这个方向走，如果不行，我就退到2，朝8走一走；再不行从4到6；从6到4。只要有一个可以通行，我们就认为5这个位置是可以到达的。代码暂时看不懂不要紧，有点绕，把条件运算符拆开写就很好懂了。

好 现在难点都说完了 开始动工

为了简便 我们只考虑四方向行走

[pre lang="ruby" line="1"]module AStar
  # 新建一个模块 我们将在这里开始
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    # 新建节点类 它的实例即节点
    attr_accessor :x, :y, :g, :h, :d
    # 节点类保存着节点的各种属性：
      # 横纵坐标
      # G值
      # H值
      # 之所以没有F 是因为F可以通过 g + h 得到
      # 父节点相对于自己的方向
    # 用一个数组进行初始化 数组包含的信息是它的横纵坐标
    # 比如 Point.new([64, 75])
    def initialize(*point)
      self.x, self.y = point
    end
  end
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target)
    # 寻路的方法
    # 接受两个数组作为参数
    # 分别代表出发点和终止点的横纵坐标
    # 调用示例：
    # AStar.make_route([34, 75], [66, 32])
  end
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target)
    target = Point.new(*target)
    # 建立终止点的节点对象
    return [] unless [2, 4, 6, 8].any? do |d|
      x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
      y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
      $game_map.passable?(x, y, 10 - d)
    end
    # 上面这一段可以拆成两部分
    #
    # flag = [2, 4, 6, 8].any? do |d|
    #  x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
    #  y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
    #  $game_map.passable?(x, y, 10 - d)
    # end
    # # 2, 4, 6, 8四个方向（即上下左右）是否可以到达终止点？
    #
    # return [] unless flag
    # # 如果一个都不能到达 就返回一个空路径 因为根本不可能找到路径
    # # 毕竟终止点是不可到达的
  end
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target)
    target = Point.new(*target)
    return [] unless [2, 4, 6, 8].any? do |d|
      x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
      y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
      $game_map.passable?(x, y, 10 - d)
    end
    origin = Point.new(*origin)
    # 建立出发点节点
    target.g = 0
    # 初始化目标点的G值
    target.h = (target.x - origin.x).abs + (target.y - origin.y).abs
    #　以及H值
    open  = [target]
    # 初始化open列表 只有一个元素 即 target
    close = []
    # 初始化close列表 因为还没有访问任何东西 所以是空的
    include_open  = ->(x, y){  !open.find{|pt| pt.x == x && pt.y == y}.nil? }
    include_close = ->(x, y){ !close.find{|pt| pt.x == x && pt.y == y}.nil? }
    # 建立两个方法，可以判断“坐标为x, y的点是否在open/close表内”
    # 这两句看不懂不要紧 明白是干什么的就可以了
  end
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target)
    target = Point.new(*target)
    return [] unless [2, 4, 6, 8].any? do |d|
      x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
      y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
      $game_map.passable?(x, y, 10 - d)
    end
    origin = Point.new(*origin)
    target.g = 0
    target.h = (target.x - origin.x).abs + (target.y - origin.y).abs
    open  = [target]
    close = []
    include_open  = ->(x, y){  !open.find{|pt| pt.x == x && pt.y == y}.nil? }
    include_close = ->(x, y){ !close.find{|pt| pt.x == x && pt.y == y}.nil? }
    # 开始循环 如果open表不是空的
    until open.empty?
      nod = open.shift
      # 从open表中取出第一个节点 作为当前节点
      # 然后把它从open表的名单中删除
      # 至于为什么是第一个 下面说明

      # 遍历四个方向
      [2, 4, 6, 8].each do |d|
        next unless $game_map.passable?(nod.x, nod.y, d)
        # 如果我站在当前节点 向d方向不能通行的话 就忽略这个方向
        # 否则继续
        x = nod.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
        y = nod.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
        # 获取 “如果我向这个方向走一步的话所站的位置” 的坐标
        if include_open.(x, y) # 如果坐标已经在open表中了
          # 也就是说 该坐标的节点是另一个已知节点的子节点
          nex = open.find{|pt| pt.x == x && pt.y == y}
          # 那么 找到这个坐标的节点
          if nod.g + 10 < nex.g
          # 如果 通过当前节点到达这个节点的消耗 比原来的消耗更小
            nex.d = 10 - d
            # 就把这个节点的父节点设为当前节点
            nex.g = nod.g + 10
            # 并更新G值（G值就是到达该节点的消耗）
            # 为什么不更新H值？
          end
        # 如果坐标不在open表中
        elsif !include_close.(x, y) # 而且也不在close表中
          # 说明这个位置还没有节点
          child = Point.new(x, y)
          # 于是我们在这里建立一个节点
          child.d = 10 - d
          # 把它的父节点设为当前节点
          child.g = nod.g + 10
          # 计算G值
          child.h = (x - origin.x).abs + (y - origin.y).abs
          # 计算H值 因为节点的H值是固定的 所以之前没有必要更新H值
          open.unshift child
          # 把子节点插入到open表的头部 简单地说 就是把子节点添加到open表中
          open.sort_by!{|pt| pt.g + pt.h}
          # 把open表按照F值（G+H）从小到大排序
          # 现在 open表的第一个节点肯定是F最小的
          # 这也就是为什么一开始我们把open表的第一个节点作为当前节点
        end
        # 如果坐标不在open表中 也并非不在close表中 说明它在close表中
        # 那么我们什么都不需要做 跳过它就行了
      end # 循环遍历
      close.push nod
      # 把当前节点加入到close表中 表明它已经被搜索了
      break if include_close.(origin.x, origin.y)
      # 如果出发点已经在close表中了 中断循环 没有必要继续下去了
    end
    # 已经在循环外了
    # 因为结束循环有两个可能
    # 1.找到了出发点 中断循环
    # 2.open表空了 找不到出发点 路径不存在
    # 所以 这里进行判断
    # 如果close表中没有出发点 那么路径不存在 返回一个空路径
    return [] unless include_close.(origin.x, origin.y)
    # 否则继续
  end
end[/pre]

[pre lang="ruby" line="1"]module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target)
    target = Point.new(*target)
    return [] unless [2, 4, 6, 8].any? do |d|
      x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
      y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
      $game_map.passable?(x, y, 10 - d)
    end
    origin = Point.new(*origin)
    target.g = 0
    target.h = (target.x - origin.x).abs + (target.y - origin.y).abs
    open  = [target]
    close = []
    include_open  = ->(x, y){  !open.find{|pt| pt.x == x && pt.y == y}.nil? }
    include_close = ->(x, y){ !close.find{|pt| pt.x == x && pt.y == y}.nil? }
    until open.empty?
      nod = open.shift
      [2, 4, 6, 8].each do |d|
        next unless $game_map.passable?(nod.x, nod.y, d)
        x = nod.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
        y = nod.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
        if include_open.(x, y)
          nex = open.find{|pt| pt.x == x && pt.y == y}
          if nod.g + 10 < nex.g
            nex.d = 10 - d
            nex.g = nod.g + 10
          end
        elsif !include_close.(x, y)
          child = Point.new(x, y)
          child.d = 10 - d
          child.g = nod.g + 10
          child.h = (x - origin.x).abs + (y - origin.y).abs
          open.unshift child
          open.sort_by!{|pt| pt.g + pt.h}
        end
      end
      close.push nod
      break if include_close.(origin.x, origin.y)
    end
    return [] unless include_close.(origin.x, origin.y)
    # 初始化路径表
    routes = []
    # 从出发点出发 沿着方向走回去就是路径了
    # 找到出发点 作为当前节点
    nod = close.find{|pt| pt.x == origin.x && pt.y == origin.y}
    # 开始循环 直到抵达目标点
    until nod.x == target.x && nod.y == target.y
      # 把当前节点的方向添加到路径表的尾部
      # 这样做 完成以后 把路径表从头到尾读一遍就是移动方向了
      # 类似于“上右上右右上右右下”这样
      routes.push nod.d

      # 记录下来以后 向那个方向移动一步
      x = nod.x + (nod.d == 4 ? -1 : nod.d == 6 ? 1 : 0)
      y = nod.y + (nod.d == 8 ? -1 : nod.d == 2 ? 1 : 0)
      # 然后获取移动后所在位置的节点 作为当前节点
      nod = close.find{|pt| pt.x == x && pt.y == y}
      # 回去循环
    end
    routes
    # 最后返回路径
    # 基础部分 完
  end
end[/pre]

写在一起，就是这样：

…………

等等，因为在某些地图通行度应该循环修正（我在说什么）所以用$game_map.passable?(x, y, dir)判断通行度是不好的……

合适的判定在Game_CharacterBase中有（如2L所说）

但是不能直接用 需要修改一下才能适合我们

注意is_passable那部分：
[pre lang="ruby" line="1"]#==============================================================================
# ** RGSS3-Based A-Star Find Path
#  * Shadow Momo
#  * Base Pack
#==============================================================================
module AStar
  class Point
    attr_accessor :x, :y, :g, :h, :d
    def initialize(*point)
      self.x, self.y = point
    end
  end
  module_function
  def make_route(origin, target, *characters)
    target = Point.new(*target)
    is_passable = ->(x, y, d){
      x = $game_map.round_x_with_direction(x, d)
      y = $game_map.round_y_with_direction(y, d)
      $game_map.valid?(x, y) && $game_map.passable?(x, y, d) &&
      $game_map.events_xy_nt(x, y).all? do |event|
        !event.normal_priority? || characters.any?{|c| c.id == event.id}
      end
    }
    return [] unless [2, 4, 6, 8].any? do |d|
      x = target.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
      y = target.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
      is_passable.(x, y, 10 - d)
    end
    origin = Point.new(*origin)
    target.g = 0
    target.h = (target.x - origin.x).abs + (target.y - origin.y).abs
    open  = [target]
    close = []
    include_open  = ->(x, y){  !open.find{|pt| pt.x == x && pt.y == y}.nil? }
    include_close = ->(x, y){ !close.find{|pt| pt.x == x && pt.y == y}.nil? }
    until open.empty?
      nod = open.shift
      [2, 4, 6, 8].each do |d|
        x = nod.x + (d == 4 ? -1 : d == 6 ? 1 : 0)
        y = nod.y + (d == 8 ? -1 : d == 2 ? 1 : 0)
        next unless is_passable.(x, y, 10 - d)
        if include_open.(x, y)
          nex = open.find{|pt| pt.x == x && pt.y == y}
          if nod.g + 10 < nex.g
            nex.d = 10 - d
            nex.g = nod.g + 10
          end
        elsif !include_close.(x, y)
          child = Point.new(x, y)
          child.d = 10 - d
          child.g = nod.g + 10
          child.h = (x - origin.x).abs + (y - origin.y).abs
          open.unshift child
          open.sort_by!{|pt| pt.g + pt.h}
        end
      end
      close.push nod
      break if include_close.(origin.x, origin.y)
    end
    return [] unless include_close.(origin.x, origin.y)
    routes = []
    nod = close.find{|pt| pt.x == origin.x && pt.y == origin.y}
    until nod.x == target.x && nod.y == target.y
      routes.push nod.d
      x = nod.x + (nod.d == 4 ? -1 : nod.d == 6 ? 1 : 0)
      y = nod.y + (nod.d == 8 ? -1 : nod.d == 2 ? 1 : 0)
      nod = close.find{|pt| pt.x == x && pt.y == y}
    end
    routes
  end
end[/pre]

好了 完成了 这部分的代码如果有更新 不会再编辑这个帖子了 最新版请见Github

但是，目前为止，我们最多调用一下AStar.make_route(...)然后获得一个数组，还是不怎么方便——当然，AStar的实现部分已经结束了，现在我们要应用。

[/fold]

更好地应用到游戏

[fold]

依旧是先了解一些常识
1.在地图上行走的事件、主角、跟随队员的类都是Game_Character类的子类；

2.Game_Character定义了一些共通的方法，其中包括移动；

3.事件的移动模式分为三种，一开始就说过了，随机、接近、自定义，这些模式是在Game_Event中定义的，如第一条所言，它是Game_Character的子类，它也有自己独享的方法。

好，让我们说的更具体吧！

1.在Game_Character中定义一个新的方法，可以自动寻路到某个坐标；

2.修改Game_Character中的move_toward_character方法（向某角色或事件移动），让它更智能；

3.修改Game_Event中的move_type_toward_player方法（移动模式：接近），同样更智能。

开始吧！

考虑到我对第一点的实现涉及到数据结构，我就详细的说明简单的带过吧！

通过AStar生成路径，把路径转换为RPG::MoveRoute对象，让事件或角色跟随这个移动路径前进。

[pre lang="ruby" line="1"]#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
  def goto_AStar(tx, ty)
    route = RPG::MoveRoute.new
    route.repeat = false
    route.skippable = true
    AStar.make_route([self.x, self.y], [tx, ty]).each do |d|
      route.list.unshift RPG::MoveCommand.new.tap{|c| c.code = d >> 1}
    end
    force_move_route(route)
  end
end[/pre]

好 现在是第二点

[pre lang="ruby" line="1"]#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
  # 大家都认得的alias
  alias :astar_move_toward_character :move_toward_character
  def move_toward_character(character)
    # 通过AStar生成路径 但是只截取第一步
    # 因为目标可能在移动
    # 你不希望我们的事件傻乎乎的跑到别人已经闪开了的位置上 不是吗？
    dir = AStar.make_route([x, y], [character.x, character.y]).shift
    # 如果没有办法到达目标 那么dir会是nil
    # 我们就调用原来的笨方法
    # 否则 就朝这个第一个方向走一步
    dir.nil? ? astar_move_toward_character(character) : move_straight(dir)
  end
end[/pre]

简单吧？

第三点：

[pre lang="ruby" line="1"]#==============================================================================
# ** Game_Event
#==============================================================================
class Game_Event
  # alias
  alias :astar_move_type_toward_player :move_type_toward_player
  def move_type_toward_player
    if @astar_last_player_pos != [$game_player.x, $game_player.y]
      # 如果玩家已经移动了
      @astar_last_player_pos = $game_player.x, $game_player.y
      # 记录下他的位置 方便下次比较是否移动了
      @astar_route = AStar.make_route([x, y], @astar_last_player_pos)
      # 然后只好重新生成路径
    end
    # 如果获取的路径是空的 也就是没有办法到达
    (dir = @astar_route.shift).nil? ?
    # 就用原来的笨方法
    astar_move_type_toward_player :
    # 否则朝好方法走一步
    move_straight(dir)
  end
end[/pre]

大功告成！

写在一起：

当然，为了修正那么一点点遗憾 也做了更改 看出来的不要举手 看不出来的请回答我改了哪里（去死）
[pre lang="ruby" line="1"]#==============================================================================
# ** RGSS3-Based A-Star Find Path
#  * Shadow Momo
#  * Expand 01
#==============================================================================

#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
  def goto_AStar(tx, ty)
    route = RPG::MoveRoute.new
    route.repeat = false
    route.skippable = true
    AStar.make_route([self.x, self.y], [tx, ty], self).each do |d|
      route.list.unshift RPG::MoveCommand.new.tap{|c| c.code = d >> 1}
    end
    force_move_route(route)
  end
  alias :astar_move_toward_character :move_toward_character
  def move_toward_character(character)
    dir = AStar.make_route([x, y], [character.x, character.y], self).shift
    dir.nil? ? astar_move_toward_character(character) : move_straight(dir)
  end
end
#==============================================================================
# ** Game_Event
#==============================================================================
class Game_Event
  alias :astar_move_type_toward_player :move_type_toward_player
  def move_type_toward_player
    if @astar_last_player_pos != [$game_player.x, $game_player.y]
      @astar_last_player_pos = $game_player.x, $game_player.y
      @astar_route = AStar.make_route([x, y], @astar_last_player_pos, self)
    end
    (dir = @astar_route.shift).nil? ? astar_move_type_toward_player :
    move_straight(dir)
  end
end[/pre]

同样的 如果再有更新 就在这里Github

现在我们来试验一下……


哇咔咔一下子变聪明了，艾里克终于被对面的姐姐找到了玩家总算能享受一场正常的追逐战了！

要注意的是，如果地图太大（100X100），而主角和事件分散在两个不可能到达的岛屿上，会十分卡顿。

是有优化的方法的，自己想去有兴趣的话可以自己琢磨。

[/fold]

成品

[fold]

基础代码：Github
拓展应用一号档：Github

[/fold]

结语

[fold]

其实一开始写这个脚本的时候，并没有打算写一个教程（不然lambda什么的根本不会用上）。只是又看到S叔的鼠标寻路，于是自己搜索寻路算法完成了脚本版（如果我没记错S叔的是dll）。

但是，在我刚完成准备发布的时候，看到xd君的github更新了脚本AStar，我大吃一惊，发现xd早就实现了——其实这也没什么，但是我接着发现，那个东西居然还是12年年初一个叫禾西的人写的！我一怒之下灵机一动就写了这东西。

当然我非常欣慰的是，禾西的实现思路好像与我完全不同……反正我二十分钟没有看懂。

无论如何，最后搞出来这东西，希望对大家有点用处。

以及

@Sion @taroxd @禾西 @myownroc （你的签名里有另一种驯鹿寻路脚本）@VIPArcher @喵呜喵5 @千葉玖濑 @晴兰  @菜鸟飞呀飞 @无脑之人 @kuerlulu @寒冷魔王 @影月千秋

[/fold]

喵呜喵5

时隔许久过来说一个BUG

RGSS3中图块有一个叫通行方向的混帐玩意儿，这个通行方向呢……无比操蛋的居然能够把某个行走图设置成从某个方向走过去时不可通行

于是，类似下面这样的情况下，目前代码中从终点逆向回到起点的寻路方式就吃瘪了




=================

仔细想想好像也不对，因为自己写的A*脚本没有遇到这个问题能够正常寻路，但是你的脚本却不行……让我想想到底是哪里不对…………

=================

虽然说不清楚，但是感觉差不多明白你的脚本寻路算法为什么用问题了，我这边是直接用要寻路的事件本身的检查能否通行方法进行判断的，这个方法里面会自动检查某个特定图块的某方向是否都能够双向正常通行来保证不会钻进封闭的图块中，而你定义的检查通行的方法只检查了其中一个方向，因此出错了，附带一张测试图片：

地图上那个梯子图块是个下方向无法通行的图块
你的A*

我的A*

taroxd

你知道我怎么更新github脚本的吧……不知道的话就看一下“输出脚本.rb"

于是非原创的脚本就被加进来了（事实上这也是github作为脚本仓库的一个目的：备份）

这种非原创的东西我不会塞到群组里就是了= =

原帖在此：https://rpg.blue/thread-228259-1-1.html

判断通行度别用 $game_map.passable? 用 CharacterBase#passable?

蓝儿

触哭了。。太长不看【误
本殿下是事件党但是还是大致的看了一下。
窝也研究过这些东西【捂脸
一对比窝就弱爆了啊qwq
刚把爹！

喵呜喵5

最终的脚本呢

太长不看

要糖的姿势太明显

删除线好评啦

kuerlulu

为什么要叫上我我只是什么都不懂的渣渣

myownroc

唯一看得懂的A*……
A*应该是加了一定筛选的广度优先（个人感觉），然后效率因此提高很多。
不过广度优先搜索的一定是最短路径，但是效率相对较低。
另外，估值函数那么处理一直感觉欠妥当（但又找不到更方便的了）。
最后问一下：例如战棋中移动到某个节点就要消耗一定体力（体力有上限），这样估值函数是不是会变得复杂许多？

无脑之人

啊 看起来好厉害【
刚和兰触学了SPFA，我感觉我现在什么都不会写了【噗
不过以前看过一篇关于A*的文章，估值函数可以仅仅选择曼哈顿距离，但也可以通过一些相对复杂的处理来实现一些复杂的东西，比如避免多个对象都走一条路（次优解），以及更加复杂的消耗（我觉得对不同类别的消耗统一比较本身就是一种估值了），反正这些东西我都不会【大雾
祝你们翻译文档做的更好咯☆

myownroc

话说我VB里A*比广度优先还慢？还是我没做好……

Sion

不错，研究得挺仔细的样子。