Path Finding

Path Finding
Version: 2.0
Author: modern algebra
Date: April 16, 2008

Version History

• Version 2.0 - Released April 16, 2008. It now creates significantly less lag, and there is also an option to set a maximum amount of iterations to reduce lag at the cost of occasional failure to find a path. You are also able to force a path through call script as well as through a move event, for use in other scripts
• Version 1.0 - Released April 11, 2008

Planned Future Versions

• Version 3.0 - Will look into developing an algorithm that works faster and more efficiently. Allow for recalculation en route if original path is interfered with. Will not force a route in move path and allow for recalculating path instead.

Description

This script finds the shortest path from an event's current position to a target position specified by the user. It then sets that path into action. Be careful when using it though. Depending on the layout of the map, it can take a fair amount of time to calculate. So, don't use it for any huge, funky mazes or anything.

Features

• No more looking at the map and setting a move route command by command. It only takes one command now to go from any square on the map to any other
• Very easy to set a new path
• Always finds the shortest path
• Very little lag for most paths
• Can set a maximum amount of iterations to reduce lag further at the cost of occasional failure
• Will work if you allow diagonal movement as well

Screenshots

N/A for this type of script, really.

Instructions

To use this, merely use the script command inside a Set Move Route event and use this code:

    find_path (target x, target y, diagonal, max_iterations)

Where target x and target y are the coordinates of the target. diagonal is an optional boolean value (true or false) denoting whether or not you want the event to be able to move diagonally or not. The value for diagonal defaults to false if it is not set by the user. max_iterations is also optional, and you can set this if you want the algorithm to quit if it is taking too long. The number you set here refers to how many nodes you let it search through before cancelling the process. If this is set to 0 or less, it will take as many iterations as necessary to find the shortest path

A sample Event:

@>Set Move Route: This Event
 :                            : $> Script: find_path (12, 33)

It's that simple. You can also put other move commands around it, use it on any characters that you could move via a normal move route, and set all the same conditions on the move route, such as Wait, Skippable, and Repeat.  Like so:

@>Set Move Route: Player (Wait)
 :                            : $> Move Down
 :                            : $> Script: find_path (12, 33, true)
 :                            : $> Move Left

Repeat works by repeating the path, not recalculating it. This means that if the path that was calculated was Down, Down, Left, the character will repeat that pattern, not necessarily going back to the square every time.


You can also set a default value for diagonal and max_iterations by call script with the codes:
    

Code: [Select]

    $game_system.pathfinding_diagonal = true/false # Allow diagonal movement
     $game_system.pathfinding_iterations = integer # When <= 0, no limit

  Then, when you do not specifically set diagonal or limit, it will default to the values you set in there

   For scripters, you can force-move a character down a path via:

Code: [Select]

    character.force_path (x, y, diagonal, max_iterations)

    character is any Game_Character object, such as $game_player or an event.

Script

Code: [Select]

#==============================================================================
#  Path Finding
#  Version: 2.0
#  Author: modern algebra (rmrk.net)
#  Date: April 10, 2008
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#  Thanks:
#    Patrick Lester! For his tutorial on A* Pathfinding algorithm (found at:
#        http://www.gamedev.net/reference/articles/article2003.asp) as well as
#        another amazingly helpful tutorial on using binary heaps (found at:
#        http://www.policyalmanac.org/games/binaryHeaps.htm). Without his excellent
#        tutorials, this script would not exist. So major thanks to him.
#    Zeriab, for tricking me into believing that this was an actual exercise.
#        Also, his table printout actually makes Tables useable :P
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#  Instructions:
#    To use, merely use this code in a script call INSIDE a Move Event:
#
#      find_path (target_x, target_y, diagonal, max_iterations)
#
#    where target_x and target_y are the target coordinates and diagonal is an
#    optional boolean value (true or false) stating whether or not to allow
#    diagonal movement. max_iterations is also optional, and you can set this if
#    you want the algorithm to quit if it is taking too long. The number you set
#    here refers to how many nodes you let it search through before cancelling
#    the process. If this is set to 0, it will take as many iterations as
#    necessary to find the shortest path.
#
#    You can also set a default value for diagonal and max_iterations
#    by call script with the codes:
#      
#      $game_system.pathfinding_diagonal = true/false # Allow diagonal movement
#      $game_system.pathfinding_iterations = integer # When <= 0, no limit
#
#    For scripters, you can force-move a character down a path via:
#
#      character.force_path (x, y, diagonal, max_iterations)
#
#    character is any Game_Character object, such as $game_player or an event.
#
#    Then, when you do not specifically set diagonal or limit, it will default
#    to the values you set in there
#==============================================================================
#==============================================================================
# ** Game_System
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#  Summary of Changes:
#    new instance variables - pathfinding_diagonal, pathfinding_iterations
#    aliased method - initialize
#==============================================================================

class Game_System
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Public Instance Variables
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  attr_accessor :pathfinding_diagonal
  attr_accessor :pathfinding_iterations
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Object Initialization
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  alias modalg_pathfinding_options_init_j5yt initialize
  def initialize
    modalg_pathfinding_options_init_j5yt
    @pathfinding_diagonal = false
    @pathfinding_iterations = 0
  end
end

#==============================================================================
# ** Game_Character
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#  Summary of Changes:
#    new methods - find_path
#==============================================================================

class Game_Character
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Find Path
  #    trgt_x, trgt_y : the target coordinates
  #    diagonal       : Is diagonal movement allowed?
  #    max_iterations : maximum number of iterations
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  def find_path (trgt_x, trgt_y, diagonal = $game_system.pathfinding_diagonal,
                    max_iterations = $game_system.pathfinding_iterations)
    path = $game_map.find_path (self.x, self.y, trgt_x, trgt_y, diagonal,
                     max_iterations, self)
    # Add the path to the move route being executed.
    @move_route.list.delete_at (@move_route_index)
    path.each { |i| @move_route.list.insert (@move_route_index, i) }
    @move_route_index -= 1
  end
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Force Path
  #    trgt_x, trgt_y : target coordinates
  #    diagonal       : Is diagonal movement allowed?
  #    max_iterations : maximum number of iterations
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  def force_path (trgt_x, trgt_y, diagonal = $game_system.pathfinding_diagonal,
                    max_iterations = $game_system.pathfinding_iterations)
    path = $game_map.find_path (self.x, self.y, trgt_x, trgt_y, diagonal,
                          max_iterations, self)
    # The path retrieved is actually backwards, so it must be reversed
    path.reverse!
    # Add an end ccommand
    path.push (RPG::MoveCommand.new (0))
    move_route = RPG::MoveRoute.new
    move_route.list = path
    move_route.repeat = false
    force_move_route (move_route)
  end
end

#==============================================================================
# ** Game_Map
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#  Summary of Changes:
#    new method - removefrom_binaryheap, find_path
#==============================================================================
class Game_Map
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Remove from Heap
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  def removefrom_binaryheap
    @open_nodes[1] = @open_nodes[@listsize]
    @listsize -= 1
    v = 1
    loop do
      u = v
      w = 2*u
      # Check if it's cost is greater than that of it's children
      if w + 1 <= @listsize # If both children exist
        v = w if @total_cost[@open_nodes[u]] >= @total_cost[@open_nodes[w]]
        v = w + 1 if @total_cost[@open_nodes[v]] >= @total_cost[@open_nodes[w + 1]]
      elsif w <= @listsize # If only one child exists
        v = w if @total_cost[@open_nodes[u]] >= @total_cost[@open_nodes[w]]
      end
      # Break if parent has less cost than it's children
      if u == v
        break
      else
        temp = @open_nodes[u]
        @open_nodes[u] = @open_nodes[v]
        @open_nodes[v] = temp
      end
    end
  end
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  # * Find Path
  #    src_x, src_y   : the source coordinates
  #    trgt_x, trgt_y : the target coordinates
  #    diagonal       : Is diagonal movement allowed?
  #    max_iterations : maximum number of iterations
  #    char           : character to follow the path
  #--------------------------------------------------------------------------
  #  Uses the A* method of pathfinding to find a path
  #~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  def find_path (src_x, src_y, trgt_x, trgt_y, diagonal, max_iterations, char)
    # No possible path if the target itself is impassable
    path = []
    # Finished if Target Location is closed
    return path if !char.passable? (trgt_x, trgt_y)
    # Initialize
    max_elements = width*height + 2
    openx = Table.new (max_elements)
    openy = Table.new (max_elements)
    @open_nodes = Table.new (max_elements)
    @total_cost = Table.new (max_elements)
    heuristic = Table.new (max_elements)
    step_cost = Table.new (width, height)
    parent_x = Table.new (width, height)
    parent_y = Table.new (width, height)
    actual_list = Table.new (width, height)
    # Add the source node to the open list
    new_openid = 1
    @open_nodes[1] = 1
    openx[1] = src_x
    openy[1] = src_y
    dist = [(trgt_x - src_x).abs, (trgt_y - src_y).abs]
    heuristic[1] = diagonal ? (dist.max*14) + (dist.min*10) : (dist[0] + dist[1])*10
    @total_cost[1] = heuristic[1]
    actual_list[src_x, src_y] = 1
    @listsize = 1
    count = 0
    loop do
      break if actual_list[trgt_x, trgt_y] != 0
      count += 1
      # Update Graphics every 500 iterations
      Graphics.update if count % 500 == 0
      return path if count == max_iterations
      return path if @listsize == 0
      node = @open_nodes[1]
      # Set the x and y value as parent to all possible children
      parent_xval, parent_yval = openx[node], openy[node]
      actual_list[parent_xval, parent_yval] = 2
      removefrom_binaryheap
      # Check all adjacent squares
      for i in 0...8
        break if i > 3 && !diagonal
        # Get the node
        x, y = case i
        when 0 then [parent_xval, parent_yval - 1] # UP
        when 1 then [parent_xval, parent_yval + 1] # DOWN
        when 2 then [parent_xval - 1, parent_yval] # LEFT
        when 3 then [parent_xval + 1, parent_yval] # RIGHT
        when 4 then [parent_xval - 1, parent_yval - 1] # UP LEFT
        when 5 then [parent_xval + 1, parent_yval - 1] # UP RIGHT
        when 6 then [parent_xval - 1, parent_yval + 1] # DOWN LEFT
        when 7 then [parent_xval + 1, parent_yval + 1] # DOWN RIGHT
        end
        # Next if this node is already in the closed list
        next if actual_list[x,y] == 2
        # Next if this tile in impassable
        next unless char.passable? (x, y) # Is the tile passable?
        # Take into account diagonal passability concerns
        if i > 3
          next unless case i
          when 4 then char.passable? (x + 1, y) || char.passable? (x, y + 1)
          when 5 then char.passable? (x - 1, y) || char.passable? (x, y + 1)
          when 6 then char.passable? (x + 1, y) || char.passable? (x, y - 1)
          when 7 then char.passable? (x - 1, y) || char.passable? (x, y - 1)
          end
        end
        # Check if this node already open
        plus_step_cost = ((x - parent_xval).abs + (y - parent_yval).abs) > 1 ? 14 : 10
        temp_step_cost = step_cost[parent_xval, parent_yval] + plus_step_cost
        if actual_list[x,y] == 1
          # If this is a better path to that node
          if temp_step_cost < step_cost[x, y]
            # Change Parent, step, and total cost
            parent_x[x, y] = parent_xval
            parent_y[x, y] = parent_yval
            step_cost[x, y] = temp_step_cost
            # Find index of this position
            index = 1
            while index < @listsize
              index += 1
              break if openx[@open_nodes[index]] == x &&
                                                openy[@open_nodes[index]] == y
            end
            @total_cost[@open_nodes[index]] = temp_step_cost + heuristic[@open_nodes[index]]
          else
            next
          end
        else # If not on open nodes
          # Add to open nodes
          new_openid += 1 # New Id for new item
          @listsize += 1 # Increase List Size
          @open_nodes[@listsize] = new_openid
          step_cost[x, y] = temp_step_cost
          # Calculate Heuristic
          d = [(trgt_x - x).abs, (trgt_y - y).abs]
          heuristic[new_openid] = diagonal ? (d.max*14) + (d.min*10) : (d[0] + d[1])*10
          @total_cost[new_openid] = temp_step_cost + heuristic[new_openid]
          parent_x[x, y] = parent_xval
          parent_y[x, y] = parent_yval
          openx[new_openid] = x
          openy[new_openid] = y
          index = @listsize
          actual_list[x, y] = 1
        end
        # Sort Binary Heap
        while index != 1
          temp_node = @open_nodes[index]
          if @total_cost[temp_node] <= @total_cost[@open_nodes[index / 2]]
            @open_nodes[index] = @open_nodes[index / 2]
            index /= 2
            @open_nodes[index] = temp_node
          else
            break
          end
        end
      end
    end
    # Get actual target node
    path_x, path_y = trgt_x, trgt_y
    # Make an array of MoveRoute Commands
    while path_x != src_x || path_y != src_y
      # Get Parent x, Parent Y
      prnt_x, prnt_y = parent_x[path_x, path_y], parent_y[path_x, path_y]
      # DOWN = 1, LEFT = 2, RIGHT = 3, UP = 4, DL = 5, DR = 6, UL = 7, UR = 8
      if path_x < prnt_x # LEFT
        # Determine if upper, lower or direct left
        code = path_y < prnt_y ? 7 : path_y > prnt_y ? 5 : 2
      elsif path_x > prnt_x # RIGHT
        # Determine if upper, lower or direct right
        code = path_y < prnt_y ? 8 : path_y > prnt_y ? 6 : 3
      else # UP or DOWN
        code = path_y < prnt_y ? 4 : 1
      end
      path.push (RPG::MoveCommand.new (code))
      path_x, path_y = prnt_x, prnt_y
    end
    return path
  end
end


Credit

• modern algebra

Thanks

• Patrick Lester, for his tutorials on the A* Pathfinding algorithm (found at: http://www.gamedev.net/reference/articles/article2003.asp and at: http://www.policyalmanac.org/games/binaryHeaps.htm)
• Zeriab, for tricking me into believing this was an actual exercise

Support

Please just post here if you encounter any problems.


This script by modern algebra is licensed under a Creative Commons Attribution-Non-Commercial-Share Alike 2.5 Canada License.

* ahref aplauds

Sounds good

nice script again, MA.

Thanks, guys.

Hi! MA,

I'm thinking about using this pathfinding in my mouse script.

But I've problem that I can't just use

Code: [Select]

$game_player.find_path(x, y, false)

Because it needs @move_route to be set. (and I'm not sure how to set it)

I will send script's project to you in PM.

Please guide me through this. Thanks!

I sent you a PM. I think it should work, but if it doesn't then PM me again. Also, I didn't actually see a script project in the PM you sent me, but that's okay. I think it will work regardless.


EDIT::


Hmm, I thought of a problem. You'll also want to be able to override a command if the player clicks to a different place. Give me a few minutes and I'll see if I can think of a solution. I have an exam tomorrow, so I might not come up with something tonight but by tomorrow I should have thought of something.

Never mind - that actually shouldn't be a problem. It should be overridden automatically

That works great 

Thanks a lot! MA

Great job, MA!

Alrighty!

Updated to Version 2.0. It now generates much less lag (though it can still be noticeable for complex search spaces).

I also added a couple of features inspired by worale, namely a maximum number of iterations and the ability to force a path on a character through a script call. 

Nice, really nice, MA.

Thanks for your effort in this script! 

By the way,

Code: [Select]

#    Zeriab, for tricking me into believing that this was an actual exercise.
#        Also, his table printout actually makes Tables useable :P

Is table printout is script? 
Where can I get it?

Table printout was a little script written by Zeriab to help debug tables. He sent it to me via PM when I needed help with something, but I'm not sure if he's ever released it publicly.

Just send him a PM I guess. I don't think he'd mind if I gave it to you, but I figure you might as well get it from him.

I was joking modern, it's not my fault you took my joke seriously
There are probably some who are happy that you took my joke seriously, but even so. You don't have to credit me. I had nothing to do with it. You have found out and made everything without my help.
I'll probably look into it eventually. If not before, then for when I try to make a path finding script for RMXP

I have not published my Table script because I forgot about it. Feel free to do it if you want, I probably won't do it myself.

@woratana:
After some searching through my outbox I found it: (It's nothing special, not really)

Code: [Select]

class Table
  ##
  # Gives a special string representation. (For debugging purposes mostly)
  #
  def to_s
    if ysize == 1
      begin
        return to_s_1d
      rescue # In the rare case where you have a 2- or 3-dimensional
      end    # table with ysize = 1
    end
    if zsize == 1
      begin
        return to_s_2d
      rescue # In the rare case where you have a 3-dimensional table
      end    # with zsize = 1
    end
    return to_s_3d
  end
 
  ##
  # Returns a representation of the 1-dimensional table as a string
  # Assumes that the table is 1-dimensional. Will throw an error otherwise
  #
  def to_s_1d
    str = '['
    for i in 0...(xsize-1)
      str += self[i].to_s + ', '
    end
    str += self[xsize-1].to_s + ']'
    return str
  end
 
  ##
  # Returns a representation of the 2-dimensional table as a string
  # Assumes that the table is 2-dimensional. Will throw an error otherwise
  #
  def to_s_2d
    str = '['
    for j in 0...ysize
      str += "\n["
      for i in 0...(xsize-1)
        str += self[i,j].to_s + ', '
      end
      str += self[xsize-1,j].to_s + ']'
    end
    str += "\n]"
    return str
  end
 
  ##
  # Returns a representation of the 3-dimensional table as a string
  # Assumes that the table is 3-dimensional. Will throw an error otherwise
  #
  def to_s_3d
    str = '{'
    for k in 0...zsize
      str += '['
      for j in 0...ysize
        str += "\n["
        for i in 0...(xsize-1)
          str += self[i,j,k].to_s + ', '
        end
        str += self[xsize-1,j,k].to_s + ']'
      end
      str += "\n]"
    end
    str += '}'
    return str
  end
end

*hugs*
 - Zeriab

@Modern Algebra
 I just tried it today, work really great!
Thanks for your effort on this 

I haven't try it in big map though, but it works with no lag in 17*13 map and no limit iterator.

In case if lag happens, I already put the iterator variable in mouse's setup part, so users can change if they see any lag.

@Zeriab
Thank! 

This will be really useful when I'm using table. >_> <_<~

Hi!

Sorry, I'm really bad at this. So this is what my event looks like:

@>Set Move Route: This Event
 :                            : $> Script: find_path (10, 10)

And the trigger is the action key. But when I test the game, and I start the event... nothing happens. The guy just stands there...

What am I doing wrong?

I won't know without seeing the map. It's possible that something is blocking the route. Can you take a screenshot of the map and event in question?

EDIT: Nevermind. It works perfectly now. Thanks!

Is it possible to tweak this so that it can walk around solid objects in its way, rather than just not executing?

What do you mean? It will not execute only if there is no path to the destination whatsoever. If there is an object in the way but there is another path to the object, it should take that path.

OK, I figured out the problem. It wasn't moving because it was picking up events in the way.

They were above and below the characters though, so I didn't think that would cause a problem.....

Is there any way to set the coordinates to the coordinates of the player?

This way, the object that is executed to move by the script, "chases" the player?

The Path Finder uses the same method for passability as when you are walking, and so the only squares that should block a path are ones that you wouldn't be able to walk through if you were trying to move that event or player manually. That being said, the passability method is retarded in RMVX and events at same level cannot walk over other events no matter what setting they're on, though your player can. I think worale wrote a script to fix that though.

As to your other question - no, not really. The way that it currently works is that it will replace the command with the commands that are generated by the algorithm - it will not continually try to find the player. Adding to the problem is that the player himself is an impassable square, and so it will not return a path anyway.

I am probably going to return to this script soon though, and I will see what I can do to address the stupidity of the approach method. I intend to do a few things once I start revising this script, and that list is:

• Allow for revising a path if an impassable event moves into the way of the path already generated - this will require a different way to setup the paths perhaps, though I will keep the same interface.
• Create a few additional pathfinding algorithms, including a near-optimal hierarchical pathfinding and a fringe search algorithm
• Fix the approach method so that it uses the pathfinding script to find better paths to the player.

OK. Well, that really sucks, but I'll find a way.

If you ever think it's possible that the script will get to the point where an event can "chase" a player, that would be awesome

I appreciate your help, and this is a fine script

Heya, I'm spaniard, so I'm sorry if my "english" is hard to understand... *heh*
First, thanks for writing this script.

I'd like to know if it's possible (in case the destination of the path isn't "passable") to find the shortest path to an adjacent location.

I fear I haven't explained it well, but I hope this helps:

"If $game_map.passable? (X,Y)
$game_player.force_path (x,y)
   Elseif $game_map.passable? (x+1,y) or $game_map.passable (x-1,y) or $game_map.passable (x,y+1) or $game_map.passable(x,y-1)
   $game_player.force_path (the location that is closer to the player)

It would be something like this, I presume...    Thx in advance ^^.

Umm, you mean in a script?

This script does already find the shortest path to a location. All you need to do is use the Set Move Route command, then Script: find_path (x, y)

So something like:

@>Set Move Route: Player
  :                           : $> Script: find_path (x, y)


Will move you to X, Y.

Unless what you are asking for is finding a path to a location nearby in case the original location x, y is impassable. In that case, what you are doing is roughly correct.

If you wanted to do it with events, it'd be roughly:

Control Variables: [UUU: Player X] = Player's X
Control Variables: [VVV: Player Y] = Player's Y
Control Variables: [XXX: Destination X] = X
Control Variables: [YYY: Destination Y] = Y
Label: Find Path 
Conditional Branch: $game_player.passable? ($game_variables[XXX], $game_variables[YYY])
  Set Move Route: Player 
                           : $> Script: find_path (x, y)
  Jump to Label: END
Else
  And I'm too lazy to do the rest, but basically you would have to check passability in reference to player position
Label: END


In any case, I will be working on a version 2 of this script soon which is going to be a lot better I hope. Part of it will include the ability to walk to closest square to destination and moving around moving events that interfere in the path after the path has been calculated.

Yay, your answer solved my problem.
I hope that version 2 will be as good as it seems, it'll be a GREAT script for my "Point & Click" game; thank you very much for your work ^^

Great script! I was hoping a solution to some eventing issues would be this easy to fix.

BUT! I was wondering if there's an easy way to make the script recalculate the path every time it is called...

Example:

I have K.T.S. set for in the day time, the villagers walk around aimlessly... but, at night time the villagers in town return to their respective houses (using your path finder). So since it only calculates each path once the next time the script is called (if i haven't left the map yet) it repeats the path taken before, even though since the villagers are set to random movement it may not be the same path needed...

Any ideas would be appreciated!