| | Listra Pathfinder Module (RGSS2) | |
| Author | Message |
---|
ListRA-92 Adv. Citizen A
Lokasi : antara ada dan tiada~ :- Status : Who says a woman has to be weak?!! Jumlah Post : 407 Voucher : 4451 Reppo : 2 Join Date : 2010-10-09
| Subject: Listra Pathfinder Module (RGSS2) Sun 12 Dec 2010, 12:01 | |
| Listra Pathfinder Module Using A*/Dijkstra's Algorithm Version 1.0 For RPG Maker VX
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. Inilah codingan scriptku...
- Spoiler:
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.forumotion.com #==============================================================================
#============================================================================== # ** 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.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 # 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..
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 RGSS2: http://ifile.it/4jfpa1d/GSAdemo2.exe |
| | | nisamerica Tengkorak Hidup
Lokasi : Di tempat yang ada oksigennya Status : Menutup Mata Jumlah Post : 654 Voucher : 5434 Reppo : 10 Join Date : 2010-09-27
| Subject: Re: Listra Pathfinder Module (RGSS2) Sun 12 Dec 2010, 18:49 | |
| WHAAAA~~??!! Perasaan baru kmaren2 deh situ ngomong mo belajar RGSS?! Wih, bagus juga nih, thanks banget dah, gwa ambil ya, mumpung lagi bikin Game ABS pake event! Btw, ini bakal mencegah event untuk tertahan di balik tembok kan? Heh, seplah, selain ABS, ni juga bagus buat caterpillar! Btw, kenapa RGSS 1 & 2? Mengharapkan cendol lebih? |
| | | Mbah Moeng Mbah Moeng
Lokasi : here Status : ini status Jumlah Post : 3934 Voucher : 40255 Reppo : 43 Join Date : 2010-08-22
| Subject: Re: Listra Pathfinder Module (RGSS2) Mon 13 Dec 2010, 06:08 | |
| @nisamerica RGSS buat RM X P RGSS2 buat RM VX jadi gk apa bikin dua"nya |
| | | nisamerica Tengkorak Hidup
Lokasi : Di tempat yang ada oksigennya Status : Menutup Mata Jumlah Post : 654 Voucher : 5434 Reppo : 10 Join Date : 2010-09-27
| Subject: Re: Listra Pathfinder Module (RGSS2) Mon 13 Dec 2010, 09:43 | |
| Ah, salah tulis, harusnya "kenapa dipisah?" Soalnya di sebelah ama prodig disatuin |
| | | Nefusa 7 Citizen E
Lokasi : Jowo Status : wow ! Jumlah Post : 50 Voucher : 511 Reppo : 0 Join Date : 2012-02-25
| Subject: Re: Listra Pathfinder Module (RGSS2) Sun 14 Apr 2013, 21:11 | |
| hmm.. berguna banget |
| | | Sponsored content
| Subject: Re: Listra Pathfinder Module (RGSS2) | |
| |
| | | | Listra Pathfinder Module (RGSS2) | |
|
Similar topics | |
|
Page 1 of 1 | |
| Permissions in this forum: | You cannot reply to topics in this forum
| |
| |
| Latest topics | » Perkenalkan by Eruku Tue 24 Nov 2015, 20:25
» Ragnarok: Believe Visual Novel by Eruku Tue 24 Nov 2015, 20:20
» In Reality Visual Novel by Eruku Tue 24 Nov 2015, 20:15
» Adakan "Home Builder Event" Buat Papan kami. by Win_Amp Tue 25 Mar 2014, 10:06
» [Game]Sambung Kata by Win_Amp Mon 24 Mar 2014, 22:59
» [GAME]Menjawab pertanyaan dengan pertanyaan. by Win_Amp Mon 24 Mar 2014, 22:59
» [Game] salah kata by Win_Amp Mon 24 Mar 2014, 22:59
» [Roleplay] Family of Vixep Citizens by SkyChampion Mon 28 Oct 2013, 18:41
» Games Keren Terbaru~!! by SkyChampion Mon 28 Oct 2013, 18:40
» " Clocksberry " by Mbah Moeng Mon 28 Oct 2013, 18:39
» [Demo included] Unwalkable: Forbidden Destiny by Mbah Moeng Mon 28 Oct 2013, 18:39
» [team recruitment] Strug Team by Mbah Moeng Mon 28 Oct 2013, 18:39
» [Manga] Tale Before Sleep 3 - God Crisis by Mbah Moeng Mon 28 Oct 2013, 18:39
» [ASK][HELP!!]Algorithma Shell Sort by Mbah Moeng Mon 28 Oct 2013, 18:38
» Rama's Sprite Galery by Mbah Moeng Mon 28 Oct 2013, 18:38
|
Poll | | Siapakah mimin ter-mimin? | Yaden | | 0% | [ 0 ] | Mbah Moeng | | 100% | [ 4 ] | Win_Amp | | 0% | [ 0 ] |
| Total Votes : 4 |
|
Top posting users this week | |
Statistics | Citizens : 2403
Topics : 1224
Posts : 23288
_______________
Welcome to VIXEP's
newest Citizen,
https://vixep.forumotion.com/u2415
|
Who is online? | In total there are 13 users online :: 0 Registered, 0 Hidden and 13 Guests None Most users ever online was 80 on Tue 17 Apr 2012, 11:03 |
|