SHARE
TWEET

[RMXP] Advanced Pathfinding

ForeverZer0 Jun 5th, 2011 497 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
  2. # Advanced Pathfinding
  3. # Author: ForeverZer0
  4. # Version: 1.0
  5. # Date: 5.30.2011
  6. #+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
  7. #
  8. # Introduction:
  9. #   This is an advanced an highly inteligent pathfinding system. It allows for
  10. #   the user to either through script or script call quickly and easily have
  11. #   events or the game player automatically walk a path to a given set of
  12. #   coordinates. The system is smart enough to quickly find paths through
  13. #   relatively complex areas, and asjust on the fly for any obstacle that moves
  14. #   to block its path. I used the A* algorithm, basic search algorithm used
  15. #   often for robotics. More on this algorithm can be read about here:
  16. #
  17. #               http://en.wikipedia.org/wiki/A*_search_algorithm
  18. #
  19. # Features:
  20. #   - Fast and intelligent pathfinding
  21. #   - Easy to use script calls
  22. #   - Optional "range" parameter can have character find alternate locations
  23. #     if the preferred one is blocked and they are within the given range.
  24. #   - Optional callbacks can be given to have something execute if when the
  25. #     character reaches its goal, or when it fails to do so.
  26. #
  27. # Instructions:
  28. #   - Place script below default scripts, and above "Main".
  29. #   - Use the following script call:
  30. #
  31. #     pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
  32. #    
  33. #     The X and Y are the only required arguments. The others can be omitted.
  34. #    
  35. #     X - The x-coordinate to pathfind to.
  36. #     Y - The y-coordinate to pathfind to.
  37. #
  38. #     CHARACTER - Either an instance of the character ($game_player,
  39. #                 $game_map.events[ID], etc) or the ID of a character. The ID
  40. #                 will be the event ID. Use -1 for the game player.
  41. #
  42. #     SUCCESS_PROC - A Proc object that will be executed when the player
  43. #                    reaches the defined coordinates.
  44. #     FAILURE_PROC - A Proc object that will be executed when the player
  45. #                    cannot reach the defined coordinates.
  46. #
  47. #   - As default, the pathfinder will make 35 attempts to recalculate a route
  48. #     that gets blocked. This value can be changed in game with the script
  49. #     call:
  50. #           $game_map.collision_retry = NUMBER
  51. #
  52. #     You can change the default value if desired by looking down to the first
  53. #     class below in the main script.
  54. #   - For longer pathfind routes, it is sometimes necessary to reset the
  55. #     search limiter. This may cause increased lag when an object blocks the
  56. #     character from being able to move, but will increase the range that the
  57. #     system can work with. Use the following script call:
  58. #
  59. #         $game_map.search_limiter = NUMBER  (Default 1000)
  60. #
  61. #   - If you are experiencing any compatibility problems, go to the Game_Map
  62. #     class below and set @recalculate_paths to false. This will take away some
  63. #     of the efficiency of recalculating collisions, but will improve may fix
  64. #     your problem.
  65. #
  66. # Compatibility:
  67. #   Highly compatible. May experience issues with Custom Movement scripts,
  68. #   but even then, it is unlikely.
  69. #
  70. # Credits/Thanks:
  71. #   - ForeverZer0, for the script
  72. #   - Special thanks to Jragyn for help making the big maze for the demo and
  73. #     help testing.
  74. #   - Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the
  75. #     original search algorithm that was implemented
  76. #
  77. #+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
  78.  
  79. #===============================================================================
  80. # ** Game_Map
  81. #===============================================================================
  82.  
  83. class Game_Map
  84.  
  85.   attr_accessor :collision_retry
  86.   attr_accessor :recalculate_paths
  87.   attr_accessor :search_limiter
  88.  
  89.   alias zer0_pathfinding_init initialize
  90.   def initialize
  91.     # Initialize instance variables used for pathfinding.
  92.     @collision_retry = 35
  93.     @recalculate_paths = true
  94.     @search_limiter = 1000
  95.     # Original method
  96.     zer0_pathfinding_init
  97.   end
  98. end
  99.  
  100. #===============================================================================
  101. # ** Interpreter
  102. #===============================================================================
  103.  
  104. class Interpreter
  105.  
  106.   def pathfind(x, y, *args)
  107.     args[0] = @event_id if args[0] == nil
  108.     args[1] = 0 if args[1] == nil
  109.     # Add a simpler call for using as a script call
  110.     Pathfind.new(Node.new(x, y), *args)
  111.   end
  112. end
  113.  
  114. #==============================================================================
  115. # ** Pathfind
  116. #==============================================================================
  117.  
  118. class Pathfind
  119.  
  120.   attr_reader   :route                  
  121.   attr_accessor :range  
  122.   attr_reader   :goal
  123.   attr_reader   :found
  124.   attr_reader   :character                                
  125.   attr_accessor :success_proc          
  126.   attr_accessor :failure_proc        
  127.   attr_accessor :target    
  128.   attr_accessor :collisions      
  129.  
  130.   def initialize(node, char = -1, range = 0, *callbacks)
  131.     # Set the character. Can either us an ID or an instance of a Game_Character.
  132.     # A value of -1, which is default, is the Game_Player.
  133.     if char.is_a?(Integer)
  134.       @character = (char == -1) ? $game_player : $game_map.events[char]
  135.     elsif char.is_a?(Game_Character)
  136.       @character = char
  137.     end
  138.     # Set forcing flag. Will be disabled for recalculating on the fly.
  139.     @forcing = true
  140.     # Call a public method, since this method may need to be used again,
  141.     # and "initialize" is private.
  142.     setup(node, range, *callbacks)
  143.   end
  144.  
  145.   def setup(node, range = 0, *callbacks)
  146.     # Initialize the node we are trying to get to.
  147.     @target = Node.new(node.x, node.y)
  148.     @goal = @target.clone
  149.     # Set beginning nodes and required variables.
  150.     @start_node = Node.new(@character.x, @character.y)
  151.     @nearest = Node.new(0, 0, 0, -1)
  152.     @range, @found, @collisions = range, false, 0
  153.     # Set callbacks for success and failure if included, else nil.
  154.     @success_proc = callbacks[0]
  155.     @failure_proc= callbacks[1]
  156.     # Initialize sets to track open and closed nodes
  157.     @open_set, @close_set = [@start_node], {}  
  158.     # Find the optimal path
  159.     calculate_path
  160.   end
  161.  
  162.   def calculate_path
  163.     # Only do calculation if goal is actually passable, unless we only
  164.     # need to get close or within range
  165.     if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
  166.       # Initialize counter
  167.       counter, wait = 0, 0
  168.       until @open_set.empty?
  169.  
  170.         counter += 1
  171.         # Give up if pathfinding is taking more than 500 iterations
  172.         if counter >= $game_map.search_limiter
  173.           @found = false
  174.           break
  175.         end
  176.         # Get the node with lowest cost and add it to the closed list
  177.         @current_node = get_current
  178.         @close_set[[@current_node.x, @current_node.y]] = @current_node
  179.         if @current_node == @goal ||
  180.            (@range > 0 && @goal.in_range?(@current_node, @range))
  181.           # We reached goal, exit the loop!
  182.           @target = @goal
  183.           @goal, @found = @current_node, true
  184.           break
  185.         else # if not goal
  186.           # Keep track of the node with the lowest cost so far
  187.           if @current_node.heuristic < @nearest.heuristic ||
  188.             @nearest.heuristic < 1
  189.             @nearest = @current_node
  190.           end
  191.           # Get adjacent nodes and check if they can be added to the open list
  192.           neighbor_nodes(@current_node).each {|neighbor|
  193.             # Skip Node if it already exists in one of the lists.
  194.             next if can_skip?(neighbor)
  195.             # Add node to open list following the binary heap conventions
  196.             @open_set.push(neighbor)
  197.             arrange(@open_set.size - 1)
  198.           }
  199.         end
  200.       end
  201.     end
  202.     # If no path was found, see if we can get close to goal
  203.     unless @found
  204.       if @range > 0 && @nearest.heuristic > 0  
  205.         # Create an alternate path.
  206.         setup(@nearest, @range, @success_proc, @failure_proc)
  207.       elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
  208.         (@collisions > $game_map.collision_retry))
  209.         # If out of retries, call the Proc for failure if defined
  210.         @failure_proc.call
  211.       end
  212.     end
  213.     # Create the move route using the generated path
  214.     create_move_route
  215.   end
  216.  
  217.   def create_move_route
  218.     # There's no path to generate if no path was found
  219.     return if !@found
  220.     # Create a new move route that isn't repeatable
  221.     @route = RPG::MoveRoute.new
  222.     @route.repeat = false
  223.     # Generate path by starting from goal and following parents
  224.     node = @goal
  225.     while node.parent
  226.       # Get direction from parent to node as RPG::MoveCommand
  227.       code = case direction(node.parent.x, node.parent.y, node.x, node.y)
  228.       when 2 then 4 # Up
  229.       when 4 then 3 # Left
  230.       when 6 then 2 # Right
  231.       when 8 then 1 # Down
  232.       else; 0
  233.       end
  234.       # Add movement code to the start of the array
  235.       @route.list.unshift(RPG::MoveCommand.new(code)) if code != 0
  236.       node = node.parent
  237.     end
  238.     # If the path should be assigned to the character
  239.     if (@forcing && !@route.list.empty?)
  240.       @collisions = 0
  241.       @character.paths.push(self)
  242.       @character.force_move_route(@route) if @character.paths.size == 1
  243.     end
  244.     # Reset forcing flag if needed
  245.     @forcing = true
  246.     # Return the constructed RPG::MoveRoute
  247.     return @route
  248.   end
  249.  
  250.   def arrange(index)
  251.     # Rearrange nodes in the open_set
  252.     while index > 0
  253.       # Break loop unless current item's cost is less than parent's
  254.       break if @open_set[index].score > @open_set[index / 2].score
  255.       # Bring lowest value to the top.
  256.       temp = @open_set[index / 2]
  257.       @open_set[index / 2] = @open_set[index]
  258.       @open_set[index] = temp
  259.       index /= 2
  260.     end
  261.   end
  262.  
  263.   def get_current
  264.     return if @open_set.empty?
  265.     return @open_set[0] if @open_set.size == 1
  266.     # Set current node to local variable and replace it with the last
  267.     current = @open_set[0]
  268.     @open_set[0] = @open_set.pop
  269.     # Loop and rearrange array according to the A* algorithm until done.
  270.     y = 0  
  271.     loop {
  272.       x = y
  273.       # If two children exist
  274.       if 2 * x + 1 < @open_set.size
  275.         if @open_set[2 * x].score <= @open_set[x].score
  276.           y = 2 * x
  277.           if @open_set[2 * x + 1].score <= @open_set[y].score
  278.             y = 2 * x + 1
  279.           end
  280.         end
  281.       # If only one child exists
  282.       elsif 2 * x < @open_set.size &&
  283.         @open_set[2 * x].score <= @open_set[x].score
  284.         y = 2 * x
  285.       end
  286.       # Swap a child if it is less than the parent.
  287.       break if x == y
  288.       temp = @open_set[x]
  289.       @open_set[x] = @open_set[y]
  290.       @open_set[y] = temp
  291.     }
  292.     # Return the original first node (which was removed)
  293.     return current
  294.   end
  295.  
  296.   def direction(x1, y1, x2, y2)
  297.     # Return the numerical direction between coordinates.
  298.     return 6 if x1 > x2 # Right
  299.     return 4 if x1 < x2 # Left
  300.     return 2 if y1 > y2 # Bottom
  301.     return 8 if y1 < y2 # Top
  302.     return 0            
  303.   end
  304.  
  305.   def neighbor_nodes(node)
  306.     # Create array to hold the nodes, then check each direction.
  307.     nodes = []
  308.     nodes.push(get_neighbor(node.x + 1, node.y, node)) # Right
  309.     nodes.push(get_neighbor(node.x - 1, node.y, node)) # Left
  310.     nodes.push(get_neighbor(node.x, node.y + 1, node)) # Down
  311.     nodes.push(get_neighbor(node.x, node.y - 1, node)) # Up
  312.     # Remove any nil elements, then return results.
  313.     return nodes.compact
  314.   end
  315.  
  316.   def get_neighbor(x, y, parent)
  317.     # Calculate direction, return new node if passable.
  318.     direction = direction(x, y, parent.x, parent.y)
  319.     if @character.passable?(parent.x, parent.y, direction)
  320.       # The heuristic is simply the distance
  321.       heuristics = ((x - @goal.x).abs + (y - @goal.y).abs)
  322.       return Node.new(x, y, parent, parent.cost + 1, heuristics)
  323.     end
  324.   end
  325.  
  326.   def can_skip?(node)
  327.     # Branch by if node is in either the open or closed set.
  328.     if @open_set.include?(node)
  329.       index = @open_set.index(node)
  330.       return true if @open_set[index].score <= node.score
  331.       # Swap them and update list order
  332.       @open_set[index] = node
  333.       arrange(index)
  334.       return true
  335.     elsif @close_set[[node.x, node.y]] != nil
  336.       # If the existing passed node has a lower score than this one.
  337.       return true if @close_set[[node.x, node.y]].score <= node.score
  338.       # Update the existing node
  339.       @close_set[[node.x, node.y]] = node
  340.     end
  341.     # Return false if no criteria was met.
  342.     return false
  343.   end
  344. end
  345.  
  346. #==============================================================================
  347. # ** Game_Character
  348. #==============================================================================
  349.  
  350. class Game_Character
  351.  
  352.   attr_accessor :paths
  353.   attr_accessor :move_route_forcing
  354.   attr_accessor :move_route
  355.  
  356.   alias zer0_pathfinding_init initialize
  357.   def initialize
  358.     # Add public instance variable for paths
  359.     @paths = []
  360.     # Original method
  361.     zer0_pathfinding_init
  362.   end
  363.  
  364.   def next_route
  365.     # Stop any custom move route that may be occuring.
  366.     if @move_route != nil
  367.       # Set index and disable forcing of current route
  368.       @move_route_index = @move_route.list.size
  369.       @move_route_forcing = false
  370.       # Reset to what it was originally
  371.       @move_route = @original_move_route
  372.       @move_route_index = @original_move_route_index
  373.       @original_move_route = nil
  374.     end
  375.     # Remove first path from the paths array.
  376.     @paths.shift
  377.     # If there is another path to follow...
  378.     if @paths[0] != nil
  379.       # Setup path again to reflect any changes since original creation
  380.       @forcing = false
  381.       @paths[0].setup(@paths[0].target, @paths[0].range,
  382.         @paths[0].success_proc, @paths[0].failure_proc)
  383.       force_move_route(@paths[0].route) if @paths[0].found
  384.     end
  385.   end
  386.  
  387.   alias zer0_recalculate_paths_move move_type_custom
  388.   def move_type_custom
  389.     if $game_map.recalculate_paths
  390.       # Interrupt if not stopping
  391.       return if jumping? || moving?
  392.       # Loop until finally arriving at move command list
  393.       while @move_route_index < @move_route.list.size
  394.         # Get the move command at index
  395.         command = @move_route.list[@move_route_index]
  396.         # If command code is 0 (end of list)
  397.         if command.code == 0
  398.           # If [repeat action] option is ON
  399.           if @move_route.repeat
  400.             # Reset move route index to the top of the list
  401.             @move_route_index = 0
  402.           end
  403.           # If [repeat action] option is OFF
  404.           unless @move_route.repeat
  405.             # If move route is forced and not repeating
  406.             if @move_route_forcing and not @move_route.repeat
  407.               # The move route is no longer forced (moving ended)
  408.               @move_route_forcing = false
  409.               # Restore original move route
  410.               @move_route = @original_move_route
  411.               @move_route_index = @original_move_route_index
  412.               @original_move_route = nil
  413.               # If there was a path to follow and we reached goal
  414.               if @paths[0] != nil
  415.                 if self.x == @paths[0].goal.x &&
  416.                   y == @paths[0].goal.y && @paths[0].success_proc
  417.                   # Call success Proc if goal is reached and it is defined.
  418.                   @paths[0].success_proc.call
  419.                 end
  420.                 next_route
  421.               end
  422.             end
  423.             # Clear stop count
  424.             @stop_count = 0
  425.           end
  426.           return
  427.         end # if command.code == 0
  428.         # For move commands (from move down to jump)
  429.         if command.code <= 14
  430.           # Branch by command code
  431.           case command.code
  432.           when 1 then move_down                 # Move down
  433.           when 2 then move_left                 # Move left
  434.           when 3 then move_right                # Move right
  435.           when 4 then move_up                   # Move up
  436.           when 5 then move_lower_left           # Move lower left
  437.           when 6 then move_lower_right          # Move lower right
  438.           when 7 then move_upper_left           # Move upper left
  439.           when 8 then move_upper_right          # Move upper right
  440.           when 9 then move_random               # Move random
  441.           when 10 then move_toward_player       # Move toward player
  442.           when 11 then move_away_from_player    # Move away from player
  443.           when 12 then move_forward             # Step forward
  444.           when 13 then move_backward            # Step backward
  445.           when 14 then jump(command.parameters[0], command.parameters[1]) # Jump
  446.           end
  447.           # If movement failure occurs when "Ignore If Can't Move" is unchecked.
  448.           if !@move_route.skippable && !moving? && !jumping?
  449.             # If path is current and collision limit is not reached
  450.             if @paths[0] != nil &&
  451.               @paths[0].collisions < $game_map.collision_retry
  452.               # Setup path again to update starting location.
  453.               # original goal node is used because pathfinding changes
  454.               # the goal node to current node
  455.               goal, range = @paths[0].target, @paths[0].range
  456.               reach = @paths[0].success_proc
  457.               fail = @paths[0].failure_proc
  458.               counter = @paths[0].collisions + 1
  459.               # Find another path to goal
  460.               @paths[0] = Pathfind.new(goal, self, range, reach, fail)
  461.               @paths[0].collisions = counter
  462.               force_move_route(@paths[0].route) if @paths[0].found
  463.               # Wait a bit before starting to follow the new path
  464.               @wait_count = 6
  465.               return
  466.             else
  467.               # Call failure Proc if defined and set move index.
  468.               @move_route_index = @move_route.list.size
  469.               @paths[0].failure_proc.call if @paths[0].failure_proc != nil
  470.               next_route
  471.             end
  472.             # End method
  473.             return
  474.           end
  475.           # Advance index
  476.           @move_route_index += 1
  477.           return
  478.         end # if command.code <= 14
  479.         # If waiting
  480.         if command.code == 15
  481.           # Set wait count (from provided parameter)
  482.           @wait_count = command.parameters[0] * 2 - 1
  483.           @move_route_index += 1
  484.           return
  485.         end # if command.code == 15
  486.         # If direction change (turning) command
  487.         if command.code >= 16 and command.code <= 26
  488.           # Branch by command code
  489.           case command.code
  490.           when 16 then turn_down                      # Turn down
  491.           when 17 then turn_left                      # Turn left
  492.           when 18 then turn_right                     # Turn right
  493.           when 19 then turn_up                        # Turn up
  494.           when 20 then turn_right_90                  # Turn 90° right
  495.           when 21 then turn_left_90                   # Turn 90° left
  496.           when 22 then turn_180                       # Turn 180°
  497.           when 23 then turn_right_or_left_90          # Turn 90° right or left
  498.           when 24 then turn_random                    # Turn at Random
  499.           when 25 then turn_toward_player             # Turn toward player
  500.           when 26 then turn_away_from_player          # Turn away from player
  501.           end
  502.           @move_route_index += 1
  503.           return
  504.         end
  505.         # If other command (commands that don't 'return')
  506.         if command.code >= 27
  507.           # Branch by command code
  508.           case command.code
  509.           when 27                                              # Switch ON
  510.             $game_switches[command.parameters[0]] = true
  511.             $game_map.need_refresh = true
  512.           when 28                                              # Switch OFF
  513.             $game_switches[command.parameters[0]] = false
  514.             $game_map.need_refresh = true
  515.           when 29 then @move_speed = command.parameters[0]     # Change speed
  516.           when 30 then @move_frequency = command.parameters[0] # Change freq
  517.           when 31 then @walk_anime = true                      # Move ON
  518.           when 32 then @walk_anime = false                     # Move OFF
  519.           when 33 then @step_anime = true                      # Stop ON
  520.           when 34 then @step_anime = false                     # Stop OFF
  521.           when 35 then @direction_fix = true                   # Direction ON
  522.           when 36 then @direction_fix = false                  # Direction OFF
  523.           when 37 then @through = true                         # Through ON
  524.           when 38 then @through = false                        # Through OFF
  525.           when 39 then @always_on_top = true                   # On top ON
  526.           when 40 then @always_on_top = false                  # On top OFF
  527.           when 41                                              # Change Graphic
  528.             # Can't change into a tile
  529.             @tile_id = 0
  530.             @character_name = command.parameters[0]
  531.             @character_hue = command.parameters[1]
  532.             # Update direction
  533.             if @original_direction != command.parameters[2]
  534.               @direction = command.parameters[2]
  535.               @original_direction = @direction
  536.               @prelock_direction = 0
  537.             end
  538.             # Update frame
  539.             if @original_pattern != command.parameters[3]
  540.               @pattern = command.parameters[3]
  541.               @original_pattern = @pattern
  542.             end
  543.           when 42 then @opacity = command.parameters[0]        # Change Opacity
  544.           when 43 then @blend_type = command.parameters[0]     # Change Blending
  545.           when 44 then $game_system.se_play(command.parameters[0]) # Play SE
  546.           when 45 then result = eval(command.parameters[0])    # Script
  547.           end
  548.           # Increment move index.
  549.           @move_route_index += 1
  550.         end
  551.       end
  552.     else
  553.       # Original method
  554.       zer0_recalculate_paths_move
  555.     end
  556.   end
  557. end
  558.  
  559. #==============================================================================
  560. # ** Node
  561. #==============================================================================
  562.  
  563. class Node
  564.  
  565.   attr_accessor :x                      
  566.   attr_accessor :y                      
  567.   attr_accessor :parent                  
  568.   attr_accessor :cost                
  569.   attr_accessor :heuristic                  
  570.  
  571.   def initialize(x, y, parent = nil, cost = 0, heuristic = 0)
  572.     # Set public instance variables.
  573.     @x, @y, @parent, @cost, @heuristic = x, y, parent, cost, heuristic
  574.   end
  575.  
  576.   def score
  577.     # Return the current "score" of this node
  578.     return @cost + @heuristic
  579.   end
  580.  
  581.   def in_range?(node, range)
  582.     # Return true/false if Nodes are within RANGE of each other.
  583.     return (@x - node.x).abs + (@y - node.y).abs <= range
  584.   end
  585.  
  586.   def ==(node)
  587.     # Returns true/false of whether self and other are equal.
  588.     return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
  589.   end
  590. end
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top