Module: Pathfinding

Defined in:
scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb,
scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00705 Pathfinding_cursor.rb,
scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00710 Pathfinding_targets.rb

Overview

Pathfinding (PSDK) by Leikt Module that handle the automatic pathfinding system. Djikstra Algorithm and optimized to be performance friendly. If you are experimenting performance issue while the algorithm is running, down the NODE_PER_FRAME value. You can customize the cost of each tag in TAGS_WEIGHT.

Defined Under Namespace

Modules: TagsWeight, Target Classes: Cursor, Request

Constant Summary collapse

OPERATION_PER_FRAME =

Amount of node to calculate in one frame (OPTIMISATION)

150
OPERATION_PER_REQUEST =

Amount of node by requests in one frame (OPTIMISATION)

50
COST_RELOAD =

Cost of the reload

15
COST_WATCH =

Cost of the watch

9
COST_WAIT =

Cost of the wait

1
OBSTACLE_DETECTION_RANGE =

Obstacle detection range

9
TRY_COUNT =

Amount of try count

5
TRY_DELAY =

Number of frame before two path search when the first one fail

60
PATH_DIRS =

Directions to check

[1, 2, 3, 4]
WAITING_ROUTE =

Move route when waiting for a new path

RPG::MoveRoute.new
TAGS_WEIGHT =

Weight of the tags, the higher is the cost, the more the path will avoid it

{
  GameData::SystemTags::Road => 2,          # Tag of the main road
  GameData::SystemTags::TSand => 4,         # Tag of the road
  GameData::SystemTags::SwampBorder => 20,  # Avoid swamp if possible
  GameData::SystemTags::DeepSwamp => 30,    # Avoid deep swamp whatever it takes
  GameData::SystemTags::MachBike => 1000,   # Prevent bug
  GameData::SystemTags::TGrass => 20
}
DEFAULT_SAVE =

Default save state

[]
PRESET_COMMANDS = 
Array.new(5) { |i| RPG::MoveCommand.new(i) }.method(:[])

Class Method Summary collapse

Class Method Details

.add_request(character, target, tries, tags) ⇒ Boolean

Add the request to the system list and start looking for path

Parameters:

  • character (Game_Character) —

    the character looking for a path

  • target (Game_Character, Array<Integer>) —

    character or coords to reach

  • tries (Integer) —

    the number of tries before giving up the path research. :infinity for infinite try count.

  • tags (Symbol) —

    the name of the Pathfinding::TagsWeight constant to use to calcultate the node weight

Returns:

  • (Boolean) —

    if the request is successfully submitted



75
76
77
78
79
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 75

def self.add_request(character, target, tries, tags)
  remove_request(character)
  @requests.push Request.new(character, Target.get(*target), tries, tags)
  return true
end

.clear

CLear all the requests



93
94
95
96
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 93

def self.clear
  debug_clear
  @requests.clone.each { |request| remove_request(request.character) }
end

.debug=(value) 



149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 149

def self.debug=(value)
  @debug = value
  if value && @debug_viewport.nil?
    @debug_viewport = Viewport.create(:main, 50_000)
    @debug_sprites = {}
    @debug_bitmap = RPG::Cache.animation('pathfinding_debug', 0)
    @debug_sprites_pool = []
  end
  if !value && @debug_viewport
    debug_clear
    @debug_sprites_pool.each(&:dispose)
    @debug_sprites_pool = []
    @debug_viewport.dispose
    @debug_viewport = nil
  end
end

.debug_add(from, cursor, path)

Add a path to display

Parameters:

  • from (Game_Character) —

    the character who follow the path

  • cursor (Cursor) —

    the cursor used to calculate the path

  • path (Array<Integer>) —

    the list of moveroute command



198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 198

def self.debug_add(from, cursor, path)
  return unless @debug

  # Initialisation
  debug_clear(from.id)
  sprites = []
  x = from.x
  y = from.y
  z = from.z
  # Run all the path and place markers
  path.each_with_index do |dir, index|
    code = [dir - 1, 0, 4, 3]
    code = [dir - 1, 1, 4, 3] if index == 0
    sprites.push s = (@debug_sprites_pool.pop ||
      Sprite.new(@debug_viewport).set_bitmap(@debug_bitmap))
      .set_rect_div(*code).set_position(x * 16 - 24, y * 16 - 16)
    s.visible = true

    cursor.sim_move?(x, y, z, dir)
    x = cursor.x
    y = cursor.y
    z = cursor.z
  end
  # Place en marker and store
  sprites.push s = (@debug_sprites_pool.pop ||
    Sprite.new(@debug_viewport).set_bitmap(@debug_bitmap))
    .set_rect_div(0, 2, 4, 3).set_position(x * 16 - 24, y * 16 - 16)
  s.visible = true
  @debug_sprites[from.id] = sprites
end

.debug_clear(from = nil)

Clear the pathfinding debug data

Parameters:

  • from (Integer, nil) (defaults to: nil) —

    the id of the caracter to clear, if nil, clear all



168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 168

def self.debug_clear(from = nil)
  return unless @debug

  if from.nil?
    @debug_sprites.values.flatten.each do |s|
      s.visible = false
      @debug_sprites_pool.push s
    end
    @debug_sprites.clear
  elsif @debug_sprites.key?(from)
    @debug_sprites[from].each do |s|
      s.visible = false
      @debug_sprites_pool.push s
    end
    @debug_sprites.delete(from)
  end
end

.debug_update

Update the pathfinding display debug



187
188
189
190
191
192
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 187

def self.debug_update
  return unless @debug

  @debug_viewport.ox = $game_map.display_x / 8 - 24
  @debug_viewport.oy = $game_map.display_y / 8 - 16
end

.load

Load the data from the Game State



140
141
142
143
144
145
146
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 140

def self.load
  return unless Game_Map::PATH_FINDING_ENABLED

  data = PFM.game_state.pathfinding_requests
  @requests = data.collect { |d| Request.load(d) }
  @requests.delete(nil) # Prevent loading error
end

.operation_per_frame=(value)

Set the number of operation per frame. By default it's 150, be careful with the performance issues.

Parameters:

  • value (Integer) —

    the new amount of operation allowed per frame



100
101
102
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 100

def self.operation_per_frame=(value)
  @operation_per_frame = value
end

.remove_request(character) ⇒ Boolean

Remove the request from the system list and return true if the request has been popped out.

Parameters:

Returns:

  • (Boolean) —

    if the request has been popped out



84
85
86
87
88
89
90
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 84

def self.remove_request(character)
  debug_clear(character.id)
  old_length = @requests.length
  @requests.delete_if { |e| e.character == character }
  @last_request_id = 0 # Reset the request id to prevent problems
  return (old_length > @requests.length)
end

.save ⇒ Array<Pathfinding::Request>

Create an savable array of the current requests

Returns:



135
136
137
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 135

def self.save
  PFM.game_state.pathfinding_requests = @requests.collect(&:save)
end

.update

Update the pathfinding system



105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 105

def self.update
  debug_update
  return if @requests.empty?

  # Initialize
  request_id = @last_request_id # Get the last updates where it's stop
  operation_counter = 0         # Count the amount of operation in this update
  first_update = true           # Indicate if the update is called in the first loop or not
  need_update = true            # When go false for a all loop => stop update
  # Loop while remains operation left and requests
  while operation_counter < @operation_per_frame
    # Update the request and calculate the new operation counter
    operation_counter += (current_request = @requests[request_id]).update(operation_counter, first_update)
    need_update ||= current_request.need_update # Need update to true if the request needs update
    current_request.character.stop_path if current_request.finished? # Delete the finished requests

    # When end of the requests list
    next unless (request_id += 1) >= @requests.length

    request_id = 0 # Go to the first request
    break if !need_update or @requests.empty? # Stop everything if update no longer needed

    first_update = false      # At this point it can't be the first update
    need_update = false       # No first update, reset the need_update to false, it will be turned to true if update is needed
  end
  @last_request_id = request_id # Save the last update position
end