Flashindo Academy
Selamat datang di Flashindo Academy, akademi pembuat Flash :wave:
Di sini Anda bisa berbagi proyek/karya Flash-mu dan lain-lain disini :)

Ayo langsung join :D dan akun langsung aktif lho.. :-


Akademi Pembuat Flash
 
HomeTata TertibFAQSearchMemberlistUsergroupsRegisterLog in

Share | 
 

 [RGSS/RGSS2] Listra Pathfinder Module

View previous topic View next topic Go down 
AuthorMessage
ListRA-92
The Headmaster
avatar

Posts : 93
Cash : 394
Appreciations : 0
Location : antara ada dan tiada~ :-
Jenjang Pendidikan : Kuliah
Join date : 2010-10-15
Status : ADT Listra Linier Berkait :hammer:

PostSubject: [RGSS/RGSS2] Listra Pathfinder Module   Sun Dec 12, 2010 11:36 am

Listra Pathfinder Module
Using A*/Dijkstra's Algorithm
For RPG Maker VX and RPG Maker XP


Sesuai keinginanku untuk men-translate script pathfinding-ku dalam bahasa GML dan AS (lihat di sini) ke dalam bahasa lain, ke dalam bahasa lain, inilah script pathfinding dalam RGSS dan RGSS2.
Namun, script RGSS/RGSS2 ini memodifikasi script Move Towards Player untuk pergerakan event yakni pada Autonomous Movement--Approach , memanfaatkan algoritma Dijkstra/A*, sehingga event dapat mencari jalur terpendek untuk mendekati Player.


Inilah codingan scriptku... :kabur:
Listra Pathfinder Module for RGSS (part 1)
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker XP
# Version 1.0
#==============================================================================
#
#                                    PART 1
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rpgmakerid.com
#  - http://prodig.forumotion.net
#  - http://vixep.forumsrpg.net
#==============================================================================

#==============================================================================
# ** PQueue
#------------------------------------------------------------------------------
#  This class, as derivation of Array, provides additional operations, such
#  as insert and remove element such that the array behaves like a priority
#  queue, and also search value in the array. This will be used on
#  pathfinding algorithms in MGraph class.
#==============================================================================

class PQueue < Array
  #--------------------------------------------------------------------------
  # * Add Element, the result array will be always ordered ascendingly
  #    ii : element to be added into the array
  #--------------------------------------------------------------------------
  def addEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.insert(iii,ii)
  end
  #--------------------------------------------------------------------------
  # * Remove Element
  #    ii : element to be removed from the array, the result remains if
  #          ii isn't found in the array
  #--------------------------------------------------------------------------
  def remEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.delete_at(iii)
  end
  #--------------------------------------------------------------------------
  # * Is Element Found?
  #    ii : element to be searched in the array (using binary search)
  #  Returns true if ii found in the array
  #--------------------------------------------------------------------------
  def found?(ii)
    i = 0
    j = self.length-1
    ff = false
    while (not ff) && i <= j
      mid = (i+j)/2
      if self[mid] == ii
        ff = true
      else
        if self[mid] < ii
          i = mid+1
        else
          j = mid-1
        end
      end
    end
    return ff
  end
end

#==============================================================================
# ** MGraph
#------------------------------------------------------------------------------
#  This class generates a passage graph of given 2-dimensional map and uses it
#  for pathfinding analysis with Dijkstra's algorithm and A*. Refer to
#  "$mgraph" for the instance of this class.
#==============================================================================

class MGraph
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :w, :h
  attr_accessor :neighbors
  attr_accessor :passage_table
  #--------------------------------------------------------------------------
  # * Map Graph Initialization
  #--------------------------------------------------------------------------
  def initialize(nh)
    @w = $game_map.width
    @h = $game_map.height
    @neighbors = nh
    # Passage table for each map nodes
    @passage_table = Table.new(@w,@h,nh)
    for i in 0..@w
      for j in 0..@h
        for k in 1..nh
          @passage_table[i,j,k-1] = $game_map.passable2?(i,j,k*2) ? 1 : 0
          if not neighborExist?(nodeOf(i,j),k)
            @passage_table[i,j,k-1] = 0
          end
        end
      end
    end
  end
  #--------------------------------------------------------------------------
  # * Node/Vertex Of
  #    x : x-position
  #    y : y-position
  #--------------------------------------------------------------------------
  def nodeOf(x,y)
    return y*@w+x+1
  end
  #--------------------------------------------------------------------------
  # * xNode, yNode
  #    idxNode : index of node
  #--------------------------------------------------------------------------
  def xNode(idxNode)
    return (idxNode-1)%@w
  end
  def yNode(idxNode)
    return (idxNode-1)/@w
  end
  #--------------------------------------------------------------------------
  # * Neighbor Of
  #    idxNode : index of node
  #    dir : down(1), left(2), right(3), or up(4)
  #  Returns index of adjacent node idxNode
  #--------------------------------------------------------------------------
  def neighborOf(idxNode,dir)
    case dir
      when 1
        return (idxNode+@w)
      when 2
        return (idxNode-1)
      when 3
        return (idxNode+1)
      when 4
        return (idxNode-@w)
    end
  end
  #--------------------------------------------------------------------------
  # * Is Neighbor Exist?
  #    idxNode : index of node
  #    dir : down(1), left(2), right(3), or up(4)
  #  Returns if adjacent node of idxNode exists
  #--------------------------------------------------------------------------
  def neighborExist?(idxNode,dir)
    case dir
      when 1
        return (yNode(idxNode)<@h-1)
      when 2
        return (xNode(idxNode)>0)
      when 3
        return (xNode(idxNode)<@w-1)
      when 4
        return (yNode(idxNode)>0)
    end
  end
  #--------------------------------------------------------------------------
  # * Reconstruct Path
  #    s : source node
  #    t : target node
  #    vertices_prev : map of navigated nodes
  #  Returns movement direction 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def reconstruct_path(s,t,vertices_prev)
    u=t
    while vertices_prev[u] != s && vertices_prev[u] != 0
      u = vertices_prev[u]
    end
    case u
      when s+@w
        return 1
      when s-1
        return 2
      when s+1
        return 3
      when s-@w
        return 4
    end
    return 0
  end
  #--------------------------------------------------------------------------
  # * Heuristic Distance
  #    u : node 1
  #    v : node 2
  #--------------------------------------------------------------------------
  def heuristic_dist(u,v)
    dx = xNode(v)-xNode(u)
    dy = yNode(v)-yNode(u)
    # Manhattan distance heuristic
    return (dx.abs+dy.abs)
  end
  #--------------------------------------------------------------------------
  # * Dijkstra's Algorithm
  #    x1, y1 : source coordinate
  #    x2, y2 : target coordinate
  #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def Dijkstra(x1, y1, x2, y2)
    # Initializations
    s = nodeOf(x1,y1)
    t = nodeOf(x2,y2)
    # Create open list q (as priority queue)
    q = PQueue.new(1,0)
    # Add s into open list q
    q.addEl(s)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    # Previous node in optimal path from source
    vertices_prev = Array.new(@w*@h+1,0)
    # Distance from source to source
    vertices_dist[s] = 0
    # The main loop
    while q.length > 1
      # Finds vertex u with least value of path distance
      d = vertices_dist[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if vertices_dist[q[ii]]<d
                  d = vertices_dist[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Remove u from open list q
      q.remEl(u)
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          alt = vertices_dist[u]+1
          if alt < vertices_dist[v]
            # Relax (u,v)
            q.addEl(v)
            vertices_dist[v]=alt
            vertices_prev[v]=u
          end
        end
      end
    end
    return 0
  end
  #--------------------------------------------------------------------------
  # * A* Algorithm
  #    x1, y1 : source coordinate
  #    x2, y2 : target coordinate
  #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def AStar(x1, y1, x2, y2)
    # Initializations
    s = nodeOf(x1,y1)
    t = nodeOf(x2,y2)
    # Create open list q (as priority queue)
    q = PQueue.new(1,0)
    # Add s into open list q
    q.addEl(s)
    # Create closed list q1, The list of nodes already evaluated.
    q1 = Array.new(@w*@h+1,false)
    # The map of navigated nodes.
    vertices_prev = Array.new(@w*@h+1,0)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    h_score = Array.new(@w*@h+1,0)
    f_score = Array.new(@w*@h+1,9999)
    # Distance from source to source
    vertices_dist[s] = 0
    h_score[s] = heuristic_dist(s,t)
    f_score[s] = h_score[s]
    # The main loop
    while q.length > 1
      # Finds vertex u with least value of f_score
      d = f_score[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if f_score[q[ii]]<d
                  d = f_score[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Move current node from open list to the closed list
      q.remEl(u)
      q1[u] = true
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          if !q1[v]
            tentative_g_score = vertices_dist[u]+1
            if !q.found?(v)
              q.addEl(v)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
            else
              tentative_is_better = false
            end
            if tentative_is_better
              if vertices_prev[v] != 0
                if f_score[u] < f_score[vertices_prev[v]]
                  vertices_prev[v] = u
                end
              else
                vertices_prev[v] = u
              end
              vertices_dist[v] = tentative_g_score
              h_score[v] = heuristic_dist(v,t)
              f_score[v] = vertices_dist[v]+h_score[v]
            end
          end
        end
      end
    end
    return 0
  end
end
Listra Pathfinder Module for RGSS2 (part 2)
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker XP
# Version 1.0
#==============================================================================
#
#                                    PART 2
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rpgmakerid.com
#  - http://prodig.forumotion.net
#  - http://vixep.forumsrpg.net
#==============================================================================

#==============================================================================
# ** Game_Map (part 2 - overriden)
#------------------------------------------------------------------------------
#  This class handles the map. It includes scrolling and passable determining
#  functions. Refer to "$game_map" for the instance of this class.
#  This part overrides setup to use MGraph initialization and adds passable2?
#  method to detect obstacles (excluding events).
#==============================================================================

class Game_Map
  #--------------------------------------------------------------------------
  # * Setup
  #    map_id : map ID
  #--------------------------------------------------------------------------
  def setup(map_id)
    # Put map ID in @map_id memory
    @map_id = map_id
    # Load map from file and set @map
    @map = load_data(sprintf("Data/Map%03d.rxdata", @map_id))
    # set tile set information in opening instance variables
    tileset = $data_tilesets[@map.tileset_id]
    @tileset_name = tileset.tileset_name
    @autotile_names = tileset.autotile_names
    @panorama_name = tileset.panorama_name
    @panorama_hue = tileset.panorama_hue
    @fog_name = tileset.fog_name
    @fog_hue = tileset.fog_hue
    @fog_opacity = tileset.fog_opacity
    @fog_blend_type = tileset.fog_blend_type
    @fog_zoom = tileset.fog_zoom
    @fog_sx = tileset.fog_sx
    @fog_sy = tileset.fog_sy
    @battleback_name = tileset.battleback_name
    @passages = tileset.passages
    @priorities = tileset.priorities
    @terrain_tags = tileset.terrain_tags
    # Initialize displayed coordinates
    @display_x = 0
    @display_y = 0
    # Clear refresh request flag
    @need_refresh = false
    # Set map event data
    @events = {}
    for i in @map.events.keys
      @events[i] = Game_Event.new(@map_id, @map.events[i])
    end
    # Set common event data
    @common_events = {}
    for i in 1...$data_common_events.size
      @common_events[i] = Game_CommonEvent.new(i)
    end
    # Initialize all fog information
    @fog_ox = 0
    @fog_oy = 0
    @fog_tone = Tone.new(0, 0, 0, 0)
    @fog_tone_target = Tone.new(0, 0, 0, 0)
    @fog_tone_duration = 0
    @fog_opacity_duration = 0
    @fog_opacity_target = 0
    # Initialize scroll information
    @scroll_direction = 2
    @scroll_rest = 0
    @scroll_speed = 4
    # Make MGraph
    $mgraph = MGraph.new(4)
  end
  #--------------------------------------------------------------------------
  # * Determine if Passable (ignoring events)
  #    x          : x-coordinate
  #    y          : y-coordinate
  #    d          : direction (0,2,4,6,8,10)
  #                  *  0,10 = determine if all directions are impassable
  #--------------------------------------------------------------------------
  def passable2?(x, y, d)
    # If coordinates given are outside of the map
    unless valid?(x, y)
      # impassable
      return false
    end
    # Change direction (0,2,4,6,8,10) to obstacle bit (0,1,2,4,8,0)
    bit = (1 << (d / 2 - 1)) & 0x0f
    # Loop searches in order from top of layer
    for i in [2, 1, 0]
      # Get tile ID
      tile_id = data[x, y, i]
      # Tile ID acquistion failure
      if tile_id == nil
        # impassable
        return false
      # If obstacle bit is set
      elsif @passages[tile_id] & bit != 0
        # impassable
        return false
      # If obstacle bit is set in all directions
      elsif @passages[tile_id] & 0x0f == 0x0f
        # impassable
        return false
      # If priorities other than that are 0
      elsif @priorities[tile_id] == 0
        # passable
        return true
      end
    end
    # passable
    return true
  end
end

#==============================================================================
# ** Game_Character (part 4 - overriden)
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#  This part overrides move_type_toward_player and move_toward_player method to
#  perform pathfinding with either Dijkstra's algorithm or A*.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Move Type : Approach (modified)
  #--------------------------------------------------------------------------
  def move_type_toward_player
    # Approach player
    move_toward_player
  end
  #--------------------------------------------------------------------------
  # * Move toward Player (modified)
  #--------------------------------------------------------------------------
  def move_toward_player
    # Get difference in player coordinates
    sx = @x - $game_player.x
    sy = @y - $game_player.y
    # If coordinates are equal
    if sx == 0 and sy == 0
      return
    end
    # Determines the movement towards player with pathfinding algorithm
    # Uncomment one of these statements to use either A* or Dijkstra's
    # algorithm.
    # Note that:
    #  - Dijkstra's algorithm is always accurate but lacks its performance.
    #    You should only use this algorithm for small maps.
    #  - A* algorithm is accurate but not as well as Dijkstra's algorithm.
    #    However, A* works much faster than Dijkstra's do. Recommended to
    #    use this, even for large maps.
    dir = $mgraph.AStar(@x,@y,$game_player.x,$game_player.y)
    #dir = $mgraph.Dijkstra(@x,@y,$game_player.x,$game_player.y)
    case dir
    when 1
      move_down
    when 2
      move_left
    when 3
      move_right
    when 4
      move_up
    else  # If no path is found
      # Get absolute value of difference
      abs_sx = sx.abs
      abs_sy = sy.abs
      # If horizontal and vertical distances are equal
      if abs_sx == abs_sy
        # Increase one of them randomly by 1
        rand(2) == 0 ? abs_sx += 1 : abs_sy += 1
      end
      # If horizontal distance is longer
      if abs_sx > abs_sy
        # Move towards player, prioritize left and right directions
        sx > 0 ? move_left : move_right
        if not moving? and sy != 0
          sy > 0 ? move_up : move_down
        end
      # If vertical distance is longer
      else
        # Move towards player, prioritize up and down directions
        sy > 0 ? move_up : move_down
        if not moving? and sx != 0
          sx > 0 ? move_left : move_right
        end
      end
    end
  end
end

Listra Pathfinder Module for RGSS2 (part 1)
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.0
#==============================================================================
#
#                                    PART 1
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rpgmakerid.com
#  - http://prodig.forumotion.net
#  - http://vixep.forumsrpg.net
#==============================================================================

#==============================================================================
# ** PQueue
#------------------------------------------------------------------------------
#  This class, as derivation of Array, provides additional operations, such
#  as insert and remove element such that the array behaves like a priority
#  queue, and also search value in the array. This will be used on
#  pathfinding algorithms in MGraph class.
#==============================================================================

class PQueue < Array
  #--------------------------------------------------------------------------
  # * Add Element, the result array will be always ordered ascendingly
  #    ii : element to be added into the array
  #--------------------------------------------------------------------------
  def addEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.insert(iii,ii)
  end
  #--------------------------------------------------------------------------
  # * Remove Element
  #    ii : element to be removed from the array, the result remains if
  #          ii isn't found in the array
  #--------------------------------------------------------------------------
  def remEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.delete_at(iii)
  end
  #--------------------------------------------------------------------------
  # * Is Element Found?
  #    ii : element to be searched in the array (using binary search)
  #  Returns true if ii found in the array
  #--------------------------------------------------------------------------
  def found?(ii)
    i = 0
    j = self.length-1
    ff = false
    while (not ff) && i <= j
      mid = (i+j)/2
      if self[mid] == ii
        ff = true
      else
        if self[mid] < ii
          i = mid+1
        else
          j = mid-1
        end
      end
    end
    return ff
  end
end

#==============================================================================
# ** MGraph
#------------------------------------------------------------------------------
#  This class generates a passage graph of given 2-dimensional map and uses it
#  for pathfinding analysis with Dijkstra's algorithm and A*. Refer to
#  "$mgraph" for the instance of this class.
#==============================================================================

class MGraph
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :w, :h
  attr_accessor :neighbors
  attr_accessor :passage_table
  #--------------------------------------------------------------------------
  # * Map Graph Initialization
  #--------------------------------------------------------------------------
  def initialize(nh)
    @w = $game_map.width
    @h = $game_map.height
    @neighbors = nh
    # Passage table for each map nodes
    @passage_table = Table.new(@w,@h,nh)
    for i in 0..@w
      for j in 0..@h
        for k in 1..nh
          @passage_table[i,j,k-1] = $game_map.passable2?(xNode(neighborOf(nodeOf(i,j),k)),yNode(neighborOf(nodeOf(i,j),k)),0x01) ? 1 : 0
          if not neighborExist?(nodeOf(i,j),k)
            @passage_table[i,j,k-1] = 0
          end
        end
      end
    end
  end
  #--------------------------------------------------------------------------
  # * Node/Vertex Of
  #    x : x-position
  #    y : y-position
  #--------------------------------------------------------------------------
  def nodeOf(x,y)
    return y*@w+x+1
  end
  #--------------------------------------------------------------------------
  # * xNode, yNode
  #    idxNode : index of node
  #--------------------------------------------------------------------------
  def xNode(idxNode)
    return (idxNode-1)%@w
  end
  def yNode(idxNode)
    return (idxNode-1)/@w
  end
  #--------------------------------------------------------------------------
  # * Neighbor Of
  #    idxNode : index of node
  #    dir : down(1), left(2), right(3), or up(4)
  #  Returns index of adjacent node idxNode
  #--------------------------------------------------------------------------
  def neighborOf(idxNode,dir)
    case dir
      when 1
        return (idxNode+@w)
      when 2
        return (idxNode-1)
      when 3
        return (idxNode+1)
      when 4
        return (idxNode-@w)
    end
  end
  #--------------------------------------------------------------------------
  # * Is Neighbor Exist?
  #    idxNode : index of node
  #    dir : down(1), left(2), right(3), or up(4)
  #  Returns if adjacent node of idxNode exists
  #--------------------------------------------------------------------------
  def neighborExist?(idxNode,dir)
    case dir
      when 1
        return (yNode(idxNode)<@h-1)
      when 2
        return (xNode(idxNode)>0)
      when 3
        return (xNode(idxNode)<@w-1)
      when 4
        return (yNode(idxNode)>0)
    end
  end
  #--------------------------------------------------------------------------
  # * Reconstruct Path
  #    s : source node
  #    t : target node
  #    vertices_prev : map of navigated nodes
  #  Returns movement direction 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def reconstruct_path(s,t,vertices_prev)
    u=t
    while vertices_prev[u] != s && vertices_prev[u] != 0
      u = vertices_prev[u]
    end
    case u
      when s+@w
        return 1
      when s-1
        return 2
      when s+1
        return 3
      when s-@w
        return 4
    end
    return 0
  end
  #--------------------------------------------------------------------------
  # * Heuristic Distance
  #    u : node 1
  #    v : node 2
  #--------------------------------------------------------------------------
  def heuristic_dist(u,v)
    dx = xNode(v)-xNode(u)
    dy = yNode(v)-yNode(u)
    # Manhattan distance heuristic
    return (dx.abs+dy.abs)
  end
  #--------------------------------------------------------------------------
  # * Dijkstra's Algorithm
  #    x1, y1 : source coordinate
  #    x2, y2 : target coordinate
  #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def Dijkstra(x1, y1, x2, y2)
    # Initializations
    s = nodeOf(x1,y1)
    t = nodeOf(x2,y2)
    # Create open list q (as priority queue)
    q = PQueue.new(1,0)
    # Add s into open list q
    q.addEl(s)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    # Previous node in optimal path from source
    vertices_prev = Array.new(@w*@h+1,0)
    # Distance from source to source
    vertices_dist[s] = 0
    # The main loop
    while q.length > 1
      # Finds vertex u with least value of path distance
      d = vertices_dist[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if vertices_dist[q[ii]]<d
                  d = vertices_dist[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Remove u from open list q
      q.remEl(u)
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          alt = vertices_dist[u]+1
          if alt < vertices_dist[v]
            # Relax (u,v)
            q.addEl(v)
            vertices_dist[v]=alt
            vertices_prev[v]=u
          end
        end
      end
    end
    return 0
  end
  #--------------------------------------------------------------------------
  # * A* Algorithm
  #    x1, y1 : source coordinate
  #    x2, y2 : target coordinate
  #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
  #--------------------------------------------------------------------------
  def AStar(x1, y1, x2, y2)
    # Initializations
    s = nodeOf(x1,y1)
    t = nodeOf(x2,y2)
    # Create open list q (as priority queue)
    q = PQueue.new(1,0)
    # Add s into open list q
    q.addEl(s)
    # Create closed list q1, The list of nodes already evaluated.
    q1 = Array.new(@w*@h+1,false)
    # The map of navigated nodes.
    vertices_prev = Array.new(@w*@h+1,0)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    h_score = Array.new(@w*@h+1,0)
    f_score = Array.new(@w*@h+1,9999)
    # Distance from source to source
    vertices_dist[s] = 0
    h_score[s] = heuristic_dist(s,t)
    f_score[s] = h_score[s]
    # The main loop
    while q.length > 1
      # Finds vertex u with least value of f_score
      d = f_score[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if f_score[q[ii]]<d
                  d = f_score[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Move current node from open list to the closed list
      q.remEl(u)
      q1[u] = true
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          if !q1[v]
            tentative_g_score = vertices_dist[u]+1
            if !q.found?(v)
              q.addEl(v)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
            else
              tentative_is_better = false
            end
            if tentative_is_better
              if vertices_prev[v] != 0
                if f_score[u] < f_score[vertices_prev[v]]
                  vertices_prev[v] = u
                end
              else
                vertices_prev[v] = u
              end
              vertices_dist[v] = tentative_g_score
              h_score[v] = heuristic_dist(v,t)
              f_score[v] = vertices_dist[v]+h_score[v]
            end
          end
        end
      end
    end
    return 0
  end
end
Listra Pathfinder Module for RGSS2 (part 2)
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.0
#==============================================================================
#
#                                    PART 2
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rpgmakerid.com
#  - http://prodig.forumotion.net
#  - http://vixep.forumsrpg.net
#==============================================================================

#==============================================================================
# ** Game_Map (part 2 - overriden)
#------------------------------------------------------------------------------
#  This class handles maps. It includes scrolling and passage determination
#  functions. The instance of this class is referenced by $game_map.
#  This part overrides setup to use MGraph initialization and adds passable2?
#  method to detect obstacles (excluding events).
#==============================================================================

class Game_Map
  #--------------------------------------------------------------------------
  # * Setup
  #    map_id : map ID
  #--------------------------------------------------------------------------
  def setup(map_id)
    @map_id = map_id
    @map = load_data(sprintf("Data/Map%03d.rvdata", @map_id))
    @display_x = 0
    @display_y = 0
    @passages = $data_system.passages
    referesh_vehicles
    setup_events
    setup_scroll
    setup_parallax
    @need_refresh = false
    # Make MGraph
    $mgraph = MGraph.new(4)
  end
  #--------------------------------------------------------------------------
  # * Determine if Passable (ignoring events)
  #    x    : x coordinate
  #    y    : y coordinate
  #    flag : The impassable bit to be looked up
  #            (normally 0x01, only changed for vehicles)
  #--------------------------------------------------------------------------
  def passable2?(x, y, flag = 0x01)
    for i in [2, 1, 0]                      # in order from on top of layer
      tile_id = @map.data[x, y, i]          # get tile ID
      return false if tile_id == nil        # failed to get tile: Impassable
      pass = @passages[tile_id]            # get passable attribute
      next if pass & 0x10 == 0x10          # *: Does not affect passage
      return true if pass & flag == 0x00    # o: Passable
      return false if pass & flag == flag  # x: Impassable
    end
    return false                            # Impassable
  end
end

#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass of the
# Game_Player and Game_Event classes.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Move Type : Approach
  #--------------------------------------------------------------------------
  def move_type_toward_player
    # Approach player
    move_toward_player
  end
  #--------------------------------------------------------------------------
  # * Move toward Player
  #--------------------------------------------------------------------------
  def move_toward_player
    sx = distance_x_from_player
    sy = distance_y_from_player
    if sx != 0 or sy != 0
      # Determines the movement towards player with pathfinding algorithm
      # Uncomment one of these statements to use either A* or Dijkstra's
      # algorithm.
      # Note that:
      #  - Dijkstra's algorithm is always accurate but lacks its performance.
      #    You should only use this algorithm for small maps.
      #  - A* algorithm is accurate but not as well as Dijkstra's algorithm.
      #    However, A* works much faster than Dijkstra's do. Recommended to
      #    use this, even for large maps.
      dir = $mgraph.AStar(@x,@y,$game_player.x,$game_player.y)
      #dir = $mgraph.Dijkstra(@x,@y,$game_player.x,$game_player.y)
      case dir
      when 1
        move_down
      when 2
        move_left
      when 3
        move_right
      when 4
        move_up
      else  # If no path is found
        if sx.abs > sy.abs                  # Horizontal distance is longer
          sx > 0 ? move_left : move_right  # Prioritize left-right
          if @move_failed and sy != 0
            sy > 0 ? move_up : move_down
          end
        else                                # Vertical distance is longer
          sy > 0 ? move_up : move_down      # Prioritize up-down
          if @move_failed and sx != 0
            sx > 0 ? move_left : move_right
          end
        end
      end
    end
  end
end

NB: Jangan lupa kredit saya yah kalo mau menggunakan ini.. Wink

Cara Pemasangan?
Buat slot script baru di atas Main pada Script Editor, lalu copas kedua bagian script Listra Pathfinder Module di situ.

Download Sample Test Driver
RGSS: http://ifile.it/h4tzakl/GSAdemo.exe
RGSS2: http://ifile.it/4jfpa1d/GSAdemo2.exe
Back to top Go down
View user profile http://flashindo.forumotion.net
 
[RGSS/RGSS2] Listra Pathfinder Module
View previous topic View next topic Back to top 
Page 1 of 1
 Similar topics
-
» The Pathfinder Game (The Redwood war)
» The Peasant Rail Gun and other Pathfinder rule abuses
» Player Character's Guide: Ranks and Stations of Drow Society
» Face Claim List
» Torag, God of the Forge

Permissions in this forum:You cannot reply to topics in this forum
Flashindo Academy :: Education Class :: Programming :: Scripts Lounge-
Jump to: