Path Finding

[modern algebra]

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 Expand

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


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

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

Script

Code Select Expand


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

* ahref aplauds

[worale]

Sounds good

nice script again, MA.

[modern algebra]

Thanks, guys.

[worale]

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 Expand

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

[modern algebra]

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

[worale]

That works great 

Thanks a lot! MA

[Leventhan]

Great job, MA!

[modern algebra]

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. 

[worale]

Nice, really nice, MA.

Thanks for your effort in this script! 

By the way,

Code Select Expand

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

[modern algebra]

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.

[Zeriab]

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 Expand

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

[worale]

@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. >_> <_<~

[SouthWall]

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?

[modern algebra]

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?

[SouthWall]

EDIT: Nevermind. It works perfectly now. Thanks!

[Nate]

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

[modern algebra]

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.

[Nate]

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?

[modern algebra]

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.

[Nate]

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

[Emin]

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

[modern algebra]

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.

[Emin]

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

[slayerofman]

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!