=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