| 赞 | 59 |
| VIP | |
| 好人卡 | |
| 积分 | 88 |
| 经验 | |
| 最后登录 | 2024-2-2 |
| 在线时间 | 501 小时 |
- 梦石
- 2
- 星屑
- 6767
- 在线时间
- 501 小时
- 注册时间
- 2018-3-23
- 回帖
- 487
|
加入我们，或者，欢迎回来。
您需要 登录 才可以下载或查看，没有账号？注册会员
×
本帖最后由 MCCF 于 2020-9-25 23:04 编辑
原贴位于RPG Maker VX Ace 讨论区
众所周知，RPG Maker原版的寻路是不完备的，时常会遇到被墙壁/桌子卡住的现象。
TyPath脚本用A*算法扩展了原有寻路，部分解决了这个问题，并为更多的扩展和支持提供基础。
[fold=关于TyPath]
TyPath是基于A*算法实现的。GameDev的A*页面 及 Amit的A*页面 让我得到了很大的启示。
另外，具体在RGSS下的实现参考了 @余烬之中 的 A*实现指南。在此对他们表示诚挚的谢意。
[/fold]
[fold=前言]
有时，我们需要让事件自主移动向角色。RPG Maker默认的 事件-自主移动-接近 解决了这一问题。
然而，顾名思义，这仅仅是朝相对离角色更进的方向移动一步。
如果在这个方向上有一障碍（尤其是凹形的那种），就有几率会被卡在障碍处。
在追逐战中，敌人被卡住的现象很影响玩家体验。
TyPath就是用于解决这个问题，使得即使在一个迷宫中，事件也能正确寻路到玩家处。
[/fold]
[fold=脚本]
[pre lang="ruby"]#==============================================================================
# TyPath寻路 V1.2
# by MCCF
#------------------------------------------------------------------------------
# [说明]
# - RPG Maker自带的寻路基于“接近”或“远离”的概念，因此过程中会不断接近目标；
# 但是，如果中途有一不可通行的障碍，则即使有另外的可行路径也不会去寻找。
# - 本脚本通过扩展的方式，使用A*算法提高寻路的精确度和灵活度，并且可以保证在有
# 路径时找到可通行的路径。
# - 有一种“堵截式寻路”的设定，该设定指示在抵达玩家附近后就会停止不动，而不是
# 像默认脚本一样随机移开。这可能使得玩家被敌人堵住去路。
#
# - 如果存在BUG或兼容性问题，如反馈我会尽量修复。该脚本也是基础脚本，可以用于其
# 它大型系统的制作。
#------------------------------------------------------------------------------
# [使用方法]
# - 复制到Main之前
#
# - 在事件页的某个注释中添加<typath>，则该事件-自主移动中使用的“接近”选项会由
# TyPath进行处理。
# - 在事件页的某个注释中添加<typath_blocked>，则该事件-自主移动中使用的“接近”
# 选项会使用堵截式寻路。
# - 在事件页的某个注释中添加<typath_limit = value>，则该事件-自主移动中使用的
# “接近”选项会使用value作为寻路精度上限（详见配置模块）。
#
# - 在移动路线中使用脚本typath_move_toward(id)，可以移动到第ID号人物处。ID为正
# 时表示地图事件ID，为0表示本事件，为负数表示玩家队伍（如-2为队伍第二个角色）。
# - 面向脚本人员：Game_Character#move_typath(x,y)用于强制角色移动到指定坐标，
# Game_Character#move_typath_to(character)用于强制角色移动到指定人物，
#------------------------------------------------------------------------------
# [使用条款]
# - 只要署名MCCF即可。只要不以自己的名义发布，您可以自由修改此脚本。
# 鼓励将此脚本在署名的情况下用作其它脚本的基础脚本。
#------------------------------------------------------------------------------
# [兼容性]
# - 此脚本默认为四方向寻路，不会试图斜向移动，但是应该与八方向移动脚本没有冲突。
# - 重写了关于事件寻路的部分，对于像素级移动等改动较大的脚本可能不兼容。
#------------------------------------------------------------------------------
# 通用配置模块
#==============================================================================
module TyPath_Config
# 基本设置 ------------------------------------------------------------------
# 是否默认用TyPath替换原生寻路
DEFAULT_TYPATH = false
# 是否默认启用堵截式寻路
TYPATH_BLOCKED = true
# 控制是否用TyPath替换默认寻路的开关ID
# 为0则不启用开关控制
TYPATH_SWITCH_ID = 0
# 性能设置 ------------------------------------------------------------------
# 寻路随机性（0-9，数值越大随机性越高）
# 增加随机性可进一步模拟原生寻路，减少玩家难度。
TYPATH_RANDOM_RATE = 0
# 寻路智能度（0-9，数值越小越智能）
# 如果严重卡顿请适当增加
TYPATH_SEARCH_RATE = 0
# 默认寻路精度（为0则无限制）
# 如果严重卡顿请适当减小
TYPATH_SEARCH_LIMIT = 0
# 附加设置 ------------------------------------------------------------------
# 有害地形的代价修正
# 数值越大则TyPath越会避免通过有害地形
DAMAGE_FLOOR_CORRECT = 2
end
#------------------------------------------------------------------------------
# 配置模块结束
#==============================================================================
#==============================================================================
# ■ TyPath_Core
#------------------------------------------------------------------------------
# TyPath核心寻路模块。
#==============================================================================
module TyPath_Core
#--------------------------------------------------------------------------
# ● 获取方向的数组
#--------------------------------------------------------------------------
def self.directions
[2, 4, 6, 8]
end
#--------------------------------------------------------------------------
# ● 节点类
#--------------------------------------------------------------------------
class Point
#--------------------------------------------------------------------------
# ● 定义实例变量
#--------------------------------------------------------------------------
attr_reader :x, :y # X坐标及Y坐标
attr_reader :g_val, :h_val # G值及H值
attr_reader :parent, :dir # 当前父节点及抵达方向
attr_reader :death # 深度
#--------------------------------------------------------------------------
# ● 初始化
#--------------------------------------------------------------------------
def initialize(cx, cy, tar_x, tar_y)
@x = cx
@y = cy
@g_val = 0
@h_val = heuristic(tar_x, tar_y)
@parent = nil
@dir = 0
@death = 0
end
#--------------------------------------------------------------------------
# ● 设置
#--------------------------------------------------------------------------
def setup(parent, dir)
@parent = parent
@dir = dir
@death = parent.death + 1
@g_val = parent.g_val + get_cost
end
#--------------------------------------------------------------------------
# ● 启发式函数
#--------------------------------------------------------------------------
def heuristic(tar_x, tar_y)
((tar_x - @x).abs + (tar_y - @y).abs) * 10
end
#--------------------------------------------------------------------------
# ● 获取抵达成本
#--------------------------------------------------------------------------
def get_cost
return 10 * TyPath_Config::DAMAGE_FLOOR_CORRECT if $game_map.damage_floor?(@x, @y)
return 10
end
end
#--------------------------------------------------------------------------
# ● 节点列表类
#--------------------------------------------------------------------------
class PointList
#--------------------------------------------------------------------------
# ● 定义实例变量
#--------------------------------------------------------------------------
attr_accessor :list # 节点数组
#--------------------------------------------------------------------------
# ● 初始化
#--------------------------------------------------------------------------
def initialize(*origin)
@list = [*origin]
end
#--------------------------------------------------------------------------
# ● 判定是否为空
#--------------------------------------------------------------------------
def empty?
@list.empty?
end
#--------------------------------------------------------------------------
# ● 取出最佳节点
#--------------------------------------------------------------------------
def shift
@list.shift
end
#--------------------------------------------------------------------------
# ● 加入节点
# 使用二分查找优化效率。
#--------------------------------------------------------------------------
def insert(node)
left = 0
right = @list.length
while left + 1 < right
mid = (left + right) / 2
if node.g_val + node.h_val > @list[mid].g_val + @list[mid].h_val
left = mid
else
right = mid
end
end
@list.insert(right, node)
end
#--------------------------------------------------------------------------
# ● 删除节点
#--------------------------------------------------------------------------
def delete(node)
@list.delete(node)
end
#--------------------------------------------------------------------------
# ● 获取指定位置的节点
#--------------------------------------------------------------------------
def get_node(cur_x, cur_y)
@list.find {|item| item.x == cur_x && item.y == cur_y }
end
end
#--------------------------------------------------------------------------
# ● 通行检查
#--------------------------------------------------------------------------
def self.passable?(char, cur_x, cur_y)
directions.any? do |dir|
x = $game_map.round_x_with_direction(cur_x, dir)
y = $game_map.round_y_with_direction(cur_y, dir)
char.passable?(x, y, 10 - dir)
end
end
#--------------------------------------------------------------------------
# ● 地图通行检查
#--------------------------------------------------------------------------
def self.map_passable?(char, cur_x, cur_y)
directions.any? do |dir|
x = $game_map.round_x_with_direction(cur_x, dir)
y = $game_map.round_y_with_direction(cur_y, dir)
$game_map.valid?(x, y) && $game_map.passable?(x, y, 10 - dir) &&
$game_map.events_xy_nt(x, y).all? do |event|
!event.normal_priority? ||
(char.is_a?(Game_Event) && char.id == event.id)
end
end
end
#--------------------------------------------------------------------------
# ● 检查两点是否邻近
#--------------------------------------------------------------------------
def self.near?(x, y, cur_x, cur_y)
distance_x(x, cur_x) + distance_y(y, cur_y) == 0
end
#--------------------------------------------------------------------------
# ● 生成接近指定角色的TyPath路径
#--------------------------------------------------------------------------
def self.create_route_to(char, tar_char, strict = true, limit = TyPath_Config::TYPATH_SEARCH_LIMIT)
tar_x = tar_char.x
tar_y = tar_char.y
return [] if char.x == tar_x && char.y == tar_y
return [] unless map_passable?(char, tar_x, tar_y)
origin = Point.new(char.x, char.y, tar_x, tar_x)
open = PointList.new(origin)
close = PointList.new()
until open.empty?
node = open.shift
directions.each do |dir|
next unless limit == 0 || node.death < limit
x = $game_map.round_x_with_direction(node.x, dir)
y = $game_map.round_y_with_direction(node.y, dir)
if x == tar_x && y == tar_y
child = Point.new(x, y, tar_x, tar_y)
child.setup(node, dir)
open.insert(child)
else
next unless char.passable?(node.x, node.y, dir)
if temp = open.get_node(x, y)
if node.g_val + temp.get_cost < temp.g_val
temp.setup(node, dir)
end
elsif temp = close.get_node(x, y)
if false
temp.setup(node, dir)
close.delete(temp)
open.insert(temp)
end
else
child = Point.new(x, y, tar_x, tar_y)
child.setup(node, dir)
open.insert(child)
end
end
end
close.insert(node)
break if close.get_node(tar_x, tar_y)
end
if strict
if cur = close.get_node(tar_x, tar_y)
routes = []
while cur
routes.unshift(cur.dir)
cur = cur.parent
end
return routes
else
return []
end
else
cur = close.list.min_by{|item| item.h_val }
routes = []
while cur
routes.unshift(cur.dir)
cur = cur.parent
end
return routes
end
end
#--------------------------------------------------------------------------
# ● 生成TyPath路径
# strict : 启用严格模式的标识。严格模式下如无法抵达目标，将会返回空数组。
#--------------------------------------------------------------------------
def self.create_route(char, tar_x, tar_y, strict = true, limit = TyPath_Config::TYPATH_SEARCH_LIMIT)
return [] if char.x == tar_x && char.y == tar_y
return [] unless passable?(char, tar_x, tar_y)
origin = Point.new(char.x, char.y, tar_x, tar_x)
open = PointList.new(origin)
close = PointList.new()
until open.empty?
node = open.shift
directions.each do |dir|
next unless limit == 0 || node.death < limit
next unless char.passable?(node.x, node.y, dir)
x = $game_map.round_x_with_direction(node.x, dir)
y = $game_map.round_y_with_direction(node.y, dir)
if temp = open.get_node(x, y)
if node.g_val + temp.get_cost < temp.g_val
temp.setup(node, dir)
end
elsif temp = close.get_node(x, y)
if false
temp.setup(node, dir)
close.delete(temp)
open.insert(temp)
end
else
child = Point.new(x, y, tar_x, tar_y)
child.setup(node, dir)
open.insert(child)
end
end
close.insert(node)
break if close.get_node(tar_x, tar_y)
end
if strict
if cur = close.get_node(tar_x, tar_y)
routes = []
while cur
routes.unshift(cur)
cur = cur.parent
end
return routes
else
return []
end
else
cur = close.list.min_by{|item| item.h_val }
routes = []
while cur
routes.unshift(cur)
cur = cur.parent
end
return routes
end
end
#--------------------------------------------------------------------------
# ● 将TyPath路径转为标准移动指令
#--------------------------------------------------------------------------
def self.make_move_command(path)
path.delete_if {|dir| dir.zero? }
route = RPG::MoveRoute.new.tap do |route|
route.repeat = false
path.each do |dir|
route.list.push(RPG::MoveCommand.new.tap{|cmd|cmd.code = dir >> 1})
end
end
end
#--------------------------------------------------------------------------
# ● 检查注释是否匹配
#--------------------------------------------------------------------------
def self.match_comments(cmd, reg)
return nil unless cmd.code == 108 || cmd.code == 408
return cmd.parameters[0] =~ reg
end
end
#==============================================================================
# ■ Game_Character
#------------------------------------------------------------------------------
# 添加了路径移动的地图人物类。
#==============================================================================
class Game_Character < Game_CharacterBase
#--------------------------------------------------------------------------
# ● 获取指定ID的人物
#--------------------------------------------------------------------------
def get_character(id)
if $game_party.in_battle
nil
elsif param < 0
$game_player
else
$game_map.events[param > 0 ? param : @event.id]
end
end
#--------------------------------------------------------------------------
# ● 根据TyPath寻路向指定ID的人物
#--------------------------------------------------------------------------
def typath_move_toward(id)
character = get_character(id)
move_typath_to(character) if character
end
#--------------------------------------------------------------------------
# ● 根据TyPath寻路向指定坐标
#--------------------------------------------------------------------------
def move_typath(tar_x, tar_y)
routes = TyPath_Core.create_route(self, tar_x, tar_y)
routes.collect! {|item| item.dir }
force_move_route(TyPath_Core.make_move_command(routes))
end
#--------------------------------------------------------------------------
# ● 根据TyPath寻路向指定人物
#--------------------------------------------------------------------------
def move_typath_to(char)
routes = TyPath_Core.create_route_to(self, char)
force_move_route(TyPath_Core.make_move_command(routes))
end
end
#==============================================================================
# ■ Game_Event
#------------------------------------------------------------------------------
# 处理事件的类。拥有条件判断、事件页的切换、并行处理、执行事件等功能。
# 在 Game_Map 类的内部使用。
#==============================================================================
class Game_Event < Game_Character
#--------------------------------------------------------------------------
# ● 自动移动的更新
#--------------------------------------------------------------------------
alias typath_update_self_movement update_self_movement
def update_self_movement
return if @move_type == 0
if typath?
if @stop_count > stop_count_threshold
if @move_type == 2
move_type_toward_player
elsif near_the_screen?
case @move_type
when 1; move_type_random
when 2; move_type_toward_player
when 3; move_type_custom
end
end
end
else
typath_update_self_movement
end
end
#--------------------------------------------------------------------------
# ● 移动类型 : 接近（随机性处理）
#--------------------------------------------------------------------------
alias typath_origin_move_type_toward_player move_type_toward_player
def typath_move_type_toward_player
if rand(10) >= TyPath_Config::TYPATH_RANDOM_RATE
move_toward_player
else
typath_origin_move_type_toward_player
end
end
#--------------------------------------------------------------------------
# ● 移动类型 : 接近
#--------------------------------------------------------------------------
def move_type_toward_player
if typath?
if update_typath
if (dir = @typath_route.shift).nil?
typath_move_type_toward_player unless typath_blocked?
else
move_straight(dir)
end
else
typath_move_type_toward_player
end
else
@typath_route = []
typath_move_type_toward_player
end
end
#--------------------------------------------------------------------------
# ● 更新TyPath数据
#--------------------------------------------------------------------------
def update_typath
if @typath_player_pos != [$game_player.x, $game_player.y]
@typath_player_pos = [$game_player.x, $game_player.y]
return false unless update_typath_route
end
return false unless update_typath_route unless @typath_route
unless @typath_route[0] && passable?(@x, @y, @typath_route[0])
return false unless update_typath_route
end
return true
end
#--------------------------------------------------------------------------
# ● 更新TyPath路径
#--------------------------------------------------------------------------
def update_typath_route
if rand(10) >= TyPath_Config::TYPATH_SEARCH_RATE
@typath_route = TyPath_Core.create_route_to(self, $game_player, false, typath_limit)
return true
else
return false
end
end
#--------------------------------------------------------------------------
# ● 检查TyPath是否启用
#--------------------------------------------------------------------------
def typath?
result = @list.any? do |item|
TyPath_Core::match_comments(item, /<typath>/i)
end
if result
return true
else
if TyPath_Config::DEFAULT_TYPATH
return true
elsif TyPath_Config::TYPATH_SWITCH_ID != 0
$game_switches[TyPath_Config::TYPATH_SWITCH_ID]
end
end
return false
end
#--------------------------------------------------------------------------
# ● 获取TyPath寻路精度
#--------------------------------------------------------------------------
def typath_limit
@list.each do |item|
if TyPath_Core::match_comments(item, /<typath_limit\s*=\s*(\d+)>/i)
return $1.to_i
end
end
return TyPath_Config::TYPATH_SEARCH_LIMIT
end
#--------------------------------------------------------------------------
# ● 获取TyPath是否启用堵截式寻路
#--------------------------------------------------------------------------
def typath_blocked?
result = @list.any? do |item|
TyPath_Core::match_comments(item, /<typath_blocked>/i)
end
return true if result
return TyPath_Config::TYPATH_BLOCKED
end
end
[/pre]
[/fold]
[fold=范例工程]
请仔细关注范例中事件的内容，将玩家和事件移动到不同的岛屿上查看效果。
范例中不一定有最新脚本，如遇BUG请尝试本帖中的脚本，如仍发生问题请反馈。
（其实已经有已知BUG了……所以去帖子上面复制吧233）
1.0版本范例工程：
1.1版本范例工程：
1.2版本改动较小，不提供范例工程，请自行从帖子中复制最新脚本。
[/fold]
[fold=实现说明]
真的有人会看这个吗？
关于“堵截式寻路”：
“堵截式寻路”就是在路径为空时，不会继续采用原生方式寻路。这也意味着事件将对玩家穷追不舍，在已经抵达玩家附近时就会停止移动，可以做到堵截玩家的效果。
关于“性能设置”：
其中的“随机性”、“智能度”和“精度”是不是看上去都差不多？
实际上，这只是由于作者词穷而已……
出于提高性能的原因，有时候TyPath在路径还未计算出来时，不会进行昂贵的路径计算，而是会使用原版寻路(typath_move_type_towrad_player)。这样仅使得路径增长一两步，却能是性能提高到原来的数倍。
而“智能度”就是用于控制进行路径计算而非使用原版寻路的几率。这意味着，当智能度设置得较低（数值较大），可以使性能有较大的提升，但是事件也越有可能出现短时间卡在墙角的现象。
至于“精度”，则是模仿了RMMV自带的A*寻路的优化方式，通过把深度大于某个值的节点抛弃掉来使得搜索强度固定在一个值。这意味着，假如精度为N，而目标在N步都到不了的地方，则寻路仍然会采用不完备的启发式方式。精度设置是最直接有效的优化方式，但是对于寻路结果的影响很大，通常在地图较小不需要大量处理的情况下使用。
另外这个“随机性”则与性能优化关联不大，而只是影响在使用原版寻路时，是否进行随机移动的操作。如果仔细观察原版寻路，会发现事件有1/3的几率会随机移动，1/6的几率会直接朝当前方向前进一步。这也是为了提高寻路的随机性和游戏的平衡性。但是有时候，事件随机乱转令人很不愉快，因此可以将随机性调低或使用堵截式寻路，达到更好的效果。
[/fold]
[fold=更新日志]
1.1版本更新：
- 现在即使目标不可到达，也会自动寻路到离目标最近的位置上。
- 进一步优化寻路速度，减少寻路对游戏FPS的影响。
- 可设置“堵截式寻路”，此时事件将
忠贞不渝死缠烂打地堵截角色。 - 可设置寻路精度及智能度，可以通过减小这两个设定值防止卡顿。
- 可设置寻路避免通过有害地形的修正。
- 以及更多奇奇怪怪的部分优化和一大堆BUG修复。
[/fold] |
|
写轮眼
发表于 2020-3-14 18:16:21
提升卡
沉默号角
喧嚣号角
变色卡
升龙剑
