【算法】Dijkstra寻路算法在RM地图上的应用

RyanBern

在RM游戏中，事件寻路问题一直是一个热点话题。你是否还为移动角色而一个个数格子而烦恼？我想大多数人都会想，要是有这样一个命令，你告诉你的事件的目的地是哪里，那么只要有一条路通向那里，事件就会找出一条路自己走过去。这就是我们常说的“寻路脚本”。

如今，有各种各样是寻路脚本已经比较完美得解决了这个问题，例如著名的A星算法，这个算法可以说被广泛得用到各种游戏上（例如RTS游戏，ARPG游戏等），它依靠的原理不是很困难，效率也不错。当然还有myownroc写的BFS寻路脚本，利用广度优先搜索也可以解决问题。不过这个帖子里面介绍的是另一种寻路算法——Dijkstra算法。
（此帖的研究结果有些坑，虽然想法比较好，但是得到的结果让人比较失望）

对图论有接触的人对这个算法应该并不陌生，Dijkstra算法是计算图中一个点到其他所有点最短路径的一个算法，也是目前最好的最短路径算法之一，时间复杂度为O(n^2)，空间复杂度为O(n)。于是在RM游戏中，一张地图就可以看作是一张有特殊结构的网格图，每个块最多只有4个邻居，并且它到它所有邻居的距离都相等。Dijkstra算法作为图论中最短路径的一般算法，当然可以用在RM的地图中。

Dijkstra算法的步骤是这样的。设V是所有顶点的集合，U里面是存放已经求出从起点到它最短路径的所有顶点，V-U是尚未确定最短路径的顶点集合。一开始U里面只有起点这个顶点。然后执行下面的步骤。

(1)在集合V-U中选取距离（注，此值需要额外记录）起点最小的顶点v，加入集合U
(2)对剩下V-U中各顶点的距离值进行修正，如果加入顶点v后，使得起点到V-U中的各个点距离变小，则修改距离值。

重复(1)(2)操作，直到所有与起点可达的顶点都在U中。

有关Dijkstra算法的正确性，这里不加多说，不过，保证Dijkstra算法正确的有一个条件希望大家记住，就是要求所有点之间的距离都是正数。

因此，结合(1)(2)两步，我们需要做下面的事情：
在(1)中，我们需要找到这个最小值，因此要对V-U顶点进行遍历。
在(2)中，我们需要对V-U中的点的距离进行修正，因此还要对V-U顶点再遍历一次。

假设地图的图块是n*n，那么我们的遍历次数会非常多，在这里我们利用RM地图的特点进行简化，可以极大降低复杂度。
RM地图特点为：每个点最多只有4个邻居，而且每个点到它邻居的距离均相等，这里不妨设为1

那么，(1)(2)两步的遍历空间就会极大减少。
由于每两个相邻顶点的距离都是1，进行修正时，修正过程中产生的值不会是最小的，因此最小值还是在原来U中顶点上达到。这就说明，先产生的可达顶点距离小，后产出的顶点距离大，而我们优先处理距离小的顶点，这是个First-Come-First-Served原则，因此可以抽象出来队列模型，我们就省去了(1)中的遍历。
为U中添加结点时，需要修正的点并不是地图上所有顶点，而时和新顶点相邻的所有顶点，而每个点的邻居最多4个，因此我们就省去了(2)中的遍历。

细心的人可以看到。这时，Dijkstra算法在RM地图中已经退化成了一个BFS算法（这就是我说的比较坑的地方，这么好的算法原来和BFS是一样的），执行步骤如下：
(1)将起点加入队列中
(2)从队列中取出第一个点v
(3)将v点所有可达的（还为进入队列一次的）邻居都放入到队列中，并记录路线方向
(4)如果队列不空，转(2)，否则退出循环
(5)回溯路径，产生移动指令。

代码如下（以下算法可以在游戏中使用）：
[pre lang="Ruby"]
=begin
Dijkstra寻路算法 By RyanBern

用法：在事件脚本中使用如下代码：

$game_player.dijkstra_move_to(x, y) #让主角移动到点(x, y)

$game_map.events[1].dijkstra_move_to(x, y) #让地图上的1号事件移动到点(x, y)

注意，如果点(x, y)无法达到，那么角色将不会移动
=end
module Dijkstra
  class Point
    attr_accessor :x
    attr_accessor :y
    def initialize(x, y)
      @x = x
      @y = y
    end
  end
  def generate_move_route(final_x, final_y)
    route = []
    path = Table.new($game_map.width, $game_map.height)
    queue = []
    queue << Point.new(self.x, self.y)
    path[self.x, self.y] = -1
    if !$game_map.valid?(final_x, final_y) || self.x == final_x && self.y == final_y
      return route
    end
    found = false
    while(!queue.empty? && !found)
      point = queue.shift
      [2,4,6,8].each do |d|
        new_x = point.x + (d == 6 ? 1 : d == 4 ? -1 : 0)
        new_y = point.y + (d == 2 ? 1 : d == 8 ? -1 : 0)
        if self.passable?(point.x, point.y, d) && path[new_x, new_y] == 0
          queue << Point.new(new_x, new_y)
          path[new_x, new_y] = d
          found = true if new_x == final_x && new_y == final_y
        end
      end
    end
    if found
      x = final_x
      y = final_y
      while(path[x, y] != -1)
        d = path[x, y]
        route << d
        x -= (d == 6 ? 1 : d == 4 ? -1 : 0)
        y -= (d == 2 ? 1 : d == 8 ? -1 : 0)
      end
    end
    return route
  end
  def generate_move_command(route)
    list = Array.new(route.size){|i| RPG::MoveCommand.new(route[route.size - 1 - i] / 2)}
    list << RPG::MoveCommand.new(0)
    commands = RPG::MoveRoute.new
    commands.skippable = false
    commands.repeat = false
    commands.list = list
    return commands
  end
  def dijkstra_move_to(x, y)
    route = generate_move_route(x, y)
    commands = generate_move_command(route)
    self.force_move_route(commands)
  end
end

class Game_Character
  include Dijkstra
end[/pre]
令我比较欣慰的是，代码还算比较短，效率也算是不错吧（希望是真的）。说实话，Dijkstra算法在图论中真的很有效，但是提到游戏中的寻路，大家先想到的绝对是A星算法。这是因为游戏中的图有特殊的结构，而Dijkstra算法的一般性太强。不过呢，Dijkstra在RM地图上退化成了BFS算法这点让我很惊讶。

PS：我看了myownroc的BFS寻路，发现脚本的结构不太一样，我的循环层数似乎少一些，不知道原理是否是一致的。
PPS：至于这东西用在游戏里面合适与否，我也不知道，不过还是慎用吧。

myownroc

我的循环多一层的原因是我用了两个变量(ij)对地图的点进行遍历，如果改成一个自然就少了一层。而且我没有用队列来储存点，用的是二维数组，这样效率低了一点(回头弄个队列的来玩玩)。ps:我怎么觉得你的循环只有一层?

Dijkstra对图的权有所判断，而BFS没用到，所以这个Dijkstra像BFS。
另外当起点终点同在一集合就可以退出循环了吧?

gonglinyuan

每一步都代价固定为1，所以一定就是BFS吧。。 真是麻烦了LZ给我们推导了这么半天///

chd114

用假位移呢？

芯☆淡茹水

这种寻路就好像是透视性的，把整张地图”看“完后，找到通向目标的捷径。
那 RyanBern 有没有试过局部的”尝试性“的寻路呢？
比如：上方不能通行-->尝试左/右，如果能通过，往左/右一步，然后再转向最初的方向（上）；如果都不能
通过 --> 后退N步，再往左或右一步（小绕），再回到最初方向（上）<<循环，直到上方能通过或设定的循环次数限制。

yagami

为何用bfs 好写 随手就写来了 QA没觉得卡 玩家没觉得卡 那就这样了 在硬件越来越牛逼得现在 cpu的瓶颈越来越少了 算法地位也就低了 如果效率的提升肉眼看不出 我宁可用低效的 简单的 可维护性强的，如果真因为这个卡了 再改A＊

刺夜之枪

我提个问题
A* 跟你们说的 Dijkstra 或者 BFS 哪个效率比较高
不知道若干(可能几十)事件一起运行的话RM会不会卡

youarelose

正方形方格图这种比较适合广度优先遍历

SailCat

理论上从起点和终点同时BFS（直到两者边界相交）会大大减少遍历的次数
就是把o(n^2)变成了o(2(n/2)^2)，也就是1/2n^2，相当于原来的2倍效率