[Video] - Pathfinding in SL (Designing Worlds)

Donnerstag vor zwei Wochen wurde im Designing Worlds Studio auf Garden of Dreams eine Talkshow aufgezeichnet, bei der Lorca, Falcon und Maestro Linden zu Gast waren und einiges zum Thema Pathfinding erzählten. Außerdem dabei war Sandry Logan vom Virtual Kennel Club, einem Anbieter von geskripteten Tieren.

Letzten Montag wurde dann das Video inworld im Studio vorgeführt, wo auch Lorca noch einmal anwesend war und Fragen beantwortete. Und gestern ist das Video schließlich auf Treet TV hochgeladen worden und es kann jetzt online angesehen werden. Da auch ein Code zum Einbetten angeboten wird, mache ich das einfach mal. Das komplette Video dauert 99 Minuten:




Kurze Zusammenfassung:
Nach der Vorstellung der Talkshow-Gäste gibt es erstmal einen längeren Abschnitt mit Sandry Logan und Saffia Widdershins auf einem VKC Sim. Dort diskutieren die Beiden über die neuen Pathfinding Pets und zeigen auch kurz einige in Aktion. Interessant ist hier ein Test von zwei Pathfinding Tieren im Vergleich zu einem alten, sensorgesteuerten Hund (etwa bei 25:25 min.). Hier wird ziemlich deutlich, welche Verbesserung Pathfinding für die automatische Navigation bedeutet.

Bei etwa 29:30 min. geht es zurück ins Studio, wo dann alle drei Lindens die Möglichkeiten von Pathfinding erläutern. Allein für den Anblick der "drei Devs vom Lab" lohnt sich schon ein kurzes Reinschauen in die Aufzeichnung. Lorca Linden (sitzt auf der Linden Couch in der Mitte) hat einen wirklich abgedrehten Avatar. Aber auch Falcon (mit Cowboyhut) und Maestro (barfüßiger Opa) gehen mit ihren Avas über den Newbie Style der meisten anderen Lindens hinaus.

Hier in Listenform einige ihrer Aussagen (Pathfinding kürze ich im folgenden mit PF ab):

• PF wurde eingeführt, weil gescriptete Navigation von Charakteren mit alten LSL-Methoden zu viel CPU Zeit benötigt, vor allem durch die Verwendung von Sensor Scans.
• Viele Charaktere mit Sensor Scans können extremen Lag auf einer Region verursachen.
• PF benötigt wesentlich weniger Ressourcen einer Region. Die komplette Navigation wird mit der Havok Physikengine auf einem Server berechnet.
• Durch Einsatz von PF werden Skripte insgesamt kleiner und effizienter, da Navigations-Funktionen als aufrufbare Routinen zur Verfügung gestellt werden.
• Die Funktion llGetStaticPath kann auch von Nicht-PF Charakteren und in Regionen mit deaktiviertem PF genutzt werden.
• llGetStaticPath führt einen Charakter oder Avatar über verschiedene Wegpunkte von einem Start- zum Zielpunkt.
• Das Navmesh ist eine Straßenkarte für PF-Charaktere.
• Die Berechnung des Navmesh ist aufwendig, das Auslesen für die Charaktere benötigt jedoch nur minimale Ressourcen.
• Das Navmesh steht automatisch zur Verfügung, ohne dass man manuell etwas machen müsste.



Quelle: Prim Perfect

• Manuelle Optimierung des Navmesh mit den Viewer-Tools bringt eine leicht verbesserte Performance für die Region.
• Rezzen von Prims und Ändern von Landboden bedeutet immer eine Änderung des bestehenden Navmesh. Berechnet wird es jedoch nur, wenn der Rebake-Button im Viewer gedrückt wird.
• Es gibt aktuell noch einige Probleme mit dem Rebake-Button (ist manchmal nicht anklickbar). Die Lindens wollen das demnächst beheben.
• Es gibt eine Möglichkeit, die PF-Charaktere waagerecht oder senkrecht zu nutzen, was bei Steigungen und Gefällen ein unterschiedliches Verhalten hervorruft. (Diesen Punkt habe ich technisch nicht ganz verstanden).
• Ein "Static Obstacle" schneidet immer ein Loch in das Navmesh. Damit ist der Bereich, wo ein Static Objekt die begehbare Fläche des Navmesh berührt, für PF-Charaktere nicht nutzbar (was in einer Kollisionsvermeidung resultiert).
• Es gibt ein Batch System für komplette Regionen, das Änderungen von PF-Eigenschaften in ganzen Gruppen durchführt. (z.B. alle Objekte mit Skripten auf "Moveable Obstacle" setzen).
• Es gibt sowohl Begrenzungen des Ressourcenverbrauch bei PF-Regionsprozessen, als auch in den einzelnen PF-Funktionen. Werden die Begrenzungen erreicht, wird die Berechnung gedrosselt, um die Region immer performant zu halten.
• Zur Zeit arbeitet LL an der Verbesserung der Begrenzungsabläufe, um den Ressourcenbedarf bei PF weiter zu verringern.
• Es gibt auch noch ein Problem mit PF-Charakteren, die mit anderen Charakteren zusammenstoßen. Diese "hängen" dann irgendwie zusammen und bilden einen Haufen. Je mehr Charaktere in diesen Haufen geraten, umso mehr Lag verursacht dieser durch Kollisionen. LL arbeitet bereits an einer Behebung dieses Problems.
• LL hat auf einer durchschnittlichen Region bereits 250 PF-Charaktere gleichzeitig laufen lassen, ohne nennenswerten Lag.
• Es gibt auch schon Nutzer-Regionen, auf denen etwa 200 PF-Charaktere laufen.
• Das theoretische Limit in einer Region liegt bei 1000 PF-Charakteren (weil mehr Prims nicht auf eine Region passen / 1 PF-Charakter = 15 Prims).
• Eine empfohlene Anzahl von PF-Charakteren liegt bei etwa 50 pro Region.
• In etwa einem Monat werden die Advanced Creator Experience Tools für PF-Charaktere veröffentlicht.



Quelle: Prim Perfect

• Die PF-Skripte von den Wilderness Experience Regionen für Premium Nutzer werden demnächst in die LL-Wiki eingestellt.
• LL beobachtet jetzt einige Zeit die Anwendung von PF bei den Nutzern und entscheidet dann, welche Erweiterungen mittelfristig für PF dazukommen werden.
• Eine mögliche Erweiterung ist "Volumetric PF", was den Charakteren dann erlauben würde, zu schwimmen und zu fliegen.
• LL würde jetzt erstmal gerne mehr Tiere, NPCs für Rollenspiele und automatische Vehikel sehen, die von den Bewohnern erstellt werden.

Nach dem Screening des Videos am Montag, veröffentlichte Lorca Linden noch einige Statistiken zu Regionen vor und nach Einführung von Pathfinding. Hier sind sie (alle Sim FPS-Angaben sind Durchschnittswerte):

Private Regionen

• Vor Einführung von PF: 44,43 FPS
• Nach Einführung von PF:
• PF ist nicht aktiviert: 44,41 FPS
• PF ist aktiviert / keine PF-Objekte: 44,29 FPS
• PF ist aktiviert / 1 PF-Objekt: 44,25 FPS
• PF ist aktiviert / 10 PF-Objekte: 44,70 FPS

Mainland Regionen

• Vor Einführung von PF: 44,66 FPS
• Nach Einführung von PF:
• PF ist nicht aktiviert: 44,46 FPS
• PF ist aktiviert / keine PF-Objekte: 44,44 FPS
• PF ist aktiviert / 1 PF-Objekt: 44,25 FPS
• PF ist aktiviert / 10 PF-Objekte: 44,79 FPS

Das bedeutet, egal ob mit oder ohne PF und unabhängig von der Anzahl von Charakteren, liegen die Abweichungen durch PF insgesamt bei unter 1%. Soviel zu einigen theoretischen Zahlenspielen zwecks Nachweis von Lag, die ich hier und da gelesen habe. ;-)

Hier ist die Seite mit dem Video auf Treet TV:
>> Pathfinding in Second Life

Und hier der Sim des Virtual Kennel Club, wo die ersten 30 Minuten aus dem Video gedreht wurden:
>> Teleport zur Isle of Dogs

Meine Blogposts zu den wichtigsten Pathfinding-Funktionen:
>> Pathfinding ab heute im kompletten Main Grid von SL - (mit Kurzanleitung)
>> Einige Infos von den Lindens zum Pathfinding
>> Pathfinding FAQ von Lorca Linden

Pathfinding Talkshow mit Lorca und Falcon Linden

Quelle: Prim Perfect

Am heutigen Donnerstag, den 27. September, wird um 2pm SLT (23 Uhr MESZ) eine Sonderausgabe der Prim Perfect Sendung "Designing Worlds" im inworld Studio des Garden of Dreams aufgezeichnet. Als Gäste werden Lorca und Falcon Linden anwesend sein und über ihre derzeitige Schwerpunktaufgabe bei Linden Lab sprechen - dem Pathfinding-Projekt. Außer den Fragen, die Saffia Widdershins für die beiden vorbereitet hat, können auch vom Publikum während der Show noch Fragen an die Lindens gestellt werden.

Neben Lorca und Falcon, wird auch noch Sandry Logan vom Virtual Kennel Club (VKC) bei der Talkshow dabei sein. Sie hat sich schon in der Beta Phase mit Pathfinding beschäftigt und bei der Entwicklung der Pathfinding Technologie mitgeholfen. Zur Demonstration wird sie einige ihrer neuen Haustiere mitbringen, die bereits die Pathfinding Funktionen nutzen. Zumindest der Bloodhound II wurde inzwischen auf die Pathfinding-Technik umgestellt.

Ziel der Show ist es, den Besuchern zu zeigen, was Pathfinding überhaupt ist, wie es genutzt werden kann und welche erstaunlichen Effekte man damit erzeugen kann. Für die vollständige Designing Worlds TV-Show werden am 2. Oktober noch ergänzende Aufnahmen im Virtual Kennel Club gemacht und die komplette Sendung kann dann ab Montag, den 8. Oktober im Designing Worlds Kanal von Treet TV angesehen werden.

>> Teleport zum Designing Worlds Studio im Garden of Dreams

Quelle: Ask the Lindens about Pathfinding – on a special edition of Designing Worlds

Pathfinding FAQ von Lorca Linden

Quelle: SL Brand Center

Am 18. September hatte Lorca Linden im LL-Forum mit seinem ersten (und bisher einzigen) Beitrag eine längere FAQ zum Thema Pathfinding gepostet. Es steht zwar nicht wirklich viel Neues drin, aber es sind ein paar ganz spezifische Tipps enthalten, die vielleicht jemand gut gebrauchen kann. Ich poste das erst heute, weil ich mir mit der Übersetzung keinen Stress gemacht habe, sondern jeden Tag nur zwei bis drei Abschnitte angegangen bin.^^

Am 20. September wurde auch der offizielle Second Life Viewer 3.4.0 veröffentlicht, der in dieser Version die volle Pathfinding-Unterstützung erhalten hat. Vorher war dies nur im Beta- und Development-Viewer zu finden. Dadurch sind die Tipps aus der FAQ nun von allen nachvollziehbar, die mit diesem Viewer in Second Life einloggen. Bei vielen TPVs geht das auch, jedoch steht dort noch nicht das View/Test-Fenster zur Verfügung, mit dem das Navmesh grafisch angezeigt werden kann.

Hier nun die Übersetzung:

Pathfinding FAQ
von Lorca Linden am 18.09.2012 um 4:05pm
- Forenübersetzung -

Wir möchten uns bei allen bedanken, die an der Pathfinding Beta teilgenommen haben und bei denen, die damit begonnen haben, Objekte und Charaktere mit Pathfinding-Funktionen zu erstellen, nachdem der Pathfinding-Servercode gridweit eingeführt wurde. Wir haben Fragen gesammelt und werden auf viele davon hier eingehen. Rückmeldungen sind weiterhin sehr willkommen!

F: Wird Pathfinding starken Lag auf meiner Region / Parzelle verursachen?
A: Nein. Für den überwiegenden Teil der Pathfinding Beta war dies eine berechtigte Sorge bei Mainland Regionen und allen Regionen, bei denen die Second Life Nutzer die Pathfinding-Grundstücke mit ihren Linksets nicht aktualisiert hatten, um sie auf "Static" umzustellen. Dies wird manchmal auch als "Pemanent" bezeichnet, was bedeutet, dass die Linkset-Nutzung auf "Walkable", "Static Obstacle", "Exclusion Volume" oder "Material Phantom" gestellt wurde.

Das Aktualisieren eurer Linksets kann dennoch die Performance verbessern und es ist notwendig, um ein optimales Verhalten von Pathfinding-Kreaturen auf eurer Region zu erreichen. Die schlechtmöglichste Performance wird nun an einem bestimmten Punkt so gekappt, dass man in den meisten Regionen keinen Performance-Unterschied nach dem Einschalten von Pathfinding bemerken wird. Bei einer Fullprim Region werden durchschnittlich nicht mehr als 4ms/Frame für das Aktualisieren des Navmesh benötigt, um die Änderungen für "Movable Obstacles" (dem Standard für Prims) für jeden Frame zu berechnen.

Auf Homestead Regionen wird bereits ab 1ms/Frame gekappt. Verminderte Performance sollte nur in Regionen wahrgenommen werden, auf denen (a) die Performance schon vorher schlecht war (das heißt, die freie CPU-Zeit war bereits kleiner als 4ms auf einer Fullprim Region oder kleiner 1ms auf einer Homestead), und (b) keine Linksets auf Static umgestellt wurden.

F: Wird das Aktualisieren einer Umgebung für Pathfinding viel Zeit in Anspruch nehmen?
A: In den meisten Fällen sollte es relativ einfach sein, eine bestehende Umgebung umzustellen, damit sie mit Pathfinding funktioniert. Wir haben das neue "Linksets"-Fenster für Pathfinding so gestaltet, dass ihr Gruppen von Objekten auswählen und ihre Pathfinding-Eigenschaften in einem Schritt ändern könnt. Wir haben ebenfalls ein neues Simulator-Konsolenkommando bereitgestellt (die Simulator-Konsole kann mit Strg+Umschalt+ö geöffnet werden), die es Einwohnern erlaubt, alle Linksets (oder auch nur die nicht geskripteten Objekte) auf ihrer Parzelle (oder einer Parzelle im Gruppenbesitz) entweder auf Walkable oder Static Obstacle zu setzen.

Estate Manager können die Konsole benutzen, um alle Linksets auf einer Region zu ändern. Man benötigt auch keine Mod-Rechte für ein Linkset, um dessen Pathfinding-Eigenschaften zu verändern. Sie können von jedem geändert werden, der (a) Eigentümer des Objektes ist, (b) Mod-Rechte für das Objekt hat, oder (c) Eigentümer der Parzelle oder Region ist, auf der sich das Objekt befindet. (Achtet darauf, dass man bei Änderungen für Objekte die nicht in eurem Besitz sind und für die man keine Mod-Rechte hat, aber die sich auf eurer Parzelle befinden, das Konsolen-Kommando verwenden muss und das Linkset-Fenster hier nicht funktioniert). Weitere Informationen über das Pathfinding Tool für Mehrfachktualisierungen könnt ihr hier nachlesen.

F: Wann werden die Pathfinding Tools im SL Viewer veröffentlicht und woher bekomme ich eine Beta-Version der Viewer-Tools?
A: Wir erwarten, dass wir die Pathfinding Tools bis Ende September in den Hauptviewer integriert haben! Bis dahin könnt ihr Zugang zu den Tools durch den Download des neuesten Beta Viewers erhalten - das ist sehr hilfreich für alle, die Pathfinding freundliche Umgebungen bauen oder nachbearbeiten wollen. Anm.: Wie oben schon angesprochen, hat inzwischen auch der SL-Viewer die Pathfinding-Tools.

F: Kann ich meine Objekte bewegen, nachdem ich sie einmal auf Static umgestellt habe?
A: Wenn ihr ein Linkset bewegt oder verändert, das auf Static gesetzt wurde, wird das Navmesh auf "unsauber" gesetzt und euch wird ein Button angezeigt, mit dem ihr ein "Rebake" ausführen könnt, was eine Aktualisierung unter Beachtung eurer Änderungen durchführt. Dabei gibt es zwei Einschränkungen: (1) Ihr könnt ein Static Linkset nicht ändern, wenn ihr nicht in der gleichen Region seid, wie das Rootprim und (2) Skripten in statischen Objekten ist es nicht erlaubt, Objekte in einer Weise zu verändern, die das Navmesh unsauber werden lassen (z.B. Verlinkung oder Aufheben der Verlinkung von Prims, Veränderung der Form, oder transformieren aller Prims, die nicht auf die physikalische Form "Keine" gesetzt sind.) Wenn ihr euch fragt, wie ihr die Türen von eurem Haus unter Pathfinding zum Funktionieren bringt, dann seht euch die nächste Frage an.

F: Wie kann ich Pathfinding für mein Haus aktivieren, dass eine geskriptete Tür eingebaut hat?
A: Wegen der Regel, die es Skripten in einem Walkable Objekt (wie z.B. einem Haus) nicht erlaubt, das Linkset auf eine Weise zu verändern, die das Navmesh ungültig werden lässt (z.B. durch Änderung der physischen Form beim Öffnen der Tür), ist es notwendig, Häuser und ähnliche Linksets etwas anders zu gestalten.

Anstatt die Tür mit dem Skript zum Öffnen und Schließen als Teil in einem Linkset zu verwenden, sollte das Linkset stattdessen die Tür aus seinem Inventar als separates Objekt "heraus rezzen". So kann die Tür mit einem Skript versehen werden, das llSetKeyframedMotion zum Schwingen oder Verschieben nutzt. Damit wird es Pathfinding Objekten ermöglicht, sauber auf die Tür zu reagieren und gleichzeitig den aufwendigen Vorgang einer Neuberechnung des Navmesh zu vermeiden. In Kürze planen wir Beispiele für diese Bauweise zu erstellen, und sie gemeinsam mit einer Anleitung für einfaches Umgestalten eines bestehenden Hauses in Bezug auf Pathfinding zur Verfügung zu stellen.

F: Warum ist das Bearbeiten des Landbodens jetzt anders als früher?
A: Aus Gründen der Performance, erzeugen wir den Landboden für Kollisionsberechnungen auf dem Server nicht länger als Heightfield (das ist so etwas wie eine topografische Karte). Stattdessen verwenden wir ein "gebogenes Mesh". Kollisionen werden damit sehr viel effizienter auf den meisten Untergründen berechnet, aber das Aktualisieren des Mesh (bei Änderungen) dauert viel länger.

Um dem Rechnung zu tragen, gibt es nun eine Änderungsverzögerung von etwa 30 Sekunden, nachdem man mit dem Bearbeiten des Landbodens aufgehört hat und bevor damit begonnen wird, das Mesh neu aufzubauen (was dann nochmal ein bis zwei Minuten dauern kann). Bis das Mesh komplett aktualisiert wurde, werden Objekte und Avatare nicht sauber mit dem Mesh kollidieren und man wird eventuell Fehler bemerken, wie Avatare, die auf und ab hüpfen, wenn sie auf dem bearbeiteten Mesh des Landbodens laufen.

F: Was bedeuten die Prozentzahlen, die im Linkset-Fenster angezeigt werden? (Beachtet, dass die Mehrheit der Nutzer sich nie um diese erweiterten Funktionen kümmern müssen).
A: Diese Zahlen sind die Begehbarkeits-Koeffizienten des Linksets für jeden Charakter-Typ. Das ist wahrscheinlich die umfangreichste, komplexeste und am wenigsten intuitive Funktion von Pathfinding.

Angenommen, ihr habt etwas gebaut, das für Tiere und menschliche NPCs vorgesehen ist. Der Aufbau enthält ein Netzwerk von Straßen und etwas Graslandschaft. Für die meiste Zeit wollt ihr, dass die Tiere auf dem Gras und die Menschen auf den Straßen bleiben. Wenn nun aber ein menschlicher NPC versucht, von Punkt A nach Punkt B zu kommen und die Straße wäre 100x länger (weil sie sehr kurvenreich ist), als der direkte Weg über das Gras, dann wollt ihr vielleicht, dass sie dann den direkten Weg nehmen. Dies ist genau das, wofür Begehbarkeits-Koeffizienten und Charakter-Typen gedacht sind.

Um das anzuwenden, sollte man die menschlichen NPCs so skripten, dass sie CHARACTER_TYPE_A und die Tiere CHARACTER_TYPE_B verwenden. Dann kann man das Linksets-Fenster öffnen und den Begehbarkeits-Koeffizienten für das Gelände auf "A=1%, B=100%" einstellen. Das bedeutet, dass Pathfinding-Charaktere, die den CHARACTER_TYPE_A verwenden, sich 100x langsamer auf dem Gelände bewegen (und Wege bevorzugen, die dieses Gelände vermeiden, außer sie sind wesentlich länger), während Kreaturen, die den CHARACTER_TYPE_B verwenden, sich mit voller Geschwindigkeit auf dem Gelände bewegen können. Anschließend wählt man alle Straßen im Linksets-Fenster aus und stellt sie auf "A=100%, B=0%". Das bewirkt, dass Charaktere die CHARACTER_TYPE_A verwenden, sich mit voller Geschwindigkeit auf den Straßen bewegen, während Kreaturen mit CHARACTER_TYPE_B diese Straßen unter allen Umständen vermeiden werden.

Beachtet bitte, dass zur Vermeidung von Unstimmigkeiten ein Pathfinding-Charakter, der sich in einem Bereich wiederfindet, der Null Begehbarkeit für dessen CHARACTER_TYPE verwendet, sich mit voller Geschwindigkeit bewegen kann, um von dort flüchten zu können. Das kann passieren, wenn der Charakter durch Kollissionen in einen solchen Bereich gestoßen wird, oder durch seine Bewegungseinstellungen dazu gezwungen wird, sich dort hinein zu bewegen (z.B. durch einen Bewegungsradius).

F: Welchen Charakter-Typ sollte ich als Hersteller verwenden, wenn ich ein Haustier erstellen möchte (oder einen Fisch, oder ein KI-Auto)?
A: Um das Zusammenspiel zwischen Linksets und Charakteren zu unterstützen, empfehlen wir folgende Charakter, die für den allgemeinen Gebrauch vorgesehen sind.

• Menschen / menschenähnlich: CHARACTER_TYPE_A
• Wilde Tiere / Geländefahrzeuge: CHARACTER_TYPE_B
• Straßenfahrzeuge: CHARACTER_TYPE_C
• Sonstiges: CHARACTER_TYPE_D

Achtet darauf, dass das entscheidende Merkmal nicht der gewählte Charakter ist, sondern die Oberflächen, auf denen sie sich bevorzugt bewegen sollen - und wie schnell sie dabei sind. Zum Beispiel könnte man ein reitbares Pferd als Haustier ansehen, aber es ist wahrscheinlich besser, es als wildes Tier/Geländefahrzeug einzustufen, so dass es nicht versuchen wird, in die Häuser seiner Besitzer zu laufen. Ähnliches gilt, wenn ihr vorgefertigte Straßenbauelemente verkauft. Dann werdet ihr es wahrscheinlich bevorzugen, wenn diese einen hohen Begehbarkeit-Koeffizienten für die Typen A und C haben und einen niedrigen Koeffizienten für Typ B.

F: Was kann ich mit dem View/Test Fenster machen, wenn ich kein Pathfinding verwende?
A: Die Ansichten, die im View/Test Fenster zur Verfügung stehen, sind nicht nur nützlich für Pathfinding. Wenn ihr Walkables, Static Obstacles, Material Volumes und Exclusion Volumes betrachtet (aber nicht "Moveable Obstacles"), dann erhaltet ihr einen Einblick in die Physik-Engine. Dies ist derzeit die einzige verfügbare Methode in einem Second Life Viewer, mit der Second Life-Nutzer die realen physischen Darstellungen ihrer Objekte sehen können, was ein nützliches Werkzeug für die Optimierung der Physik eurer Region sein kann.

Wenn ihr euch zum Beispiel fragt, wie der Simulator ein Fahrzeug oder eine seltsame Sculpty-Wiese "sieht", die ihr gebaut habt, dann versucht dieses Linkset vorrübergehend in das Navmesh aufzunehmen, ein Re-Baking auszuführen und es anzusehen. Wir hoffen, dies in Zukunft noch mehr zu einer Funktion auszubauen.

Es gibt auch eine Einschränkung, die es zu beachten gilt: Die Visualisierung von Pathfinding berücksichtigt nicht den konvexen Radius eines Objektes, der intern als zusätzliches Toleranzelement bei Kollissionen verwendet wird. Aus diesem Grund können bestimmte Linksets etwas kleiner im Viewer erscheinen, als sie in der Engine sind.

Wir haben auch eine praktische Funktion in die Pathfinding Tools aufgenommen, mit der ihr direkt zu Objekten teleportieren könnt, für die ihr die Änderungsrechte habt.

Quelle: [LL Forum] - Pathfinding FAQ

Weitere Informationen (wenn auch schon etwas älter), hatte ich bereits zum Start von Pathfinding hier im Blog mal zusammengefasst. Das findet man unter folgendem Link:
>> Pathfinding ab heute im kompletten Main Grid von SL

Einige Infos von den Lindens zum Pathfinding

Es gibt inzwischen zwei Artikel bei Nalates Urriah, in denen Informationen von Linden Lab Mitarbeitern zur Pathfinding Einführung zu finden sind. Die ersten Infos stammen von Donnerstagmorgen (MESZ) aus einem Kommentar von Lorca Linden und der andere Artikel ist erst ein paar Stunden alt und berichtet von den Pathfinding Office Hours am Donnerstagabend. Den Kommentar von Lorca habe ich übersetzt, den Bericht zu den Office Hour zusammengefasst.

Ich bin zwar der Meinung, dass Linden Lab für solche Informationen besser einen eigenen Blogpost veröffentlichen sollte, aber das ist eben bis jetzt noch nicht passiert. Und deswegen bin ich ganz froh, wenigstens überhaupt ein paar Aussagen von Linden Mitarbeitern zu lesen, denn es liegt sicher nicht an der Einstellung genau dieser Lindens, dass LL bisher den Start von Pathfinding nicht offiziell bekanntgegeben hat.

Quelle: Nalates' Things & Stuff

Second Life Pathfinding Performance

Kommentar von Lorca Linden
Geschrieben am 08.08.2012 um 9:32pm
- Übersetzung -

Obwohl Lindens im Allgemeinen nicht in Resident Blogs posten, mache ich in diesem Fall eine Ausnahme. Erwartet aber nicht von uns, dass dies zur Gewohnheit wird.

Ich möchte zunächst Nalates danken, für die meiner Meinung nach unvoreingenomme Berichterstattung zum gesamten Pathfinding-Thema. Obwohl ich mit mehreren Aussagen aus dem "Tsunami"-Post (*) nicht einverstanden war, wurde uns damit bewußt gemacht, dass es Missverständnisse im Zusammenhang mit Pathfinding gab, die einer Klärung bedurften (insbesondere in Bezug der Auswirkungen auf die Performance) und dies war ein nützlicher Anhaltspunkt, die Bedenken der Bewohner aufzuzeigen, während wir uns noch in der Entwicklungsphase befanden.

Der Performance-Einfluss von 18%, auf den sich der Phoenix Viewer Blog bezogen hat, ist der schlimmste Fall, der eintreten könnte, was aber selten in der Praxis zu sehen sein wird - z.B. könnte man eine so große Auswirkung auf einer schlecht optimierten Region sehen, die hunderte von Pathfinding Charakteren beinhaltet, die alle gleichzeitig ausgeführt werden. Die durchschnittlich gemessenen (viewerseitigen) FPS im gesamten Grid waren gestern Abend 0,03 FPS höher, als am Abend davor. Die durchschnittliche serverseitige Performance war gridweit ebenfalls auf normalem Level vor und nach dem Aufspielen des Pathfinding Server Code. Die Crash-Rate von Regionen - ausgenommen ein paar holpriger Stunden während des Rollout - blieb niedrig. Alles zusammengenommen, soweit es das Lab sagen kann, hat sich Pathfinding in den allermeisten Situationen nicht negativ auf die Leistung oder Stabilität ausgewirkt.

Ich möchte auch klarstellen, dass die Auswirkungen auf einige Fahrzeuge nicht direkt im Zusammenhang mit Pathfinding stehen, sondern mit der zugrundeliegenden Physik und den Geländeoptimierungen, die Pathfinding erst ermöglichen und die auch Vorteile bringen, die über Pathfinding hinausgehen. Soweit wir das beurteilen können, ist nur ein kleiner Prozentsatz des bestehenden Content von diesem Physik-Upgrade betroffen.

Wir sind nicht der Ansicht, dass Pathfinding in vollem Umfang eingeführt wurde, solange die Pathfinding-Tools im Viewer nicht die Betaphase verlassen haben. Deshalb haben wir noch keine offizielle Ankündigung gemacht. Ich stimme zu, dass wir eine Überarbeitung unserer Pathfinding bezogenen Wiki-Seiten benötigen, denn ein Teil der Informationen dort wurde nicht aktualisiert, seit wir in der Alphahase waren. Wir planen in Kürze einen Blogpost zu veröffentlichen, in dem wir zu einigen verbreiteten Missverständnissen über Pathfinding aufklären werden, von denen wir gehört haben. Weiterhin planen wir auch die Aktualisierung der Anleitung für "Good Building Practices" ("Gute Baupraktiken"), so dass dies eine nützliche Ressource für Bewohner wird, die optimierte Inhalte erstellen wollen.

Wir verstehen, dass Pathfinding ein verwirrendes Thema sein kann und begrüßen die Bemühungen, die sich interessierte Residents machen, um die technischen Details zu verstehen. Wenn ihr irgendwelche brennenden Fragen zu Pathfinding habt, kommt bitte zu unserem User Group Treffen auf Pathtest1 (auf Aditi) am Donnerstag um 4:00pm SLT und stellt eure Fragen. Vor allem sind wir sehr gespannt, was ihr Bewohner mit den neuen Pathfinding Tools und den LSL Funktionen erstellen wollt!

Quelle: Kommentar von Lorca Linden zu "Second Life Pathfinding Performance"

(*): Mit "Tsunami"-Post ist ein Blogpost gemeint, den Nalates im Mai 2012 geschrieben hatte und in dem sie ihre Bedenken äußerte, dass die Pathfinding Funktionen nach der Einführung im Main Grid zu einem "flutwellenartigen" Zusammenbruch der Performance führen würde.

Quelle: Nalates' Things & Stuff

Pathfinding Meeting Week 32

Nun die Zusammenfassung der Pathfinding Office Hours von gestern Abend SLT bzw. heute Nacht MESZ. Teilgenommen hatten von LL die Herren Lorca Linden, Stinson Linden und Falcon Linden.

Performance
Zur Performance wurde gesagt, dass das Grid bisher mit durchschnittlicher Leistung läuft und keine Änderung gegenüber dem Zeitraum vor der Aufspielung von Pathfinding aufweist. Das bedeute auch, dass obwohl die meisten Regionen bisher nicht optimiert wurden, deren Performance deshalb nicht gesunken ist.

Was macht der Pathfinding Code?
Zu dieser Frage hat Falcon Linden eine längere Abhandlung gehalten. In Kurzform:
Zuerst wird das Navmesh aktualisiert, um die dynamischen Hindernisse zu erfassen. Die Zeit die dafür benötigt wird, wird gemessen. Diese Zeit wird dann verglichen mit der vorgegebenen Maximalzeit von 4ms (Fullprim Region) bzw. 1ms (Homestead Region). Wenn mehr Zeit benötigt wurde, werden soviele Update Schritte in den nachfolgenden Frames übersprungen, bis die durchschnittliche Zeit von 4ms oder 1ms wieder erreicht wird.

Diese Anzahl von übersprungenen Frames kann man sich im AI-Statistikbereich des Regions-Statistik Fensters ansehen. Bei einer optimierten Region sollte die Zeit für ein Update des dynamischen Navmesh nahe Null liegen und bisher haben wir nur in ganz wenigen Regionen gesehen, dass es damit ein Problem gab.

Als nächstes führen eine Suche möglicher Pfade für die Charaktere durch. Es gibt zusätzliche Begrenzungen für diesen Suchvorgang. Wenn wir über diese Zeit kommen, drosseln wir ab und versuchen es mit dem nächsten Frame. Wenn wir unter der Begrenzungszeit bleiben, erhöhen wir das Tempo für den nächsten Frame. Wir erhöhen die Anzahl der Suche nach Pfaden, wenn die Suche in jedem Frame < 1ms ist und wir verringern die Anzahl, wenn die Suche > 2ms pro Frame benötigt.

Danach bearbeiten wir die Physik der Charaktere. Wenn der Charakter dabei zu lange für diesen Vorgang benötigt (mehr als 50µs), überspringen wir danach einige Aktualisierungen.

Optimieren oder nicht?
Auch hier gab wieder Falcon Linden die Antwort. Er sagte, es kann nie schaden, Objekte auf Walkable oder Obstacle einzustellen. Dies kann eine Verbesserung bringen, oder auch nicht, abhängig von den Gegebenheiten. Als Optimierungsschritte empfiehlt Falkon dieses Vorgehen.

1. Schaut euch die Performance der Region an. Ist sie schlechter als vor Pathfinding? Wenn nicht, dann könnt ihr einfach für die Zukunft schon mal etwas optimieren.
2. Wenn die Performance schlechter ist, als vor Pathfinding, schaut euch das Fenster zur Sim Statistik an (Strg+Umschalt+1). Ist die AI Step Time hoch? Wenn ja, gibt es Skipped Silhouette Steps? Wenn auch dies der Fall ist, dann eine der beiden folgenden Möglichkeiten durchführen:

1. Optimiert euren Content, indem ihr so viele Objekte wie möglich auf statische Eigenschaften umstellt (Static Obstacle, Walkable, usw.).
2. Schaltet das dynamische Pathfinding aus.

Hier noch ein Ausschnitt des Bereiches aus dem Statistikfenster, von dem Falcon oben spricht:

Dazu sagte Lorca Linden, dass der zweite Punkt nicht generell notwendig ist. Denn die durchschnittliche Statistik des Grid seit der Umstellung zeige eigentlich, dass alles so schnell läuft, wie bisher.

Navmesh
Zum Thema Navmesh sagte Falcon Linden, dass die Ansicht der 3D Welt im View/Test Fenster bei aktivierten Checkboxen eine extrem genaue Darstellung der Physik ist, so wie sie auch die Physik Engine sieht, mit Ausnahme eines 10 cm Abstands bei Boxen. Dazu will er sich demnächst mal etwas genauer auslassen.

Probleme
Motor Loon, ein Anbieter von SL-Vehikeln, hat seine Region bereits komplett optimiert. Dabei ist ihm aufgefallen, dass Phantomprims in Linksets auf Solid gestellt werden. Ein weiteres Problem sind LSL Skripte in Objekten, die diese auf irgendeine Weise bewegen. Stellt man diese Objekte auf Static Obstacle, gibt es Skriptfehlermeldungen und die Funktion wird nicht mehr sauber ausgeführt. Also, keine Objekte auf Static stellen, die irgendwas irgendwie bewegen. (Das gilt auch für einige Posebälle, die beim Ändern der Avatar Position ihre eigene Lage verändern).

Problembehebung
Linden Lab will die Pathfinding Tools weiter verbessern und das Problem mit den Phantomprims in Linksets als nächstes angehen. Gibt es eine Skriptfehlermeldung und man weiß nicht, welches Objekt dieses erzeugt, kann man im Linksetfenster erstmal alles wieder auf Movable stellen und dann mit der "Halbierungsmethode" das Objekt suchen. Man stellt zunächst eine Hälfte auf Static Obstacle und schaut ob der Fehler auftritt. wenn nicht, steckt das entsprechende Objekt in der anderen Hälfte der Liste. Dann macht man in der Hälfte, in der das Objekt steckt, den nächsten Halbierungsversuch, usw. Mit dieser Methode hat man nach spätestens zwanzig Schritten das einzelne Objekt gefunden.

Der Rest von Nalates Artikel dreht sich um Erklärungen, warum dieser oder jener Fehler erst jetzt gefunden wurde. LL sagt, jeder hätte wochenlang Zeit gehabt, mögliche Fehler zu melden. Die Bewohner bei der Office Hour sagen, man teste nur die Dinge, die man selbst später richtig laufen haben möchte. Und da nicht so viele Leute an den Tests teilgenommen haben, wurden eben viele Fehler im Vorfeld nicht gefunden.

Quelle: Pathfinding Meeting Week 32

Weitere Infos zum neuen Pathfinding findet man in meinem Blogpost vom 8. August:
>> Pathfinding ab heute im kompletten Main Grid von SL

Pathfinding ab heute im kompletten Main Grid von SL

Eigentlich wollte ich zur Einführung von Pathfinding keinen eigenen Blogpost schreiben. Mein Land in SL ist einfach zu klein, um darauf etwas Sinnvolles mit den neuen Funktionen zu machen. Deshalb spiele ich nur ein bisschen damit rum und stelle nach und nach meine Objekte auf eine für mich logische PF-Eigenschaft um. Könnte ja sein, dass ein anderer Bewohner auf meiner Region einen automatischen Charakter erstellt und losschickt.

Der Grund, jetzt doch einen Blogpost zu schreiben, liegt an einigen übertrieben besorgten Meldungen, die im Bildzeitungsstil die Leute verunsichern. Der Ursprung ist ein Artikel aus dem Phoenix/Firestorm Blog, der durch weitere Interpretationen zu einigen Falschinformationen geführt hat. Nachdem ich nun gestern verschiedene Fragen per IM erhalten habe, schreibe ich mal meine Sicht der Dinge hier auf.

Ich bin zwar auch kein Experte was Pathfinding angeht, aber ich versuche alle Informationen in kleinen Kapiteln zusammenzutragen, die mir bisher zum Thema bekannt sind.

Pathfinding im ganzen SL Main Grid
Gestern, am 7. August, wurde Pathfinding auf die Hauptkanal-Regionen im Main Grid aufgespielt. Heute, zwischen 16 und 20 Uhr MESZ, folgen dann die restlichen Regionen in SL. Danach sollten alle Probleme, die im Zusammenhang von Regionswechseln mit getragenen Mesh-Attachments stehen, behoben sein. Denn dann laufen alle Regionen auf der neueren Havok 7.1 Physikengine.

Pathfinding und die Sim-Performance
Nachdem Pathfinding auf eine Region aufgespielt wurde, sind die neuen Skriptfunktionen, das dynamische Pathfinding (Navmesh und Region Rebaking) und die neue Physikengine aktiv. Solange dann keine geskripteten Charaktere das dynamische Pathfinding nutzen, sollte es auf der Region auch keine Änderung in der Performance geben.

Die Aussage: "Sobald Pathfinding auf der eigenen Region aktiv ist, wird es die Simleistung beeinflussen" ist Quatsch, was inzwischen genügend Leute bestätigen konnten, inklusive mir. Sollte dennoch jemand der Meinung sein, dass es einen Einfluss auf die Performance gibt, dann ist es auch möglich, das dynamische Pathfinding für die Region komplett abzuschalten. Die PF-Skriptfunktionen und die neue Physikengine bleiben dann allerdings weiter aktiv.

Dynamisches Pathfinding für eine Region abschalten
Dies kann nur vom Besitzer einer Region oder einer Person mit Estate Manager Rechten durchgeführt werden. Da im Phoenix Blog nur die hauseigenen Viewer beschrieben werden, beziehe ich mich hier auf den SL Beta Viewer 3.4.0 von LL, denn so wird es dann auch im offiziellen Viewer zu finden sein.

1. Sollte das Entwickler-Menü noch nicht geöffnet sein, dann dies mit Strg + Umschalt + Q erledigen (engl. "Development"-Menü).
2. Die Debug Konsole öffnen unter > Entwickler > UI > Regions-Debug-Konsole.
3. In das Konsolen Fenster nun set dynamic_pathfinding false eingeben und Return drücken.
4. Die Region neu starten.

Dieser Vorgang kann auch wieder umgekehrt werden, indem man oben bei Schritt Nr. 3
set dynamic_pathfinding true eingibt.

Konsole zum Abschalten des Pathfinding öffnen (Klick für großes Bild)

Pathfinding und Objekteintritt
Möchte man nur auf einer Parzelle die Pathfinding Charaktere blockieren, ohne dafür die ganze Region zu deaktivieren, dann kann man in der Land-Info unter "Optionen" den Objekteintritt für die Parzelle deaktivieren. Damit wird das Navmesh an den Rändern der Parzelle unterbrochen und es können sich keine Charaktere in die Parzelle hineinbewegen. Es gibt dazu zwar noch einen Bugreport in der Jira, aber der wird früher oder später auch behoben sein.

Das Characters-Fenster (Klick für großes Bild)

Pathfinding und die Optimierung
Jeder, der Baurechte und ein paar eigene Prims auf einer Region oder Parzelle hat, kann Pathfinding Charaktere erzeugen, Linksets ändern und das Navmesh neu berechnen. Dementsprechend kann auch jeder seine eigenen Prims optimieren. Die notwendigen Pathfinding Tools dazu, sind im Viewer-Menü unter 
> Bauen > Pathfinding zu finden.

Das View/Test-Fenster

Es gibt drei Hauptfenster mit den folgenden Funktionen:

• Linksets: Hier können die Eigenschaften aller eigenen Objekte einer Region oder Parzelle an die Erfordernisse für Pathfinding Charaktere angepasst werden. Dieses Fenster ist das Hauptwerkzeug in Verbindung mit dem Vorhaben "Optimieren einer Region".
• Characters: Hier werden alle Pathfinding Charaktere angezeigt, die sich auf der Region oder Parzelle befinden. Damit hat man einen Überblick zur Anzahl der Charaktere, sowie über deren Verbrauch an Skriptzeiten. Bei maximal 4ms gesamter Skriptzeit, werden Pathfinding Berechnungen übersprungen, um die Skriptzeit nicht weiter ansteigen zu lassen. Allerdings sollte man als Vergleich auch die angezeigte Skriptzeit in der Viewer-Statistik heranziehen (Strg+Umschalt+1), denn die Charakter CPU Zeiten sind Spitzenwerte, die nicht permanent verbraucht werden.
• View / Test: Damit kann man das Terrain (Simboden) und alle Objekte darauf, entsprechend ihrer Funktion beim Pathfinding, eingefärbt anzeigen lassen. Über Checkboxen lassen sich die unterschiedlichen Eigenschaften auswählen So erhält man einen schnellen Überblick darüber, welche Flächen begehbar sind (Navmesh) und welche Objekte welche Eigenschaft für die Charaktere haben.

Das Linksets-Fenster (Klick für großes Bild)

Optimierung:
Bei meiner Parzelle wurde meinen Prims automatisch nach der Aufspielung von Pathfinding unterschiedliche Eigenschaften zugewiesen. Zum Beispiel wurden alle Prims oder Linksets, die ein Skript enthalten haben, auf "Movable Obstacle" gesetzt. Da dies aber völlig überbestimmt ist, sollte man hier mit der Optimierung beginnen.

Um nun eine Region oder Parzelle zu optimieren, kann man vielen Objekten eine neue Eigenschaft zuweisen, sofern es Sinn macht. Da die Pathfinding Tools noch nicht in die deutsche Sprache übersetzt wurden, haben diese Eigenschaften noch englische Bezeichnungen.

Mögliche Eigenschaften von Objekten:

• Walkable - Dies weist man Objekten zu, auf denen sich Charaktere fortbewegen sollen. Der Simboden ist standardmäßig auf Walkable, bei Prims muss man das manuell vornehmen (z.B. den Boden von Häusern oder die Lauffläche auf Brücken). Die Kombination aus Simboden und Walkable Objekten ergibt dann das begehbare Navmesh.
• Static Obstacle - Das kann man allen Objekten zuweisen, die sich nicht bewegen und die für Charaktere ein Hinderniss darstellen sollen. Das kann man z.B. Hauswänden, Möbeln, Parkbänken, Laternen, usw. zuweisen. Im Grunde allem, was sich nicht irgendwie bewegt. Mit der Umstellung von Movable Obstacle auf Static Obstacle, kann man sein Land schon ein gutes Stück optimieren.
• Movable Obstacle - Dies weist man nur Objekten zu, die ein Hindernis für Charaktere darstellen sollen und die sich zusätzlich bewegen. Das können Türen in einem Haus sein, oder ein Vehikel, das auf dem Grundstück steht, oder ein geskriptetes Tier (z.B. ein Breedable). Hier sollte man darauf achten, dass wirklich nur Objekte, die sich auch bewegen, auf Movable Obstacle stehen.
• Movable Phantom - Diese Eigenschaft haben alle Objekte automatisch erhalten, die schon vor Pathfinding auf Phantom gesetzt waren (z.B. Bäume oder Wasser in einem Pool). Objekte unter Movable Phantom haben keinen Effekt auf Pathfinding Charaktere und sind neben der Eigenschaft "Static Obstacle" die zweite Einstellung, die man zum Optimieren der Landperformance anwenden sollte. Das "Phantom" in der Bezeichnung bedeutet in diesem Fall nicht, dass das Objekt für Avatare Phantom ist, sondern nur für die PF-Charaktere. Das heißt, auch eine Straße kann Moveable Phantom sein und man kann trotzdem mit einem Vehikel darauf fahren.
• Material Volume - Dies ist nur eine Hilfseigenschaft, um die Bewegung von Charakteren zu beeinflussen. Man kann damit zum Beispiel in hohem Gras ein durchsichtiges Phantomprim platzieren und einen langsamen Bewegungskoeffizient dafür vergeben. Dann werden Charaktere langsamer, sobald sie in das hohe Gras laufen und mit dem Phantomprim kollidieren. Für normale Prims auf dem Land ist diese Eigenschaft eher unwichtig.
• Exclusion Volume - Diese Eigenschaft kann man ebenfalls einem durchsichtigen Phantomprim geben. Der Raum, der von diesem Prim eingenommen wird, ist für Pathfinding Charaktere tabu, das heißt, dorthin können sie sich nicht bewegen.

Pathfinding und geskriptete Objekte:
Beim Umstellen von Objekten mit Skripten auf "Static Obstacle" sollte man vorsichtig sein. Wenn durch das Skript das Objekt bewegt, gedreht oder in seiner Größe verändert wird, dann kommt es häufig zu Skriptfehler Meldungen. Statische Objekte schneiden bildlich gesehen ein Loch in das Navmesh, auf dem sich die Charaktere bewegen. Damit können diese dann nicht über oder durch diese Objekte laufen. Versucht nun ein Skript, die Form oder Position dieser Objekte zu ändern, wird das vom Pathfinding Code verhindert, da sonst das schon berechnete Navmesh fehlerhaft sein würde. Objekte, die in diesem Fall eine Fehlermeldung ausgeben, sollten deshalb auf "Moveable Obstacle" oder "Phantom Obstacle" umgestellt werden.

Pathfinding-Optimierungsschritte
Zum Optimieren öffnet man das Linksets-Fenster im Viewer. Steht man auf seinem eigenen Land, erhält man eine Liste mit allen Objekten, die vom Pathfinding erfasst werden. Von links nach rechts findet man die folgenden Spalten in der Anzeige:

• Name - Name des Objekts
• Description - Inhalt des Beschreibungsfeldes des Objekts
• Owner - Besitzer des Objekts
• Impact - Anzahl der verbrauchten Prims für das Land (Land Impact)
• Distance - Entfernung des Objekts vom Avatar
• Linkset use - Eigenschaft des Objekts für Pathfinding-Charakter
• A% bis D% - Bewegungskoeffizient für die verschiedenen Charaktertypen

Wie ich im vorherigen Abschnitt schon beschrieben habe, sollte man sich vor allem die Objekte ansehen, die auf Moveable Obstacle stehen. Dazu am besten die Liste nach dieser Eigenschaft sortieren, indem man einmal auf die Registerkarte "Linkset use" klickt. Wo immer es Sinn macht, sollte man Moveable Obstacle auf Static Obstacle oder Moveable Phantom umstellen.

Die Schritte zum Ändern einer Eingenschaft sind:

1. Eintrag in Liste auswählen.
2. Ganz links unten im Fenster die gewünschte Eigenschaft unter "Choose linkset use..." auswählen.
3. Ganz rechts unten im Fenster auf "Apply changes" klicken. Das muss nach jeder einzelnen Änderung einer Eigenschaft gemacht werden, bevor man den nächsten Eintrag aus der Liste auswählt. Allerdings kann man auch mehrere Einträge gleichzeitig ändern. Wichtig ist nur, immer mit Apply changes das Ganze auch abzuschließen.
4. Nun sollte eine Meldung erscheinen, die darüber informiert, dass das Navmesh nach dieser Änderung nicht mehr aktuell ist.
5. Um das Navmesh zu aktualisieren, muss man am unteren Fensterrand des Viewers auf den "Rebake Region"-Button klicken. Dieser Button ist dort zu finden, wo sonst auch der "Aufstehen"-Button erscheint, wenn der Avatar irgendwo sitzt.

Hier kann man die drei Pathfinding Funktionsfenster öffnen

Wenn man in mehreren Durchläufen umstellen will, sollte man nicht nach jedem einzelnen Vorgang ein Rebake Region durchführen, denn das zieht die Region-FPS kurzzeitig nach unten. Macht man das zu oft hintereinander, könnten sich andere Bewohner oder Besucher auf der Region genervt fühlen. Also am besten, alle Änderungen vornehmen, die man machen möchte und dann erst Rebaken.

Sobald man auf  "Rebake Region" klickt, wird der Button halb durchsichtig. Solange er noch in diesem Zustand zu sehen ist, wird das Navmesh im Hintergrund berechnet. In dieser Zeit sollte man keine weiteren Änderungen an Linksets durchführen oder neue Charaktere rezzen/erstellen.

Pathfinding Optimierungsbeispiel
Ein klassisches Beispiel zur Optimierung wäre ein Haus mit Einrichtungsgegenständen. Häuser können nur optimiert werden, wenn sie Modify, also änderbar sind. Vor der Änderung sollte man die Verlinkung des Hauses aufheben, aber alle Prims ausgewählt lassen. Dann die Strg-Taste gedrückt halten und den Fussboden, sowie die Tür-Prims abwählen und anschließend den Rest des Hauses wieder verlinken.

Nun vergibt man die folgenden Eigenschaften:

• Fussboden: Walkable
• Tür: Moveable Obstacle
• Wände, Treppen und Einrichtung: Static Obstacle
• Hat man ein Kaminfeuer: Moveable Phantom

Pathfinding und Viewer
Das Ein- und Ausschalten von Regionen, sowie das Erstellen von Pathfinding Charakteren (Skripte) kann man in jedem Viewer durchführen. Die Pathfinding Tools mit den verschiedenen Fenstern, stehen allerdings bisher in nur wenigen Viewern zur Verfügung.

Diese sind (Stand 14. August 2012):

• Second Life Beta Viewer 3.4.0
• Second Life Development Viewer 3.4.1
• Pathfinding Project Viewer - (eigentlich veraltet, geht aber noch)
• Nirans Viewer 1.48 - (Einschränkung, dass das Navmesh nicht angezeigt werden kann)
• Zen Viewer 3.3.5.3 - (Einschränkung, dass das Navmesh nicht angezeigt werden kann)

Pathfinding und die Skripte
Die Charaktere, von denen ich immer spreche, sind 3D-Objekte, die mit den neuen Pathfinding Skriptfunktionen verschiedene Bewegungen oder Handlungen auf Regionen ausführen können. Diese Objekte können aus Prims, Sculpties oder Meshes gebaut sein. Bewegen können sie sich nur auf Simboden (SL-Land) oder auf Prims, denen die Eigenschaft "Walkable" zugewiesen wurde. Die Kombination aus Simboden und Walkable Prims nennt man "Navmesh". Auf Wasser können sich Charaktere nicht bewegen, da es dort schlicht kein Navmesh gibt.

Hier eine Liste der bisher verfügbaren Charakterfunktionen. Unter dem Link der jeweiligen Funktion findet man immer am Ende der Seite ein Beispielskript, das man zum Testen verwenden kann.

• llEvade - Damit versucht ein Charakter, sich vor einem Avatar oder einem anderen Objekt zu verstecken.
• llFleeFrom - Damit hält ein Charakter eine bestimmten Abstand zu einem bestimmten Punkt ein. (Achtung! Hier fehlt beim Beispielskript das llCreateCharacter nach dem state_entry(). Am besten diese Zeile von einem anderen Skript reinkopieren).
• llNavigateTo - Gibt einem Charakter vor, sich zu einem bestimmten Punkt innerhalb der Region oder in angrenzenden Regionen zu bewegen. (Achtung! Hier ist die Charaktergeschwindigkeit im Beispielskript zu hoch. Ich empfehle generell eine Geschwindigkeit von ca. 15).
• llPatrolPoints - Hiermit lassen sich verschiedene Koordinatenpunkte bestimmen, zwischen denen der Charakter patroulliert, also quasi Wache schiebt.
• llPursue - Mit dieser Funktion verfolgt ein Charakter einen Avatar oder ein anderes Objekt.
• llWanderWithin - Damit bewegt sich ein Charakter innerhalb einer Kreisfläche um einen bestimmten Mittelpunkt herum.

Es gibt auch noch weitere LSL-Befehle, die direkt mit Pathfinding zu tun haben, aber nicht direkt einen Charakter steuern. Alle LSL-Befehle sind auf der folgenden Wiki-Seite zu finden:
>> Pathfinding LSL functions

Pathfinding und Charaktertypen
Es gibt vier verschiedene Charaktertypen, die mit A, B, C und D gekennzeichnet sind. Als Beispielanwendung wurde in der Wiki diese vorläufige Zuweisung gegeben:

• A = Mensch
• B = Kreatur
• C = Roboter
• D = Andere

Jedem der Charaktere kann man einen anderen Bewegungskoeffizienten zuweisen. 100% bedeutet dabei keine Einschränkung, bei 50% wird der Charakter um die Hälfte abgebremst, usw. Damit ist es möglich, in "schwierigem" Gelände einen Charakter so zu verlangsamen, dass es realistisch wirkt. Eine sinnvolle Anwendung wird aber wohl erst ersichtlich, wenn man einige Charaktere in Aktion beobachtet hat und der Meinung ist, hier oder da sollten sie sich langsamer bewegen.

Charakter Land Impact:
Ein Pathfinding Charakter, der über eines der Charakter-Skripte erzeugt wurde, belegt mindestens 15 Prims Land Impact. Dabei ist es egal, ob der Charakter nur aus einem Prim besteht, oder tatsächlich aus einem Linkset mit 15 Prims. Sobald dann bei einem Charakter eine der ausgewerteten Land Impact Kosten (Server, Physik, Download) größer wird als 15, wird auch der Land Impact größer als 15 Prims.

Pathfinding und die offenen Probleme
Es gibt im Augenblick noch einige Probleme im Zusammenhang mit Pathfinding. Diese sind in den aktuellen Release Notes am Ende der Liste zu finden. Ich habe die Problemliste seit dem Start der Alpha Phase im Beta Grid verfolgt. Gegenüber den ursprünglichen Fehlern ist die heutige Liste bereits sehr klein geworden. Und einiges lässt sich auch nur nach der Einführung im Main Grid beheben, denn im Beta Grid werden weder Vehikel Rennen ausgetragen, noch gibt es dort 40 Avatare gleichzeitig auf einem Sim.

Hier ein paar der gröbsten Probleme, die zur Zeit noch nicht behoben wurden:

• Schnelle Vehikel können sich mit dem Simboden verhaken und bleiben stecken.
• Verschiedene kleine physische Objekte können durch den Simboden fallen.
• SVC-8048 - Vehikel verhalten sich unberrechenbar auf PF-Regionen.
• PATH-796 - Ein verlinktes Flexi Prim als Child eines Nicht-Flexi Prim, ändert das Flexi-Prim auf Nicht-Phantom.
• PATH-651 - Pathfinding Charaktere bleiben einfach stehen, wenn sie in eine Region kommen, die dynamisches Pathfinding abgeschaltet hat.
• PATH-536 - Man kann Objekte, die in das Navmesh integriert sind, als Attachment tragen, was das Navmesh des Objektes zu einem Reset veranlasst.
• PATH-345 - Es wird kein path_update durchgeführt, wenn ein Charakter in Richtung Norden oder Osten in eine neue Region wechselt.

Sonstiges

Toolfenster-Buttons:
Die beiden Pathfinding Tool Fenster "Characters" und "Linksets" enthalten im unteren Bereich eine Reihe von nützlichen Buttons. Damit kann man für einen ausgewählten Listeneintrag die folgenden Dinge durchführen:

• Take - Das Objekt wird in das Inventar aufgenommen und auf dem Land entfernt.
• Take Copy - Eine Kopie des Objekts wird in das Inventar aufgenommen. Das Original bleibt aber auf dem Land.
• Teleport me to it - Der eigene Avatar wird zu dem ausgewählten Objekt teleportiert.
• Return - Das Objekt wird seinem Besitzer zurückgeschickt, auch wenn es jemand anderem gehört.
• Delete - Das Objekt wird gelöscht, ist dann aber noch im Papierkorb vom Inventar zu finden.
• Checkbox: Show beacon - Es wird eine farbiges Achsenkreuz im Nullpunkt des ausgewählten Objekts angezeigt.
• Checkbox: Show physics capsule - Zeigt einen blauen Ballon, der den physikalischen Kolissionskörper des Charakter darstellt. Oft befindet sich der größte Teil dieses Ballons im Inneren des Objekts.

Menüeinträge bei rechter Maustaste:
Möchte man ein ganz bestimmtes Objekt oder einen PF-Charakter auf seine Eigenschaften hin überprüfen, kann man dieses auch mit der rechten Maustaste anklicken. Im Menü erscheint dann, je nachdem ob es ein Objekt oder Charakter ist, entweder der Menüeintrag "Show in Linksets" oder "Show in Characters". Geht man auf den Eintrag, öffnet das jeweilige Fenster und das ausgewählte Element wird hervorgehoben und kann direkt bearbeitet werden. Dies ist vor allem ganz nützlich bei Linksets, deren Liste im Linkset-Fenster ziemlich lang sein kann.


Links zu Pathfinding (alle englisch):
>> Pathfinding Quick Start Guide
>> Pathfinding Tools in the Second Life Viewer
>> Pathfinding NavMesh
>> Pathfinding LSL functions
>> Release Notes von Pathfinding aus der Woche der gridweiten Aufspielung

Weitere Informationen gibt es in meinem Blogpost vom 10. August zur Pathfinding Einführung:
>> Einige Infos von den Lindens zum Pathfinding

Update 09.08.2012:

• Neuer Abschnitt: "Pathfinding und Objekteintritt"
• Neuer Abschnitt: "Pathfinding Optimierungsbeispiel"
• Neuer Unterabschnitt: Sonstiges > "Menüeinträge bei rechter Maustaste"
• Neuer letzter Absatz im Abschnitt: Pathfinding-Optimierungsschritte > "Sobald man auf  "Rebake Region" klickt..."
• Geänderter Text im ersten Absatz des Unterabschnitts: Pathfinding und die Optimierung > Optimierung: "Zum Beispiel wurden alle Prims oder Linksets, die ein Skript enthalten haben, auf "Movable Obstacle" gesetzt. Da dies aber völlig überbestimmt ist, sollte man hier mit der Optimierung beginnen..."

Update 14.08.2012:

• Neuer Unterabschnitt: Pathfinding und die Optimierung > "Pathfinding und geskriptete Objekte"
• Neuer Unterabschnitt: Pathfinding und Charaktertypen > "Charakter Land Impact"
• Zen Viewer zum Abschnitt "Pathfinding und Viewer" hinzugefügt

Anmerkung:
Das ist jetzt ein erster schneller Entwurf einer deutschen Hilfe für Pathfinding. Ich habe sicher vieles nicht erwähnt, einiges vergessen und evtl. auch was falsches geschrieben. Ich werde versuchen, diesen Blogpost im Laufe der Zeit zu erweitern und zu verbessern, so dass das langsam zu etwas Brauchbarem wird. Wenn jemand gerne ein bestimmtes Thema hier noch aufgenommen haben möchte, oder einen Fehler gefunden hat, oder eine wichtige Ergänzung hätte, würde ich mich über eine Meldung in den Kommentaren freuen.