#encoding:utf-8
#==============================================================================
# ■ 事件自动寻路
#
# 本插件的前置插件为：《多帧4_8方图，4_8向行走》＋《多帧事件连续移动》
# 1.定点，障碍绕行，可后台超低速寻路，保障帧率
# 2.多个事件一起寻路，帧率影响不太明显，但会寻路比较慢
#------------------------------------------------------------------------------
#使用说明：
# 让事件可以寻路，调用make_passing(true)，false则该事件不能寻路
# 自动寻向指定点，move_toward_pos(x,y)函数
# 取消当前寻路指令，cancel_pathing函数
# 如果有几个事件一起寻路的话，最好不要同时放出，建议间隔10帧，若目标很远要隔久一点。
# 若要追逐玩家的话，不要每帧都追，隔几十帧追一下。
#
# 注意：是全地图搜索。越远越慢，地形越迷宫越慢，建议距离不要超过１００图块
#------------------------------------------------------------------------------
# by rmav (有任何问题请毫无顾忌滴提出)
#
#
# v1.04 若在路径中发生意外，重新寻路
#==============================================================================
$imported ||= {}
$imported[:rmav_pathing] = 20140213.1
module Rmav
Opt_pathing={
detour: true, #在路径上碰到临时障碍，是否绕行
##不绕行的话，障碍消失，会自动继续下去
total_cycles: 50, #越大寻路越快，但在超大地图迷宫地形上相隔很远的话，容易卡顿
##如果在游戏中掉帧明显，可降低10
failed_and_stop: false, #全地图寻路失败时，停止
failed_and_rand: false, #全地图寻路失败时，随机移动
failed_and_back: true #全地图寻路失败时，在后台极低速一直寻路
##全地图寻路失败时，以上只能三选一
}
class Path_node
attr_accessor :i,:j,:f,:g,:h,:pre,:next,:pos
def initialize(point=[0,0])
@i=point[0]
@j=point[1]
@f=@g=@h=0
@pre=@next=nil
end
def p
[@i,@j]
end
def cal_fgh(s_p, e_p)
if @pre
@g=@pre.g+(@pre.p[0]-@i).abs+(@pre.p[1]-@j).abs
else
@g=(s_p[0]-@i).abs+(s_p[1]-@j).abs
end
@h=(e_p[0]-@i).abs+(e_p[1]-@j).abs
@f=@g+@h
end
end
class Pathfinder
@@total_cycles_per_frame=Rmav::Opt_pathing[:total_cycles]
@@left_cycles_curFrame=Rmav::Opt_pathing[:total_cycles]
@@finder_cnt=0
@@total_low_speeds=0
@@mini_cycles_per_frame=10
@@mini_finder_cnt=0
@@low_speed_max=10
def initialize(passable,p_max=[99,99],p_min=[0,0])
@open_nodes=[]
@open_points={}
@close_points={}
@passable=passable
@p_min=p_min
@p_max=p_max
@cancel=false
@mini_cancel=false
@low_speed=0
end
def set_low_speed(low_speed)
tmp=[low_speed,@@low_speed_max].min
if @@total_low_speeds+@low_speed<@@total_cycles_per_frame
@low_speed=tmp
@@total_low_speeds+=@low_speed
end
end
def self.reset_left_cycles
@@left_cycles_curFrame=Rmav::Opt_pathing[:total_cycles]
end
def self.clear_left_cycles
@@left_cycles_curFrame=0
end
def min_heapify(sz,i)
return nil if sz.size<=i || i<0
l_child=r_child=min_child=0
cur_size=sz.size
i_node=sz[i]
loop do
l_child=2*i+1
r_child=2*i+2
if l_child>=cur_size
break
elsif r_child>=cur_size
min_child=l_child
else
min_child=
(sz[l_child].f<=sz[r_child].f)?(l_child):(r_child)
end
if sz[min_child].f>=i_node.f
break
else
sz[i]=sz[min_child]
sz[i].pos=i
i=min_child
end
end
sz[i]=i_node
sz[i].pos=i
end
def heap_extract_min(sz)
return nil if sz.size<=0
min=sz[0]
sz[0] = sz[-1]
sz[0].pos=0
sz.pop
min_heapify(sz,0)
min
end
def heap_decrease_key(sz,i,f)
return nil if sz.size<=0|| sz[i].f<=f
sz[i].f=f
tmp=i
i_node=sz[i]
parent=0
loop do
parent=(tmp-1)/2
if sz[parent].f>f
sz[tmp]=sz[parent]
sz[tmp].pos=tmp
tmp=parent
else
break
end
break if parent<=0
end
sz[tmp]=i_node
sz[tmp].pos=tmp
end
def min_heap_insert(sz,node)
f=node.f
node.f=999999999
node.pos=sz.size
sz<<node
heap_decrease_key(sz,sz.size-1,f)
end
def adj_p(p,d,p_max=@p_max,p_min=@p_min)
case d
when 2; [p[0],p[1]+1] if p[1]+1<=p_max[1]
when 4; [p[0]-1,p[1]] if p[0]-1>=p_min[0]
when 6; [p[0]+1,p[1]] if p[0]+1<=p_max[0]
when 8; [p[0],p[1]-1] if p[1]-1>=p_min[1]
end
end
def a_star(start_p,end_p)
return nil if start_p==end_p
@cancel=false
@@finder_cnt+=1
while (@@total_cycles_per_frame-@@total_low_speeds)/@@finder_cnt<8
Fiber.yield
if @cancel
@@finder_cnt-=1
@@total_low_speeds-=@low_speed
@low_speed=0
return nil
end
end
@open_nodes.clear
@open_points.clear
@close_points.clear
cycles_cnt=0
reach_end_node=nil
start_node=Path_node.new(start_p)
@open_nodes<<start_node
node = @open_nodes.shift
[2,4,6,8].each{|d|
point=adj_p(node.p,d)
if point&&@passable.call(node.i,node.j,d)
tmp=Path_node.new(point)
tmp.pre=node
tmp.cal_fgh(start_p, end_p)
min_heap_insert(@open_nodes,tmp)
@open_points[tmp.p]=tmp
end
}
@close_points[node.p]=node
while(@open_nodes.size>0)
if @low_speed>0
if cycles_cnt>@low_speed
@@left_cycles_curFrame-=cycles_cnt
cycles_cnt=0
Fiber.yield
end
elsif cycles_cnt>(@@total_cycles_per_frame-@@total_low_speeds)/@@finder_cnt
@@left_cycles_curFrame-=cycles_cnt
cycles_cnt=0
Fiber.yield
end
if @cancel
break
end
if @@left_cycles_curFrame<1
Fiber.yield
break if @cancel
end
min=heap_extract_min(@open_nodes)
@open_points.delete(min.p)
[2,4,6,8].each{|d|
point=adj_p(min.p,d)
next unless point
if point==end_p
tmp=Path_node.new(point)
tmp.pre=min
reach_end_node=tmp
break
end
if point!=min.pre.p&&@passable.call(min.i,min.j,d)
if !@close_points.has_key?(point)
tmp=Path_node.new(point)
tmp.pre=min
tmp.cal_fgh(start_p, end_p)
tmp2=@open_points[tmp.p]
if tmp2
if tmp2.g>tmp.g
tmp2_f_pre=tmp2.f
tmp2.pre=min
tmp2.g=tmp.g
new_f=tmp.g+tmp.h
heap_decrease_key(@open_nodes,tmp2.pos,new_f)
end
else
min_heap_insert(@open_nodes,tmp)
@open_points[tmp.p]=tmp
end
end
end
}
@close_points[min.p]=min
break if reach_end_node
cycles_cnt+=1
end
@@finder_cnt-=1
@@total_low_speeds-=@low_speed
@low_speed=0
@open_nodes.clear
@open_points.clear
@close_points.clear
reach_end_node
end
def terminate
@open_nodes.clear
@open_points.clear
@close_points.clear
end
def mini_star(start_p,end_p,view=9)
return nil if start_p==end_p
@mini_cancel=false
@@mini_finder_cnt+=1
while @@mini_cycles_per_frame/@@mini_finder_cnt<5
Fiber.yield
if @mini_cancel
@@mini_finder_cnt-=1
return nil
end
end
cycles_cnt=0
p_min=[];p_max=[]
p_min[0]=(start_p[0]<end_p[0])?(start_p[0]-view/2):(end_p[0]-view/2)
p_min[1]=(start_p[1]<end_p[1])?(start_p[1]-view/2):(end_p[1]-view/2)
p_max[0]=(start_p[0]>end_p[0])?(start_p[0]+view/2):(end_p[0]+view/2)
p_max[1]=(start_p[1]>end_p[1])?(start_p[1]+view/2):(end_p[1]+view/2)
p_min[0]=@p_min[0] if p_min[0]<@p_min[0]
p_min[1]=@p_min[1] if p_min[1]<@p_min[1]
p_max[0]=@p_max[0] if p_max[0]>@p_max[0]
p_max[1]=@p_max[1] if p_max[1]>@p_max[1]
open_nodes=[]
open_points={}
close_points={}
reach_end_node=nil
start_node=Path_node.new(start_p)
open_nodes<<start_node
node = open_nodes.shift
[2,4,6,8].each{|d|
point=adj_p(node.p,d,p_max,p_min)
if point&&@mini_passable.call(node.i,node.j,d)
tmp=Path_node.new(point)
tmp.pre=node
tmp.cal_fgh(start_p, end_p)
min_heap_insert(open_nodes,tmp)
open_points[tmp.p]=tmp
end
}
close_points[node.p]=node
while(open_nodes.size>0)
if cycles_cnt>@@mini_cycles_per_frame/@@mini_finder_cnt
cycles_cnt=0
Fiber.yield
end
if @mini_cancel
break
end
min=heap_extract_min(open_nodes)
open_points.delete(min.p)
[2,4,6,8].each{|d|
point=adj_p(min.p,d,p_max,p_min)
next unless point
if point==end_p
tmp=Path_node.new(point)
tmp.pre=min
reach_end_node=tmp
break
end
if point!=min.pre.p&&@mini_passable.call(min.i,min.j,d)
if !close_points.has_key?(point)
tmp=Path_node.new(point)
tmp.pre=min
tmp.cal_fgh(start_p, end_p)
tmp2=open_points[tmp.p]
if tmp2
if tmp2.g>tmp.g
tmp2_f_pre=tmp2.f
tmp2.pre=min
tmp2.g=tmp.g
new_f=tmp.g+tmp.h
heap_decrease_key(open_nodes,tmp2.pos,new_f)
end
else
min_heap_insert(open_nodes,tmp)
open_points[tmp.p]=tmp
end
end
end
}
close_points[min.p]=min
break if reach_end_node
cycles_cnt+=1
end
@@mini_finder_cnt-=1
open_nodes.clear
open_points.clear
close_points.clear
reach_end_node
end
def cancel
@cancel=@mini_cancel=true
end
def mini_cancel
@mini_cancel=true
end
def set_localpassable_method(method)
@mini_passable=method
end
def set_pass_method(method)
@passable=method
end
end#class Pathfinder
end#module Rmav
class Game_Event
alias_method :initialize_org_event_rmav_7,:initialize
def initialize(map_id, event)
initialize_org_event_rmav_7(map_id, event)
@path_finder=false
end
def make_passing(enable=true)
@path_finder=enable
init_pathing if enable
end
def init_pathing
@path_to_point=nil
@blocked_cnt=0
@repassable=Proc.new{|x,y,d| passable_ex?(x, y, d)}
end
#--------------------------------------------------------------------------
# ● 判定是否可以通行（检查 地图的通行度 和 前方是否有路障）
# d : 方向（2,4,6,8）
#--------------------------------------------------------------------------
def passable_ex?(x, y, d)
x2 = $game_map.round_x_with_direction(x, d)
y2 = $game_map.round_y_with_direction(y, d)
return false unless $game_map.valid?(x2, y2)
return true if @through || debug_through?
return false unless map_passable?(x, y, d)
return false unless map_passable?(x2, y2, reverse_dir(d))
return false if collide_with_characters?(x2, y2)
return false if $game_player.pos_nt?(x2, y2)
return true
end
def find_path_to(x,y)
cancel_pathing
@path_to_point=[x,y]
@pathnode=nil
passable_method=Proc.new{|x,y,d| $game_map.passable?(x,y,d)}
unless @pathfinder
@pathfinder=Rmav::Pathfinder.new(
passable_method,[$game_map.width,$game_map.height])
end
@pathfinder.set_pass_method(passable_method)
@pathing=Fiber.new{
@pathnode=@pathfinder.a_star([x,y],[@x,@y])
@pathing=nil
}
end
def move_toward_pos(x,y)
if @path_to_point!=[x,y]
find_path_to(x,y)
end
end
def repath_to(x,y,speed_ctl=0)
reset_pathing
node=nil
unless @pathfinder
@pathfinder=Rmav::Pathfinder.new(
nil,[$game_map.width,$game_map.height])
end
@pathfinder.set_pass_method(@repassable)
@pathfinder.set_low_speed(speed_ctl)
@pathing=Fiber.new{
@pathnode=@pathfinder.a_star([x,y],[@x,@y])
@pathing=nil
}
end
def local_pathing(s_p,e_p)
return nil unless @pathfinder
reset_local_pathing
@mini_node=nil
@pathfinder.set_localpassable_method(@repassable)
@local_pathing=Fiber.new{
@mini_node=@pathfinder.mini_star(s_p,e_p)
@local_pathing=nil
}
end
def reset_pathing
@pathnode=nil
@pathfinder.cancel if @pathfinder
@pathing.resume if @pathing
@repathing.resume if @repathing
@local_pathing.resume if @local_pathing
end
def cancel_pathing
@path_to_point=nil
reset_pathing
end
def reset_local_pathing
@pathfinder.mini_cancel if @pathfinder
@local_pathing.resume if @local_pathing
end
alias_method :update_self_movement_rmav_org_rmav_7,:update_self_movement_rmav
def update_self_movement_rmav
return if moving? || @move_route_forcing
if @path_finder&&!$game_map.interpreter.running?
return unless @path_to_point#没有目标点
if near_the_screen?
if @pathing
@pathing.resume;return
end
if @repathing
@repathing.resume;return
end
if @local_pathing
@local_pathing.resume;return
end
unless @pathnode #全地图寻路失败
@rand_steps||=1
if Rmav::Opt_pathing[:failed_and_rand]
if (@rand_steps%=3)!=0
move_type_random_rmav
@rand_steps+=1
elsif @stop_count>180
move_type_random_rmav
@rand_steps+=1
end
elsif Rmav::Opt_pathing[:failed_and_back]
repath_to(*@path_to_point,2)
end
return
end
@pathnode=@pathnode.pre if @pathnode.p==[@x,@y]
if @pathnode
dx=@pathnode.p[0]-@x
dy=@pathnode.p[1]-@y
if Rmav::Opt_walk[:dir8_on]
if @pathnode.pre&&@pathnode.pre.p[0]!=@x&&@pathnode.pre.p[1]!=@y
dx=@pathnode.pre.p[0]-@x
dy=@pathnode.pre.p[1]-@y
end
end
if dx.abs>1||dy.abs>1
@pathnode=nil
repath_to(*@path_to_point,10)
return
end
move_diagonal([0,6,4][dx],[0,2,8][dy])
if @move_succeed
@path_to_point=nil if @path_to_point==@pathnode.p #到达目的
if Rmav::Opt_walk[:dir8_on]&&dx.abs==dy.abs
@pathnode=@pathnode.pre.pre
else
@pathnode=@pathnode.pre
end
@failed_node=nil
@blocked_cnt=0
else
#挡住了
@blocked_cnt+=1
#p "dang~~~"
if Rmav::Opt_walk[:dir8_on]&&dx.abs==dy.abs
@failed_node=@pathnode.pre
else
@failed_node=@pathnode
end
if Rmav::Opt_pathing[:detour]
if @blocked_cnt>60
repath_to(*@path_to_point,10)
@blocked_cnt=1
else
if @failed_node.pre
if collide_with_characters?(*@failed_node.pre.p)
failed_node=@failed_node.pre
else
failed_node=@failed_node
end
if failed_node.pre &&!collide_with_characters?(*failed_node.pre.p)
if @mini_node
tmp2_node=@mini_node
while tmp2_node&&tmp2_node.pre
tmp2_node=tmp2_node.pre
end
tmp2_node.pre=@failed_node_reserved.pre.pre
@pathnode=@mini_node
@mini_node=nil
@failed_node_reserved=nil
while @pathnode&&@pathnode.p!=[@x,@y]
@pathnode=@pathnode.pre
end
else
if @local_pathing
@local_pathing.resume
else
@failed_node_reserved=failed_node
local_pathing(failed_node.pre.p,[@x,@y])
end
end
else#后续多点被堵
#repathing
repath_to(*@path_to_point) if @blocked_cnt>5
end
else
#终点被占用，到达倒数第２点
end
end#@blocked_cnt
else#指定不绕，会停在那直到障碍移开
#不用处理，不绕
end
end
end
end
return
end
update_self_movement_rmav_org_rmav_7
end
end
class Scene_Base
alias_method :update_org_base_rmav_7,:update
def update
Rmav::Pathfinder.reset_left_cycles
update_org_base_rmav_7
end
end