| | Listra Pathfinder Module (RGSS) | |
| 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 (RGSS) Sun 12 Dec 2010, 11:56 | |
| Listra Pathfinder Module Using A*/Dijkstra's Algorithm Version 1.0 For 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. Namun, script RGSS 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 RGSS (part 1) - Code:
-
#============================================================================== # Listra Pathfinder Module by Bunga Tepi Jalan # for RPG Maker X[b][/b]P # 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://www.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?(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 RGSS (part 2) - Code:
-
#============================================================================== # Listra Pathfinder Module by Bunga Tepi Jalan # for RPG Maker X[b][/b]P # 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://www.rpgmakerid.com # - http://prodig.forumotion.net # - http://vixep.forumotion.com #==============================================================================
#============================================================================== # ** 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
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 RGSS: http://ifile.it/h4tzakl/GSAdemo.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 (RGSS) 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! Cendol ah~ |
| | | | Listra Pathfinder Module (RGSS) | |
|
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 2 users online :: 0 Registered, 0 Hidden and 2 Guests None Most users ever online was 80 on Tue 17 Apr 2012, 11:03 |
|