Class: Pathfinding::Request

Inherits:
Object show all
Defined in:
scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb

Overview

Class that describe a pathfinding request

A request has three caracteristics :
- Character : the character summonning the request
- Target : the target to reach
- Priority : The priority of the request between others

Algorithm steps 1st step : Initialization

Creation of the variables (#initialize)

2nde step: Search

Calculate NODES_PER_FRAME nodes per frame to optimize the process (#update_search)
Nodes are calculated in #calculate_node with A* algorithm
Once a path is found, or all possibilies are studied, the request start watching

3rd step : Watch

The Request look for obstacles on the path and restart the search (reload) if there is one

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(character, target, tries, tags) ⇒ Request

Create the request

Parameters:

  • character (Game_Character) —

    the character to give a path

  • target (Target) —

    the target data

  • tries (Integer, Symbol) —

    the amount of tries allowed before fail, use :infinity to have unlimited tries

  • tags (Symbol) —

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



258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 258

def initialize(character, target, tries, tags)
  log_debug "Character ##{character.id} request created."
  @character = character
  @target = target
  @state = :search
  @cursor = Cursor.new(character)
  @open = [[0, character.x, character.y, character.z, @cursor.state, -1]]
  @closed = Table32.new($game_map.width, $game_map.height, 7)
  @character.path = :pending # @character.force_move_route(WAITING_ROUTE)
  @remaining_tries = @original_remaining_tries = tries
  @need_update = true
  @tags = tags
  @tags_weight = (Pathfinding::TagsWeight.const_defined?(tags) ?
    Pathfinding::TagsWeight.const_get(tags) : Pathfinding::TagsWeight::DEFAULT)
  Pathfinding.debug_clear(character.id)
end

Instance Attribute Details

#character ⇒ Game_Character (readonly)

The character which needs a path

Returns:



248
249
250
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 248

def character
  @character
end

#need_update ⇒ Boolean (readonly)

Indicate if the request needs update or not

Returns:

  • (Boolean) 


251
252
253
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 251

def need_update
  @need_update
end

Class Method Details

.load(data)

(Class method) Load the requests from the given argument

Parameters:

  • data (Array<Object>) —

    the data generated by the save method



537
538
539
540
541
542
543
544
545
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 537

def self.load(data)
  character = $game_map.events[data[0]]
  target    = Target.load(data[1])
  tries     = data[2]
  tags      = data[3] || :DEFAULT
  return nil unless character && target && tries # Prevent loading error : when map change

  return Request.new(character, target, tries, tags)
end

Instance Method Details

#backtrace(tx, ty, tz) ⇒ Array<Integer>

Calculate the path from the given node

Parameters:

Returns:



512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 512

def backtrace(tx, ty, tz)
  x = tx
  y = ty
  z = tz
  closed = @closed
  path = []
  code = closed[x, y, z]
  until code == -1
    path.unshift code & 0xF # Direction
    x = (code >> 4) & 0x3FF
    y = (code >> 14) & 0x3FF
    z = (code >> 24) & 0xF
    code = closed[x, y, z]
  end
  return path
end

#calculate_node ⇒ Object

Calculate a node and return it if a path is found

Returns:



462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 462

def calculate_node
  # Check for empty list
  return :not_found if (open = @open).empty?

  # Initialize
  target = @target
  cursor = @cursor
  game_map = $game_map
  tags_weight = @tags_weight

  # Get next node
  node = open.shift

  # Closing the selected open node
  (closed = @closed)[node[1], node[2], node[3]] = node[5]

  # Open each side nodes
  PATH_DIRS.each do |direction|
    next unless cursor.sim_move?(node[1], node[2], node[3], direction, *node[4])

    # Check target
    if target.reached?(kx = cursor.x, ky = cursor.y, kz = cursor.z)
      closed[kx, ky, kz] = direction | node[1] << 4 | node[2] << 14 | node[3] << 24
      return backtrace(kx, ky, kz)
    end

    # Open the node and store the backtrace
    next unless closed[kx, ky, kz] == 0 && open.select { |a| a[1] == kx && a[2] == ky && a[3] == kz }.empty?

    # Cost calculation : start with last node cost
    # Add the weight of the tag
    # Retrieve the straight direction (we prefer straight lines)
    cost = node.first + tags_weight[game_map.system_tag(kx, ky)] - ((node[5] & 0xF) == direction ? 1 : 0)
    backtrace_move = direction | node[1] << 4 | node[2] << 14 | node[3] << 24
    # Sort and insert the new node
    unless open.empty?
      index = 0
      index += 1 while index < open.length and open[index].first < cost
      open.insert(index, [cost, kx, ky, kz, cursor.state, backtrace_move])
    else
      open[0] = [cost, kx, ky, kz, cursor.state, backtrace_move]
    end
  end
  # Target not found
  return nil
end

#finished? ⇒ Boolean

Indicate if the request is ended

Returns:

  • (Boolean) 


301
302
303
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 301

def finished?
  return @character.path.nil?
end

#process_result(result)

Process the result of the node calculation

Parameters:

  • result (Array<Integer>, nil, Symbol) —

    the result value



349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 349

def process_result(result)
  if result == :not_found
    # If result not found, it start waiting before retrying
    if @remaining_tries == :infinity || (@remaining_tries -= 1) > 0
      log_debug "Character ##{@character.id} fail to found path. Retrying..."
      @state = :wait
      @retry_countdown = TRY_DELAY
    else
      # If no more chances : the path finding end here
      log_debug "Character ##{@character.id} fail to found path"
      @character.stop_path
    end
  # A path is found : throw it to the character
  elsif result
    # Reset the try counter
    @remaining_tries = @original_remaining_tries
    # Start watching for obstacles
    @state = :watch
    send_path(result)
  end
end

#reload? ⇒ Boolean

Indicate if the request is to reload

Returns:

  • (Boolean) 


295
296
297
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 295

def reload?
  return @state == :reload
end

#save ⇒ Array<Object>

Gather the data ready to be saved

Returns:



531
532
533
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 531

def save
  return [@character.id, @target.save, @original_remaining_tries, @tags]
end

#searching? ⇒ Boolean

Indicate if the request is search for path

Returns:

  • (Boolean) 


277
278
279
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 277

def searching?
  return @state == :search
end

#send_path(path)

Make the character following the found path

Parameters:

  • path (Array<Integer>) —

    The path, list of move direction



428
429
430
431
432
433
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 428

def send_path(path)
  log_debug "Character ##{@character.id} found a path"
  Pathfinding.debug_add(@character, @cursor, path)
  @character.define_path((path << 0).collect(&PRESET_COMMANDS))
  # @character.force_move_route(Pathfinding.path_to_route(path))
end

#stucked? ⇒ Boolean

Detect if the character is stucked

Returns:

  • (Boolean) 


437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 437

def stucked?
  # Get the data
  route = @character.path
  return true unless route.is_a?(Array)

  route_index = @character.move_route_index
  x = @character.x
  y = @character.y
  z = @character.z
  b = @character.__bridge

  # Iterate commands to the last one, which is Lentgh - 2 (considering the empty command at end)
  route[route_index..[route.length - 2, route_index + OBSTACLE_DETECTION_RANGE - 1].min]&.each do |command|
    return true unless @cursor.sim_move?(x, y, z, command.code, b)

    x = @cursor.x
    y = @cursor.y
    z = @cursor.z
    b = @cursor.__bridge
  end
  return false
end

#update(operation_counter, is_first_update) ⇒ Integer

Update the requests and return the number of performed actions

Parameters:

  • operation_counter (Integer) —

    the amount of operation left

  • is_first_update (Boolean) —

    indicate if it's the first update of the frame

Returns:



309
310
311
312
313
314
315
316
317
318
319
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 309

def update(operation_counter, is_first_update)
  @need_update ||= is_first_update # Need update forced to true if it's the first update
  case @state
  when :search then return update_search(operation_counter)
  when :watch then return update_watch(is_first_update)
  when :reload then return update_reload(is_first_update)
  when :wait then return update_wait(is_first_update)
  else
    return 1
  end
end

#update_reload(is_first_update)

Reload the request



412
413
414
415
416
417
418
419
420
421
422
423
424
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 412

def update_reload(is_first_update)
  # Check first update
  return 1 unless is_first_update

  log_debug "Character ##{@character.id} reload request"
  @character.path = :pending # @character.force_move_route(WAITING_ROUTE)
  @open.clear
  @open.push [0, character.x, character.y, character.z, @cursor.state, -1]
  @closed.resize(0, 0, 0) # Clear the table
  @closed.resize($game_map.width, $game_map.height, 7)
  @state = :search
  return COST_RELOAD
end

#update_search(operation_counter) ⇒ Integer

Update the request search and return the new remaining node count

Parameters:

  • node_counter (Integer) —

    the amount of node per frame remaining

Returns:



324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 324

def update_search(operation_counter)
  # Check target already reached
  if @target.reached?(@character.x, @character.y, @character.z)
    @state = :watch
    return 1
  elsif @target.check_move(@character.x, @character.y)
    @state = :reload
    return 1
  end
  # Initialize
  nodes = 0
  nodes_max = operation_counter > OPERATION_PER_REQUEST ? OPERATION_PER_REQUEST : operation_counter
  result = nil
  # Main loop : calculate a certain amount of node to get a result
  while nodes < nodes_max && !result
    result = calculate_node
    nodes += 1
  end
  # Process the result
  process_result(result)
  return nodes + 1
end

#update_wait(is_first_update)

Update the request when waiting before retrying to find path



400
401
402
403
404
405
406
407
408
409
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 400

def update_wait(is_first_update)
  # Check first update
  return 1 unless is_first_update

  # Update the count_down
  @retry_countdown -= 1
  @state = :reload if @retry_countdown <= 0
  @need_update = false
  return COST_WAIT
end

#update_watch(is_first_update)

Update the request when looking for obstacles



372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 372

def update_watch(is_first_update)
  # Check first update
  return 1 unless is_first_update

  # Optimization : Detect stuckness and target mouvement only if the character is on one tile
  if @character.real_x % 128 + @character.real_y % 128 == 0
    # Check target movement
    if @target.check_move(@character.x, @character.y)
      log_debug "Character ##{@character.id}'s target has moved"
      @state = :reload
      return 1
    end
    # Check if the character is stucked
    if stucked?
      log_debug "Character ##{@character.id} is stucked"
      @state = :reload
    # Detect if the target is already reached (player passing next to the event, etc)
    elsif @target.reached?(@character.x, @character.y, @character.z)
      log_debug "Character ##{@character.id} reached the target"
      @character.stop_path
    end
  end
  # Return default cost of a watch update
  @need_update = false
  return COST_WATCH
end

#waiting? ⇒ Boolean

Indicate if the request is watching for obstacle

Returns:

  • (Boolean) 


283
284
285
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 283

def waiting?
  return @state == :wait
end

#watching? ⇒ Boolean

Inidicate if the request is waiting for new try

Returns:

  • (Boolean) 


289
290
291
 
# File 'scripts/01450 Systems/00003 Map Engine/00002 Logic/00650 RMXP/00700 Pathfinding.rb', line 289

def watching?
  return @state == :watch
end