#=============================================================================== # JPS Pathfinding v 1.3 # By ChrisClark13 # Based off of the Pathfinding script by Jet10985 & Venima #=============================================================================== # This script allows Events and the Player to use JPS Pathfinding (an extra # fast optimization of regular A* Pathfinding) to avoid obstacles while going # to a speficied point on the map (or within a certain distance if the dist # parameter is used). # # Features: # • Uses speedy JPS Pathfinding, which is faster than A* by several times # in most cases. # • Only recalculates path when it absoultely has to based on if the path is # blocked or not (configurable how far down the path it checks). # • The find_path command can be seamlessly inserted into MoveRoutes and Event # pages. # • Includes a command (setup_patrol_routes) that will set up a basic partol # route given a list of coordinates. # • Can be set up to call bits of code (see Proc objects in the Standard # Library/callbacks) when the path either succeeds or fails. Also when a step # is taken along the path or when the path gets blocked. # * Has an option instead path to the closest spot possible #=============================================================================== # Changelog # v1.0: * Released # v1.3: * Added in convience method for creating a move route with find_path # in it. # * Made advanced options (Procs) harder to access to reduce the long # method signatures and since only advanced users (ones who know how to # script) should be using them anyways. # * Added in Procs that are called whenever a step is taken along the # path and whenever the path gets blocked. # * Made it so additional args are passed to the procs. # * Fixed some weirdness in that if a path was blocked and a new path was # found immediately, it would go along that new path instantly. Now it # acts like the normal move route in that it waits until next time to # move. # * !!! Reordered arguments since I kept tripping over them in my own # projects # * Added in method to test whether or not a character is currently # following a path. # * Added in a functionality to instead go to the closest spot possible # if dist is negative. # * Bugfix: Made lookahead_dist actually work properly. #=============================================================================== # Overwritten Methods: # None #------------------------------------------------------------------------------- # Aliased methods: # class Game_Character # init_public_members # init_private_members #=============================================================================== =begin #=============================================================================== # Basic Options #=============================================================================== To move a player or event, use this in an event "Script..." command or inside of a Move Route (the Event page version has extra parameters): Move Route version: find_path(x, y, dist = 0, lookahead_dist = 1, recalc_if_blocked = true) x: the target x y: the targey y All off these parameters are optional and have default values according to what's above. dist: how close the character needs to get to the target. A value that's 0 will make them straight to the spot. A value that's less than 0 will make them instead get as close as possible. lookahead_dist: How far the character will check ahead each step to see if the path is blocked. A value of -1 will make them check the entire path, other values less then 1 will be set to 1. recalc_if_blocked: Whether or not the path will fail outright if the path gets blocked. If it's set to true the character will wait RECALC_WAIT frames and try to find a new path up to MAX_RECALC times. Note: If used with in a Move Route that has Skippable set, it'll skip the path if it gets blocked at any point (making setting recalc_if_blocked useless). Though it'll still call the failure callback. Event Page version: find_path(x, y, dist = 0, ev = 0, wait = true, lookahead_dist = 1, recalc_if_blocked = true) Only has a couple more parameters, otherwise is the same as the Move Route version. ev: Id of the character to be moved. By default it's called on the calling event. Use -1 for the player and anything above 0 for a speficic event on the map wait: whether or not the Event page's processing will stop while the character is in motion. Works like the Wait setting on with the Set Move Route command. Optional parameters can be defined as far as you like, though if a parameter is after some others you don't want, you'll have to set those other ones too. (Just how Ruby works.) Testing if a character is currently following a path: You can use following_path? to test whether or not a character is following a path like so in a conditional branch. get_character(0).following_path? #=============================================================================== # Patrol routes #=============================================================================== To setup a simple patrol route use this in a script call in a Move Route: setup_patrol_route(*coords) coords: a list of numbers that are the x and y positions of the patrol points like so: x0, y0, x1, y1, x2, y2, x3, y4... and so on. When the character fails to get to a speficic patrol point, they will start going between the points in reverse order. (Also, when they reach a point the list is shuffled so the point they just reached is at the bottom of the list) #=============================================================================== # Advanced options: #=============================================================================== There are some callbacks that are called at certain points in the code for those of you who are more programmatically minded. They are all set on a per Game_Character basis via script call like so: $game_player.proc_success = Proc.new {|path| puts "Path success!!" } event = get_character(0) event.proc_blocked = Proc.new {|path, block_x, block_y| #Get mad! event.balloon_id = 5 } proc_success(path) Called when the character reaches the target for the first time and will not be called again until a new path is set. The path argument is the JPS_Path that the character is currently using to path find. proc_failure(path) Called whenever the path fails, either because the path got blocked and recalc_if_blocked is set to false or because the recalucation limit was reached. (See below) The path argument is the JPS_Path that the character is currently using to path find. proc_step(path, old_x, old_y) Called whenever the character takes a step along the path. Path is the JPS_Path, old_x and old_y arguments are where the character was previously. proc_blocked(path, block_x, block_y) Called whenever it's discovered the path is blocked when looking ahead. Path is the JPS_Path, block_x and block_y is where the blockage is. As for the JPS_Path passed in the procs, you can access it's info or do whatever to it, though try not to break the path. The current goal can be acessed with path.goal.x and path.goal.y (and the adjusted goal can be accessed with path.adjusted_goal). If you need to get a move route with find_path in it use: character.create_path_route(x, y, dist = 0, lookahead_dist = 1, recalc_if_blocked = true) It returns a MoveRoute with a find_path command at the top. =end module CC13 module JPS # Max times a pathfinding attempt can iterate, unlikely to # ever be met due to how JPS works. MAX_ITERATIONS = 1000 #Max times a character can attempt to recalculate a path MAX_RECALCS= 10 #Time in frames that a character will wait before making another #recalcuation attempt (or moving at all really). RECALC_WAIT = 60 #Maximum distance for a position that can be considered when looking #for a position that is the closest to the goal. #Likely to be what can truly effect your lag if it's set really high. MAX_CLOSEST_DISTANCE = 10 #==============================================================================# #==============================================================================# #==# • Please don't touch anything beyond this point unless you know what #==# #==# you're doing!! #==# #==============================================================================# #==============================================================================# #Don't touch! Lookup table used in the code REL_DIR_HASH = { [-1, 1] => [ 4, 2], [ 0, 1] => [ 0, 2], [ 1, 1] => [ 6, 2], [ 1, 0] => [ 6, 0], [ 1,-1] => [ 6, 8], [ 0,-1] => [ 0, 8], [-1,-1] => [ 4, 8], [-1, 0] => [ 4, 0] } #Don't touch! Lookup table used in the code DIR_HASH = { 1 => [4,2], 2 => [0,2], 3 => [6,2], 6 => [6,0], 9 => [6,8], 8 => [0,8], 7 => [4,8], 4 => [4,0] } #Don't touch! Lookup table used in the code CMD_HASH = { [ 0, 1] => [1], [-1, 0] => [2], [ 1, 0] => [3], [ 0, -1] => [4], [-1, 1] => [2, 1], [ 1, 1] => [3, 1], [-1,-1] => [2, 4], [ 1,-1] => [3, 4] } end end class Node include Comparable attr_accessor :x, :y, :parent, :cost, :cost_estimated def initialize(x, y) @x, @y = x, y @cost = 0 @cost_estimated = 0 @on_path = false @parent = nil end def total_cost cost + cost_estimated end def <=>(other) total_cost <=> other.total_cost end def ==(other) return false unless Node === other @x == other.x && @y == other.y end def distance_pos(x, y) return (@x - x).abs + (@y - y).abs end def distance(other) return (@x - other.x).abs + (@y - other.y).abs end end class JPS_Path attr_reader :list attr_reader :goal attr_reader :adjusted_goal attr_reader :dist def initialize(char) @char = char @goal = nil @dist = nil @list = [] @map = $game_map end def find_successors(node) x = node.x y = node.y gx = goal.x gy = goal.y find_neighbors(node).each {|neighbor| nx = neighbor[0] ny = neighbor[1] jump_point = jump_point_search(nx, ny, x, y) if (jump_point) jump_node = Node.new(jump_point[0], jump_point[1]) next if @closed_set.include?(jump_node) cost = node.cost + node.distance(jump_node) index = @open_set.find_index(jump_node) # If we already have a node for this point, # we kind of don't need this new one we just made if (index != nil && cost < @open_set[index].cost) @open_set[index].parent = node @open_set[index].cost = cost else jump_node.cost = node.cost + node.distance(jump_node) jump_node.cost_estimated = @goal.distance(jump_node) jump_node.parent = node @open_set << jump_node end end } end def jump_point_search(x, y, px, py) dx = x <=> px dy = y <=> py diag = dx != 0 && dy != 0 horz = CC13::JPS::REL_DIR_HASH[[dx, dy]][0] vert = CC13::JPS::REL_DIR_HASH[[dx, dy]][1] #Short circuit if unpassable if (diag) return nil if !@char.diagonal_passable2?(px, py, horz, vert) elsif (!diag) return nil if !@char.passable?(px, py, (horz != 0) ? horz : vert) end #Return if we're at the goal! (Or close enough to it) if (x == @adjusted_goal.x && y == @adjusted_goal.y) || (@dist > 0 && @goal.distance_pos(x, y) <= @dist) return [x, y] end #Forced neighbors check return [x, y] unless get_forced_neighbors(x, y, dx, dy).empty? new_x = @map.round_x_with_direction(x, horz) new_y = @map.round_y_with_direction(y, vert) #Diagonal horz/vert jump check if (diag) jhorz = jump_point_search(new_x, y, x, y) jvert = jump_point_search(x, new_y, x, y) if (jhorz || jvert) return [x, y] end end #Continue jumping check if (diag && @char.diagonal_passable2?(x, y, horz, vert)) return jump_point_search(new_x, new_y, x, y) elsif (!diag && @char.passable?(x, y, (horz != 0) ? horz : vert)) return jump_point_search(new_x, new_y, x, y) end return nil end def find_neighbors(node) x = node.x y = node.y positions = [] dx = 0 dy = 0 #If the node has a parent, get forced and natural neighbors if (node.parent) dx = x <=> node.parent.x dy = y <=> node.parent.y positions.concat(get_natural_neighbors(x, y, dx, dy)) positions.concat(get_forced_neighbors(x, y, dx, dy)) return positions end #if not, just get all the neighbors 9.times {|i| i += 1 next if i == 5 horz = CC13::JPS::DIR_HASH[i][0] vert = CC13::JPS::DIR_HASH[i][1] new_x = @map.round_x_with_direction(x, horz) new_y = @map.round_y_with_direction(y, vert) if (i % 2 == 0) next unless @char.passable?(x, y, (horz != 0) ? horz : vert) else next unless @char.diagonal_passable2?(x, y, horz, vert) end positions << [new_x, new_y] } return positions end def get_natural_neighbors(x, y, dx, dy) horz = CC13::JPS::REL_DIR_HASH[[dx, dy]][0] vert = CC13::JPS::REL_DIR_HASH[[dx, dy]][1] if (dx != 0 && dy != 0) positions = [] horz_pos = nil vert_pos = nil if (@char.passable?(x, y, horz)) horz_pos = [@map.round_x_with_direction(x, horz), y] positions << horz_pos end if (@char.passable?(x, y, vert)) vert_pos = [x, @map.round_y_with_direction(y, vert)] positions << vert_pos end if (@char.diagonal_passable2?(x, y, horz, vert)) positions << [horz_pos[0], vert_pos[1]] end return positions elsif (dx != 0 && @char.passable?(x, y, horz)) return [[@map.round_x_with_direction(x, horz), y]] elsif (dy != 0 && @char.passable?(x, y, vert)) return [[x, @map.round_y_with_direction(y, vert)]] end return [] end def get_forced_neighbors(x, y, dx, dy) #Short circuit, diagonals have no forced neighbors since those cases are #covered by the straight directions return [] if (dx != 0 && dy != 0) positions = [] if (dx != 0) horz = CC13::JPS::REL_DIR_HASH[[dx, dy]][0] new_x = @map.round_x_with_direction(x, horz) rev_horz = @char.reverse_dir(horz) #Check to the North north_y = @map.round_y_with_direction(y, 8) if (!@char.passable?(x, north_y, rev_horz) && @char.passable?(x, y, 8)) positions << [x, north_y] if (@char.diagonal_passable2?(x, y, horz, 8)) positions << [new_x, north_y] end end #Check to the South south_y = @map.round_y_with_direction(y, 2) if (!@char.passable?(x, south_y, rev_horz) && @char.passable?(x, y, 2)) positions << [x, south_y] if (@char.diagonal_passable2?(x, y, horz, 2)) positions << [new_x, south_y] end end elsif (dy != 0) vert = CC13::JPS::REL_DIR_HASH[[dx, dy]][1] new_y = @map.round_y_with_direction(y, vert) rev_vert = @char.reverse_dir(vert) #Check to the East east_x = @map.round_x_with_direction(x, 6) if (!@char.passable?(east_x, y, rev_vert) && @char.passable?(x, y, 6)) positions << [east_x, y] if (@char.diagonal_passable2?(x, y, 6, vert)) positions << [east_x, new_y] end end #Check to the West west_x = @map.round_x_with_direction(x, 4) if (!@char.passable?(west_x, y, rev_vert) && @char.passable?(x, y, 4)) positions << [west_x, y] if (@char.diagonal_passable2?(x, y, 4, vert)) positions << [west_x, new_y] end end end return positions end def find_closest_possible_to_goal(dist) #"dist" will either be: positive or negative. open = [Node.new(@goal.x, @goal.y)] closed = [] #We're just looking for passability here, so a full blown JPS search isn't #really feasible. So just use a mini A* search. loop do #Pop closest node current = open.min return nil if !current || (dist > 0 && current.distance(@goal) > dist.abs) || current.distance(@goal) > CC13::JPS::MAX_CLOSEST_DISTANCE closed << open.delete(current) #Goal check return current if !@char.collide_with_characters?(current.x, current.y) && [2, 4, 6, 8].any? {|i| @char.passable?(current.x, current.y, i)} #Moar nodes! [2, 4, 6, 8].shuffle!.each do |i| x2 = $game_map.round_x_with_direction(current.x, i) y2 = $game_map.round_y_with_direction(current.y, i) node = Node.new(x2, y2) if !open.include?(node) && !closed.include?(node) node.cost = @goal.distance(node) open << node end end end end def calculate(goal_x, goal_y, dist) @start = Node.new(@char.x, @char.y) @goal = Node.new(goal_x, goal_y) @adjusted_goal = @goal @dist = [dist, 0].max @list.clear #Short circuit checks return true if @dist > 0 && @start.distance(@goal) <= @dist return false if ![2, 4, 6, 8].any? {|i| @char.passable?(@start.x, @start.y, i) } if @char.collide_with_characters?(@goal.x, @goal.y) || ![2, 4, 6, 8].any? {|i| @char.passable?(@goal.x, @goal.y, i)} return false if dist == 0 @adjusted_goal = find_closest_possible_to_goal(dist) return false if !@adjusted_goal end return true if @start == @adjusted_goal #This check is last since the goal may change. @open_set = [@start] @closed_set = [] iterations = 0 loop do return false if iterations >= CC13::JPS::MAX_ITERATIONS iterations += 1 #Pop node with the least score in a roundabout fashion current = @open_set.min return false unless current @closed_set << @open_set.delete(current) #Goal check if current == @adjusted_goal || (@dist > 0 && current.distance(@adjusted_goal) <= @dist) backtrace_path(current) return true end #More nodes for the node god! Um... get more nodes in our list find_successors(current) end return false end def backtrace_path(node) #~ ROUTE_MOVE_DOWN = 1 # Move Down #~ ROUTE_MOVE_LEFT = 2 # Move Left #~ ROUTE_MOVE_RIGHT = 3 # Move Right #~ ROUTE_MOVE_UP = 4 # Move Up #~ ROUTE_MOVE_LOWER_L = 5 # Move Lower Left #~ ROUTE_MOVE_LOWER_R = 6 # Move Lower Right #~ ROUTE_MOVE_UPPER_L = 7 # Move Upper Left #~ ROUTE_MOVE_UPPER_R = 8 # Move Upper Right debug_hash = {[1] => "down", [2] => "left", [3] => "right", [4] => "up", [ 2, 1] => "down & left", [ 3, 1] => "down & right", [ 2, 4] => "up & left", [ 3, 4] => "up & right"} until node.nil? pos = node node = node.parent next if node.nil? relative_pos = [pos.x <=> node.x, pos.y <=> node.y] cmds = CC13::JPS::CMD_HASH[relative_pos] cmd_count = [(pos.x - node.x).abs, (pos.y - node.y).abs].max cmd_count.times do cmds.each{|cmd| @list.unshift(RPG::MoveCommand.new(cmd))} end end end end class Game_Character attr_accessor :proc_success attr_accessor :proc_failure attr_accessor :proc_step attr_accessor :proc_blocked alias :jps_init_public_members :init_public_members def init_public_members jps_init_public_members @proc_success = Proc.new {|path|} @proc_failure = Proc.new {|path|} @proc_step = Proc.new {|path, old_x, old_y|} @proc_blocked = Proc.new {|path, block_x, block_y|} end alias :jps_init_private_members :init_private_members def init_private_members jps_init_private_members @recalcs = 0 @last_path_x = 0 @last_path_y = 0 @path = nil @path_ended = true end def find_path(x, y, dist = 0, lookahead_dist = 1, recalc_if_blocked = true) #Return if the goal's not even on the map #This is bad and you should feel bad return if !$game_map.valid?(x, y) #Goal Check gx, gy = x, y if @path && @path.adjusted_goal && !@path_ended gx = @path.adjusted_goal.x gy = @path.adjusted_goal.y end if @x == gx && @y == gy || (dist > 0 && ((@x - x).abs + (@y - y).abs) <= dist) @recalcs = 0 @path.list.clear if @path proc_success.call() unless @path_ended @path_ended = true return end # If there's not a path made at all OR the goal's changed # OR we got off it somehow THEN restart the path if !@path || @path.goal.x != x || @path.goal.y != y || @path.dist != [dist, 0].max || @last_path_x != @x || @last_path_y != @y @path = JPS_Path.new(self) unless @path @recalcs = 0 @path_ended = false @last_path_x, @last_path_y = @x, @y #Failure condition when starting a new path is slightly different #If we fail to calcuate a path if !@path.calculate(x, y, dist) @move_succeed = false #If we're allowed to recalc, then queue up a recalcuation if recalc_if_blocked && !@move_route.skippable @wait_count = CC13::JPS::RECALC_WAIT else #Otherwise just call proc_failure proc_failure.call(@path) unless @path_ended @path_ended = true end #Return in either case. return end # Check if we need to recalcuate the path, # either because of a failed recalc before or if we get blocked. elsif @path.list.empty? || !path_lookahead(lookahead_dist) @move_succeed = false #If we're allowed to recalc if recalc_if_blocked && @recalcs < CC13::JPS::MAX_RECALCS && !@move_route.skippable #Then try to recalc if !@path.calculate(x, y, dist) #If it fails, return; Otherwise we go to the follow part of the code @wait_count = CC13::JPS::RECALC_WAIT @recalcs += 1 end return else #If we're not allowed to recalc then call proc_failure and return proc_failure.call(@path) unless @path_ended @path_ended = true return end end return if @path.list.empty? #Path following code #We already checked if we're okay to move so just do so. process_move_command(@path.list.shift) @proc_step.call(@path, @last_path_x, @last_path_y) #Update last path x and y so we can check if #we got off track next time around @last_path_x, @last_path_y = @x, @y #Move the move_route_index back one #If the checks failed eailer it'll either be set back #one anyway or skipped based on path setting. @move_route_index -= 1 end def path_lookahead(lookahead_dist) lookahead_dist = @path.list.length if lookahead_dist == -1 lookahead_dist = [lookahead_dist, @path.list.length, 1].sort[1] x, y = @x, @y lookahead_dist.times do |i| dirs = CC13::JPS::DIR_HASH[@path.list[i].code * 2] if !passable?(x, y, dirs[0] != 0 ? dirs[0] : dirs[1]) block_x = $game_map.round_x_with_direction(x, dirs[0]) block_y = $game_map.round_y_with_direction(y, dirs[1]) @proc_blocked.call(@path, block_x, block_y) return false end x = $game_map.round_x_with_direction(x, dirs[0]) y = $game_map.round_y_with_direction(y, dirs[1]) end return true end def setup_patrol_route(*coords) msgbox("Wrong number of args for setup_patrol_route!") if (coords.length % 2) != 0 @proc_success = Proc.new { cmd = @move_route.list.pop #Pop off the move route end command #Move the just completed path to the end of the list (advance the list) @move_route.list.push(@move_route.list.shift) @move_route.list.push(cmd) #Push the move route end command back on @move_route_index -= 1 } @proc_failure = Proc.new { cmd = @move_route.list.pop #Pop off the move route end command @move_route.list.reverse! #Reverse the list @move_route.list.push(cmd) #Push the move route end command back on @move_route_index -= 1 } cmd_list = [] (coords.length / 2).times do |i| #Make move commands and put them in the list code_string = "find_path(#{coords[i * 2]}, #{coords[i *2 +1]})" cmd_list.push(RPG::MoveCommand.new(45, [code_string])) end #Push the move route end command back on there. cmd_list.push(RPG::MoveCommand.new) @move_route.list = cmd_list @move_route_index = -1 end def create_path_route(x, y, dist = 0, lookahead_dist = 1, recalc_if_blocked = true) route = RPG::MoveRoute.new cmd_string = "find_path(#{x}, #{y}, #{dist}, #{lookahead_dist}, #{recalc_if_blocked})" route.list = [RPG::MoveCommand.new(45, [cmd_string]), RPG::MoveCommand.new] return route end def following_path? return !@path_ended end end class Game_CharacterBase def diagonal_passable2?(x, y, horz, vert) x2 = $game_map.round_x_with_direction(x, horz) y2 = $game_map.round_y_with_direction(y, vert) (passable?(x, y, vert) && passable?(x, y2, horz)) && (passable?(x, y, horz) && passable?(x2, y, vert)) end end class Game_Interpreter # Called from script command in event page, different from move route def find_path(x, y, dist = 0, ev = 0, wait = true, lookahead_dist = 1, recalc_if_blocked = true) $game_map.refresh if $game_map.need_refresh #Get the character char = get_character(ev) return unless char route = char.create_path_route(x, y, dist, lookahead_dist, recalc_if_blocked) route.repeat = false route.wait = wait char.force_move_route(route) Fiber.yield while char.move_route_forcing if wait end end