イベントが呼び出されるたびに1回だけ移動を発動する経路探索スクリプトを見つけるのに苦労していました。多くの試行錯誤と、残念ながらチャットボットによるある種の支援を経て、2011年のこの古典的なパスファインダーを私が求めていた形に仕上げることができました。
元のスクリプト作者である cozziekuns（および Modern Algebra）に全クレジットを贈ります。また、説明文の大部分は cozziekuns によって書かれており、必要に応じて微調整を加えています。
2012年1月にこの機能/修正をリクエストしていただいた johantnjl にも感謝申し上げます。あなたのプロジェクトが役に立つことを願っています 
バージョン履歴
- <Version 1.0> 2011.12.31 - 初版リリース (myhgis による軽微な修正 2026.07.19)
説明
このスクリプトを使用すると、最短経路で任意のキャラクターを別のタイルに移動させることができます。ただし、広大なマップでは処理にかなり時間がかかります。
機能
-
驚くほど高速で正確な経路探索
-
スクリプト呼び出しが簡単
-
設定がほぼ不要
使用方法
スクリプトを本来の意図通り、1歩ずつ移動せずに使用するには、移動ルートイベントを作成し、スクリプトコマンドとして以下を使用します：
find_path(target_x, target_y)
また、以下の呼び出しにより、スクリプト経由で経路を強制することもできます。これは、スクリプトが呼び出されるたびに1回だけ移動するように編集されたものです：
force_path(target_x, target_y)
Modern Algebraのスクリプトには、経路発見後の再計算に関する既知のバグがあります。このスクリプトの一部は彼の VX 版からの単純な変換であり（アルゴリズムのみがわずかに遅く、雑である点が異なります）、そのためこのバグもこのスクリプトに含まれています。
クレジット
- cozziekuns
- 彼の VX 版スクリプトを提供してくれた Modern Algebra
謝辞
- Patrick Lester氏。彼のよく知られた A* チュートリアル は非常に役立ちました。
#===============================================================================
# [VXA] Pathfinding
#-------------------------------------------------------------------------------
# Version: 1.0
# Author: cozziekuns (rmrk)
# Last Date Updated: 12/31/2011 (MM/DD/YYYY)
#===============================================================================
# Description:
#-------------------------------------------------------------------------------
# This script allows you to move any character to another tile using the
# shortest path possible. It takes a significantly longer time on large maps.
#===============================================================================
# Updates
# ------------------------------------------------------------------------------
# o 12/31/2011 - Started Script
#===============================================================================
# To-do List
#-------------------------------------------------------------------------------
# o Allow for dynamic recalculation if one wants to repeat the pathfinding
# process for any reason.
#===============================================================================
# Instructions
#-------------------------------------------------------------------------------
# To use, create a move route event and as a script command use:
#
# find_path(target_x, target_y)
#
# Additionally, one can force a path through a script using the following call:
#
# force_path(target_x, target_y)
#
# There is a known bug that is present in Modern Algebra's script regarding the
# recalculation of a path once found. Since some of this script is simply
# a convert from his VX version (only the algorithm is different by being
# slightly slower and sloppier :P), the bug is also found in this script.
#===============================================================================
#==============================================================================
# ** Game_Map
#==============================================================================
class Game_Map
def find_path(target_x, target_y, sx, sy, passable, char)
path = []
max_elements = width * height + 2
checked_items = 0
@open_list_items = 0
@open_list = Table.new(max_elements)
@nodes = Table.new(max_elements, 2)
open = Table.new(width, height)
closed = Table.new(width, height)
parent = Table.new(width, height, 3)
@f_cost = Table.new(width, height)
@open_list[0] = 0
@nodes[0, 0] = sx
@nodes[0, 1] = sy
next_point = [sx, sy]
closed[sx, sy] = 1
loop do
next_point = delete_from_heap if not next_point == [sx, sy]
# Target is unreachable — cancel search and stay idle
return [] if next_point.nil?
open[next_point[0], next_point[1]] = 0
closed[next_point[0], next_point[1]] = 2 if not next_point == [sx, sy]
parent_x, parent_y = next_point[0], next_point[1]
for i in 1..4
dir = i * 2
x, y = case dir
when 2; [parent_x, parent_y + 1]
when 4; [parent_x - 1, parent_y]
when 6; [parent_x + 1, parent_y]
when 8; [parent_x, parent_y - 1]
end
next unless $game_map.valid?(x, y)
next if closed[x, y] == 2
next unless custom_passable?(char, parent_x, parent_y, dir, x, y, target_x, target_y)
if not open[x, y] == 1
open[x, y] = 1
parent[x, y, 0] = parent_x
parent[x, y, 1] = parent_y
parent[x, y, 2] = parent[parent_x, parent_y, 2] + 10
g = parent[x, y, 2] + 10
h = ((target_x - x).abs + (target_y - y).abs) * 10
@f_cost[x, y] = g
checked_items += 1
@open_list_items += 1
@nodes[checked_items, 0] = x
@nodes[checked_items, 1] = y
add_to_heap(checked_items)
else
old_g = parent[x, y, 2] + 10
new_g = parent[parent_x, parent_y, 2] + 20
next if old_g < new_g
parent[x, y, 0] = parent_x
parent[x, y, 1] = parent_y
parent[x, y, 2] = new_g
g = parent[x, y, 2] + 10
h = ((target_x - x).abs + (target_y - y).abs) * 10
@f_cost[x, y] = g
end
end
next_point = nil
break if closed[target_x, target_y] == 2
end
# Double-check that destination was reached
return [] unless closed[target_x, target_y] == 2
path_x, path_y = target_x, target_y
loop do
parent_x = parent[path_x, path_y, 0]
parent_y = parent[path_x, path_y, 1]
dx = path_x - parent_x
dy = path_y - parent_y
if dx == 1
code = 6 # right
elsif dx == -1
code = 4 # left
elsif dy == 1
code = 2 # down
elsif dy == -1
code = 8 # up
else
code = 0
end
path.push(RPG::MoveCommand.new(code))
path_x, path_y = parent_x, parent_y
break if path_x == sx and path_y == sy
end
return path
end
def custom_passable?(char, x, y, d, nx, ny, target_x, target_y)
return false unless char.map_passable?(x, y, d)
return true if nx == target_x && ny == target_y
return !char.collide_with_characters?(nx, ny)
end
def add_to_heap(value)
m = @open_list_items
@open_list[m] = value
while m != 1
if fcost(@open_list[m]) < fcost(@open_list[m / 2])
temp = @open_list[m / 2]
@open_list[m / 2] = @open_list[m]
@open_list[m] = temp
m /= 2
else
break
end
end
end
def delete_from_heap
return nil if @open_list_items <= 0
next_point = @open_list[0]
@open_list[0] = @open_list[@open_list_items]
@open_list_items -= 1
v = 1
loop do
u = v
w = 2 * u
if w + 1 <= @open_list_items
v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
v = w + 1 if fcost(@open_list[v - 1]) >= fcost(@open_list[w])
elsif w <= @open_list_items
v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
end
if u != v
temp = @open_list[u - 1]
@open_list[u - 1] = @open_list[v - 1]
@open_list[v - 1] = temp
else
break
end
end
return nil if next_point.nil?
return @nodes[next_point, 0], @nodes[next_point, 1]
end
def fcost(point)
x = @nodes[point, 0]
y = @nodes[point, 1]
return @f_cost[x, y]
end
end
#==============================================================================
# ** Game_CharacterBase
#==============================================================================
class Game_CharacterBase
def find_path(target_x, target_y)
path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
path = path[0, 1] || []
@move_route.list.delete_at(@move_route_index)
path.each { |cmd| @move_route.list.insert(@move_route_index, cmd) }
@move_route_index -= 1
end
def force_path(target_x, target_y)
return if @x == target_x && @y == target_y
path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
return if path.nil? || path.empty?
next_step = path.last
move_straight(next_step.code)
end
def count_iterations(target_x, target_y)
path = $game_map.find_path(target_x, target_y, @x, @y, true, self)
return path.size
end
end