Advanced Pathfinder

khkramer · Jan 7, 2018

So I searched my PC and found a copy of a more advanced pathfinder, which can be used for more complex situations like maps with lots of obstacles, other npc's etc.

It was originally made by Blizzard from the Chaos-Project forum, I only made some small edits to make working with Essentials easier, so full credit goes to him.

--
Docs:

The basic usage of the script is as follows:

The first parameter here is the event that should move, the second parameter in this case are the x and y of the destination.

Code:

PathFinder.find(:BOY,[40,13])

It can also be used to move to another event like so:

Code:

PathFinder.find(:BOY,:GRUNT)

In the examples above BOY and GRUNT are the event names, these are case-insensitive but be sure not to have duplicate event names on your map.

--

The script:

Code:

#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
# Lagless Path Finder by Blizzard
# with small modification by khkramer
# Version: 1.23
# Type: Pathfinding System
# Date: 9.2.2013
# Date v1.01: 11.4.2013
# Date v1.1: 29.7.2013
# Date v1.2: 7.10.2013
# Date v1.21: 8.10.2013
# Date v1.22: 11.11.2013
# Date v1.23: 28.05.2017
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#
#  This work is protected by the following license:
# #----------------------------------------------------------------------------
# #
# #  Creative Commons - Attribution-NonCommercial-ShareAlike 3.0 Unported
# #  ( https://creativecommons.org/licenses/by-nc-sa/3.0/ )
# #
# #  You are free:
# #
# #  to Share - to copy, distribute and transmit the work
# #  to Remix - to adapt the work
# #
# #  Under the following conditions:
# #
# #  Attribution. You must attribute the work in the manner specified by the
# #  author or licensor (but not in any way that suggests that they endorse you
# #  or your use of the work).
# #
# #  Noncommercial. You may not use this work for commercial purposes.
# #
# #  Share alike. If you alter, transform, or build upon this work, you may
# #  distribute the resulting work only under the same or similar license to
# #  this one.
# #
# #  - For any reuse or distribution, you must make clear to others the license
# #    terms of this work. The best way to do this is with a link to this web
# #    page.
# #
# #  - Any of the above conditions can be waived if you get permission from the
# #    copyright holder.
# #
# #  - Nothing in this license impairs or restricts the author's moral rights.
# #
# #----------------------------------------------------------------------------
#
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#
# IMPORTANT NOTE:
#
#   This Path Finder is a derived version of Blizz-ABS's original Path Finder.
#   If you are using Blizz-ABS, please remove this script. Blizz-ABS has a
#   Path Finder already built-in.
#
#
# Compatibility:
#
#   99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause
#   incompatibility issues with exotic map systems.
#
#
# Features:
#
#   - calculates path from point A to point B on the map
#   - allows immediate calculation as well as path calculation requests that
#     are done over the course of a few frames in order to reduce lag
#   - supports dynamic calculation that is done every step to ensure the
#     character reaches its targets
#   - can assign other characters as targets so dynamic calculation with a
#     moving will cause the character to find the target regardless of his
#     changed position
#
# new in v1.01:
#   - fixed attempted optimizations to work properly
#
# new in v1.1:
#   - fixed a problem with how dyn_request is handled
#   - added PASSABLE parameter for all path finder functions to determine
#     how to behave when using the RANGE parameter
#
# new in v1.2:
#   - added waypoints
#   - Game_Character#has_path_target? now returns true as well when using
#     target coordinates instead of a target character
#
# new in v1.21:
#   - added option for loose movement when target cannot be reached
#   - added separate option for debug messages
#
# new in v1.22:
#   - fixed a problem with waypoints when using range
#
#
# Instructions:
#
# - Explanation:
#
#   This script will allow your characters to walk from point A to point B,
#   navigating by themselves, finding the shortest path and all that without
#   you having to manually specify their moving route. They can also navigate
#   through dynamically changing environments or track a dynamically moving
#   target.
#
# - Configuration:
#
#   MAX_NODES_PER_FRAME - maximum number of node calculation per frame when
#                         using path requests instead of immediate calculations
#   DIRECTIONS_8_WAY    - if set to true, it will smooth out corner movement
#                         and use a diagonal movement step wherever possible
#                         (this does NOT mean that the path finder will do
#                         8-directional path finding!)
#   LOOSE_MOVEMENT      - if set to true, it will cause characters to continue
#                         moving when the target cannot be reached for some
#                         reason, following its last movement path (works only
#                         with "dyn" variants)
#   DEBUG_MESSAGES      - if set to true, it will display messages when paths
#                         can't be found
#
#
# - Script calls:
#
#   This path finder offers you several script calls in order to designate path
#   finding to characters on the map. Following script calls are at your
#   disposal:
#
#     PathFinder.find(C_ID, TARGET[, RANGE[, PASSABLE]])
#     PathFinder.request(C_ID, TARGET[, RANGE[, PASSABLE]])
#     PathFinder.dyn_find(C_ID, TARGET[, RANGE[, PASSABLE]])
#     PathFinder.dyn_request(C_ID, TARGET[, RANGE[, PASSABLE]])
#
#   C_ID     - either an event ID, 0 for the player character or an actual
#              character (e.g. $game_map.events[ID])
#   TARGET   - an array with X,Y coordinates, an actual target character,
#              an array with arrays of X,Y waypoints or an array of actual
#              character waypoins
#   RANGE    - range within which the target should be located (greater than 0)
#   PASSABLE - when using a range, this is used to determine if the next tile
#              must be passable as well, false by default, used usually when
#              passability between 2 tiles isn't used
#
#   This is how the 8 different script calls behave:
#
#   - The "find" variants always calculate the path immediately.
#   - The "request" variants always request a path calculation to be done over
#     the course of several frames in order to avoid lag. Requesting paths for
#     multiple characters will cause the calculation to take longer as each
#     frame only a certain number of nodes is calculated (can be configured).
#     So if there are more characters requesting a path, naturally each one
#     will consume a part of the allowed node calculations every frame.
#   - The "dyn" variants (dynamic) will recalculate/request a calculation every
#     step in order to keep a path up to date with an ever-changing
#     environment. You won't need to use these calls if there are no moving
#     events on the map or if there are no environmental passability changes.
#   - When using a "dyn" variant, if actual coordinates (X, Y) are used, the
#     character will find its path to these fixed coordinates. If an actual
#     target character is being used, the path finder will track the character
#     instead of fixed coordinates. If the character changes its position, the
#     path calculation will attempt to find a path to the new position of the
#     target.
#   - Using "dyn_find" a lot, with many characters at the same time and/or for
#     long paths may cause performance issue and lag. Use it wisely.
#   - Using "dyn_request" is much more performance-friendly, but it will also
#     cause characters to "stop and think". This can also cause problems in a
#     constantly changing environment as the environment may change during the
#     few frames while the calculation is being done. Use it wisely.
#   - In order to queue multiple targets like waypoints, simply call any of the
#     functions as many times as you need.
#
#   In order to cancel dynamic path calculation for a character, use following
#   script call:
#
#     character.clear_path_target
#
#   Example:
#
#     $game_map.events[23].clear_path_target
#
#   In order to check if a character has a dynamic path calculation for a
#   target, use following script call:
#
#     character.has_path_target?
#
#   Example:
#
#     if $game_map.events[23].has_path_target?
#
#
# Notes:
#
#   - This path finder is an implementation fo the A* Search Algorithm.
#   - The PathFinder module is being updated during the call of
#     $game_system.update. Keep this in mind if you are using specific exotic
#     scripts.
#   - When using the option LOOSE_MOVEMENT, keep in mind that it doesn't work
#     accurately with dyn_request, because request calculations aren't done
#     immediately like with dyn_find.
#
#
# If you find any bugs, please report them here:
# https://forum.chaos-project.com
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# START Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

module BlizzCFG

  MAX_NODES_PER_FRAME = 50
  DIRECTIONS_8_WAY = false
  LOOSE_MOVEMENT = false
  DEBUG_MESSAGES = true#false

end

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# END Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

$lagless_path_finder = 1.22

#==============================================================================
# module PathFinder
#==============================================================================

module Math

  def self.hypot_squared(x, y)
    return (x * x + y * y)
  end

end

#==============================================================================
# module PathFinder
#==============================================================================

module PathFinder

  PATH_DIRS = [[0, 1, 2], [-1, 0, 4], [1, 0, 6], [0, -1, 8]]
  DIR_DOWN_LEFT = [2, 4]
  DIR_LEFT_DOWN = [4, 2]
  DIR_DOWN_RIGHT = [2, 6]
  DIR_RIGHT_DOWN = [6, 2]
  DIR_LEFT_UP = [4, 8]
  DIR_UP_LEFT = [8, 4]
  DIR_RIGHT_UP = [6, 8]
  DIR_UP_RIGHT = [8, 6]
  DIR_OFFSETS = [[0, 0], [-1, 1], [0, 1], [1, 1], [-1, 0], [0, 0], [1, 0],
                 [-1, -1], [0, -1], [1, -1]]

  @requests = {}

  def self.clear
    @requests = {}
  end

  def self.find(char, target, range = 0, pass = false)
    char, target = self.check_args(char, target, range, pass, false, true)
    self._find(char, target, true)
    return true
  end

  def self.dyn_find(char, target, range = 0, pass = false)
    char, target = self.check_args(char, target, range, pass, true, true)
    self._find(char, target, true)
    return true
  end

  def self.request(char, target, range = 0, pass = false)
    char, target = self.check_args(char, target, range, pass, false, false)
    self._request(char, target, true)
    return true
  end

  def self.dyn_request(char, target, range = 0, pass = false)
    char, target = self.check_args(char, target, range, pass, true, false)
    self._request(char, target, true)
    return true
  end

  def self.check_args(char, target, range, pass, dynamic, immediate)
    range = 0 if range == nil || range < 0
    char = _resolveEvent(char)
    target = PathTarget.new(target, range, pass, dynamic, immediate)
    if $DEBUG && BlizzCFG::DEBUG_MESSAGES && char == nil
      p "Warning! Character to move does not exist!"
    end
    return [char, target]
  end

  def self._find(char, target, new = false)
    if @requests[char] == nil && (!char.has_path_target? || !new)
      @requests[char] = PathRequest.new(char.x, char.y, target)
      result = nil
      result = self.calc_node(char) while result == nil
      if $DEBUG && BlizzCFG::DEBUG_MESSAGES && result.size == 0
        p "Warning! Path Finder could not find path for character at (#{target.x},#{target.y})!"
      end
      if !BlizzCFG::LOOSE_MOVEMENT && target.dynamic
        char.set_found_step(result)
      else
        char.set_found_path(result)
      end
    end
    char.add_path_target(target) if new
  end

  def self._request(char, target, new = false)
    if @requests[char] == nil
      @requests[char] = PathRequest.new(char.x, char.y, target)
    end
    char.add_path_target(target) if new
  end

  def self.update
    @requests = {} if @requests == nil
    characters = @requests.keys
    count = BlizzCFG::MAX_NODES_PER_FRAME
    while characters.size > 0 && count > 0
      char = characters.shift
      dynamic = @requests[char].target.dynamic
      result = self.calc_node(char)
      if result != nil
        if !BlizzCFG::LOOSE_MOVEMENT && dynamic
          char.set_found_step(result)
        else
          char.set_found_path(result)
        end
      else
        characters.push(char)
      end
      count -= 1
    end
  end

  def self.calc_node(char)
    request = @requests[char]
    if request.open.size == 0
      @requests.delete(char)
      return []
    end
    found = false
    key = request.open.keys.min {|a, b|
      a[2] > b[2] ? 1 : (a[2] < b[2] ? -1 :
          (Math.hypot_squared(a[0] - request.target.x, a[1] - request.target.y) <=>
              Math.hypot_squared(b[0] - request.target.x, b[1] - request.target.y)))}
    request.closed[key[0], key[1]] = request.open[key]
    request.open.delete(key)
    kx, ky = 0, 0
    passable = false
    passable_checked = false
    PATH_DIRS.each {|dir|
      kx, ky = key[0] + dir[0], key[1] + dir[1]
      passable = false
      passable_checked = false
      if (kx - request.target.x).abs + (ky - request.target.y).abs <= request.target.range
        if request.target.pass
          passable = char.passable?(key[0], key[1], dir[2])
          passable_checked = true
        else
          passable = true
        end
        if passable
          request.closed[kx, ky] = dir[2]
          found = true
          break
        end
      end
      if request.closed[kx, ky] == 0
        passable = char.passable?(key[0], key[1], dir[2]) if !passable_checked
        if passable
          request.open[[kx, ky, key[2] + 1]] = dir[2]
        end
      end}
    return nil if !found
    result = request.backtrack(kx, ky)
    @requests.delete(char)
    return result
  end

end

#==============================================================================
# PathTarget
#==============================================================================

class PathTarget

  attr_reader :range
  attr_reader :pass
  attr_reader :dynamic
  attr_reader :immediate

  def initialize(target, range, pass, dynamic, immediate)
    if !target.is_a?(Array)
      @char = _resolveEvent(target)
    else
      @x, @y = target
    end
    @range = range
    @pass = pass
    @dynamic = dynamic
    @immediate = immediate
  end

  def x
    return (@char != nil ? @char.x : @x)
  end

  def y
    return (@char != nil ? @char.y : @y)
  end

end

#==============================================================================
# PathRequest
#==============================================================================

class PathRequest

  attr_reader :open
  attr_reader :closed
  attr_reader :sx
  attr_reader :sy
  attr_reader :target

  def initialize(sx, sy, target)
    @sx, @sy, @target = sx, sy, target
    @open = {[@sx, @sy, 0] => -1}
    @closed = Table.new($game_map.width, $game_map.height)
  end

  def backtrack(tx, ty)
    cx, cy, x, y, result = tx, ty, 0, 0, []
    loop do
      cx, cy = cx - x, cy - y
      break if cx == @sx && cy == @sy
      result.unshift(@closed[cx, cy])
      x, y = PathFinder::DIR_OFFSETS[@closed[cx, cy]]
    end
    return self.modify_8_way(result)
  end

  def modify_8_way(result)
    if BlizzCFG::DIRECTIONS_8_WAY
      result.each_index {|i|
        if result[i] != nil && result[i + 1] != nil
          case [result[i], result[i + 1]]
            when PathFinder::DIR_DOWN_LEFT, PathFinder::DIR_LEFT_DOWN
              result[i], result[i + 1] = 1, nil
            when PathFinder::DIR_DOWN_RIGHT, PathFinder::DIR_RIGHT_DOWN
              result[i], result[i + 1] = 3, nil
            when PathFinder::DIR_LEFT_UP, PathFinder::DIR_UP_LEFT
              result[i], result[i + 1] = 7, nil
            when PathFinder::DIR_RIGHT_UP, PathFinder::DIR_UP_RIGHT
              result[i], result[i + 1] = 9, nil
          end
        end}
      result.compact!
    end
    return result
  end

end

#==============================================================================
# Game_System
#==============================================================================

class Game_System

  alias update_lagless_path_finder_later update
  def update
    PathFinder.update
    update_lagless_path_finder_later
  end

end

#==============================================================================
# Game_Map
#==============================================================================

class Game_Map

  alias setup_lagless_path_finder_later setup
  def setup(map_id)
    PathFinder.clear
    setup_lagless_path_finder_later(map_id)
  end

end

#==============================================================================
# Game_Character
#==============================================================================

class Game_Character

  def add_path_target(target)
    @path_targets = [] if @path_targets == nil
    @path_targets.push(target)
  end

  def clear_path_target
    @path_targets = nil
  end

  def next_path_target
    if @path_targets.size <= 1
      self.clear_path_target
    else
      @path_targets.shift
    end
  end

  def has_path_target?
    return (@path_targets != nil && @path_targets.size > 0)
  end

  def set_found_path(path)
    return if path.size == 0
    route = RPG::MoveRoute.new
    route.repeat = false
    # each move command code equals direction / 2
    path.reverse.each {|dir| route.list.unshift(RPG::MoveCommand.new(dir / 2))}
    #$debugje = true
    self.force_move_route(route)#, true)
  end

  def set_found_step(path)
    return if path.size == 0
    route = RPG::MoveRoute.new
    route.repeat = false
    # each move command code equals direction / 2
    route.list.unshift(RPG::MoveCommand.new(path[0] / 2))
    self.force_move_route(route)
  end

  alias update_lagless_path_finder_later update
  def update
    update_lagless_path_finder_later
    return if self.moving? || !self.has_path_target? || self.jumping?
    if (@x - @path_targets[0].x).abs + (@y - @path_targets[0].y).abs <=
        @path_targets[0].range
      self.next_path_target
      check = true
    else
      check = @path_targets[0].dynamic
    end
    if check && self.has_path_target?
      if @path_targets[0].immediate
        PathFinder._find(self, @path_targets[0])
      else
        PathFinder._request(self, @path_targets[0])
      end
    end
  end

end

def get_character(parameter)
  # Branch by parameter
  case parameter
    when -1  # player
      return $game_player
    when 0  # this event
      events = $game_map.events
      return events == nil ? nil : events[@event_id]
    else  # specific event
      events = $game_map.events
      return events == nil ? nil : events[parameter]
  end
end

def getEventByName(name)
  if name.is_a?(Symbol)
    name = name.to_s
  end
  
  $game_map.events.values.each do |event|
    return event if event.name.downcase == name.downcase
  end
  
  return nil
end

def getEventByXY(x, y)
  $game_map.events.values.each do |event|
    return event if event.x == x && event.y == y
  end

  return nil
end

def _resolveEvent(event)
  if event.is_a?(Game_Event) || event.is_a?(Game_Player)
    return event
  end
  
  if event.is_a?(Numeric)
    return get_character(event)
  end
  
  return getEventByName(event) # Symbol or string
end

If you find any bugs, please let me know.

Ededdinson · Feb 11, 2018

Hello. I was wondering how you would go about making the event find the player instead of finding a spot or another event? Any help is appreciated. Thank you!

komaoto · Feb 12, 2018

It's right here, inside the Script Calls section:

Code:

#   C_ID     - either an event ID, 0 for the player character or an actual
#              character (e.g. $game_map.events[ID])

Ededdinson · Feb 12, 2018

Ah my mistake. Thanks a ton!

m6woodard · Nov 2, 2018

I am encountering an error that I cannot seem to fix well when exiting a map while being pursued by an event. This is not a bug, I think, just the script was not intended to do this.

[Pok?mon Essentials version 17.2]
Exception: TypeError
Message: no implicit conversion from nil to integer
Advanced_Pathfinding:444:in `[]'
Advanced_Pathfinding:444:in `backtrack'
Advanced_Pathfinding:439:in `loop'
Advanced_Pathfinding:445:in `backtrack'
Advanced_Pathfinding:379:in `calc_node'
Advanced_Pathfinding:325:in `update'
Advanced_Pathfinding:479:in `update'
Scene_Map:165:in `follow_update'
Scene_Map:161:in `loop'
Scene_Map:170:in `follow_update'

I was able to come up with the work around below however it slows the game down to an unplayable fps when the player leaves the map when pursued by event A for around 10 tiles into the new map, then speeds back up again. If the player tries to reenter the previous map with event A that was following it, the slow down reoccurs in those 10 tiles until the player has reached the previous map. Meanwhile event A that was pursuing the player stops at the edge of the map and doesn't move until the player has reentered their map and then the event begins to pursue the player again.

If the player travels far enough away the event A will reset and the slow down will not happen when entering event A's map.

MAX_NODES_PER_FRAME = 50
DIRECTIONS_8_WAY = false
LOOSE_MOVEMENT = true
DEBUG_MESSAGES = false

I am using two events, an npc and a controlling event next to it. The controlling event is:

Page 1:
Control Variable: 37 CurrentGameMap = Map ID
if CurrentGameMap == 78
PathFinder.dyn_find($game_map.events[16],$game_player)
end

Page 2:
If selfswitch A is on then do nothing.

The NPC event is:

Page1:
Text: Found you!
pbSetSelfSwitch(17,"A",true)
$game_map.events[16].clear_path_target
Control Self Switch: A = ON

Page 2:
Text:Told you I could find you.

Setting LOOSE_MOVEMENT = true made the error dissappear when using dynamic find and exiting the map. Still occurs when using dynamic request.

The if CurrentGameMap == 78 keeps the event from trying to find the player until the player has reached the map it's on.

The I found you part works just fine and stops looking for the player once it has found the player.

I can't call .clear_path_target every time the player exits the map because the borders are just too big and I have more than one map with this issue. So this won't work.

I either need a way to use .clear_path_target on an event that is located on a different map then the player like $game_map.events[x] does for the current map.

Or I need to figure out how to cancel the path when the event cannot find the player from within the actual script, which is my weakest area. I have tried a few things to no effect. Any suggestions would be most appreciative.

Other than this, I am loving this script.

Xerado · Dec 14, 2018

Great script! The only thing I can't seem to figure out is how would I go about changing an event's self switches after the pathfinding has completed? (The event running the pathfinder is the event moving.)

Callmefreak · Dec 16, 2018

I was testing this out, and it was pretty easy to use until I got this. There's this warning whenever the script can't find the tile.

Spoiler:

It wouldn't matter so much except whenever I try to close the window, it comes right back. I have to restart my laptop if I want to continue to use the game maker.

I don't know if there's a way to fix this? I have no idea if there's a way to have the warning actually go away and close the game out, but I figured you should know that this is happening.

I was specifically trying to make it so the event would walk to that tile if a switch was activated. What's weird is, I checked the map and it does have 40,13 without anything in the way of it.

khkramer · Apr 25, 2019

Callmefreak said:
I was testing this out, and it was pretty easy to use until I got this. There's this warning whenever the script can't find the tile.

Spoiler:

It wouldn't matter so much except whenever I try to close the window, it comes right back. I have to restart my laptop if I want to continue to use the game maker.

I don't know if there's a way to fix this? I have no idea if there's a way to have the warning actually go away and close the game out, but I figured you should know that this is happening.

I was specifically trying to make it so the event would walk to that tile if a switch was activated. What's weird is, I checked the map and it does have 40,13 without anything in the way of it.

Very late response on my part :P

But you can disable these debug messages if they're a problem around line 214: DEBUG_MESSAGES is set to true, if you set it to false then those popups won't appear.

Skyflyer · Jun 21, 2019

Sorry for the question but I don't really understand what does this script does, if anyone can explain it I would appreciate it. Thanks