| [VX] Listra Pathfinder Module | |
|
2011-01-20, 18:27 | [VX] Listra Pathfinder Module |
---|
bungatepijalan Moe Princess
Posts : 1487 Thanked : 30 Engine : Multi-Engine User Skill : Intermediate Type : Developer
Awards:
| Listra Pathfinder Module (LPM) Version 1.2 - For RPG Maker VX Type: NPC Movement System Using A*/Dijkstra's Algorithm PengenalanSesuai 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 Fitur
- Menggunakan algoritma Dijkstra dan A*
- Memodifikasi fungsi event move_type_toward_player dan move_toward_player
Screenshots(Ga perlu ) DemoDownload: 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. ScriptsPart 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 FAQQ : 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 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 | |
|
Halaman 1 dari 1 |
|
|
Permissions in this forum: | Anda tidak dapat menjawab topik
| |
|
|
Latest 10 Topics | [Web Novel] Gloria Infidelis 2016-11-17, 21:27 by LightNightKnight
[Announcement] Forum baru untuk RMID 2016-08-25, 16:39 by TheoAllen
Where I'm Wrong ? 2016-07-24, 16:10 by ReydVires
flakeheartnet's Resources part III 2016-07-08, 14:30 by flakeheartnet
Keira's Art Warehouse 2016-06-28, 19:27 by KeiraBlaze
Theo Core Time System + Bingung 2016-06-27, 16:24 by Lockin
Error Script, Maybe ? 2016-06-27, 16:20 by Lockin
Nusaimoe @ RMID Lounge 2016-06-21, 05:02 by Jihad Bagas
Call Random Battle 2016-06-15, 17:04 by Lockin
Flakeheartnet Resources Part II [come back gift] 2016-06-07, 15:51 by flakeheartnet
|
Statistics
|
Members: [ 4947 ]
Topics: [ 8258 ]
Posts: [ 112606 ]
Newest member: [ https://rmid.forumotion.net/u4968 ]
|
|
|
|