=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++代码实现。感兴趣的童鞋可以到
[url=http://blog.csdn.net/u013632138/article/details/50672596]http://blog.csdn.net/u013632138/article/details/50672596[/url] 观赏一二
(博主就是我)
* 扯淡：离开学就剩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[i].fill(false)}
@cost.each_with_index {|e, i| @cost[i].fill(INF)}
@path.each_with_index {|e, i| @path[i].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[i]
nx = cx+DX[i]
ny = cy+DY[i]
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[i]
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
写轮眼
发表于 2016-2-20 00:42:49
收藏
分享
提升卡
沉默号角
喧嚣号角
变色卡
升龙剑
楼主
