*Listra Pathfinding Module

[Keroro]

Listra Pathfinding Module

Descrizione

Lo script implementa l'algoritmo di pathfinding A* in RGSS e modifica il Player affinché i comandi Move Towards Player e Autonomous Movement - Approach facciano uso di questo algoritmo, così l'evento può trovare la strada più veloce per avvicinarsi al giocatore.

Utile per implementare battle system su mappa e per caterpillar system e con le opportune modifiche anche per creare un RTS.

 

Autore

Bunga Tepi Jalan (aka Listra)

 

Istruzioni per l'uso

Lo script è composto da due parti, la prima parte è il CORE formato da due classi, una Priority Queue ed un Map Graph.

La Priority Queue serve ad immagazzinare i percorsi e a restituire quello a distanza minore, il Map Graph converte la mappa in un formato idoneo a eseguire l'algoritmo A - star. Per ulteriori dettagli ho scritto qualcosa in questo topic o potete chiedere :)

 

#==============================================================================
# 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://www.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

 

 

La Seconda parte è composta dalle modifiche al Player per automatizzare il movimento degli eventi, qui dovete stare attenti a non rompere la compatibilità con gli altri script!

 

#==============================================================================
# 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://www.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

[Guardian of Irael]

Uh ben commentato! XD Ha giudicare dalla lunghezza del codice sembra più elaborato dei soliti che giravano! XD Ma l'A* non lo conosco, quindi... D:

Bel lavoro! ^ ^

[Keroro]

Sto scrivendo una risposta chilometrica in cui spiego qualcosa in più nel topic http://www.rpg2s.net/forum/index.php?showtopic=14699 XD

[Guardian of Irael]

Ah ecco, mi pareva fosse fresco il discordo, ma non ricordavo! XD Leggo lì e più non dimando ° °

^ ^

[Keroro]

Vabbè se è pertinente alla discussione chiedi qua XD

 

Come funziona l'A-Star?

 

Esistono due liste, una aperta ed una chiusa e ci sono delle funzioni accessorie, il costo del nodo, la distanza stimata h, la distanza cumulativa f.

Nella lista aperta vanno i nodi da valutare e ci si mette il punto di partenza all'inizio.

Nella lista chiusa vanno i nodi già valutati.

 

All'algoritmo si passano due parametri, il punto di partenza ed il punto di arrivo.

 

Nella lista aperta si individua il nodo con costo cumulativo f minore, si controlla se è il nodo finale (e se lo è, si ricostruisce il percorso migliore).

Se non è il nodo finale si aggiunge il suddetto nodo alla lista chiusa perché ormai valutato e si mettono i suoi vicini nella lista aperta, calcolando i costi cumulati.

 

Poi si riparte selezionando il nodo con costo cumulato minore e si va avanti finché non si trova il nodo finale oppure finché non si coprono tutti i nodi. Naturalmente più ostacoli ci sono (nel calcolo dei nodi vicini si escludono i nodi non passabili), meno nodi si dovranno analizzare nel caso peggiore e quindi paradossalmente più è complicato il percorso più veloce sarà l'analisi.

Edited February 21, 2012 by Keroro

[Guardian of Irael]

Vabbè se è pertinente alla discussione chiedi qua XD

Sì, scherzavo! XD

 

Esistono due liste, una aperta ed una chiusa e ci sono delle funzioni accessorie, il costo del nodo, la distanza stimata h, la distanza cumulativa f.

Nella lista aperta vanno i nodi da valutare e ci si mette il punto di partenza all'inizio.

Nella lista chiusa vanno i nodi già valutati.

Capire quello che si dice dopo aver fatto l'esame di algoritmi e strutture di dati qualche giorno fa è bellissimo (peccato per le liste di adiacenza che andavano a creare alberi > >)! XD

Capisco il sistema di colorare i nodi (fatto così): già visitati o non visitati ^ ^

Gli dò un'occhiata allora per bene al codice per vedermi come ci va con l'RGSS :3

 

e quindi paradossalmente più è complicato il percorso più veloce sarà l'analisi.

Spettacolo se gli faccio fare una strada dritta muore! XDXD

 

Grazie per la spiegazione! ^ ^

[Maxy]

Naturalmente più ostacoli ci sono (nel calcolo dei nodi vicini si escludono i nodi non passabili), meno nodi si dovranno analizzare nel caso peggiore e quindi paradossalmente più è complicato il percorso più veloce sarà l'analisi.

 

Ma non è vero, l'A* se non ci sono ostacoli ha la performance migliore O(n) dove n è la distanza (se la funzione euristica è corretta, ma quando il percorso è privo di ostacoli l'euristica coincide con la distanza e quindi è corretta, no?)

[Guardian of Irael]

Su wiki è abbastanza dettagliata la descrizione! ^ ^

Mmmh perchè proprio A*? E' il migliore? O magari il più comodo da usare con questo codice? Ne conoscete altri utili? :3

^ ^

[Keroro]

Hai ragione, nell'a-star il caso migliore è quello senza ostacoli ._.

Mi sono confuso con l'algoritmo che ho implementato ieri per il mio gioco, un path finding fatto con il flood fill, in cui il caso migliore è con tanti ostacoli!

[Maxy]

Mi permetto di suggerire un'idea per implementare lo script:

La prima funzione del PQueue, ovvero addEl, performa una ricerca elemento per elemento, ma non è meglio, siccome la lista è ordinata, usare il metodo di bisezione che ha usato per la funzione found?

La mia proposta potrebbe essere questa, può andare?

 

  def addEl(ii)
   i=0
   j=self.length
   mid=0
   while i<j
  mid = (i+j)/2
  if self[mid]<ii
    i=mid+1
  else
    j=mid
  end
   end
   self.insert(i,ii)
 end

 

Saluti