[XP] Path Finder - Wersja do druku

Spoiler: (Otwórz)
Kod:

#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

# Lagless Path Finder by Blizzard

# Version: 1.0

# Type: Pathfinding System

# Date: 9.2.2013

#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

#   

#  This work is protected by the following license:

# #----------------------------------------------------------------------------

# #  

# #  Creative Commons - Attribution-NonCommercial-ShareAlike 3.0 Unported

# #  ( http://creativecommons.org/licenses/by-nc-sa/3.0/ )

# #  

# #  You are free:

# #  

# #  to Share - to copy, distribute and transmit the work

# #  to Remix - to adapt the work

# #  

# #  Under the following conditions:

# #  

# #  Attribution. You must attribute the work in the manner specified by the

# #  author or licensor (but not in any way that suggests that they endorse you

# #  or your use of the work).

# #  

# #  Noncommercial. You may not use this work for commercial purposes.

# #  

# #  Share alike. If you alter, transform, or build upon this work, you may

# #  distribute the resulting work only under the same or similar license to

# #  this one.

# #  

# #  - For any reuse or distribution, you must make clear to others the license

# #    terms of this work. The best way to do this is with a link to this web

# #    page.

# #  

# #  - Any of the above conditions can be waived if you get permission from the

# #    copyright holder.

# #  

# #  - Nothing in this license impairs or restricts the author's moral rights.

# #  

# #----------------------------------------------------------------------------

# 

#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

# 

# IMPORTANT NOTE:

# 

#   This Path Finder is a derived version of Blizz-ABS's original Path Finder.

#   If you are using Blizz-ABS, please remove this script. Blizz-ABS has a

#   Path Finder already built-in.

# 

# 

# Compatibility:

# 

#   99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause

#   incompatibility issues with exotic map systems.

# 

# 

# Features:

# 

#   - calculates path from point A to point B on the map

#   - allows immediate calculation as well as path calculation requests that

#     are done over the course of a few frames in order to reduce lag

#   - supports dynamic calculation that is done every step to ensure the

#     character reaches its targets

#   - can assign other characters as targets so dynamic calculation with a

#     moving will cause the character to find the target regardless of his

#     changed position

# 

# 

# Instructions:

#   

# - Explanation:

#   

#   This script will allow your characters to walk from point A to point B,

#   navigating by themselves, finding the shortest path and all that without

#   you having to manually specify their moving route. They can also navigate

#   through dynamically changing environments or track a dynamically moving

#   target.

# 

# - Configuration:

# 

#   MAX_NODES_PER_FRAME - maximum number of node calculation per frame when

#                         using path requests instead of immediate calculations

#   DIRECTIONS_8_WAY    - if set to true, it will smooth out corner movement

#                         and use a diagonal movement step wherever possible

#                         (this does NOT mean that the path finder will do

#                         8-directional path finding!)

# 

# - Script calls:

# 

#   This path finder offers you several script calls in order to designate path

#   finding to characters on the map. Following script calls are at your

#   disposal:

#   

#     PathFinder.find(C_ID, X, Y)

#     PathFinder.find(C_ID, X, Y, RANGE)

#     PathFinder.find(C_ID, TARGET)

#     PathFinder.find(C_ID, TARGET, RANGE)

#     PathFinder.request(C_ID, X, Y)

#     PathFinder.request(C_ID, X, Y, RANGE)

#     PathFinder.request(C_ID, TARGET)

#     PathFinder.request(C_ID, TARGET, RANGE)

#     PathFinder.dyn_find(C_ID, X, Y)

#     PathFinder.dyn_find(C_ID, X, Y, RANGE)

#     PathFinder.dyn_find(C_ID, TARGET)

#     PathFinder.dyn_find(C_ID, TARGET, RANGE)

#     PathFinder.dyn_request(C_ID, X, Y)

#     PathFinder.dyn_request(C_ID, X, Y, RANGE)

#     PathFinder.dyn_request(C_ID, TARGET)

#     PathFinder.dyn_request(C_ID, TARGET, RANGE)

# 

#   C_ID   - either an event ID, 0 for the player character or an actual

#            character (e.g. $game_map.events[ID])

#   X      - X target coordinate

#   Y      - Y target coordinate

#   RANGE  - range within which the target should be located (greater than 0)

#   TARGET - an actual target character

#   

#   This is how the 4 different script calls behave:

#   

#   - The "find" variants always calculate the path immediately.

#   - The "request" variants always request a path calculation to be done over

#     the course of several frames in order to avoid lag. Requesting paths for

#     multiple characters will cause the calculation to take longer as each

#     frame only a certain number of nodes is calculated (can be configured).

#     So if there are more characters requesting a path, naturally each one

#     will consume a part of the allowed node calculations every frame.

#   - The "dyn" variants (dynamic) will recalculate/request a calculation every

#     step in order to keep a path up to date with an ever-changing

#     environment. You won't need to use these calls if there are no moving

#     events on the map or if there are no environmental passability changes.

#   - When using a "dyn" variant, if actual coordinates (X, Y) are used, the

#     character will find its path to these fixed coordinates. If an actual

#     target character is being used, the path finder will track the character

#     instead of fixed coordinates. If the character changes its position, the

#     path calculation will attempt to find a path to the new position of the

#     target.

#   - Using "dyn_find" a lot, with many characters at the same time and/or for

#     long paths may cause performance issue and lag. Use it wisely.

#   - Using "dyn_request" is much more performance-friendly, but it will also

#     cause characters to "stop and think". This can also cause problems in a

#     constantly changing environment as the environment may change during the

#     few frames while the calculation is being done. Use it wisely.

#   

#   In order to cancel dynamic path calculation for a character, use following

#   script call:

#   

#     character.clear_path_target

#   

#   Example:

#     

#     $game_map.events[23].clear_path_target

#   

#   In order to check if a character has a dynamic path calculation for a

#   target, use following script call:

#   

#     character.has_path_target?

#   

#   Example:

#     

#     if $game_map.events[23].has_path_target?

#   

# 

# Notes:

# 

#   - This path finder is an implementation fo the A* Search Algorithm.

#   - The PathFinder module is being updated during the call of $game_system.update.

#     Keep this in mind if you are using specific exotic scripts.

# 

# 

# If you find any bugs, please report them here:

# http://forum.chaos-project.com

#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

# START Configuration

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

module BlizzCFG

  MAX_NODES_PER_FRAME = 100

  DIRECTIONS_8_WAY = false

end

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

# END Configuration

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

$lagless_path_finder = 1.0

#==============================================================================

# module PathFinder

#==============================================================================

module Math

  def self.hypot_squared(x, y)

    return (x * x + y * y)

  end

end

#==============================================================================

# module PathFinder

#==============================================================================

module PathFinder

  PATH_DIRS = [[0, 1, 2], [-1, 0, 4], [1, 0, 6], [0, -1, 8]]

  DIR_DOWN_LEFT = [2, 4]

  DIR_LEFT_DOWN = [4, 2]

  DIR_DOWN_RIGHT = [2, 6]

  DIR_RIGHT_DOWN = [6, 2]

  DIR_LEFT_UP = [4, 8]

  DIR_UP_LEFT = [8, 4]

  DIR_RIGHT_UP = [6, 8]

  DIR_UP_RIGHT = [8, 6]

  DIR_OFFSETS = [[0, 0], [-1, 1], [0, 1], [1, 1], [-1, 0], [0, 0], [1, 0],

                [-1, -1], [0, -1], [1, -1]]

  @requests = {}

  def self.clear

    @requests = {}

  end

  def self.find(char, x, y = nil, range = 0)

    char, x, y, range = self.check_args(char, x, y, range)

    self._find(char, x, y, range, false)

    return true

  end

  def self.dyn_find(char, x, y = nil, range = 0)

    tx, ty = x, y

    char, x, y, range = self.check_args(char, x, y, range)

    self._find(char, x, y, range, true)

    char.set_path_target(tx, ty, range, true)

    return true

  end

  def self.request(char, x, y = nil, range = 0)

    char, x, y, range = self.check_args(char, x, y, range)

    self._request(char, x, y, range, false)

    return true

  end

  def self.dyn_request(char, x, y = nil, range = 0)

    char, x, y, range = self.check_args(char, x, y, range)

    self._request(char, x, y, range, true)

    char.set_path_target(tx, ty, range, false)

    return true

  end

  def self.check_args(char, x, y, range)

    if x.is_a?(Game_Character)

      range = (y != nil ? y : 0)

      y = x.y

      x = x.x

    end

    range = 0 if range < 0

    if char.is_a?(Numeric)

      char = (char > 0 ? $game_map.events[char] : $game_player)

    end

    p "Warning! Character to move does not exist!" if $DEBUG && char == nil

    return [char, x, y, range]

  end

  def self._find(char, x, y, range, dynamic)

    @requests[char] = PathRequest.new(char.x, char.y, x, y, range, dynamic)

    result = nil

    result = self.calc_node(char) while result == nil

    @requests.delete(char)

    if $DEBUG && result == []

      p "Warning! Path Finder could not find path for character at (#{x},#{y})!"

    end

    char.set_found_path(result)

  end

  def self._request(char, x, y, range, dynamic)

    if @requests[char] == nil

      @requests[char] = PathRequest.new(char.x, char.y, x, y, range, dynamic)

    end

  end

  def self.update

    @requests = {} if @requests == nil

    characters = @requests.keys

    count = BlizzCFG::MAX_NODES_PER_FRAME

    while characters.size > 0 && count > 0

      char = characters.shift

      result = self.calc_node(char)

      result != nil ? char.set_found_path(result) : characters.push(char)

      count -= 1

    end

  end

  def self.calc_node(char)

    request = @requests[char]

    if request.open.size == 0

      @requests.delete(char)

      return []

    end

    found = false

    key = request.open.keys.min {|a, b|

        a[2] > b[2] ? 1 : (a[2] < b[2] ? -1 :

        (Math.hypot_squared(a[0] - request.tx, a[1] - request.ty) <=>

        Math.hypot_squared(b[0] - request.tx, b[1] - request.ty)))}

    request.closed[key[0], key[1]] = request.open[key]

    request.open.delete(key)

    kx, ky = 0, 0

    passable = false

    passable_checked = false

    PATH_DIRS.each {|dir|

        kx, ky = key[0] + dir[0], key[1] + dir[1]

        if request.range == 0 && kx == request.tx && ky == request.ty

          request.closed[kx, ky] = dir[2]

          found = true

          break

        end

        passable = false

        passable_checked = false

        if request.range > 0 &&

            (kx - request.tx).abs + (ky - request.ty).abs <= request.range

          passable = char.passable?(key[0], key[1], dir[2])

          passable_checked = true

          if passable

            request.closed[kx, ky] = dir[2]

            found = true

            break

          end

        end

        if request.closed[kx, ky] == 0

          passable = char.passable?(key[0], key[1], dir[2]) if !passable_checked

          if passable

            request.open[[kx, ky, key[2] + 1]] = dir[2]

          end

        end}

    return nil if !found

    result = request.backtrack(kx, ky)

    @requests.delete(char)

    return result

  end

end

#==============================================================================

# PathRequest

#==============================================================================

class PathRequest

  attr_reader :open

  attr_reader :closed

  attr_reader :sx

  attr_reader :sy

  attr_reader :tx

  attr_reader :ty

  attr_reader :range

  attr_reader :dynamic

  def initialize(ox, oy, tx, ty, range, dynamic = false)

    @sx, @sy, @tx, @ty, @range, @dynamic = ox, oy, tx, ty, range, dynamic

    @open = {[@sx, @sy, 0] => -1}

    @closed = Table.new($game_map.width, $game_map.height)

  end

  def backtrack(tx, ty)

    cx, cy, x, y, result = tx, ty, 0, 0, []

    loop do

      cx, cy = cx - x, cy - y

      break if cx == @sx && cy == @sy

      result.unshift(@closed[cx, cy])

      x, y = PathFinder::DIR_OFFSETS[@closed[cx, cy]]

    end

    return self.modify_8_way(result)

  end

  def modify_8_way(result)

    if BlizzCFG::DIRECTIONS_8_WAY

      result.each_index {|i|

          if result[i] != nil && result[i + 1] != nil

            case [result[i], result[i + 1]]

            when PathFinder::DIR_DOWN_LEFT, PathFinder::DIR_LEFT_DOWN

              result[i], result[i + 1] = 1, nil

            when PathFinder::DIR_DOWN_RIGHT, PathFinder::DIR_RIGHT_DOWN

              result[i], result[i + 1] = 3, nil

            when PathFinder::DIR_LEFT_UP, PathFinder::DIR_UP_LEFT

              result[i], result[i + 1] = 7, nil

            when PathFinder::DIR_RIGHT_UP, PathFinder::DIR_UP_RIGHT

              result[i], result[i + 1] = 9, nil

            end

          end}

      result.compact!

    end

    return result

  end

end

#==============================================================================

# Game_System

#==============================================================================

class Game_System

  alias update_lagless_path_finder_later update

  def update

    PathFinder.update

    update_lagless_path_finder_later

  end

end

#==============================================================================

# Game_Map

#==============================================================================

class Game_Map

  alias setup_lagless_path_finder_later setup

  def setup(map_id)

    PathFinder.clear

    setup_lagless_path_finder_later(map_id)

  end

end

#==============================================================================

# Game_Character

#==============================================================================

class Game_Character

  def set_path_target(x, y, range, immediate)

    @path_x, @path_y, @path_range, @path_immediate = x, y, range, immediate

  end

  def clear_path_target

    @path_x, @path_y, @path_range, @path_immediate = nil, nil, nil, nil

  end

  def has_path_target?

    return (@path_x != nil)

  end

  def set_found_path(path)

    return if path.size == 0

    route = RPG::MoveRoute.new

    route.repeat = false

    # each move command code equals direction / 2

    path.reverse.each {|dir| route.list.unshift(RPG::MoveCommand.new(dir / 2))}

    self.force_move_route(route)

  end

  alias update_move_lagless_path_finder_later update_move

  def update_move

    update_move_lagless_path_finder_later

    return if self.moving? || !self.has_path_target?

    x, y = @path_x, @path_y

    x, y = @path_x.x, @path_x.y if @path_x.is_a?(Game_Character)

    if @x == x && @y == y

      #p @x, x, @y, y

      #p @path_x

      self.clear_path_target

    elsif @path_immediate

      PathFinder.dyn_find(self, @path_x, @path_y, @path_range)

    else

      PathFinder.dyn_request(self, @path_x, @path_y, @path_range)

    end

  end

end