Pathfinding Performance

.Leo

Krieger

1

Sonntag, 30. November 2008, 11:16

Pathfinding Performance

Schon wieder ne Frage...^^

Ich habe das Pathfinding-Script von Near-Fantastica:

Spoiler

Ruby Quellcode

#==============================================================================
#   ¦ Path Finding
#   By: Near Fantastica
#   Date: 24.09.05
#   Version: 1
#
#   Player :: $game_player.find_path(x,y)
#   Event Script Call :: self.event.find_path(x,y)
#   Event Movement Script Call :: self.find_path(x,y)
#==============================================================================
 
class Game_Character
  #--------------------------------------------------------------------------
  alias pf_game_character_initialize initialize
  alias pf_game_character_update update
  #--------------------------------------------------------------------------
  attr_accessor :map
  attr_accessor :runpath
  #--------------------------------------------------------------------------
  def initialize
	pf_game_character_initialize
	@map = nil
	@runpath = false
  end
  #--------------------------------------------------------------------------
  def update
	run_path if @runpath == true
	pf_game_character_update
  end
  #--------------------------------------------------------------------------
  def run_path
	return if moving?
	step = @map[@x,@y]
	if step == 1
  	@map = nil
  	@runpath = false
  	return
	end
	dir = rand(2)
	case dir
	when 0
  	move_right if @map[@x+1,@y] == step - 1 and step != 0
  	move_down if @map[@x,@y+1] == step - 1 and step != 0
  	move_left if @map[@x-1,@y] == step -1 and step != 0
  	move_up if @map[@x,@y-1] == step - 1 and step != 0
	when 1
  	move_up if @map[@x,@y-1] == step - 1 and step != 0
  	move_left if @map[@x-1,@y] == step -1 and step != 0
  	move_down if @map[@x,@y+1] == step - 1 and step != 0
  	move_right if @map[@x+1,@y] == step - 1 and step != 0
	end
  end
  #--------------------------------------------------------------------------
  def find_path(x,y)
	sx, sy = @x, @y
	result = setup_map(sx,sy,x,y)
	@runpath = result[0]
	@map = result[1]
	@map[sx,sy] = result[2] if result[2] != nil
  end
  #--------------------------------------------------------------------------
  def setup_map(sx,sy,ex,ey)
	map = Table.new($game_map.width, $game_map.height)
	map[ex,ey] = 1
	old_positions = []
	new_positions = []
	old_positions.push([ex, ey])
	depth = 2
	depth.upto(100){|step|
  	loop do
    	break if old_positions[0] == nil
    	x,y = old_positions.shift
    	return [true, map, step] if x == sx and y+1 == sy
    	if $game_player.passable?(x, y, 2) and map[x,y + 1] == 0
      	map[x,y + 1] = step
      	new_positions.push([x,y + 1])
    	end
    	return [true, map, step] if x-1 == sx and y == sy
    	if $game_player.passable?(x, y, 4) and map[x - 1,y] == 0
      	map[x - 1,y] = step
      	new_positions.push([x - 1,y])
    	end
    	return [true, map, step] if x+1 == sx and y == sy
    	if $game_player.passable?(x, y, 6) and map[x + 1,y] == 0
      	map[x + 1,y] = step
      	new_positions.push([x + 1,y])
    	end
    	return [true, map, step] if x == sx and y-1 == sy
    	if $game_player.passable?(x, y, 8) and map[x,y - 1] == 0
      	map[x,y - 1] = step
      	new_positions.push([x,y - 1])
    	end
  	end
  	old_positions = new_positions
  	new_positions = []
	}
	return [false, nil, nil]
  end
end
 
class Interpreter
  #--------------------------------------------------------------------------
  def event
	return $game_map.events[@event_id]
  end
end

zum Lesen den Text mit der Maus markieren

Nun will ich, dass Events dem Spieler folgen, jedoch geht das Ganze schon nur bei einem Event auf 5 FPS runter...

Ich rufe das Script in einem andern Script so auf:

	Ruby Quellcode
1	$game_map.events[1].find_path($game_player.x,$game_player.y)

Ich brauche Hilfe, damit das Script flüssiger läuft, hat irgendjemand Ideen/Vorschläge wie ich das ausbessern könnte? Oder ein anderes, ressourcensparenderes Script rumliegen?

.Leo

Cremno

Krieger

2

Sonntag, 30. November 2008, 11:20

http://www.rmxp.org/forums/index.php?topic=55274.0

.Leo

Krieger

3

Sonntag, 30. November 2008, 11:41

Danke!^^

Das Script ist auf jeden Fall besser, auf die Funktion bezogen, aber bei der Performanc ändert sich nichts, ca. 3 FPS, mein Spiel läuft normalerweise mit 38-40... Kann mir jemand helfen?

.Leo

Süleyman der Prächtige

Kriegsherr

Motto: ---

4

Sonntag, 30. November 2008, 12:35

Wie rufst du den Befehl auf? Die ganze Zeit nebenbei im parrallel Prozess? Dann wäre es kein Wunder, aber anders kann ich es mir nicht erklären. Es gibt auch den Befehl "Follow Player".

Edit Oder vielleicht hilft dir das Train Actors Skript aus Monstas Skript Explorer (hier auf der Hauptseite unter Tools).

Neo-Bahamut

Himmelsgleicher

Motto: Wer anderen eine Bratwurst brät, der hat ein Bratwurstbratgerät.

5

Sonntag, 30. November 2008, 12:38

Original-Demo eines Pathfinding-Skripts im Anhang =O

»Neo-Bahamut« hat folgende Datei angehängt:

Pathfind.rar (197,27 kB - 22 mal heruntergeladen - zuletzt: 19. Juli 2010, 02:12)

Spoiler: Wurstinator

zum Lesen den Text mit der Maus markieren

Spoiler: Lazer-Wurst

zum Lesen den Text mit der Maus markieren

Spoiler: Hallowurst

zum Lesen den Text mit der Maus markieren

.Leo

Krieger

6

Sonntag, 30. November 2008, 13:24

@Coco
Ich bin kein Idiot! xD
Glaub ich jedenfalls...
Ich habe im ersten Post erwähnt, dass ich es in einem anderen Script aufrufe, ganz konkret im Scene_Map, das jedes Frame geupdatet wird...
Sind das im Train-Actros script Events? Wenn nicht, gibts Probleme mit meinem Aks, und per Follow_Player wirds blöd weil ich nicht noch mehr Eventseiten machen kann, die ich per Local-Switches aufrufen kann, mit Schaltern und Variabeln kann ich aus anderen Gründen nicht arbeiten...

@Bahami^^
Was soll mir die Demo bringen, ich hab den Code ja daraus kopiert...?

.Leo

Neo-Bahamut

Himmelsgleicher

Motto: Wer anderen eine Bratwurst brät, der hat ein Bratwurstbratgerät.

7

Sonntag, 30. November 2008, 13:29

In der Demo gibbets so einen, der dir die ganze Zeit folgt^^

Spoiler: Wurstinator

zum Lesen den Text mit der Maus markieren

Spoiler: Lazer-Wurst

zum Lesen den Text mit der Maus markieren

Spoiler: Hallowurst

zum Lesen den Text mit der Maus markieren

Chaosgod Espér

Enchanted lord of Shadows

8

Sonntag, 30. November 2008, 14:25

...
Benutz das Pixelmovement Script von fOetzbärchi.. Da iss en pathfinding Script mit drin. Dieses speichert die Waypoints einer Map in seperate Files.. so verbraucht er kaum Performance beim laden und abarbeiten.

There was a Cave,
below a Silent's Grave.
Tunnels, extending far, running wide,
going deep into the World on the other Side.
Poor little Child, that was to brave,
died painfully deep down, in the Devil's Cave.

Evrey

Oberschurke im Ruhestand

Motto: "Satzzeichen sind keine Rudeltiere." - Chesra

9

Sonntag, 30. November 2008, 18:42

Notfalls gibt's hier performence-steigernde Scripte, z.B. verlinkt in meiner Signi

Diese "Bremse" kommt daher, dass der Pfad-Befehl im Event nur als ein Schritt zählt. Heißt also, der Maker will 40mal in der Sekunde dieses Script ausführen. Schon mies, huh? 2 Lösungen bieten sich an: a) baue eine Wait-Funktion in deinen Wander-Loop; b) versuchs mit dem Evententruckler oder wie der nochmal heißt^^" Der steigert von fast allem die Performence

Standard bei allem, das ich mache

Edit Das Script wäre der "1000Events"-Link in meiner Signi.

compétences

mes compétences	max.
Maps machen
Musik machen
Scripts machen
Story ausdenken
Pixeln und so
Events proggen

(Dieser Tab ist rein satirisch.)

mes projets

Silentium

Name: Silentium
Maker: Eigenbau (C++, x86-SSE/AVX-Assembly, Ruby/Lua)

Story	NPCs	Scripts	Ressis	Maps	Gesamt
(3+4)%	42	69%	0815	-17.438	103.38% ± 6.3mm²

(Die Tabelle erfüllt lediglich satirische Zwecke.)

Onyx
Eine in C++ implementierte, modulare, plattformunabhängige, virtuelle Maschine. Die Test-Version ist bereits halb fertig. Ab dann gibt es vielleicht mehr Infos. Sie soll die auf dem ersten Blick LISP-artige und eigens dafür konstruierte Sprache Obsidian ausführen können. Experimentell wird auch ein Lua-Compiler für Onyx gebaut. Ziel ist eine leistungsfähige, virtuelle Maschine für beliebige Scriptsprachen. Theoretisch gesehen müsste man bloß noch einen kompatiblen Compiler schreiben, der Quellcode jener Sprache in Onyx-Assembly, oder direkt in Onyx-Bytecode übersetzt. Ob die jemand nutzen wird, ist eine andere Frage und nur ein sekundäres... nein, eher tertiäres Ziel dieser VM. Primär dient es mir lediglich dazu, mein Verständnis von Hardware, ISA, und Assembly zu vertiefen, sowie eigene Grenzen auszutesten.

Warnung!
Das Entwickeln einer virtuellen Maschine oder Programmiersprache (im wahnsinnigsten Fall beides) ist eine höchst komplizierte Tätigkeit, aus der viel Frust und Hirnmatsche hervor gehen. Sollte sich dennoch ein ähnlich wahnsinniger finden, der sowas zusammen schustern will, so lege ich ihm/ihr die folgenden Bücher ans Herz:
- Compiler - Das Drachenbuch [978-3-8273-7097-6]
  Dieses Buch schlachtet ausführlich und leicht verständlich die Grundlagen bis hoch zu den Experten-Techniken des Compilerbaus aus. Es fängt mit der Automaten-Theorie und formalen Sprachen an, arbeitet sich durch Analysetechniken vor, und landet schließlich bei Techniken wie Optimierung und Register-Zuweisung. Das Buch wiegt 3Kg oder 4Kg. Hab's mal gewogen. Ist also nicht gerade die Lektüre für unterwegs.
- Computerarchitektur [3-8273-7016-7]
  Hier werden leicht verständlich die wichtigsten Entwicklungen der Rechnerarchitekturen erklärt (Gut, das Buch ist in die Jahre gekommen, aber der Weg zu heute ist ein winziger Schritt, den man sich nach diesem Buch selbst erdenken kann). Hauptbestandteil des Buchs ist eine relativ umfassende Betrachtung der Funktionsweise dreier gänzlich unterschiedlicher, aber dominierender Prozessor-Typen am Beispiel des Pentium II, UltraSPARC II, sowie picoJava. Die meisten Elemente dieses Buchs sind zwar für die Konstruktion einer virtuellen Maschine irrelevant, oder aufgrund der Tatsache, dass die VM Software ist und z.B. Byte-Grenzen hat, sogar zu Leistungseinbußen führen kann, doch ist ein hinreichendes Verständnis dieser Maschinen, mit denen wir arbeiten, äußerst hilfreich für die Überlegungen, wie die VM arbeiten soll.
Es kann sehr hilfreich und inspirierend sein, den Code quelloffener, virtueller Maschinen anderer Sprachen zu überfliegen. Meine Lieblings-Quelle war und ist stets die VM von Lua. Sie ist schlank, verständlich, in C implementiert, und basiert im Gegensatz zu vielen anderen Scriptsprachen-VMs auf einer Register-Maschine statt einer Stapelmaschine. Es wäre natürlich vorteilhaft, die entsprechende Sprache zu verstehen, in der man auch die eigene VM implementieren will. Weiterhin ist es äußerst vorteilhaft, eine leistungsstarke und bequeme Sprache wie C++ zu beherrschen, um die VM zu implementieren. Und bevor irgendwer auf die Idee kommt: Assembly ist NICHT als dominierende Sprache für den Bau einer VM geeignet. Wer die Frage des "Warum?" nicht beantworten kann, sollte zunächst die gewählte Sprache und Assembly hinreichend verstehen lernen, und es dann erneut mit der Frage versuchen. Es lohnt sich dennoch, Assembly zu lernen. Allein schon, um erneut das Verständnis zu vertiefen, zumal ihr mehr oder weniger gezwungen seid, auch für eure VM eine Assembler-Sprache zu entwickeln (Außer natürlich ihr schreibt eure Test-Programme Bit für Bit ;3).

enfin

Je ne peux pas parler français.
C'est tout ce que Goodle et les restes de cours de français.

Signaturstand: 24.07.2013

.Leo

Krieger

10

Montag, 1. Dezember 2008, 18:35

Ookay...
Danke für die vielen Antworten, aber ich habe es vorübergehend gelöst, indem ich den Move_toward_player ein wenig umgeschrieben habe...
Läuft flüssig und funktioniert soweit.^^

Ich melde mich sobald ich Probleme damit habe...

.Leo

Evrey

Oberschurke im Ruhestand

Motto: "Satzzeichen sind keine Rudeltiere." - Chesra

11

Montag, 1. Dezember 2008, 19:28

Mich würde int'ressieren, WIE du es umgeschrieben hast, falls es kein Geheimnis is' xD Schließlich nutzt Du das Script nicht alleine, und ich denke, der Code wäre für mich und Andere ebenfalls int'ressant

compétences

mes compétences	max.
Maps machen
Musik machen
Scripts machen
Story ausdenken
Pixeln und so
Events proggen

(Dieser Tab ist rein satirisch.)

mes projets

Silentium

Name: Silentium
Maker: Eigenbau (C++, x86-SSE/AVX-Assembly, Ruby/Lua)

Story	NPCs	Scripts	Ressis	Maps	Gesamt
(3+4)%	42	69%	0815	-17.438	103.38% ± 6.3mm²

(Die Tabelle erfüllt lediglich satirische Zwecke.)

Onyx
Eine in C++ implementierte, modulare, plattformunabhängige, virtuelle Maschine. Die Test-Version ist bereits halb fertig. Ab dann gibt es vielleicht mehr Infos. Sie soll die auf dem ersten Blick LISP-artige und eigens dafür konstruierte Sprache Obsidian ausführen können. Experimentell wird auch ein Lua-Compiler für Onyx gebaut. Ziel ist eine leistungsfähige, virtuelle Maschine für beliebige Scriptsprachen. Theoretisch gesehen müsste man bloß noch einen kompatiblen Compiler schreiben, der Quellcode jener Sprache in Onyx-Assembly, oder direkt in Onyx-Bytecode übersetzt. Ob die jemand nutzen wird, ist eine andere Frage und nur ein sekundäres... nein, eher tertiäres Ziel dieser VM. Primär dient es mir lediglich dazu, mein Verständnis von Hardware, ISA, und Assembly zu vertiefen, sowie eigene Grenzen auszutesten.

Warnung!
Das Entwickeln einer virtuellen Maschine oder Programmiersprache (im wahnsinnigsten Fall beides) ist eine höchst komplizierte Tätigkeit, aus der viel Frust und Hirnmatsche hervor gehen. Sollte sich dennoch ein ähnlich wahnsinniger finden, der sowas zusammen schustern will, so lege ich ihm/ihr die folgenden Bücher ans Herz:
- Compiler - Das Drachenbuch [978-3-8273-7097-6]
  Dieses Buch schlachtet ausführlich und leicht verständlich die Grundlagen bis hoch zu den Experten-Techniken des Compilerbaus aus. Es fängt mit der Automaten-Theorie und formalen Sprachen an, arbeitet sich durch Analysetechniken vor, und landet schließlich bei Techniken wie Optimierung und Register-Zuweisung. Das Buch wiegt 3Kg oder 4Kg. Hab's mal gewogen. Ist also nicht gerade die Lektüre für unterwegs.
- Computerarchitektur [3-8273-7016-7]
  Hier werden leicht verständlich die wichtigsten Entwicklungen der Rechnerarchitekturen erklärt (Gut, das Buch ist in die Jahre gekommen, aber der Weg zu heute ist ein winziger Schritt, den man sich nach diesem Buch selbst erdenken kann). Hauptbestandteil des Buchs ist eine relativ umfassende Betrachtung der Funktionsweise dreier gänzlich unterschiedlicher, aber dominierender Prozessor-Typen am Beispiel des Pentium II, UltraSPARC II, sowie picoJava. Die meisten Elemente dieses Buchs sind zwar für die Konstruktion einer virtuellen Maschine irrelevant, oder aufgrund der Tatsache, dass die VM Software ist und z.B. Byte-Grenzen hat, sogar zu Leistungseinbußen führen kann, doch ist ein hinreichendes Verständnis dieser Maschinen, mit denen wir arbeiten, äußerst hilfreich für die Überlegungen, wie die VM arbeiten soll.
Es kann sehr hilfreich und inspirierend sein, den Code quelloffener, virtueller Maschinen anderer Sprachen zu überfliegen. Meine Lieblings-Quelle war und ist stets die VM von Lua. Sie ist schlank, verständlich, in C implementiert, und basiert im Gegensatz zu vielen anderen Scriptsprachen-VMs auf einer Register-Maschine statt einer Stapelmaschine. Es wäre natürlich vorteilhaft, die entsprechende Sprache zu verstehen, in der man auch die eigene VM implementieren will. Weiterhin ist es äußerst vorteilhaft, eine leistungsstarke und bequeme Sprache wie C++ zu beherrschen, um die VM zu implementieren. Und bevor irgendwer auf die Idee kommt: Assembly ist NICHT als dominierende Sprache für den Bau einer VM geeignet. Wer die Frage des "Warum?" nicht beantworten kann, sollte zunächst die gewählte Sprache und Assembly hinreichend verstehen lernen, und es dann erneut mit der Frage versuchen. Es lohnt sich dennoch, Assembly zu lernen. Allein schon, um erneut das Verständnis zu vertiefen, zumal ihr mehr oder weniger gezwungen seid, auch für eure VM eine Assembler-Sprache zu entwickeln (Außer natürlich ihr schreibt eure Test-Programme Bit für Bit ;3).

enfin

Je ne peux pas parler français.
C'est tout ce que Goodle et les restes de cours de français.

Signaturstand: 24.07.2013

.Leo

Krieger

12

Montag, 1. Dezember 2008, 19:41

Ehm ja tut mir leid...^^

Edit: ist ne neue Methode, hab ich nur vergessen zu erwähnen...^^

Hier der Code, es wurden nur die ersten 3 Zeilen verändert (in Game_Character 3):

Ruby Quellcode

#--------------------------------------------------------------------------
  # * Move toward Event
  #--------------------------------------------------------------------------
  def move_toward_event(event)
	# Get difference in player coordinates
	sx = @x - $game_map.events[event].x
	sy = @y - $game_map.events[event].y
	# If coordinates are equal
	if sx == 0 and sy == 0
  	return
	end
	# 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

Das Ganze mit

	Ruby Quellcode
1	$game_map.events[irgendeineid].move_toward_event(zieleventid)

aufgerufen.

Ich habe aber ein kleines Problem, wie mir grade aufgefallen ist, die Events laufen auch Diagonal, durch fast alles durch und berühren das andere Event bevor sie eig. da sind...

Wie kann ich das ändern? Hab im Moment irgendwie keinen Plan, weil ich bei dem Ganzen nicht wirklich durchblick. xD

.Leo