[XP] Yet Another A* Pathfinding Script! (NEW: Version 1.4)

[Cowlol]

A* Pathfinding Script
Version: 1.4


Introduction

Yeah, I know there are already tons of similar scripts out there, but I believe this one is more efficient than some of the other scripts I tried, and it also has (in my opinion!) better documentation. In case you don't know what A* is, it's an algorithm to find the optimal path from one node to another. In case of RPG Maker XP, it can find the path a character (event or player) should take from their current position to any other tile on the map. The character can then follow the map as if it was specified as a custom move route. This is particularly useful in strategy battle systems where the player selects a destination and the unit automatically moves to that position, avoiding any obstacles along the way. There are many other uses for such an algorithm, but that's for you to think about. As I said, this script is fairly efficient. Here's the time it takes my script to find a path through a simple map of a given size (in tiles):

50x50: 0.027 seconds
100x100: 0.25 seconds
500x500: 2.641 seconds

I tried the same maps with another script and got the following results:
50x50: 0.141 seconds
100x100: 1.5 seconds
500x500: script hanging

That's not to say my script is the fastest available (Eivien's pathfinding script is considerably faster on huge maps), but I'd say it's efficient enough for most purposes and definitely for my purposes. Of course, making it even faster is an option for future versions.

Some of the features of this script include a very simple interface that still allows power users to get the most out of the script, defining code to be called when the goal is reached or no path is found, using a goal 'area' (range around goal tile) instead of a single tile, automatically generating a new path if the path was obstructed by the time the character followed it (eg. another character blocked it), getting as close as possible to goal if no path was found.

The code is also well-documented. This is the first time I implemented A*, and I had to go through several tutorials and other implementations to do it, so I know how it feels when you want to learn something but the code you're learning from lacks good documentation.

Screenshots

There's not much to show really. Just a character groing from point A to point B. Instead, download the demo and see for yourself.

Demo

Script Demo
The demo includes a large variety of examples illustrating the different features of the script.

Script

Spoiler: Script (Version 1.4)

 

#==============================================================================

# ** A* Pathfinding Script

#------------------------------------------------------------------------------

#  Script by            :   RPG (aka Cowlol)

#  Last Update          :   September 26th, 2008

#  Version              :   1.4

#  Contact Information  :   ArePeeGee on AIM

#------------------------------------------------------------------------------

#  A relatively efficient implementation of the A* pathfinding algorithm.

# For more information on A*, check the following links:

#     1. [url=http://www.policyalmanac.org/games/aStarTutorial.htm]http://www.policyalmanac.org/games/aStarTutorial.htm[/url]

#     2. [url=http://www-cs-students.stanford.edu/~amitp/gameprog.html]http://www-cs-students.stanford.edu/~am ... eprog.html[/url]

#------------------------------------------------------------------------------

# Usage:

#

#   First you have to add this script somewhere under the default scripts

#   (and above main), I assume you know how to add a new script section and 

#   paste this script there. I don't know much about the SDK thing, but I 

#   don't think you'll get any trouble when using this scripts with others.

#   Note that this script overwrites the move_type_custom method of the

#   Game_Character class, any other script that modifies that method 

#   might clash with this one.

#

#   Now, simply create a new instance of the A_Star_Pathfinder class and 

#   supply it with the required parameters. For example, to have the player

#   move to tile (x, y), you could  add a script command to a new event

#   page and type something like:

#

#       goal_node = Node.new(x, y)             

#       path = A_Star_Pathfinder.new(goal_node)

#

#   The constructor can take more information, such as the character

#   that will move according to the result of pathfinding (Game_Character, 

#   map event ID, or -1 for player (default)), and whether the character 

#   should follow the path right away (true by default, if you set it to 

#   false, you'll have to call generate_path yourself). 

#   Here's another example of usage:

#

#       node = Node.new(x, y)

#       char = event_id         # same as char = $game_map.events[event_id]

#       path = A_Star_Pathfinder.new(node, char, false)

#       # do other stuff

#       path.generate_path      # and then generate the path

#

#   As an alternative, you can call the constructor without parameters,

#   and call the setup, calculate_path, and generate_path manually.

#   This gives you more control because the setup method allows you to

#   specify more options such as methods to call when the path is

#   reached or couldn't be found (implemented as Proc objects). 

#   You can also specify size of the goal area instead of looking for only 

#   one tile, and indicate whether the character should get as close as 

#   possible to goal if no path was found. Here's an example of such usage:

#

#     path = A_Star_Pathfinder.new

#     goal = Node.new(1, 0)

#     char = $game_player

#     range = 1

#     get_close = true

#     # lambda creates Procs, an alternative is Proc.new { ... }

#     reach = lambda { p "REACHD GOAL!!!" }

#     fail = lambda { p "COULDN'T FIND PATH!!!" }

#     path.setup(goal, char, range, get_close, reach, fail)

#     path.calculate_path

#     path.generate_path

#

#   If you used earlier versions of this script, you were able to supply

#   a limit on the number of pathfinding iterations performed (in case

#   you don't want the script to run for too long); this is now specified

#   by manually changing the constant ITERATION_LIMIT in A_Star_Pathfinder

#   class. A value of -1 (default) means no such limit is used.

#

#   Another interesting constant is COLLISION_WAIT, which is set to 5 by

#   default. This constant controls a feature that allows the character

#   to generate a new path if it was interrupted when following a path.

#   For example, a path might have been generated but as the character

#   was following it another character moved to block the path, setting

#   COLLISION_WAIT to any value bigger than -1 forces the generation of

#   another path to get around blocking characters, with the value of

#   the constant used to add some waiting between such attempts.

#

#   A related constant is COLLISION_LIMIT which imposes a limit on the

#   maximum number of times the character should try to find a new path

#   in case of collision, this is important because rare map design

#   and event movement conditions could result in the character stuck

#   trying to generate new paths forever. If you don't care for that,

#   you could set it to -1 to disregard the limit.

#

#   Starting with version 1.4, characters could be supplied with

#   multiple paths. Once the first path is reached or couldn't be

#   found, the next path is generated and followed, and so on. 

#   If you'd rather new paths were followed immediately instead of

#   waiting for current path to be followed, you'll have to stop

#   all pending paths by calling the stop_all_paths method on the

#   character and then creating the new path. You could also just

#   stop following the current path by calling the stop_path method.

#

#------------------------------------------------------------------------------

# Version Information:

#   - Version 1.4:

#       - Characters can now follow multiple paths. Generating another

#         path while character is following a path adds the new path

#         to a list so that it would be followed after all pending paths

#         were followed, instead of overwriting current path.

#       - Characters now get stop_path and stop_all_paths methods to

#         stop following current path and follow the next one in the

#         list, and to stop all paths and empty the list. stop_all_paths

#         could be used to imitate the old behavior of overwriting

#         current path and following new one immediately.

#       - Fixed various bugs caused by the introduction of multiple paths.

#       - You can now supply integer values in place of Game_Character,

#         the value is the event map ID or -1 for the player character.

#   - Version 1.3:

#       - Changed collision_wait and limit variables to COLLISION_WAIT

#         and ITERATION_LIMIT constants that are changed manually in

#         the script and that apply to all pathfinding. I think this

#         makes the script neater.

#       - Added a COLLISION_LIMIT constant to control number of path-

#         finding attempts on collision.

#       - Added the ability to specify a goal area instead of single node,

#         this is achieved by supplying the setup method with a range of

#         tiles around the goal, with 0 (the default) disabling that

#         feature. Pathfinding succeeds as soon as a tile within the

#         goal's range (see in_range? method) is found.

#       - Character can now try to get as close as possible to tile

#         if a path wasn't found.

#       - Switched to a zlib/libpng license for terms of use, which

#         is mostly a more formal version of the old terms.

#   - Version 1.2:

#       - Fixed a recursive bug with tiles with directional passability,

#         thanks to Twin Matrix for pointing it out!

#       - Removed the cache pass feature because it was useless.

#   - Version 1.1:

#       - Added a mechanism to prevent the generated path from being

#         blocked by other characters. When such a collision happens,

#         the character will try to generate a new path to goal. This

#         can be turned off if you set collision_wait to -1

#       - Now you can provide blocks to be called when the path is

#         reached or if no path is found.

#       - Added the cache pass flag to allow generating passability

#         information in a Table for faster access. This was inspired

#         by a post by Anaryu at 

#         http://www.rmxp.org/forums/showthread.php?t=16589

#       - Better documentation

#   - Version 1.0:

#       - Initial release version.

#------------------------------------------------------------------------------

# Known bugs:

#

#   - Slower than Eivien's pathfinder at:

#       http://www.rmxp.org/forums/showthread.php?t=24242

#     this is not really a bug but I'm interested in learning more

#     about efficient implementations of A*.

#   - Found a bug or have some ideas for the next version? Tell me on AIM!

#------------------------------------------------------------------------------

# Terms of Use:

#

#   I'm releasing this script under a zlib/libpng license which means

#   you can use it any way you like as long as you don't claim it as

#   your own and keep the following notice unchanged. If you have any

#   questions or problems regarding this script, feel free to contact me.

#

#   Copyright (c) 2007 Firas Assad

#

#   This software is provided 'as-is', without any express or implied

#   warranty. In no event will the authors be held liable for any damages

#   arising from the use of this software.

#

#   Permission is granted to anyone to use this software for any purpose,

#   including commercial applications, and to alter it and redistribute it

#   freely, subject to the following restrictions:

# 

#   1.  The origin of this software must not be misrepresented; you must 

#       not claim that you wrote the original software. If you use this 

#       software in a product, an acknowledgment in the product 

#       documentation would be appreciated but is not required.

#

#   2.  Altered source versions must be plainly marked as such, and 

#       must not be misrepresented as being the original software.

#

#   3.  This notice may not be removed or altered from any 

#       source distribution.

#

#

#==============================================================================

 

#==============================================================================

# ** Node

#------------------------------------------------------------------------------

#  A node represents part of the path generated by the pathfinder,

#  It corrosponds to a single tile

#==============================================================================

 

class Node

  #--------------------------------------------------------------------------

  # * Public Instance Variables

  #--------------------------------------------------------------------------

  attr_accessor :x                        # x coordinate of current node

  attr_accessor :y                        # y coordinate of current node

  attr_accessor :parent                   # parent node

  attr_accessor :g                        # cost of getting to this node

  attr_accessor :h                        # distance to goal (heuristic)

  #--------------------------------------------------------------------------

  # * Object Initialization

  #--------------------------------------------------------------------------

  def initialize(x, y, parent = nil, g = 0, h = 0)

    @x = x

    @y = y

    @parent = parent

    @g = g

    @h = h

  end

  #--------------------------------------------------------------------------

  # * The Total 'Cost' at This Node (AKA f(n))

  #--------------------------------------------------------------------------

  def cost

    # f(n) = g(n) + h(n)

    return @g + @h

  end

  #--------------------------------------------------------------------------

  # * Two Nodes Are Equal If They Are on the Same Tile

  #--------------------------------------------------------------------------

  def ==(other)

    return false unless other and other.is_a?(Node)

    return true if other.x == @x and other.y == @y

    return false

  end

  

  #--------------------------------------------------------------------------

  # * Check If Another Node is Within This Node's Range

  #--------------------------------------------------------------------------

  def in_range?(other, range)

    # Get absolute value of difference

    abs_sx = (@x - other.x).abs

    abs_sy = (@y - other.y).abs

    return abs_sx + abs_sy <= range

  end

end

 

#==============================================================================

# ** A_Star_Pathfinder

#------------------------------------------------------------------------------

#  This class generates a path using the A* algorithm. Not a very good

#  implementation but I'm still proud of it.

#==============================================================================

 

class A_Star_Pathfinder

  #--------------------------------------------------------------------------

  # * Constants

  #--------------------------------------------------------------------------

  ITERATION_LIMIT = -1        # Maximum number of loop iterations before

                              # the pathfinder gives up. -1 for infinity.

  COLLISION_WAIT = 5          # No. of frames to wait before attempting to

                              # find another path in case of collision; 

                              # -1 disables such collision behevior. 

  COLLISION_LIMIT = 30        # Maximum number of attempts to find another

                              # path in case of collision. -1 for infinity.

  #--------------------------------------------------------------------------

  # * Public Instance Variables

  #--------------------------------------------------------------------------

  attr_reader   :goal_node                # the goal!

  attr_reader   :character                # character looking for a path

  attr_reader   :found                    # was the path found?

  attr_reader   :route                    # the route returned after 

                                          # calling generate_path

  attr_accessor :range                    # Size of goal area

  attr_accessor :get_close                # If true and no path is found then

                                          # get as close as possible.

  attr_accessor :reach_method             # Proc called when goal is reached

  attr_accessor :fail_method              # Proc called when no path is found

  attr_accessor :original_goal_node       # goal node before pathfinding

  attr_accessor :collision_counter        # counter for the number of times path

                                          # was obstructed and re-generated

  

  #--------------------------------------------------------------------------

  # * Object Initialization

  #     goal_node : A Node representing the end point

  #     char      : The character that'd use the result of pathfinding,

  #                 either a Game_Character, event ID, or -1 for player

  #     run       : If true, the path is also generated

  #--------------------------------------------------------------------------

  def initialize(goal_node = nil, char = -1, run = true)

    # If no goal node is provided, this acts as a default constructor that

    # takes no parameters and does nothing. Useful if you do things manually

    unless goal_node

      return

    end

    # Setup variables

    setup(goal_node, char)

    # Find the optimal path

    calculate_path

    # We're done, time to generate the path

    generate_path if run

  end

  

  #--------------------------------------------------------------------------

  # * Setup Initial Values for Variables

  #     goal_node : A Node representing the end point

  #     character : The character that'd use the result of pathfinding

  #     range     : The size of the goal area, 0 means the goal is the

  #                 node, 1 means within 1 tile around goal, etc.

  #     close     : If true the character will try to get as close as

  #                 possible to path if it isn't found.

  #     reach     : A Proc that will be called when the goal is reached

  #     fail      : A proc that will be called if no path was found

  #--------------------------------------------------------------------------

  def setup(goal_node, character, range = 0, close = false,

            reach = nil, fail = nil)

    @original_goal_node = Node.new(goal_node.x, goal_node.y)

    @goal_node = Node.new(goal_node.x, goal_node.y)

    @character = A_Star_Pathfinder.int_to_character(character)

    unless @character

      raise "A_Star_Pathfinder Error : Invalid Character"

    end

    @start_node = Node.new(@character.x, @character.y)

    @range = range

    @get_close  = close

    @reach_method = reach

    @fail_method = fail

 

    @open_list = Array.new            # List of nodes to be checked,

                                      # implemented as a binary heap

    @open_list.push(@start_node)    

    @closed_list = Hash.new           # Set of nodes already checked, this

                                      # is a hash of arrays of [x, y] pairs

                                      # representing map tiles

    @found = false

    # Saves node with lowest h in case we want to get close to it

    @nearest = Node.new(0, 0, 0, -1)

  end

  

  #--------------------------------------------------------------------------

  # * Search For the Optimal Path

  #--------------------------------------------------------------------------

  def calculate_path

    iterations_counter = 0

    # Only do calculation if goal is actually passable, unless we only

    # need to get close or within range

    if @character.passable?(@goal_node.x, @goal_node.y, 0) or 

       @get_close or

       @range > 0

      until @open_list.empty?

        iterations_counter = iterations_counter + 1

        # Prevents script hanging

        Graphics.update if (iterations_counter % 200 == 0) 

        # If we hit the iteration limit, exit

        if ITERATION_LIMIT != -1 and iterations_counter >= ITERATION_LIMIT

          @found = false

          break

        end

        # Get the node with lowest cost and add it to the closed list

        @current_node = find_lowest_cost

        @closed_list[[@current_node.x, @current_node.y]] = @current_node

        if @current_node == @goal_node or 

           (@range > 0 and @goal_node.in_range?(@current_node, @range))

          # We reached goal, exit the loop!

          @original_goal_node = @goal_node

          @goal_node = @current_node

          @found = true

          break

        else # if not goal

          # Keep track of the node with the lowest cost so far

          if @current_node.h < @nearest.h or @nearest.h < 1

            @nearest = @current_node

          end

          # Get adjacent nodes and check if they can be added to the open list

          adjacent_nodes = get_adjacent_nodes(@current_node)

          for adj_node in adjacent_nodes

            if skip_node?(adj_node)

              # Node already exists in one of the lists, skip it

              next

            end

            # Add node to open list following the binary heap conventions

            heap_add(@open_list, adj_node)

          end

        end

      end

    end

    # If no path was found, see if we can get close to goal

    unless @found

      if @get_close and @nearest.h > 0

        @goal_node = @nearest

        setup(@goal_node, @character, @range, @get_close, @reach_method, 

                 @fail_method)

        calculate_path

      else

        # Call the fail method if one is provided

        if @fail_method

          @fail_method.call

        end

      end

    end

  end

  

  #--------------------------------------------------------------------------

  # * Return Game_Character Object From Integer Arguments

  #     char  : If -1, the player character is returned; for other integers,

  #             map event with ID matching the integer is returned

  #--------------------------------------------------------------------------  

  def self.int_to_character(char)

    if char.is_a?(Integer)

      if char == -1

        char = $game_player

      else

        char = $game_map.events[char]

      end

    end

    return char

  end

  

  #--------------------------------------------------------------------------

  # * Add an Item to the Binary Heap (for open_list). This is Based on

  #   Algorithm Here: [url=http://www.policyalmanac.org/games/binaryHeaps.htm]http://www.policyalmanac.org/games/binaryHeaps.htm[/url]

  #     array : Array to add the node to

  #     item  : Item to add!

  #--------------------------------------------------------------------------

  def heap_add(array, item)

    # Add the item to the end of the array

    array.push(item)

    # m is the index of the 'current' item

    heap_update(array, array.size - 1)

  end

  

  #--------------------------------------------------------------------------

  # * Make Sure the Item at Index is in the Right Place

  #     array : Array to update

  #     index : Index of the item

  #--------------------------------------------------------------------------

  def heap_update(array, index)

    m = index

    while m > 0

      # If current item's cost is less than parent's

      if array[m].cost <= array[m / 2].cost

        # Swap them so that lowest cost bubbles to top

        temp = array[m / 2]

        array[m / 2] = array[m]

        array[m] = temp

        m /= 2

      else

        break

      end

    end

  end

  

  #--------------------------------------------------------------------------

  # * Remove an Item from the Binary Heap (for open_list) & Return it.

  #   This is Based on Algorithm Here: 

  #   http://www.policyalmanac.org/games/binaryHeaps.htm

  #     array : Array to remove the node from

  #--------------------------------------------------------------------------

  def heap_remove(array)

    if array.empty?

      return nil

    end

    #Get original first element

    first = array[0]

    # Replace first element with last one

    last = array.slice!(array.size - 1)

    if array.empty?

      return last

    else

      array[0] = last

    end

    v = 0   # Stores a smaller child, if any

    # Loop until no more swapping is needed

    while true

      u = v

      # If both children exist

      if 2 * u + 1 < array.size

        v = 2 * u if array[2 * u].cost <= array[u].cost

        v = 2 * u + 1 if array[2 * u + 1].cost <= array[v].cost

      # If only one child exists

      elsif 2 * u < array.size

        v = 2 * u if array[2 * u].cost <= array[u].cost

      end

      # If at least one child is less than parent, swap them

      if u != v

        temp = array[u]

        array[u] = array[v]

        array[v] = temp

      else

        break

      end

    end

    # Return the original first node (which was removed)

    return first

  end

  

  #--------------------------------------------------------------------------

  # * Can We Skip This Node? (because it already exists in a list)

  #     node : Node to check

  #--------------------------------------------------------------------------

  def skip_node?(node)

    skip_node = false

    copy = @open_list.index(node)

    if copy

      #If the existing copy is 'better' than the new one, skip new node

      if @open_list[copy].cost <= node.cost

        skip_node = true

      else

        # Otherwise swap them, making sure heap is in right order

        @open_list[copy] = node

        heap_update(@open_list, copy)

        skip_node = true

      end

    end

    # The closed list is a hash so this is relatively easier

    if @closed_list[[node.x, node.y]]

      # If the existing copy is 'better' than the new one

      if @closed_list[[node.x, node.y]].cost <= node.cost

        skip_node = true

      else

        # Update the existing node

        @closed_list[[node.x, node.y]] = node

      end

    end

    # Return the result

    return skip_node

  end

 

  #--------------------------------------------------------------------------

  # * Find Node With Lowest Cost on the Open List

  #--------------------------------------------------------------------------

  def find_lowest_cost

    # Just return top of the heap

    return  heap_remove(@open_list)

  end

  

  #--------------------------------------------------------------------------

  # * Distance Between Two Points (Heuristic)

  #--------------------------------------------------------------------------

  def distance(x1, y1, x2, y2)

    # A simple heuristic value (Manhattan distance)

    return ((x1 - x2).abs + (y1 - y2).abs)

  end

  

  #--------------------------------------------------------------------------

  # * Get a List of Adjacent Nodes

  #     node : The 'center' node

  #--------------------------------------------------------------------------

  def get_adjacent_nodes(node)

    # Array to hold the nodes

    nodes = Array.new

    # Right

    new_x = node.x + 1

    new_y = node.y

    add_node(nodes, new_x, new_y, node)

    # Left

    new_x = node.x - 1

    new_y = node.y

    # Down

    add_node(nodes, new_x, new_y, node)

    new_x = node.x

    new_y = node.y + 1

    add_node(nodes, new_x, new_y, node)

    # Up

    new_x = node.x

    new_y = node.y - 1

    add_node(nodes, new_x, new_y, node)

    return nodes

  end

  

  #--------------------------------------------------------------------------

  # * Add a Node to an Array

  #--------------------------------------------------------------------------

  def add_node(array, x, y, parent)

    direction = get_direction(x, y, parent.x, parent.y)

    if @character.passable?(parent.x, parent.y, direction)

      # The cost of movement one step to a new tile is always 1

      g = parent.g + 1

      # The heuristic is simply the distance

      h = distance(x, y, @goal_node.x, @goal_node.y)

      new_node = Node.new(x, y, parent, g, h)

      array.push(new_node)

    end

  end

 

  #--------------------------------------------------------------------------

  # * Get Direction From a Point to Another

  #--------------------------------------------------------------------------

  def get_direction(x1, y1, x2, y2)

    # If first point is to the ... of the second

    if x1 > x2        # right

      return 6

    elsif x1 < x2     # left

      return 4

    elsif y1 > y2     # bottom

      return 2

    elsif y1 < y2     # top

      return 8

    end

    # Otherwise they are on the same position

    return 0

  end

 

  #--------------------------------------------------------------------------

  # * Generate the Path by Following Parents and Return it 

  #   as RPG::MoveRoute

  #     follow : If true the path is assigned to the character as a

  #     forced move route.

  #--------------------------------------------------------------------------

  def generate_path(follow = true)

    # There's no path to generate if no path was found

    if !@found

      return

    end

    # Create a new move route that isn't repeatable

    @route = RPG::MoveRoute.new

    @route.repeat = false

    # Generate path by starting from goal and following parents

    node = @goal_node

    code = 0    # Movement code for RPG::MoveCommand

    while node.parent

      # Get direction from parent to node as RPG::MoveCommand

      direction = get_direction(node.parent.x, node.parent.y, node.x, node.y)

      case direction

        when 2 # Up

          code = 4

        when 4 # Left

          code = 3

        when 6 # Right

          code = 2

        when 8 # Down

          code = 1

      end

      # Add movement code to the start of the array

      @route.list.unshift(RPG::MoveCommand.new(code)) if code != 0

      node = node.parent

    end

    # If the path should be assigned to the character

    if follow and !@route.list.empty?

      @character.add_path(self)

    end

    # Return the constructed RPG::MoveRoute

    return @route

  end

end

 

#==============================================================================

# ** Game_Character 

#------------------------------------------------------------------------------

#  Just make the move_route variables public

#==============================================================================

 

class Game_Character

  attr_accessor :move_route_forcing

  attr_accessor :move_route

  attr_accessor :a_star_paths         # all the paths assigned to character

  #--------------------------------------------------------------------------

  # * Object Initialization

  #--------------------------------------------------------------------------

  # Alias to add path variable, 'stack level too deep' error is prevented

  # since $@ (error locations) is set after player presses F12

  unless $@

    alias :a_star_pathfinder_old_initialize :initialize

  end

  def initialize

    a_star_pathfinder_old_initialize

    @a_star_paths = []

  end

  #--------------------------------------------------------------------------

  # * Add a Path to be Followed by Character

  #-------------------------------------------------------------------------- 

  def add_path(path)

    path.collision_counter = 0

    @a_star_paths.push(path)

    if @a_star_paths.size == 1

      force_move_route(path.route)

    end

  end

  

  #--------------------------------------------------------------------------

  # * Stop Custom Movement

  #--------------------------------------------------------------------------

  def stop_custom_movement

    if @move_route

      @move_route_index = @move_route.list.size

      # The move route is no longer forced (moving ended)

      @move_route_forcing = false

      # Restore original move route

      @move_route = @original_move_route

      @move_route_index = @original_move_route_index

      @original_move_route = nil

    end

  end

  

  #--------------------------------------------------------------------------

  # * Follow Next Path, if Any

  #--------------------------------------------------------------------------   

  def follow_next_path

    stop_custom_movement

    @a_star_paths.shift

    if @a_star_paths[0]

      # Setup path again to reflect any changes since original creation

      goal = @a_star_paths[0].original_goal_node

      char = @a_star_paths[0].character

      range = @a_star_paths[0].range

      close = @a_star_paths[0].get_close

      reach = @a_star_paths[0].reach_method

      fail = @a_star_paths[0].fail_method

      @a_star_paths[0].setup(goal, char, range, close, reach, fail)

      @a_star_paths[0].calculate_path

      @a_star_paths[0].generate_path(false)

      force_move_route(@a_star_paths[0].route) if @a_star_paths[0].found

    end

  end

  

  #--------------------------------------------------------------------------

  # * Stop Following Current Path

  #-------------------------------------------------------------------------- 

  def stop_path

    if @a_star_paths[0]

      stop_custom_movement

      follow_next_path 

    end

  end

  

  #--------------------------------------------------------------------------

  # * Stop All Generated Paths

  #-------------------------------------------------------------------------- 

  def stop_all_paths

    stop_custom_movement

    @a_star_paths = []

  end

  

  #--------------------------------------------------------------------------

  # * Move Type : Custom (move event, pattern, etc.)

  #   Note: The script overwrites this method, which _might_ lead to

  #   compatibility problems with other scripts. You can remove this

  #   method to fix any such problem, but the character won't be able

  #   to detect the need to recalculate the path.

  #--------------------------------------------------------------------------

  def move_type_custom

    # Interrupt if not stopping

    if jumping? or moving?

      return

    end

    # For each move command starting from the index

    while @move_route_index < @move_route.list.size

      # Get the move command at index

      command = @move_route.list[@move_route_index]

      # If command code is 0 (end of list)

      if command.code == 0

        # If [repeat action] option is ON

        if @move_route.repeat

          # Reset move route index to the top of the list

          @move_route_index = 0

        end

        # If [repeat action] option is OFF

        unless @move_route.repeat

          # If move route is forced and not repeating

          if @move_route_forcing and not @move_route.repeat

            # The move route is no longer forced (moving ended)

            @move_route_forcing = false

            # Restore original move route

            @move_route = @original_move_route

            @move_route_index = @original_move_route_index

            @original_move_route = nil

### CODE ADDED HERE ############################################################

            # If there was a path to follow and we reached goal

            if @a_star_paths[0]

              if self.x == @a_star_paths[0].goal_node.x and 

                  y == @a_star_paths[0].goal_node.y

                # Call the reach method if one was provided

                if @a_star_paths[0].reach_method

                  @a_star_paths[0].reach_method.call

                end

              end

              follow_next_path 

            end

### ADDED CODE ENDS ############################################################

          end

          # Clear stop count

          @stop_count = 0

        end

        return

      end # if command.code == 0

      # For move commands (from move down to jump)

      if command.code <= 14

        # Branch by command code

        case command.code

        when 1  # Move down

          move_down

        when 2  # Move left

          move_left

        when 3  # Move right

          move_right

        when 4  # Move up

          move_up

        when 5  # Move lower left

          move_lower_left

        when 6  # Move lower right

          move_lower_right

        when 7  # Move upper left

          move_upper_left

        when 8  # Move upper right

          move_upper_right

        when 9  # Move at random

          move_random

        when 10  # Move toward player

          move_toward_player

        when 11  # Move away from player

          move_away_from_player

        when 12  # 1 step forward

          move_forward

        when 13  # 1 step backward

          move_backward

        when 14  # Jump

          jump(command.parameters[0], command.parameters[1])

        end

        # If movement failure occurs when [Ignore if can't move] option is OFF

        if not @move_route.skippable and not moving? and not jumping?

### CODE ADDED HERE ############################################################

          # If there's a path but it couldn't be followed (probably because

          # another character blocked it)

          if @a_star_paths[0] and 

             A_Star_Pathfinder::COLLISION_WAIT >= 0 and

             (A_Star_Pathfinder::COLLISION_LIMIT < 0 or

             @a_star_paths[0].collision_counter <= A_Star_Pathfinder::COLLISION_LIMIT)

            # Setup path again to update starting location.

            # original goal node is used because pathfinding changes

            # the goal node to current node

            goal = @a_star_paths[0].original_goal_node

            char = @a_star_paths[0].character

            range = @a_star_paths[0].range

            close = @a_star_paths[0].get_close

            reach = @a_star_paths[0].reach_method

            fail = @a_star_paths[0].fail_method

            counter = @a_star_paths[0].collision_counter

            # Find another path to goal

            @a_star_paths[0] = A_Star_Pathfinder.new

            @a_star_paths[0].setup(goal, char, range, close, reach, fail)

            @a_star_paths[0].calculate_path

            @a_star_paths[0].generate_path(false)

            @a_star_paths[0].collision_counter = counter + 1

            force_move_route(@a_star_paths[0].route) if @a_star_paths[0].found

            # Wait a bit before starting to follow the new path

            @wait_count = A_Star_Pathfinder::COLLISION_WAIT

            return

          elsif @a_star_paths[0]

            # If collision wait is -1 or reached collision limit,

            # stop character and call any fail method

            @move_route_index = @move_route.list.size

            if @a_star_paths[0].fail_method 

              @a_star_paths[0].fail_method.call

            end

            follow_next_path 

          end

### ADDED CODE ENDS ############################################################

          return

        end

        # Advance index

        @move_route_index += 1

        return

      end # if command.code <= 14

      # If waiting

      if command.code == 15

        # Set wait count (from provided parameter)

        @wait_count = command.parameters[0] * 2 - 1

        @move_route_index += 1

        return

      end # if command.code == 15

      # If direction change (turning) command

      if command.code >= 16 and command.code <= 26

        # Branch by command code

        case command.code

        when 16  # Turn down

          turn_down

        when 17  # Turn left

          turn_left

        when 18  # Turn right

          turn_right

        when 19  # Turn up

          turn_up

        when 20  # Turn 90° right

          turn_right_90

        when 21  # Turn 90° left

          turn_left_90

        when 22  # Turn 180°

          turn_180

        when 23  # Turn 90° right or left

          turn_right_or_left_90

        when 24  # Turn at Random

          turn_random

        when 25  # Turn toward player

          turn_toward_player

        when 26  # Turn away from player

          turn_away_from_player

        end

        @move_route_index += 1

        return

      end # if command.code >= 16 and command.code <= 26

      # If other command (commands that don't 'return')

      if command.code >= 27

        # Branch by command code

        case command.code

        when 27  # Switch ON

          $game_switches[command.parameters[0]] = true

          $game_map.need_refresh = true

        when 28  # Switch OFF

          $game_switches[command.parameters[0]] = false

          $game_map.need_refresh = true

        when 29  # Change speed

          @move_speed = command.parameters[0]

        when 30  # Change freq

          @move_frequency = command.parameters[0]

        when 31  # Move animation ON

          @walk_anime = true

        when 32  # Move animation OFF

          @walk_anime = false

        when 33  # Stop animation ON

          @step_anime = true

        when 34  # Stop animation OFF

          @step_anime = false

        when 35  # Direction fix ON

          @direction_fix = true

        when 36  # Direction fix OFF

          @direction_fix = false

        when 37  # Through ON

          @through = true

        when 38  # Through OFF

          @through = false

        when 39  # Always on top ON

          @always_on_top = true

        when 40  # Always on top OFF

          @always_on_top = false

        when 41  # Change Graphic

          # Can't change into a tile

          @tile_id = 0

          @character_name = command.parameters[0]

          @character_hue = command.parameters[1]

          # Update direction

          if @original_direction != command.parameters[2]

            @direction = command.parameters[2]

            @original_direction = @direction

            @prelock_direction = 0

          end

          # Update frame

          if @original_pattern != command.parameters[3]

            @pattern = command.parameters[3]

            @original_pattern = @pattern

          end

        when 42  # Change Opacity

          @opacity = command.parameters[0]

        when 43  # Change Blending

          @blend_type = command.parameters[0]

        when 44  # Play SE

          $game_system.se_play(command.parameters[0])

        when 45  # Script

          result = eval(command.parameters[0])

        end

        # Update move_route_index and move to next move command in the list

        @move_route_index += 1

      end # if command.code >= 27

    end # while @move_route_index < @move_route.list.size

  end 

 

end

 

 

Instructions
Check the big comment at the top of the script!

FAQ

Waiting for some~

Version Info

Version 1.4:
- Characters can now follow multiple paths. Generating another path while character is following a path adds the new path to a list so that it would be followed after all pending paths were followed, instead of overwriting current path.
- Characters now get stop_path and stop_all_paths methods to stop following current path and follow the next one in the list, and to stop all paths and empty the list. stop_all_paths could be used to imitate the old behavior of overwriting current path and following new one immediately.
- Fixed various bugs caused by the introduction of multiple paths.
- You can now supply integer values in place of Game_Character, the value is the event map ID or -1 for the player character.

Refer to the big comment at the top of the script for previous versions.

 

[samamanjaro]

Oh sweeto, thanks for this, I was looking for a nice recent pathfinding script, thanks!

 

[Link in Pink]

This is a great pathfinding script. I'll be using this ;D

 

[Kain Nobel]

110% awesomeness and a half man, great job! :thumb:

I was impressed about how quickly the events in the demo (and the extra ones I set up to test) were to recalculate the optimal path to get to their destinations in real time! The avoiding events test works like a charm, the maze test was pure perfection, and the event tracking the player test was pretty cool too. I expanded the map to 100x100 and made 25 events to hunt the player down, and no matter where I went they would find me quick even when I tried to make my own maze more tricky and block 3/4ths of each of the possible paths off.

Things I always wanted to do as far as NPC management was to use a day/night system to put events on a scheduel, and use a pathfinding system so those events could find their way home at night, or find their way to work during the day no matter where they were on the map, but origionally that would require micromanaging each and every damn event on the map, who wants to do that? With this, it would be possible without the micromanagement of predetermined move routes, the AStar system gets an A+

There are some small things that could be easier, like instead of doing...

ch = $game_map.events[003] or whatever, then using ch in your arg, you could always just put an integer in the arg for -1 as player, 0 as this event and 1 or more for event ID. Other than that, I'm definately going to be using this too!

 

[Cowlol]

110% awesomeness and a half man, great job! :thumb:

I was impressed about how quickly the events in the demo (and the extra ones I set up to test) were to recalculate the optimal path to get to their destinations in real time! The avoiding events test works like a charm, the maze test was pure perfection, and the event tracking the player test was pretty cool too. I expanded the map to 100x100 and made 25 events to hunt the player down, and no matter where I went they would find me quick even when I tried to make my own maze more tricky and block 3/4ths of each of the possible paths off.

Things I always wanted to do as far as NPC management was to use a day/night system to put events on a scheduel, and use a pathfinding system so those events could find their way home at night, or find their way to work during the day no matter where they were on the map, but origionally that would require micromanaging each and every damn event on the map, who wants to do that? With this, it would be possible without the micromanagement of predetermined move routes, the AStar system gets an A+

There are some small things that could be easier, like instead of doing...

ch = $game_map.events[003] or whatever, then using ch in your arg, you could always just put an integer in the arg for -1 as player, 0 as this event and 1 or more for event ID. Other than that, I'm definately going to be using this too!

Thanks, I really appreciate your reply. I'm glad you found the script useful, I never thought of using the script for a day/night system like that, so it's nice to see people using it in different ways. I personally wrote it for a tactical battle system, but I know someone else was using it to have all guards in area move towards player once player is spotted by a guard, and then there's your system. The cool thing about scripts like this is that they are just bases for more complex systems, instead of being the system itself. It still requires a game designer to tweak it into their own vision, instead of just plugging countless scripts in a game and then calling it yours.

Your integer argument suggestion is excellent, I'll definitely have it in the next version.

 

[Cowlol]

I just released a new version (1.4). The biggest addition is the ability to have multiple paths that will be executed in order; in other words, if you create a path for a character to follow while the same character is already following a path you created earlier, the character adds the new path to a list and continues following the old path until the goal is reached or character gives up, at which point the next path in the list is generated (starting from where old path ended) and followed.

The old behavior was that new paths overwrote old paths, and if you still want that behavior you should call the stop_all_paths method on the character before creating a new path; this effectively stops processing all previously added paths and starts with an empty list. You could also just stop the path currently being followed using the stop_path method of Game_Character. Refer to version information and instructions for more information.

Another addition is Kain Nobel's suggestion of specifying character as an integer, which is interpreted as the event's map ID or as the player if the argument was -1.

Due to the new multiple paths feature, there are several additions to the Game_Character class and some changes in overwritten methods, so if you're trying to get this script work with something else you might want to go over that class again. The new changes could also introduce new bugs, so please notify me if you spot one. It could also break some old scripts that depend on the one-script-at-a-time behavior.

 

[Twin Matrix]

Hi hi. So few posts. o_O This is a great script!

Anyways. I was wondering, how do I add movement to the end of a path? E.g. I want the player to move to point B and then turn up. I can't do it through that "wait for all movement" thing, because there are other characters pathfinding during that time as well. (It's a chase.) And those other characters aren't done yet when the player reaches point B.

 

[Cowlol]

Well that's a good idea. dario8676 PM'd me asking for the ability to specify how many steps to take following the path (instead of following the whole thing), and that's a good idea too. They'll definitely be in the next version.

I've been pretty busy recently, however, so it might take a couple of weeks (or more) before I release that. Sorry...

 

[Twin Matrix]

Wow, okay, I thought that was already in the script. I must have confused it with Near_Fantastica's.

Ok cool. ^^ Can't wait to see it.

And that other one is a good idea, too, though I honestly don't see any practical use for it.. X_x

 

[dario8676]

Being able to specify the # of steps to take following a path would be useful if doing like a tactical type battle engine.

 

[Twin Matrix]

^

Oh, okay, right. ^^

Hey, cowlol, I have a question. I'm working into my system, that it first tries to give an event a path, and if the way is blocked, it uses the move_to def, which teleports the event. But to do the move_to, it should check first if the event has a path or not.

So basically, how do I check for if an event has a (working) path?

Thanks!

 

[Cowlol]

Well, you could use the failure method for that:

path = A_Star_Pathfinder.new
goal = Node.new(x, y)
char = $game_player
range = 1
get_close = true
# Method to call when path is reached
reach = nil
# Method to call when unable to reach path
fail = lambda { char.move_to(x, y) }
path.setup(goal, char, range, get_close, reach, fail)
path.calculate_path
path.generate_path

An alternative is to check the value of path.found after calling path.calculate path, but there will still be cases when found is true but the path isn't reached (because another character is in the way for example). So it's best to use the failure method, you could put any code you want between the curly brackets.

 

[dario8676]

Hey cowlol, i'm just a little curious. You said that you originally made this pathfinding script for a tactical type battle engine right? How did you handle specifying the number of steps that could be taken towards an event/enemy/e.t.c without being able to specify any kind of movement counter tracker in your script? In other words, if the enemy was only 2 tile spaces away to your right, but there was a stream of water blocking the path, and it would actually take 10 steps or so to walk around that stream in order to reach the enemy. How would you tell the event not to move/follow the path in that situation?

Technically he would be in attack/target range for the player/event, so logic would tell him that he could reach the enemy, but in reality it would take more than 2 steps to reach him because of the stream of water. See what i mean?

 

[Cowlol]

Well, two things:

1. One option the script gives you is to generate a path but not follow it (pathfinder.generate_path(false)), then you can access the route using pathfinder.route or by the return value of the generate_path method. Using that route, I could check the route's size (route.list.size - 1) to know how long it takes me to reach a place. I account for that number in AI's next move calculation and if it's within bounds, I manually add it to the character I want to control (character.add_path(pathfinder)). I could also have the character follow a route until their turn points (or steps) run out, but that's a property in my modification of the character and actor classes and not the script itself (if character turn points == 0, stop moving and delete all paths). There's no partial pathfinding because I just have the character calculate paths to all opponents and follow the shortest one until turn points are consumed.

2. I haven't done much work on enemy turn yet; most of my work so far has been on player turn and I didn't need pathfinding much. So I never got the chance to thoroughly test it in that area. Feel free to notify me about any problems or needs that arise as you give it a try.

With that said, I'll certainly work on implementing your suggestion because I can think of several scenarios where it'd be desirable. It's not exactly hard to implement the new functionality, but I've been pretty busy as I mentioned earlier. Hopefully I'd get some time to work on it within the next week.

 

[Twin Matrix]

Well, you could use the failure method for that:

path = A_Star_Pathfinder.new
goal = Node.new(x, y)
char = $game_player
range = 1
get_close = true
# Method to call when path is reached
reach = nil
# Method to call when unable to reach path
fail = lambda { char.move_to(x, y) }
path.setup(goal, char, range, get_close, reach, fail)
path.calculate_path
path.generate_path

An alternative is to check the value of path.found after calling path.calculate path, but there will still be cases when found is true but the path isn't reached (because another character is in the way for example). So it's best to use the failure method, you could put any code you want between the curly brackets.

Hmm. Is there a way to do that shorter, or do add that into the script somewhere? Because I call like 6 paths in a row each time (as it checks for passability of a tile, and then if it isn't passable, it calls a new path) and that whole bunch of code wouldn't fit in with the ifs and switches and variables that change. X_X

Actually. Wait, what. What is @get_close? o_o Does that mean that if the target tile isn't passable, the character still moves as close as possible? Or does it mean that if the path is blocked, that the character moves as close as possible?

Because basically what I want to do is:

- Create path to move to player.
- If can't get close to player, do:
- Teleport to hero with move_to.

Right now, what I have is that it checks the passability for each tile around the player, until a passable is found, and then creates a path. For each created path, created_paths goes up by 1. If the path fails (because it just can't reach the player) failed_paths goes up by 1. If failed_paths == created_paths, it teleports the player.

But of course it would be just awesome if this could be done in a better way. Like that the event moves closest to the player as possible, then checks if the enemy is within range, and if not teleports the enemy. Is this possible with @get_close? I read about a "goal area". Do you think I could apply this to what I want?

If this @goal_area is true, that would be so great, because then I can just put the @goal_area for all the tiles around the player. Much faster! If @get_close does go as close as possible, I'd use that too. But then my only problem would be that I don't have a way of knowing when the path has 'ended', 'cause I can only check if the event is in range with the player at the end of the path. Is there a way to maybe do this?

Thanks so much!! ^_^

(I'm sorry if I ask stupid questions, but in the script explanation I find that it isn't too clear with how to actually use everything. ><)

 

[Kain Nobel]

If it wasn't for this script, I wouldn't have SDK'd the Game_Character.move_type_custom method, but I did. With the exception of you and your crazy pathfinding script though, I don't think it'd serve much use to anybody else though I did it exclusively for this script. I'm going to go ahead and post the SDK I did for it, then I'm going to post aliased mods I did to Game_Character.

Please note this SDK part hasn't been 'approved' yet, but your script is a good way to put it to the test.

Spoiler: GAME_CHARACTER#MOVE_TYPE_CUSTOM

#==============================================================================
# ** Enable Part II Check
#==============================================================================
if SDK::Parts.include?(2) || 
   SDK::Indidual_Parts.include?('GAME_CHARACTER#MOVE_TYPE_CUSTOM')

#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * SDK Log Branch
  #--------------------------------------------------------------------------
  SDK.log_branch(:Game_Character, :move_type_custom, :move_type_custom_moving?,
  :move_type_custom_repeat?, :move_type_custom_movement,
  :move_type_custom_skippable?, :move_type_custom_wait, 
  :move_type_custom_direction, :move_type_custom_other)
  SDK.log_branch(:Game_Character, :move_type_custom, :move_type_custom_repeat?,
  :move_type_custom_repeat, :move_type_custom_release)
  #--------------------------------------------------------------------------
  # * Move Type : Custom
  #--------------------------------------------------------------------------
  def move_type_custom
    # Interrupt if not stopping
    if move_type_custom_moving?
      return
    end
    # Loop until finally arriving at move command list
    while @move_route_index < @move_route.list.size
      # Acquiring move command
      command = @move_route.list[@move_route_index]
      # If command code is 0 (last part of list)
      if command.code == 0
        move_type_custom_repeat?(command)
        return
      end
      # During move command (from move down to jump)
      if command.code <= 14
        move_type_custom_movement(command)
        if not move_type_custom_skippable?
          move_type_custom_blocked
          # If movement failure occurs when [Ignore if can't move] option is OFF
          return
        end
        @move_route_index += 1
        return
      end
      # If waiting
      if command.code == 15
        move_type_custom_wait(command)
        return
      end
      # If direction change command
      if command.code >= 16 and command.code <= 26
        move_type_custom_direction(command)
        @move_route_index += 1
        return
      end
      # If other command
      if command.code >= 27
        move_type_custom_other(command)
        @move_route_index += 1
      end
    end
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Moving?
  #-----------------------------------------------------------------------------
  def move_type_custom_moving?
    return (jumping? or moving?)
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Repeat?
  #-----------------------------------------------------------------------------
  def move_type_custom_repeat?(command)
    # If [repeat action] option is ON
    if @move_route.repeat
      move_type_custom_repeat
    end
    # If [repeat action] option is OFF
    unless @move_route.repeat
      # If move route is forcing
      if @move_route_forcing and not @move_route.repeat
        move_type_custom_release
      end
      # Clear stop count
      @stop_count = 0
    end
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Repeat
  #-----------------------------------------------------------------------------
  def move_type_custom_repeat
    # First return to the move route index
    @move_route_index = 0
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Reset
  #-----------------------------------------------------------------------------
  def move_type_custom_release
    # Release forced move route
    @move_route_forcing = false
    # Restore original move route
    @move_route = @original_move_route
    @move_route_index = @original_move_route_index
    @original_move_route = nil
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Movement
  #-----------------------------------------------------------------------------
  def move_type_custom_movement(command)
    # Branch by command code
    case command.code
    when 1  # Move down
      move_down
    when 2  # Move left
      move_left
    when 3  # Move right
      move_right
    when 4  # Move up
      move_up
    when 5  # Move lower left
      move_lower_left
    when 6  # Move lower right
      move_lower_right
    when 7  # Move upper left
      move_upper_left
    when 8  # Move upper right
      move_upper_right
    when 9  # Move at random
      move_random
    when 10  # Move toward player
      move_toward_player
    when 11  # Move away from player
      move_away_from_player
    when 12  # 1 step forward
      move_forward
    when 13  # 1 step backward
      move_backward
    when 14  # Jump
      jump(command.parameters[0], command.parameters[1])
    end
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Skippable?
  #-----------------------------------------------------------------------------
  def move_type_custom_skippable?
    return (@move_route.skippable and moving? and jumping?)
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Blocked
  #-----------------------------------------------------------------------------
  def move_type_custom_blocked
    # Insert code here :)
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Wait
  #-----------------------------------------------------------------------------
  def move_type_custom_wait(command)
    # Set wait count
    @wait_count = command.parameters[0] * 2 - 1
    @move_route_index += 1
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Direction
  #-----------------------------------------------------------------------------
  def move_type_custom_direction(command)
    # Branch by command code
    case command.code
    when 16  # Turn down
      turn_down
    when 17  # Turn left
      turn_left
    when 18  # Turn right
      turn_right
    when 19  # Turn up
      turn_up
    when 20  # Turn 90° right
      turn_right_90
    when 21  # Turn 90° left
      turn_left_90
    when 22  # Turn 180°
      turn_180
    when 23  # Turn 90° right or left
      turn_right_or_left_90
    when 24  # Turn at Random
      turn_random
    when 25  # Turn toward player
      turn_toward_player
    when 26  # Turn away from player
      turn_away_from_player
    end
  end
  #-----------------------------------------------------------------------------
  # * Move Type Custom : Other
  #-----------------------------------------------------------------------------
  def move_type_custom_other(command)
    # Branch by command code
    case command.code
    when 27  # Switch ON
      $game_switches[command.parameters[0]] = true
      $game_map.need_refresh = true
    when 28  # Switch OFF
      $game_switches[command.parameters[0]] = false
      $game_map.need_refresh = true
    when 29  # Change speed
      @move_speed = command.parameters[0]
    when 30  # Change freq
      @move_frequency = command.parameters[0]
    when 31  # Move animation ON
      @walk_anime = true
    when 32  # Move animation OFF
      @walk_anime = false
    when 33  # Stop animation ON
      @step_anime = true
    when 34  # Stop animation OFF
      @step_anime = false
    when 35  # Direction fix ON
      @direction_fix = true
    when 36  # Direction fix OFF
      @direction_fix = false
    when 37  # Through ON
      @through = true
    when 38  # Through OFF
      @through = false
    when 39  # Always on top ON
      @always_on_top = true
    when 40  # Always on top OFF
      @always_on_top = false
    when 41  # Change Graphic
      @tile_id = 0
      @character_name = command.parameters[0]
      @character_hue = command.parameters[1]
      if @original_direction != command.parameters[2]
        @direction = command.parameters[2]
        @original_direction = @direction
        @prelock_direction = 0
      end
      if @original_pattern != command.parameters[3]
        @pattern = command.parameters[3]
        @original_pattern = @pattern
      end
    when 42  # Change Opacity
      @opacity = command.parameters[0]
    when 43  # Change Blending
      @blend_type = command.parameters[0]
    when 44  # Play SE
      $game_system.se_play(command.parameters[0])
    when 45  # Script
      result = eval(command.parameters[0])
    end
  end
end

#==============================================================================
# ** Ends Enable Part II Check
#==============================================================================
end

Spoiler: Pathfinder Game_Character SDK mods

class Game_Character
  #--------------------------------------------------------------------------
  # * Alias Listing
  #--------------------------------------------------------------------------
  alias_method :a_star_pathfinder_old_move_blocked, :move_type_custom_blocked
  alias_method :a_star_pathfinder_old_move_release, :move_type_custom_release
  #--------------------------------------------------------------------------
  # * Move Type Custom : Blocked
  #--------------------------------------------------------------------------
  def move_type_custom_blocked
    # If there's a path but it couldn't be followed (probably because
    # another character blocked it)
    if @a_star_path != nil and 
       A_Star_Pathfinder::COLLISION_WAIT >= 0 and
       (A_Star_Pathfinder::COLLISION_LIMIT < 0 or
       @collision_counter <= A_Star_Pathfinder::COLLISION_LIMIT)
      # The basic properties of the path don't change, only the
      # start position (character's current location) does.
      # Also note that we use the 'original goal node' because
      # pathfinding changes the goal node to current node
      # (which might not be the goal but within its range)
      goal = @a_star_path.original_goal_node
      char = @a_star_path.character
      range = @a_star_path.range
      close = @a_star_path.get_close
      reach = @a_star_path.reach_method
      fail = @a_star_path.fail_method
      # Find another path to goal
      @a_star_path = A_Star_Pathfinder.new
      @a_star_path.setup(goal, char, range, close, reach, fail)
      @a_star_path.calculate_path
      @a_star_path.generate_path
      # Force this method to wait before attempting to generate
      # another path
      @wait_count = A_Star_Pathfinder::COLLISION_WAIT
      @collision_counter += 1
    elsif @a_star_path != nil
      # If collision wait is -1 then just stop the character
      # and call the fail method, if any
      @move_route_index = @move_route.list.size
      if @a_star_path.fail_method != nil
          @a_star_path.fail_method.call
      end
      @a_star_path = nil
      @collision_counter = 0
    end
    return
  end
  #--------------------------------------------------------------------------
  # * Move Type Custom : Release
  #--------------------------------------------------------------------------
  def move_type_custom_release
    # If there's a path but it couldn't be followed (probably because
    # another character blocked it)
    if @a_star_path != nil and 
       A_Star_Pathfinder::COLLISION_WAIT >= 0 and
       (A_Star_Pathfinder::COLLISION_LIMIT < 0 or
       @collision_counter <= A_Star_Pathfinder::COLLISION_LIMIT)
      # The basic properties of the path don't change, only the
      # start position (character's current location) does.
      # Also note that we use the 'original goal node' because
      # pathfinding changes the goal node to current node
      # (which might not be the goal but within its range)
      goal = @a_star_path.original_goal_node
      char = @a_star_path.character
      range = @a_star_path.range
      close = @a_star_path.get_close
      reach = @a_star_path.reach_method
      fail = @a_star_path.fail_method
      # Find another path to goal
      @a_star_path = A_Star_Pathfinder.new
      @a_star_path.setup(goal, char, range, close, reach, fail)
      @a_star_path.calculate_path
      @a_star_path.generate_path
      # Force this method to wait before attempting to generate
      # another path
      @wait_count = A_Star_Pathfinder::COLLISION_WAIT
      @collision_counter += 1
    elsif @a_star_path != nil
      # If collision wait is -1 then just stop the character
      # and call the fail method, if any
      @move_route_index = @move_route.list.size
      if @a_star_path.fail_method != nil
          @a_star_path.fail_method.call
      end
      @a_star_path = nil
      @collision_counter = 0
    end
    a_star_pathfinder_old_move_release
  end
end

Everything appears to be working mostly fine with this, I did it directly in the demo, but it does seem like there is at least one small problem that arose from me doing this; the character never knows when they've reached their goal and continues to walk around it. I copied your edits directly and pasted them into the respective aliased methods, it'll probably just take a small tweak to the code and it'll work fine.

EDIT: There are other problems I found with my SDK split too, I'm going to go ahead and fix those later. Perhaps your script would be better off without this SDK mod, I highly doubt anybody else would bother to make overwrites in move_type_custom unless of course it had to do with maybe Isometric scripts or something.

 

[dario8676]

Kain, how does the sdk addon you made work? I'm a little curious.

 

[Kain Nobel]

The SDK just breaks down Game_Character.move_type_custom so you can alias methods to it (its a scripter thing). I did it exclusively for Cowlol's script since it directly overwrites this method, so other than that its probably not needed unless maybe you have an Isometric movement script or something that modifies the same method. It isn't an 'official' part of the SDK yet, I still got a bug or two to track down.

For now, I wouldn't worry about the SDK version I cooked up, just stick with the origional version of the A_Star_Pathfinder script (until the individual SDK part is bug free.) If Cowlol decided to take this path later, and use the new SDK with it, he'll post it for ya, but A_Star is already SDK friendly.

@Cowlol : To avoid hijacking your topic over this, I'll keep in contact with you via PM once I fix the method split.

 

[Cowlol]

Wow, a Halloween theme?

Anyway, just wanted to say that I'm still alive and still plan on updating the script and responding to your questions. I'll get back to you in the next few days (hopefully tomorrow). Sorry for the inconvenience.

Also that's pretty cool Kain. I appreciate it. I'll have a look at your mod later and see if there's anything I could help you with.

 

[e]

Just a question; wouldn't get a better average running-time (i.e.: O(nlogn)) with a binary tree implementation of your heap instead of an array implementation? Though Ruby arrays are different from conventional array, so I don't know...