Pathfinder-Script

[_Matrix]

***Version 2.1***

Hallo, ich hab letztens mal ein Weg-Finder-Skript erstellt.
Es ermöglicht Kollisionsfreie Bewegung eines Events oder den Spieler zum Ort xy.
Edit:
Die Neue Version ist auch für dynamische Anwendungen (siehe Demo) geeignet.
Vorsicht! Der Rechenaufwand steigt expotenziell mit der Anzahl der Umwegen an.

Das Skript enthält mehrere Funktionen, u.a auch die Möglichkeit eine Flash-Map zu erstellen.

Funktionen:

pathfinder(x, y):
erstellt eine Karte mit Bewegungsmöglichkeit zum Ziel.

move_toward_player
move_toward_pos(x, y):
Bewegt den Character zu einer bestimmten Position jeweils einen Schritt pro Aufruf. Ruft Pathfinder auf.

turn_toward_pos(x, y)
Dreht den Character zu einer bestimmten Position.

set_move_route(x, y, distance = 0, forcing = false):
erstellt eine neue Auto-Move-Route zum Ziel. Wenn <forcing> gesetzt wird, geht das Objekt sofort los. Ruft Pathfinder auf.

get_rangemap(x, y, range, color):
erstellt eine Range-Map für das Objekt mit den angegebenen Reichweite und in der angegebenen Farbe und gibt sie zurück. (Das Farbformat muss 12 bit Hexadezimal sein, um es als Flashmap anzeigen zu lassen. Siehe Hilfe unter Tilemap. Anschließend nur noch in die flash_data der aktuellen Tilemap rein.)
(Interessant für KS wie in FF-Tactics)

Variablen:

@start_node
Erster Knoten. Alle Knoten verweisen auf den nächsten bis zum Ziel.

@range_map
flash_data - komatible Table-Map

#==============================================================================
# ** Game_Character (part 4)
#------------------------------------------------------------------------------
#  Pathfinder-Erweiterung Version 2.1
#  Erstellt von: _Matrix
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * erstelle ein Raster der Map mit einem A*-Algorhitmus
  #     ziel_x : x-Koordinate vom Ziel
  #     ziel_y : y-Koordinate vom Ziel
#--------------------------------------------------------------------------
  def pathfinder(x, y)
    open_list = []
    close_list = []
    # setze das Ziel als Startpunkt
    # (Zurückverfolgung ist einfacher, als Nachbildung des Weges)
    open_list[$game_map.width * y + x] = Node.new(x, y, dist(x, y, @x, @y))
    # Untersuche die Karte nach einem Weg
    moves = 1
    loop do
      # setze den prüf-Knoten in die close_list
      current_node = open_list[$game_map.width * y + x]
      close_list[$game_map.width * y + x] = current_node
      open_list[$game_map.width * y + x] = nil
      # nehme die 4 nächsten Knoten in die Liste auf
      for i in 0..3
        case i
        when 0
          new_x = x - 1
          new_y = y
          d = 4
        when 1
          new_x = x + 1
          new_y = y
          d = 6
        when 2
          new_x = x
          new_y = y - 1
          d = 8
        else
          new_x = x
          new_y = y + 1
          d = 2
        end
        if passable?(x, y, d) and
            close_list[$game_map.width * new_y + new_x] == nil
          # Distanz zum Ziel + Wegkosten
          value = dist(new_x, new_y, @x, @y) + moves
          if open_list[$game_map.width * new_y + new_x] == nil
            open_list[$game_map.width * new_y + new_x] = Node.new(new_x, new_y, value, current_node)
          elsif open_list[$game_map.width * new_y + new_x].value > value
            open_list[$game_map.width * new_y + new_x].value = value
            open_list[$game_map.width * new_y + new_x].last_node = current_node
          end
        end
      end
      # Finde den Knoten mit dem niedrigsten Wert.
      lowest_node = nil
      for node in open_list
        next if node == nil
        if lowest_node == nil or node.value < lowest_node.value
          lowest_node = node
        end
      end
      # Kein Weg gefunden
      return false if lowest_node == nil
      # Weg gefunden?
      if lowest_node.x == @x and lowest_node.y == @y
        @start_node = lowest_node
        return true
      end
      x = lowest_node.x
      y = lowest_node.y
      moves += 1
    end
  end
  #--------------------------------------------------------------------------
  # get the distance between 2 points
  #--------------------------------------------------------------------------
  def dist(x1, y1, x2, y2)
    return (x2 - x1).abs + (y2 - y1).abs
  end
  #--------------------------------------------------------------------------
  # * Find a path to the player
  #--------------------------------------------------------------------------
  def move_toward_player
    move_toward_pos($game_player.x, $game_player.y, 2)
  end
  #--------------------------------------------------------------------------
  # * Find a path to (x, y)
  #     x : x-Koordinate
  #     y : y-Koordinate
  #     distance : Abstand zum Zielobjekt (Luftlinie)
  #--------------------------------------------------------------------------
  def move_toward_pos(x, y, distance = 1)
    return if moving?
    # überprüfe, ob eine Entfernung zum Spieler besteht
    abs_sx = (@x - x).abs
    abs_sy = (@y - y).abs
    if Math.sqrt(abs_sx * abs_sx + abs_sy * abs_sy) < distance then
      # wenn nicht, ändere nur die Blickrichtung
      turn_toward_pos(x, y)
      return
    end
    # gehe richtung Ziel
    if pathfinder(x, y) then
      return if @start_node == nil
      # nächster Knoten
      @start_node = @start_node.last_node
      if @start_node != nil
        if @start_node.x > @x
          move_right
          return
        elsif @start_node.x < @x
          move_left
          return
        elsif @start_node.y < @y
          move_up
          return
        else
          move_down
          return
        end
      end
    end
  end
  #--------------------------------------------------------------------------
  # * Fill Auto-Move-Route
  #     x : x-Koordinate
  #     y : y-Koordinate
  #     distance : Abstand zum Zielobjekt
  #     forcing  : flag zur sofortigen Ausführung
  #--------------------------------------------------------------------------
  def set_move_route(x, y, distance = 0, forcing = false)
    return if moving?
    # setze den weg
    if pathfinder(x, y) then
      return if @start_node == nil
      my_start_node = @start_node.last_node
      # erstelle eine neue Moveroute
      @move_route = RPG::MoveRoute.new
      @move_route.repeat = false
      @move_route.list = []
      xx = @x
      yy = @y
      while(my_start_node != nil)
        abs_sx = (xx - x).abs
        abs_sy = (yy - y).abs
        if Math.sqrt(abs_sx * abs_sx + abs_sy * abs_sy) <= distance
          break
        end
        if my_start_node.x > xx
          # right
          @move_route.list.push(RPG::MoveCommand.new(3))
          xx += 1
        elsif my_start_node.x < xx
          # left
          @move_route.list.push(RPG::MoveCommand.new(2))
          xx -= 1
        elsif my_start_node.y < yy
          # up
          @move_route.list.push(RPG::MoveCommand.new(4))
          yy -= 1
        else
          # down
          @move_route.list.push(RPG::MoveCommand.new(1))
          yy += 1
        end
        my_start_node = my_start_node.last_node
      end
      # drehe dich zum spieler (optional)
      # @move_route.list.push(RPG::MoveCommand.new(25))
      # beende den weg mit einem 0-code
      @move_route.list.push(RPG::MoveCommand.new(0))
      @move_route_forcing = forcing
    end
  end
  #--------------------------------------------------------------------------
  # * Turn Towards Position
  #--------------------------------------------------------------------------
  def turn_toward_pos(x, y)
    # Get difference in player coordinates
    sx = @x - x
    sy = @y - y
    # If coordinates are equal
    if sx == 0 and sy == 0
      return
    end
    # If horizontal distance is longer
    if sx.abs > sy.abs
      # Turn to the right or left towards player
      sx > 0 ? turn_left : turn_right
    # If vertical distance is longer
    else
      # Turn up or down towards player
      sy > 0 ? turn_up : turn_down
    end
  end
    #--------------------------------------------------------------------------
  # * erstelle eine Move-Range-Map
  #     x     : x-Koordinate
  #     y     : y-Koordinate
  #     range : Reichweitenangabe
  #     color : Farbwert
#--------------------------------------------------------------------------
  def get_rangemap(x, y, range, color)
    @range_map = Table.new($game_map.width, $game_map.height)
    # Startpunkt setzen
    @range_map[x, y] = color
    # überprüfe die benachbarten Felder
    test_environment(x, y, range, color)
    return @range_map
  end
  #--------------------------------------------------------------------------
  # Node defines a point in the path
  #--------------------------------------------------------------------------
  class Node
    #------------------------------------------------------------------------
    # * Public Instance Variables
    #------------------------------------------------------------------------
    attr_accessor :x            # x-Koordinate
    attr_accessor :y            # y-Koordinate
    attr_accessor :value        # Knotenkosten
    attr_accessor :last_node    # Übergeordneter Knoten
    #------------------------------------------------------------------------
    # * Object Initialization
    #------------------------------------------------------------------------
    def initialize(x, y, value, last_node = nil)
      @x = x
      @y = y
      @value = value
      @last_node = last_node
    end
  end
  #--------------------------------------------------------------------------
  # Interne Hilfsfunktion
  #--------------------------------------------------------------------------
  private
  def test_environment(x, y, depth, color)
    return if depth <= 0
    if (@range_map[x - 1, y] == 0 or @range_map[x - 1, y] == color) and
        passable?(x, y, 4)
      @range_map[x - 1, y] = color
      test_environment(x - 1, y, depth - 1, color)
    end
    if (@range_map[x + 1, y] == 0 or @range_map[x + 1, y] == color) and
        passable?(x, y, 6)
      @range_map[x + 1, y] = color
      test_environment(x + 1, y, depth - 1, color)
    end
    if (@range_map[x, y - 1] == 0 or @range_map[x, y - 1] == color) and
        passable?(x, y, 8)
      @range_map[x, y - 1] = color
      test_environment(x, y - 1, depth - 1, color)
    end
    if (@range_map[x, y + 1] == 0 or @range_map[x, y + 1] == color) and
        passable?(x, y, 2)
      @range_map[x, y + 1] = color
      test_environment(x, y + 1, depth - 1, color)
    end
  end
end

Einfach auf eine Leere Seite hinter Game_Character 3 oder sonstwo Einfügen.

WICHTIG!!!
Warum merkt keiner, dass das Script so gar nicht funktioniert?
Es muss ein Eingriff ins Skript vorgenommen werden und zwar:

Auf der Seite "Game_Character 3" die Funktion "passable?(x, y, d)" die Zeile "if event.x == new_x and event.y == new_y" erweitern mit " and event != self"
Das bewirkt, dass das Event-Feld sich nicht selbst als Hindernis betrachtet.

Benutzung:
Als Eventbefehl in eine Skrip-Aktion:
get_character(#).Funktion

"Funktion" durch Funktionsnamen ersetzen
"#" durch Event-ID erstetzen oder: (-1: Spieler, 0: Objekt selbst)

Edit:
Die Demo mit Version 2.0 findet ihr hier
(Bild aus alter Version)
Pathfinder Demo.jpg

*edit*
In Version 2.1 sind bisher keine Fehler aufgetreten.

Wenn Ihr das Skript benutzt bitte den Credits-Eintrag nicht vergessen.
Hoffe ich konnte jemanden damit helfen.

P.s. Dieses Script ist ohne Änderungen zu 100% Kompatibel mit meinem Collisions-check-Script

[derula]

Hi, darf man fragen, wozu das hier gut ist?

Zitat von _Matrix

    for y in 0..$game_map.height - 1
      for x in 0..$game_map.width - 1
        if not passable?(x, y, 0)
          @path[$game_map.width * y + x] = 999
        else
          @path[$game_map.width * y + x] = 998
        end
      end
    end

Du musst doch nicht bei jedem Path-Finding alle Felder auf Passierbarkeit in alle Richtungen überprüfen? (Ganz zu Schweigen davon, dass das dann in einem unperformanten, und auch noch eindimensionalen Array gespeichert wird; eine zweidimensionale Table wäre hier sicher eine bessere Lösung!) Das kann doch gar keine akzeptable Geschwindigkeit bringen. Noch dazu hast du später noch mal einen Loop über _alle_ Felder der Map, der _erneut_ für jedes einzelne Feld in einem immer größer werdenden Radius um das Ziel (wenn ich das richtig verstanden habe) die Passierbarkeit in alle Richtungen überprüft. Und das ist auch noch in einer weiteren Schleife!

Ähm, ich glaube nicht, dass das Skript für Realeinsatz geeignet ist, bei größeren Maps dürfte der Algorithmus sicher einige Sekunden dauern, vor allem bei längeren Wegen.

Wenn du das in einem Projekt verwenden willst, würde ich dir dringend empfehlen, den A*-Algorithmus anzusehen. Hier findest du ein paar Anregungen dazu, bzw. auch eine vollständige Implementierung (die natürlich noch für den RPG-Maker angepasst werden muss).

Aber ich finde es generell toll, dass auch noch jemand anders als ich hier Skripte postet

[_Matrix]

Erstmal Danke für das Feedback.

Du musst doch nicht bei jedem Path-Finding alle Felder auf Passierbarkeit in alle Richtungen überprüfen? ...

Nein, eigentlich nicht. Aber um einige Felder von Vornherein auszuschließen muss ich die Begehbarkeit prüfen. Sowohl Tiles, Tile-Events und Charactere.
Die eigenen Abfrage eignet sich da am besten.
Das mit den "leeren loop" ist blöd. Das weiß ich zwar, hab aber keine bessere Methode gefunden.

Ich hab mir eventuell überlegt, ob ich nicht einmalig die Kollisionsmap der Karte abspeichere und die Bewegbaren Events mit einer anderen Kollisionsmap überlagere. Dann würde die aktuallisierung schneller gehen. Fraglich wäre nur ob der Einsatz eines 2. Arrays sich rentieren würde.

Das mit den 1-Dimensionalen Arrays statt auf Tables zuzugreifen.
Ok hast eindeutig recht. War wohl noch zusehr bei C
Mit Tabels klappen kurze Strecken auch auf größeren Maps auf meinem PC ohne Ruckeln.^^

Wenn du das in einem Projekt verwenden willst, würde ich dir dringend empfehlen, den A*-Algorithmus anzusehen

Mein spiel benötigt nicht unbedingt einen Pathfinder, aber für das neue KS wäre es ein Vorteil.

Ich guck mal ob sich der A*-Algorythmus Problemlos auf den Maker übertragen lässt.
Wobei ich sagen muss, dass mein System nicht arg so weit davon entfernt war. Das Skript arbeitet auch nur den Bereich ab, der die Länge des gefundennen Weges nicht überschreitet.
Ich hab mir bereits überlegt, wie ich die falsche Richtung durch entfernungseinschätzung minimiere.
Allerdings kann ich mit dem A*-Algorithmus kein Table verwenden, da es nur Zahlen speichert.

Da ich Montag noch frei habe, setze ich mich mal an einer Umsetzung drann.
Ich hoffe, dass dadurch noch ein wenig Rechenzeit eingespart wird.

[derula]

Zitat von _Matrix

Nein, eigentlich nicht. Aber um einige Felder von Vornherein auszuschließen muss ich die Begehbarkeit prüfen.

Aber warum musst du das denn machen? Ah, ich ahne, weil du nachher nur die eine Richtung überprüfst... wäre es nicht besser, du schreibst z.B. statt

if @path[$game_map.width * y + x - 1] == 998 and passable?(x, y, 4)

folgendes:

if passable?(x, y, 4) and passable?[y, x - 1, 6]

? Dann überprüfst du auch wirklich nur die Felder die dich interessieren, und auch die nur in die interessanten Richtungen.

[_Matrix]

Nachdem ein Kollege von mir abgesagt hat und alle guten Filme aus der Videothek weg waren hatte ich eine Menge Zeit am Skript zu arbeiten.

Ich hab das ganze Skript überarbeitet und ein A*-Algorithmus eingebaut, der trotz anfänglichen Komplikationen extrem gut funktioniert.
Hab mir noch mal Wipikedia zurate gezogen, wo der Algorithmus detailiert beschrieben ist.

Jetzt gibt es auch nur noch Abfragen in die Richtung, die in Frage kommt.
Leider kann man das Skript nicht mehr zum erstellen einer Move-Range benutzen. Ich erstell morgen eins.
Die demo lad ich schon mal hoch. (Benötigt immernoch RTP)

Project1.rar Diesesmal ist ein Labyrinth in der Höhle. Ja mir war langweilig.

Edit:
Die neue Version vom Skript ist nun im 1. Post von mir vorhanden.