The RPG Maker Resource Kit

---

• 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

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

---

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.

• 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

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

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

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

---


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


---

• modern algebra

• 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

---

Please just post here if you encounter any problems.

---

/me 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
$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!  :D

By the way,
#    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 :dog:
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)
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!  :D

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 :D

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!

When I write a new version of this script, I will allow for it. As it is, you would need to alter the script so that it retains the size of the path and the old command, and then just reset the move event command.

I just wanted to let you know that this is a very great and important VX script ;)

You have all my compliments :)

Thank you for that. It is still quite flawed though. I do intend to work on making a better version once my schedule clears up.

Still a great script MA.

Just cleaning some spam.
~Fix'd spam junkie Shandy333~ He needs to keep his shit shut.

Necro for the sake of support:
I have this http://www.rpgmakervx.net/index.php?showtopic=17774&st=0&p=153712&#entry153712 (http://www.rpgmakervx.net/index.php?showtopic=17774&st=0&p=153712&#entry153712) script - how would the pathfinding work, assuming I set one tile paths to look like, vertically and in order, ceiling wall wall ceiling?
Would it recognize a path there?

Umm, not sure. I have not really looked at the coding for that script before. Have you tested it?

Did test, not sure what caused it, but something more than this script mucked it up. Not sure what so can't provide a straight test conclusion.
I know path finding worked in a room with no obstacles but not from one room to another. Odd that, really.

How easy would it be to allow this to create a path to get to the position (but one) of the player? Looking at the script and running some tests, it doesn't seem to like you specify a position that VX determines as impassable.

I tried to do something with it without going into anything too heavy for the GIAW contest, but didn't get too far with it at the time. Thinking about it though, I'd also need something along the lines of what you had planned for V3 of this script, in particular the recalculation of the route part due to the game including many moments in which the situation of the game and the player could change (in both subtle and dramatic ways).

Really, it'd just be nice to be able to move towards the player's location. Unless it'd just be simpler for me to work on my own version of the script so that I can make it work easier with the other idea(s) that I have planned.

I have no issues with scripting path finding algorithms (having based my uni dissertation on said algorithms), but seeing as this script already exists, I figured I'd see what you could do before I start the researching and planning that I'll have to do. Even some good ideas for me to look into/work on would be appreciated.

Thanks in advance, for whatever you can provide me with.

Hey MA, any news on a V3 of this script? We're trying to get a stable mouse system going, and we're running into problems with the current version of this script, which we're using for the script. It's actually just lag stuff, which we're trying to fix in other means, but we're getting some problems. I read that you have a better, faster version of this coming.. Is this still in development?

Or heck, what would be even easier, if you could maybe explain how we could set two different counts. One to keep track of the iterations, and one to keep track of the steps between the paths, and I think we could fix the problems we're having.

Sorry for necro posting but I found a bug:

The script  allows me to make a npc (or character) walk to a specific x and y coordinate on a map. It will determine the shortest path and walk there. How ever I found in maps with heavy obstacles that npc will not move.

For example, Suppose you have a pub with lots of NPC's, chairs, tables and obstacles. now make an NPC walk from point A to b, wait, walk from point b to the exit (disappear - wait re-apear) and walk to point C (some other place in the pub). Depending on how obstacle heavy your pub is (and this one is obstacle heavy) that NPC will disappear (it will essentially skip to the "leave the pub" section) and then after some frames re-apear and try to walk across the pub. This should not happen. the NPC should follow the command given by:

find_path (target_x, target_y, diagonal, max_iterations)

in this instance max-iterations is set to 0 (tested it with a number like 10 still doesn't change anything). Now maps that are not obstacle heavy like plains or a small forest the character can walk to the location given by this command. How ever if the map were to have lots of barrels or trees and lots of ways that the character could get to there destination it will skip that step or not move at all or in this case, the case of the pub example, leave and come back - essentially skipping to some other part of the movement commands given.

Hope this helps. I believe its an issue with your antilogarithm.

Bump

Are you still planning to make V3 of this script? I'm just curious because I can't use it, since routes aren't being recalculated. It would be great if anyone could fix this, as my scripting skills aren't good enough to alter this script by myself. And sorry for necropost.

Is there a way to make an event go directly to the player ? This sounds like a gnar-gnar script, but it'd be even better if you could do that.
I've tried setting the script in the move route to "find_path($game_player.x, $game_player.y)" on repeat, but it doesn't seem to work. The event stays in place. And the pathfinding on the default "approach" is really iffy... when the events are too far away from the player, they get stuck in walls or don't move at all.

This is the only viable pathfinding script I can find for VX, unfortunately I'm having the same problem as slayer.

Would really appreciate it if you could do something about that recalculation (maybe a line that reloads the event page?). Script doesn't need to be any more efficient IMO, it just needs to be able to recalculate.

If it helps as reference, I have an ACE pathfinding script which does recalculate:

[spoiler]#===============================================================================
# Pathfinding & Event formations
# By Jet10985(Jet) & Venima
#===============================================================================
# This script will allow you to use a pathfinder to move players or events.
# Modification: This script will also allow you to use a pathfinder which
# incorporates formation handling.
# This script has: 2 customization options.
#
# Modifications:
# Pathfinder:
# Goal location may now be inpassable, pathfinder will still reach it.
# Pathfinder still works "as intended" when the move route is set to repeat.
# Added parameter: distance (explained below).
# Added parameter: jump (set to true if the moves should be jumps instead of
# walking).
# Added parameter: commonEvent (provide the common event id for the pathfinder
# to run the event before each move (useful for adding sound or effects to
# movements)
# Added parameters:
# catchup (provide a value to indicate how far from the target the event
#   should be before it speeds up its movement)
# catchupSpeed (provide a value for the speed when catching up)
# normalSpeed (provide a value for the speed after its caught up)
# Note: Pathfinder is a bit more processor heavy when used with a repeating
# move route (it was useless before, so this is only a benefit)
# Formations:
# Added find_formation_path function
# Added turn_with_player function
#
#===============================================================================
# Overwritten Methods:
# None
#-------------------------------------------------------------------------------
# Aliased methods:
# None
#===============================================================================
=begin

===============================================================================
Instructions:

===============================================================================
Standard pathfinder:
-------------------------------------------------------------------------------

To move a player or event, use this in a move route's "Script..." command:

find_path(x, y, distance = 0, jump = false, commonEvent = 0, catchup = 0,
      catchupSpeed = 5, normalSpeed = 4)

x is the target x

y is the targey y

distance is set to 0 by default and can be omitted to keep the default value.
While x and y represent the target location, the event will only be moved
up to the specified distance from the target. This makes it easier to have
an event follow the player, without getting in the player's way. This could
be used as an alternative to following, except it works on any events,
not just party members.

jump is set to false by default and can be omitted. Jump specifies that
instead of the event "moving" to the target, the event will make small "jumps"
to the target. If you specify jump, you cannot omit any previous parameters.

commonEvent is set to 0 by default and can be omitted. This specifies the
id of a common event that you want executed before each move step. Currently
this only applies to repeating paths. When set to 0, no common event is called.
If you specify commonEvent you cannot omit any previous parameters.

catchup is set to 0 by default and can be omitted. Catchup specifies that if
the event is equal to or past the catchup distance, they will move faster to
"catch up". Their speed becomes the catchUp speed. Once caught up, they will
return to the normalSpeed. If you specify catchup you cannot omit any previous
parameters.

catchupSpeed is set to 5 by default and can be omitted. It is used when catchup
is specified to a value above 0. (see catchup for details). If you specify
catchupSpeed you cannot omit any previous parameters.

normalSpeed is set to 5 by default and can be omitted. It is used when catchup
is specified to a value above 0. (see catchup for details). If you specify
normalSpeed you cannot omit any previous parameters.



Running the script outside of a move route (as a standalone script call)
has two extra parameters after x and y called "ev" and "wait" but has no
commonEvent or catcup parameters.

find_path(x, y, ev = 0, wait = false, distance = 0, jump = false)

ev is set to 0 by default and can be omitted like so: find_path(9, 4).
Ev represents which character is to be moved. -1 is the player, 0 is the
calling event, and anything above is an event on the map whose ID is the ev.

wait is set to false by default and can be omitted like so:
find_path(9, 4) or find_path(9, 4, -1)
find_path(x, y) or find_path(x, y, ev)
wait specifies if the player will have to wait for the move route to finish
to start moving again.

-------------------------------------------------------------------------------
Examples:

Example of following the player at a distance:

In event's custom move route or specified move route (on repeat):
  find_path($game_player.x, $game_player.y, 3)
 
Example of an event following an event with id 2 and catching up:
  find_path($game_events[2].x, $game_events[2].y, 0, false, 0, 3)

===============================================================================
Formation handling:
-------------------------------------------------------------------------------

To move an event using a formation use this in a move route:

find_formation_path(followId, shiftX, shiftY, catchup = FORM_CATCHUP_DIST,
      catchupSpeed = 5, normalSpeed = 4)
     
followId is the character that this event is in formation with. -1 = player,
0 = current event (although this is pointless) and above 0 is the event id.

shiftX is the relational x position from the followId character WHEN that
character faces "down". If you enter -1, this event will move to the left if
its facing down, or right if its facing up.

shiftY is the relational y position from the followId character WHEN that
character faces "down". If you enter -1, this event will move above if its
facing down, or below if it's facing up.

catchup's default value is specified by the parameter FORM_CATCHUP_DIST and
can be omitted. This specifies how far behind this event can get before it
speeds up to catch up.

catchupSpeed's default value is 5 and can be omitted. This specifies how fast
this event will move when it's "catching up". If you specify catchupSpeed, you
cannot omit any previous parameters.

normalSpeed's default value is 4 and can be omitted. This specifies how fast
this event will move when it isn't "catching up". If you specify normalSpeed,
you cannot omit any previous parameters.


You also have another command for formations:
Entering "turn_with_leader" as a separate script after find_formation_path
will cause the event to turn the same way the player is turned after arriving
at their formation position.
Entering "turn_with_leader(1)" will turn the same way as event with id 1.
Turn_with_leader also has a second optional parameter. Entering "left" or -1
will turn this event left of the leader's direction, entering "right" or 1
will turn this event right of the leader's direction, and entering "back" or 2
will turn this event opposite of the leader's direction. Again, if you specify
this parameter, you cannot omit the previous one.

-------------------------------------------------------------------------------
Examples:

Example of 2 events acting similar to followers behind the player:
In a repeating move-route for Event 01:
find_formation_path(-1,0,-1)
In a repeating move_route for Event 02:
find_formation_path(1,0,-1)

Example of an event covering the player's back 2 spaces away:
In a repeating move-route:
find_formation_path(-1,0,-2)
turn_with_leader(-1,"back")

Example of an event with a formation determined by in-game variables:
In a repeating move-route:
find_formation_path(-1, $game_variables[1], $game_variables[2])

=end

#===============================================================================
# Customisation options below:
#===============================================================================
module Venima
  module Formations
    #
    FORM_CATCHUP_DIST = 3
  end
end

module Jet
  module Pathfinder
   
    # While mainly for coders, you may change this value to allow the
    # pathfinder more time to find a path. 1000 is default, as it is enough for
    # a 100x100 MAZE so, yeah.
    # Note from Venima, you probably don't want to change this value too much
    MAXIMUM_ITERATIONS = 500
   
  end
end
#===============================================================================
# Customisation end
#===============================================================================

class Node
 
  include Comparable

  attr_accessor :point, :parent, :cost, :cost_estimated

  def initialize(point)
    @point = point
    @cost = 0
    @cost_estimated = 0
    @on_path = false
    @parent = nil
  end

  def mark_path
    @on_path = true
    @parent.mark_path if @parent
  end
   
  def total_cost
    cost + cost_estimated
  end

  def <=>(other)
    total_cost <=> other.total_cost
  end
   
  def ==(other)
    point == other.point
  end
end

class Point
 
  attr_accessor :x, :y
 
  def initialize(x, y)
    @x, @y = x, y
  end

  def ==(other)
    return false unless Point === other
    @x == other.x && @y == other.y
  end

  def distance(other)
    (@x - other.x).abs + (@y - other.y).abs
  end

  def relative(xr, yr)
    Point.new(x + xr, y + yr)
  end
end

class Game_Map
 
  def each_neighbor(node, char = $game_player)
    x = node.point.x
    y = node.point.y
    nodes = []
    4.times {|i|
      i += 1
      new_x = round_x_with_direction(x, i * 2)
      new_y = round_y_with_direction(y, i * 2)
      next unless char.passable?(x, y, i * 2)
      #removed line below (technically, if your goal is an inpassable block,
      # e.g. an event, you can still reach it)
      #next unless char.passable?(new_x, new_y, 10 - i * 2)
      nodes.push(Node.new(Point.new(new_x, new_y)))
    }
    nodes
  end
 
  def find_path(tx, ty, sx, sy, dist, jump, char = $game_player)
    start = Node.new(Point.new(sx, sy))
    goal = Node.new(Point.new(tx, ty))
    return [] if start == goal or (dist > 0 and start.point.distance(goal.point) <= dist)
    return [] if ![2, 4, 6, 8].any? {|i| char.passable?(tx, ty, i) }
    open_set = [start]
    closed_set = []
    path = []
    iterations = 0
    loop do
      return [] if iterations == Jet::Pathfinder::MAXIMUM_ITERATIONS
      iterations += 1
      current = open_set.min
      return [] unless current
      each_neighbor(current, char).each {|node|
        if node == goal or (dist > 0 and node.point.distance(goal.point) <= dist)
          node.parent = current
          node.mark_path
          return recreate_path(node, jump)
        end
        next if closed_set.include?(node)
        cost = current.cost + 1
        if open_set.include?(node)
          if cost < node.cost
            node.parent = current
            node.cost = cost
          end
        else
          open_set << node
          node.parent = current
          node.cost = cost
          node.cost_estimated = node.point.distance(goal.point)
        end
      }
      closed_set << open_set.delete(current)
    end
  end
 
  def recreate_path(node, jump)
    path = []
    hash = {[1, 0] => 6, [-1, 0] => 4, [0, 1] => 2, [0, -1] => 8}
    until node.nil?
      pos = node.point
      node = node.parent
      next if node.nil?
      ar = [pos.x <=> node.point.x, pos.y <=> node.point.y]
      if jump
        path.push(RPG::MoveCommand.new(14,ar))
      else
        path.push(RPG::MoveCommand.new(hash[ar] / 2))
      end
    end
    return path
  end
end

class Game_Character
 
  #modified function (added handling for repeated move route (recalculates path
  # each step so it doesn't just loop it's old path route and will revalidate 
  # if x or y changes, will follow variable value if x and y are set to it)
  def find_path(x, y, dist = 0, jump = false, commonEvent = 0, catchup = 0, catchupSpeed = 5, normalSpeed = 4)
    path = $game_map.find_path(x, y, self.x, self.y, dist, jump).reverse
    if !@move_route.repeat
      @move_route.list.delete_at(@move_route_index)
      @move_route.list.insert(@move_route_index, *path)
      @move_route_index -= 1
    elsif path.length > 0
      if commonEvent > 0
        $game_temp.reserve_common_event(commonEvent)
      end
      if catchup > 0
        if @move_speed < catchupSpeed && path.length >= catchup
          process_move_command(RPG::MoveCommand.new(29,[catchupSpeed]))
        elsif @move_speed >= catchupSpeed && path.length < 2
          process_move_command(RPG::MoveCommand.new(29,[normalSpeed]))
        end
      end
      process_move_command(path[0])
      @move_route_index -= 1
    end
    return path.length
  end

  def get_character(i)
    if i == -1
      return $game_player
    end
    if i == 0
      return $game_map.events[@event_id]
    end
    if i > 0
      return $game_map.events[i]
    end
  end
 
  def find_formation_path(followId, shiftX, shiftY, catchup = Venima::Formations::FORM_CATCHUP_DIST, catchupSpeed = 5, normalSpeed = 4)
    x = shift_follow_x(followId, shiftX, shiftY)
    y = shift_follow_y(followId, shiftX, shiftY)
    if find_path(x,y,0,false,0,catchup,catchupSpeed,normalSpeed) == 0
      char = get_character(followId)
      find_path(char.x,char.y,3,false,0,catchup,catchupSpeed,normalSpeed)
    end
  end
 
  def shift_follow_x(followId, shiftX, shiftY)
    char = get_character(followId)
    case char.direction
    when 2
      return char.x + shiftX
    when 4
      return char.x - shiftY
    when 6
      return char.x + shiftY
    when 8
      return char.x - shiftX
    end
    return char.x
  end
 
  def shift_follow_y(followId, shiftX, shiftY)
    char = get_character(followId)
    case char.direction
    when 2
      return char.y + shiftY
    when 4
      return char.y - shiftX
    when 6
      return char.y + shiftX
    when 8
      return char.y - shiftY
    end
    return char.y
  end
 
  def turn_with_leader(eventId = -1, dirmod = "")
    dir = get_character(eventId).direction
    mod = 0
    if dirmod == "left" || dirmod == -1
      case dir
      when 2
        set_direction(4)
      when 4
        set_direction(2)
      when 6
        set_direction(8)
      when 8
        set_direction(6)
      end
    elsif dirmod == "right" || dirmod == 1
      case dir
      when 2
        set_direction(6)
      when 4
        set_direction(8)
      when 6
        set_direction(2)
      when 8
        set_direction(4)
      end
    elsif dirmod == "back" || dirmod == 2
      case dir
      when 2
        set_direction(8)
      when 4
        set_direction(6)
      when 6
        set_direction(4)
      when 8
        set_direction(2)
      end
    else
      set_direction(dir)
    end
  end
end

class Game_Interpreter
 
  #modified line below (added distance parameter)
  def find_path(x, y, ev = 0, wait = false, dist = 0, jump = false)
    char = get_character(ev)
    #modified line below (added distance parameter)
    path = $game_map.find_path(x, y, char.x, char.y, dist, jump)
    path.reverse!
    path.push(RPG::MoveCommand.new(0))
    route = RPG::MoveRoute.new
    route.list = path
    route.wait = wait
    route.skippable = true
    route.repeat = false
    char.force_move_route(route)
  end
end[/spoiler]

I would convert it but, I only know RGSS3, I don't know the differences between that and RGSS2.