Pathfinding

**Version:** 1.0

**Author:** cozziekuns

**Date:** New Years Eve, 2011

**Version History**

- <Version 1.0> 2011.12.31 - Original Release

Planned Future Versions

- <Version 1.1> Allow for dynamic recalculation if one wants to repeat the path-finding process for any reason.

**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.

Features

- Incredibly fast and accurate pathfinding
- Easy script calls
- Almost no configuration

Screenshots

Not really applicable for this type of thing.

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

), the bug is also found in this script.

**Script**

`#===============================================================================`

# [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]

return path 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

x, y = case i * 2

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 if closed[x, y] == 2

next unless char.passable?(parent_x, parent_y, i * 2)

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

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]

if path_x < parent_x

code = 2

elsif path_x > parent_x

code = 3

else

code = path_y < parent_y ? 4 : 1

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 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

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 @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)

@move_route.list.delete_at(@move_route_index)

path.each { |i| @move_route.list.insert(@move_route_index, i) }

@move_route_index -= 1

end

def force_path(target_x, target_y)

path = $game_map.find_path(target_x, target_y, @x, @y, false, self)

path.reverse!

path.push (RPG::MoveCommand.new(0))

move_route = RPG::MoveRoute.new

move_route.list = path

move_route.repeat = false

force_move_route(move_route)

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

**Credit**

- cozziekuns
- Modern Algebra, for his VX version of the script

Thanks

- Patrick Lester, and his well known A* Tutorials which were immensely helpful.

**Author's Notes**

Happy New Years Eve! I'm in America right now so I don't get an early New Years