Envision, Create, Share

Welcome to HBGames, a leading amateur game development forum and Discord server. All are welcome, and amongst our ranks you will find experts in their field from all aspects of video game design and development.

Advanced Pathfinding

Advanced Pathfinding Version: 1.1
By: ForeverZer0

Introduction

This is an advanced an highly intelligent pathfinding system. It allows for the user to either through script or script call quickly and easily have events or the game player automatically walk a path to a given set of coordinates. The system is smart enough to quickly find paths through relatively complex areas, and adjust on the fly for any obstacle that moves to block its path. I used the A* algorithm, basic search algorithm used often for robotics. More on this algorithm can be read about here: A* Search Algorithm

Features
  • Fast and intelligent pathfinding
  • Easy to use script calls
  • Optional "range" parameter can have character find alternate locations if the preferred one is blocked and they are within the given range.
  • Optional callbacks can be given to have something execute if when the character reaches its goal, or when it fails to do so.

Screenshots

Can quickly and easily navigate a maps like these, lag-free:
Maze1.png
Maze2.png

Demo

Demo Link

Script

[rgss]#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# Advanced Pathfinding
# Author: ForeverZer0
# Version: 1.1
# Date: 5.30.2011
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# Introduction:
#   This is an advanced an highly intelligent pathfinding system. It allows for
#   the user to either through script or script call quickly and easily have
#   events or the game player automatically walk a path to a given set of
#   coordinates. The system is smart enough to quickly find paths through
#   relatively complex areas, and adjust on the fly for any obstacle that moves
#   to block its path. I used the A* algorithm, basic search algorithm used
#   often for robotics. More on this algorithm can be read about here:
#
#               http://en.wikipedia.org/wiki/A*_search_algorithm
#
# Features:
#   - Fast and intelligent pathfinding
#   - Easy to use script calls
#   - Optional "range" parameter can have character find alternate locations
#     if the preferred one is blocked and they are within the given range.
#   - Optional callbacks can be given to have something execute if when the
#     character reaches its goal, or when it fails to do so.
#
# Instructions:
#   - Place script below default scripts, and above "Main".
#   - Use the following script call:
#
#     pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#    
#     The X and Y are the only required arguments. The others can be omitted.
#    
#     X - The x-coordinate to pathfind to.
#     Y - The y-coordinate to pathfind to.
#
#     CHARACTER - Either an instance of the character ($game_player,
#                 $game_map.events[ID], etc) or the ID of a character. The ID
#                 will be the event ID. Use -1 for the game player.
#
#     SUCCESS_PROC - A Proc object that will be executed when the player
#                    reaches the defined coordinates.
#     FAILURE_PROC - A Proc object that will be executed when the player
#                    cannot reach the defined coordinates.
#
#   - As default, the pathfinder will make 35 attempts to recalculate a route
#     that gets blocked. This value can be changed in game with the script
#     call:
#           $game_map.collision_retry = NUMBER
#
#     You can change the default value if desired by looking down to the first
#     class below in the main script.
#   - For longer pathfind routes, it is sometimes necessary to reset the
#     search limiter. This may cause increased lag when an object blocks the
#     character from being able to move, but will increase the range that the
#     system can work with. Use the following script call:
#
#         $game_map.search_limiter = NUMBER  (Default 1000)
#
#   - If you are experiencing any compatibility problems, go to the Game_Map
#     class below and set @recalculate_paths to false. This will take away some
#     of the efficiency of recalculating collisions, but will improve may fix
#     your problem.
#
# Compatibility:
#   Highly compatible. May experience issues with Custom Movement scripts,
#   but even then, it is unlikely.
#
# Credits/Thanks:
#   - ForeverZer0, for the script
#   - Special thanks to Jragyn for help making the big maze for the demo and
#     help testing.
#   - Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the
#     original search algorithm that was implemented
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
 
#===============================================================================
# ** Game_Map
#===============================================================================
 
class Game_Map
 
  attr_accessor :collision_retry
  attr_accessor :recalculate_paths
  attr_accessor :search_limiter
 
  alias zer0_pathfinding_init initialize
  def initialize
    # Initialize instance variables used for pathfinding.
    @collision_retry = 35
    @recalculate_paths = true
    @search_limiter = 1000
    # Original method
    zer0_pathfinding_init
  end
end
 
#===============================================================================
# ** Interpreter
#===============================================================================
 
class Interpreter
 
  def pathfind(x, y, *args)
    args[0] = @event_id if args[0] == nil
    args[1] = 0 if args[1] == nil
    # Add a simpler call for using as a script call
    Pathfind.new(Node.new(x, y), *args)
  end
end
 
#==============================================================================
# ** Pathfind
#==============================================================================
 
class Pathfind
 
  attr_reader   :route                  
  attr_accessor :range  
  attr_reader   :goal
  attr_reader   :found
  attr_reader   :character                                
  attr_accessor :success_proc          
  attr_accessor :failure_proc        
  attr_accessor :target    
  attr_accessor :collisions      
 
  def initialize(node, char = -1, range = 0, *callbacks)
    # Set the character. Can either us an ID or an instance of a Game_Character.
    # A value of -1, which is default, is the Game_Player.
    if char.is_a?(Integer)
      @character = (char == -1) ? $game_player : $game_map.events[char]
    elsif char.is_a?(Game_Character)
      @character = char
    end
    # Set forcing flag. Will be disabled for recalculating on the fly.
    @forcing = true
    # Call a public method, since this method may need to be used again,
    # and "initialize" is private.
    setup(node, range, *callbacks)
  end
 
  def setup(node, range = 0, *callbacks)
    # Initialize the node we are trying to get to.
    @target = Node.new(node.x, node.y)
    @goal = @target.clone
    # Set beginning nodes and required variables.
    @start_node = Node.new(@character.x, @character.y)
    @nearest = Node.new(0, 0, 0, -1)
    @range, @found, @collisions = range, false, 0
    # Set callbacks for success and failure if included, else nil.
    @success_proc = callbacks[0]
    @failure_proc= callbacks[1]
    # Initialize sets to track open and closed nodes
    @open_set, @close_set = [@start_node], {}  
    # Find the optimal path
    calculate_path
  end
 
  def calculate_path
    # Only do calculation if goal is actually passable, unless we only
    # need to get close or within range
    if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
      # Initialize counter
      counter, wait = 0, 0
      until @open_set.empty?
 
        counter += 1
        # Give up if pathfinding is taking more than 500 iterations
        if counter >= $game_map.search_limiter
          @found = false
          break
        end
        # Get the node with lowest cost and add it to the closed list
        @current_node = get_current
        @close_set[[@current_node.x, @current_node.y]] = @current_node
        if @current_node == @goal ||
           (@range > 0 && @goal.in_range?(@current_node, @range))
          # We reached goal, exit the loop!
          @target = @goal
          @goal, @found = @current_node, true
          break
        else # if not goal
          # Keep track of the node with the lowest cost so far
          if @current_node.heuristic < @nearest.heuristic ||
            @nearest.heuristic < 1
            @nearest = @current_node
          end
          # Get adjacent nodes and check if they can be added to the open list
          neighbor_nodes(@current_node).each {|neighbor|
            # Skip Node if it already exists in one of the lists.
            next if can_skip?(neighbor)
            # Add node to open list following the binary heap conventions
            @open_set.push(neighbor)
            arrange(@open_set.size - 1)
          }
        end
      end
    end
    # If no path was found, see if we can get close to goal
    unless @found
      if @range > 0 && @nearest.heuristic > 0  
        # Create an alternate path.
        setup(@nearest, @range, @success_proc, @failure_proc)
      elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
        (@collisions > $game_map.collision_retry))
        # If out of retries, call the Proc for failure if defined
        @failure_proc.call
      end
    end
    # Create the move route using the generated path
    create_move_route
  end
 
  def create_move_route
    # There's no path to generate if no path was found
    return if !@found
    # 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
    while node.parent
      # Get direction from parent to node as RPG::MoveCommand
      code = case direction(node.parent.x, node.parent.y, node.x, node.y)
      when 2 then 4 # Up
      when 4 then 3 # Left
      when 6 then 2 # Right
      when 8 then 1 # Down
      else; 0
      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 (@forcing && !@route.list.empty?)
      @collisions = 0
      @character.paths.push(self)
      @character.force_move_route(@route) if @character.paths.size == 1
    end
    # Reset forcing flag if needed
    @forcing = true
    # Return the constructed RPG::MoveRoute
    return @route
  end
 
  def arrange(index)
    # Rearrange nodes in the open_set
    while index > 0
      # Break loop unless current item's cost is less than parent's
      break if @open_set[index].score > @open_set[index / 2].score
      # Bring lowest value to the top.
      temp = @open_set[index / 2]
      @open_set[index / 2] = @open_set[index]
      @open_set[index] = temp
      index /= 2
    end
  end
 
  def get_current
    return if @open_set.empty?
    return @open_set[0] if @open_set.size == 1
    # Set current node to local variable and replace it with the last
    current = @open_set[0]
    @open_set[0] = @open_set.pop
    # Loop and rearrange array according to the A* algorithm until done.
    y = 0  
    loop {
      x = y
      # If two children exist
      if 2 * x + 1 < @open_set.size
        if @open_set[2 * x].score <= @open_set 
 
Now, this is by far not the first A* pathfinding script for XP... so the difference is that this one is better in performance? Lag-free on the above-shown map is indeed not too bad for the number of checks required, so I have to wonder: Lag-free on what system? ^^

On a completely unrelated note, entirely focussed on my fight for proper scripting style: The reason why there has to be a username tag in alias zer0_pathfinding_init initialize, while class Pathfind is apparently not endangered to be taken by any other scripter at all is completely beyond me.
 

Atoa

Member

@BlueScope
The alias is on the class Game_Character initialize, not on the class Pathfinding.

Also i think that "telling the proper scripting style" is like telling people what clothes they must use. Unless it's an gross error, each one have it own style. And if it don't make an noticeable performance loss, or make things a lot confusing, who cares how the script was coded?

@ForeverZer0
The script is quite good, and it have an great compatibility. Something hard to find in an script like this.
 
I'd be willing to use this, if it had 8 directional support.

For myself, that seems to be the major flaw and failing in all pathfinding scripts I've found for rpgmaker. they all only use 4 directions.
 
I don't have rmxp with me right now to try this, but I do have a question about lag. Would this generate lag on a complex 100 x 100 map if multiple events, say 20, were using it? I am very sleepy right now, so I apologize if that has a rude sounding tone to it, I'm honestly just curious. Thanks :)
 
I honestly never tried it with 20 events at the same time. For the most part, lag will only occur at the actual point of the script call when the path is calculated. From that point, the event is just walking the path. If they hit a collision that blocks their defined route, then it recalculates again from the current point.
 
Just set the X and Y to the player's x and y.

The only problem I foresee is that it will want to complete that route, and really won't be chasing the player. If the player moves, the event will still move to the original coordinates. You could fix this by clearing the paths and resetting them each time the character moves, which would work, though not very efficient.
 

SPN

Member

@ShadowMainZERO
Not sure if this is exactly what you were looking for, but I was figuring out chase-related ideas today, and posted a quick how-to in the basics of it. Combining it with this script could give you some interesting options. Feel free to check it out!

Check it!
 
this is very nice script , could be used for many things :biggrin:
can i ask a question?
is there a way for it to activate switch as soon as finished path?
x = 1
y = 3
id = 5
range = 0
s = <<<<------ dunno what to put here to activate certain switch. ex: switch 4
f =
pathfind(x, y, id, range, s, f)

and 2nd question, is there a way to forcefully deactivate path of a certain event char ? thx :smile:
 
[rgss]s = Proc.new { $game_switches[ID] = true/false }
[/rgss]

What do you mean by deactivate? You mean cancel the route and stopping once it has already started? If so, then "no" there is no built-in way, which is an oversight of mine. I have not tested this, but I think it should work:

[rgss]class Interpreter
 
  def cancel_pathfind(id = @event_id)
    character = id == -1 ? $game_player : $game_map.events[id]
    character.paths = []
    character.move_route_forcing = false
    character.move_route = nil
  end
end
[/rgss]

Just within a script call use "cancel_pathfind(CHARACTER_ID)". If no argument is supplied, it will work on the event that it is called in. Use -1 as an ID for the player. Let me know if it works.
 
Code:
class Interpreter

  

  def cancel_pathfind(id = @event_id)

    character = id == -1 ? $game_player : $game_map.events[id]

    character.paths = [] 

    character.move_route_forcing = false

    character.move_route = nil

  end

end
it work nicely , now its even more awesome , thx :biggrin:

Code:
s = Proc.new { $game_switches[ID] = true/false }
this work too , but i had to press f9 for the switch to work or it'll just stand there , does it need some kind of refresh?

*edit* : im sorry i should be more specific , i use switch to activate another pathfind script so after he arrive to lets say point A i want him to move to point B , but for that to happen i have to press F9 for it to work.

*edit no.2* : sorry it actually work , :tongue: i put another script that clash with yours that need to press f9 for it to work, is there any script call that can refresh? or has some function as pressing f9 ?
 
Code:
key = Win32API.new('user32.dll', 'keybd_event', ['i', 'i', 'l', 'l'], 'v')

key.call(0x78, 0, 0, 0)

key.call(0x78, 0, 2, 0)

This will virtually press the F9 key.
 
Small update.

Fixed a little bug that would occasionally pop up when an event finished a move route. Just forgot to add an additional condition to a branch.
 

Thank you for viewing

HBGames is a leading amateur video game development forum and Discord server open to all ability levels. Feel free to have a nosey around!

Discord

Join our growing and active Discord server to discuss all aspects of game making in a relaxed environment. Join Us

Content

  • Our Games
  • Games in Development
  • Emoji by Twemoji.
    Top