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.