ListRA-92 The Headmaster
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:
| Subject: [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... 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..
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
| |
|