Per 2016, RMID pindah ke RMID Discord (Invite link dihapus untuk mencegah spambot -Theo @ 2019). Posting sudah tidak bisa dilakukan lagi.
Mohon maaf atas ketidaknyamanannya dan mohon kerjasamanya.

Share | 
 

 [VX] Listra Pathfinder Module

Topik sebelumnya Topik selanjutnya Go down 
[VX] Listra Pathfinder Module Empty2011-01-20, 18:27
Post[VX] Listra Pathfinder Module
#1
bungatepijalan 
Moe Princess
bungatepijalan

Level 5
Posts : 1487
Thanked : 30
Engine : Multi-Engine User
Skill : Intermediate
Type : Developer
Awards:
[VX] Listra Pathfinder Module Vide
Listra Pathfinder Module (LPM)
Version 1.2 - For RPG Maker VX
Type: NPC Movement System
Using A*/Dijkstra's Algorithm


Pengenalan

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 RGSS2.
Namun, script 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.

NB: Maap yah telat posting LPM versi RGSS2 sekian lama setelah LPM dalam RGSS diposting :hammer:



Fitur

  • Menggunakan algoritma Dijkstra dan A*
  • Memodifikasi fungsi event move_type_toward_player dan move_toward_player



Screenshots

(Ga perlu :kabur:)


Demo
Download: http://ifile.it/4jfpa1d/GSAdemo2.exe
Maap, demo ini bukan yang terbaru, kalo mau, copas aja script terbaru di bawahnya.

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


Scripts

Part 1:
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.2
#==============================================================================
#
#                                    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, A*, or Floyd–Warshall Algorithm).
#
#  To learn about pathfinding algorithms, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://en.wikipedia.org/wiki/Floyd–Warshall_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://rmid.forumotion.net
#  - http://prodig.forumotion.net
#  - http://vixep.forumotion.com
#==============================================================================

module LPM
  #--------------------------------------------------------------------------
  # * Listra Pathfinder Module Configuration
  #--------------------------------------------------------------------------
 
  # Config 1 -- Pathfinding algorithm to be used:
  #  1. Dijkstra's algorithm, always accurate but lacks its performance.
  #    Use this only for small maps.
  #  2. A* algorithm, 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.
  ALGO_USED = 2
 
  #==============================================================================
  # ** 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, values of elements priority will be always sorted
    #  descendingly
    #    ii : element to be added into the array
    #    PT : priority table to which array elements index
    #--------------------------------------------------------------------------
    def enqueue(ii,pt)
      iii = 0
      while iii < self.length && pt[self[iii]] > pt[ii]
        iii += 1
      end
      self.insert(iii,ii)
    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 :algo
    attr_accessor :neighbors
    attr_accessor :passage_table
    attr_accessor :floydpath, :floydnext
    #--------------------------------------------------------------------------
    # * Invariables
    #--------------------------------------------------------------------------
    INFINITY = 9999
    #--------------------------------------------------------------------------
    # * Graph Initialization
    #    nh : number of neighbors or allowed directions
    #    inalgo : pathfinding algorithm to be used
    #--------------------------------------------------------------------------
    def initialize(nh,inalgo)
      @w = $game_map.width
      @h = $game_map.height
      @algo = inalgo
      @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,s)
      # Unknown distance function from source to v
      vertices_dist = Array.new(@w*@h+1,INFINITY)
      # 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 > 0
        # Removes vertex u with least vertices_dist from open list and set it as
        # current node
        u = q.pop
        # Search completed
        if u == t
          return reconstruct_path(s,t,vertices_prev)
        end
        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.enqueue(v,vertices_dist)
              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,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,INFINITY)
      h_score = Array.new(@w*@h+1,0)
      f_score = Array.new(@w*@h+1,INFINITY)
      # 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 > 0
        # Removes vertex u with least f_score from open list and set it as
        # current node
        u = q.pop
        # Search completed
        if u == t
          return reconstruct_path(s,t,vertices_prev)
        end
        # Move current node from open list to the closed list
        q1[u] = true
        for i in 1..@neighbors
          if @passage_table[xNode(u),yNode(u),i-1] == 1
            v = neighborOf(u,i)
            tentative_g_score = vertices_dist[u]+1
            if !q1[v] && q.index(v) == nil
              q.enqueue(v,f_score)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
              if q1[v]
                q1[v] = 0
              end
            else
              tentative_is_better = false
            end
            if tentative_is_better
              vertices_prev[v] = u
              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
      return 0
    end
  end

end
Part 2:
Code:
#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.2
#==============================================================================
#
#                                    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, A*, or Floyd–Warshall Algorithm).
#
#  To learn about pathfinding algorithms, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://en.wikipedia.org/wiki/Floyd–Warshall_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://rmid.forumotion.net
#  - http://prodig.forumotion.net
#  - http://vixep.forumotion.com
#==============================================================================

#==============================================================================
# ** 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
    # Initializes MGraph instance
    $mgraph = LPM::MGraph.new(4,LPM::ALGO_USED)
  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
      case $mgraph.algo
      when 1
        dir = $mgraph.Dijkstra(@x,@y,$game_player.x,$game_player.y)
      when 2
        dir = $mgraph.AStar(@x,@y,$game_player.x,$game_player.y)
      end
      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


FAQ

Q : Kenapa dinamain Listra?
A : Itu nama karakter artworkku yang juga ada dalam demo LPM

Q : Adakah LPM dalam versi RGSS?
A : Ya, cekidot aja di: https://rmid.forumotion.net/t2891-xp-listra-pathfinder-module :kabur:

Q : Benarkah LPM hanya untuk event2/NPC? Adakah script sejenis LPM yang bisa untuk player (sistem point-to-click seperti pd game2 sejenis RO, Warcraft/DotA, dll)?
A : Tentu. Script sejenis LPM? Ada: http://www.brighthub.com/video-games/pc/articles/103148.aspx ; script ini jg bisa menggunakan mouse, semoga membantu :)
Maap merujuk script org lain, tapi LPM sama sekali tidak mengadopsi dari script ini :-

Q : Bagaimana kompabilitas script LPM?
A : Ga akan bentrok ama script2 kecilan lainnya, tapi entahlah utk script lain besar2an yang menggunakan movement

Q : Apakah LPM bisa juga utk pergerakan 8 arah?
A : Maap, tidak bisa


Credits

  • Bunga Tepi Jalan
  • Wikipedia
  • Amit's A* Pages
 

[VX] Listra Pathfinder Module

Topik sebelumnya Topik selanjutnya Kembali Ke Atas 
Halaman 1 dari 1

Permissions in this forum:Anda tidak dapat menjawab topik
RPGMakerID :: Scripts & Event Systems :: RMVX Scripts-