Willkommen im Graceful Algorithms Team!
Als Experiment haben wir beschlossen, „Tagebücher“ von Entwicklern zu führen, in denen wir Erfahrungen austauschen und einige interessante Ergebnisse unserer Experimente hervorheben werden. Dies ist unser Debütartikel zum "Pathfinder 3D" -Projekt - eine Bereicherung für die Unity-Spiel-Engine, mit der Sie nach Pfaden im dreidimensionalen Raum suchen können. Darin werden wir über den Weg vom Ursprung der Idee zu einem vollwertigen Produkt und über einige der Probleme sprechen, auf die wir gestoßen sind. Dieses Material ist nützlich für Personen, die ihr Projekt starten und in Zukunft unterstützen möchten, sowie für Personen, die eine Suche nach einem Pfad im Weltraum durchführen möchten.
Ein Team von zwei Personen begann mit der Arbeit an dem Vermögenswert. Der erste hatte einige Entwicklungen, die es ermöglichten, den kürzesten Weg in komplexen Graphen so schnell wie möglich zu finden, um in Echtzeit zu arbeiten, und den Wunsch, eine praktische Anwendung für sie zu finden. Der zweite hatte einige Erfahrungen mit Unity und suchte nach einer Idee für ein Startup. Da sie oft miteinander kommunizierten, ist es nicht verwunderlich, dass irgendwann die Idee entstand, einen Vermögenswert für die Suche nach einem Pfad im dreidimensionalen Raum zu schaffen.
Bei der Untersuchung des Unity-Asset-Katalogs wurden viele Lösungen gefunden, um den Pfad im zweidimensionalen Raum zu finden, nicht jedoch im dreidimensionalen. Es wurde deutlich, dass dies eine großartige Gelegenheit war, in den Markt für Unity-Software-Add-Ons einzusteigen, insbesondere angesichts der Sichtbarkeit und Unterhaltung des erwarteten Ergebnisses.
Ziel war es, die Suche nach einem Pfad im dreidimensionalen Raum und die typischen Fähigkeiten bestehender Lösungen zum Auffinden eines Pfades im zweidimensionalen Raum direkt zu implementieren. Wir begannen zu arbeiten: Einer entwickelte direkt den Pfadsuchmechanismus, die zweiten Klassen und Methoden zur Verwaltung des Pfadsuchprozesses, Konfigurationsschnittstellen, Testszenen, Dokumentation und den Projektstandort und war auch an der Registrierung und Einrichtung von Servicekonten beteiligt, die für den Verkauf des Assets erforderlich sind.
Kurz nach Arbeitsbeginn wurde klar, dass das Team einige gemeinsame Ressourcen benötigt, um sich Notizen zu machen: eine Liste der Aufgaben und Probleme, die gelöst werden mussten, Informationen über die getroffenen Entscheidungen, Ideen und Forschungsergebnisse, die für die Zukunft interessant waren. Nachdem wir die vorhandenen Lösungen analysiert hatten, stoppten wir bei
Trello aufgrund seiner Funktionalität, Einfachheit, Bequemlichkeit und eines angenehmen Erscheinungsbilds. Wie die Praxis gezeigt hat, ist dieser Service für kleine Teams sehr praktisch. Wenn das Team mehr als 5 Personen hat, empfehlen wir die Verwendung eines vollwertigen Projektmanagementsystems.
Als Nächstes beschreiben wir die Entscheidungen, die während der Entwicklung der ersten Version des Assets getroffen wurden, und die Logik, die wir bei ihrer Entscheidung befolgt haben. Menschen, die Erfahrung mit Unity haben und mit Wegfindungsalgorithmen vertraut sind, werden sofort verstehen, wo in Zukunft Probleme auftreten werden. An diesen Stellen haben wir eine einfache Lösung verwendet, um die Entwicklungszeit bis zum Eingang der ersten funktionierenden Version des Assets zu verkürzen und nicht ins Stocken zu geraten, da die Begeisterung begrenzt und unbeständig ist. Daher haben wir uns mit einem der häufigsten Gründe für die Schließung solcher Startups befasst, aufgrund derer viele Projekte sterben, ohne geboren zu werden. Alle Problembereiche wurden nach Veröffentlichung des Vermögenswerts korrigiert.
Um den Pfad zu finden, wurde der
A * -Algorithmus
(A-Stern) aufgrund seiner hohen Betriebsgeschwindigkeit in großen offenen Räumen gewählt. Die meisten Pfadsuchalgorithmen arbeiten mit Graphen, die durch eine diskrete Matrix dargestellt werden. Es wäre möglich, diese Matrix im Voraus zu konstruieren, aber der einmalige Prozess ihrer Konstruktion im dreidimensionalen Raum mit Hindernissen sah diese Zeit als ziemlich schwierige Aufgabe an. Darüber hinaus war nicht klar, wie dies ohne Leistungseinbußen zu tun ist, da zum Zeitpunkt des Beginns der Arbeit an dem Asset keine Erfahrung mit Hintergrundprozessen und Multithreading in Unity sowie mit Multithreading im Allgemeinen vorhanden war. Der Graph wurde in Echtzeit erstellt, indem der Raum mit physikalischen Strahlen (Physics.BoxCast) in Suchrichtung untersucht wurde. Die gefundenen Trajektorien wurden auf gebrochene mit weniger Zwischenpunkten reduziert und dann durch Splines geglättet.
Die Hauptschwierigkeit war die Unmöglichkeit, die physikalischen Methoden der Engine asynchron zu verwenden, da sie ausschließlich im Haupt-Thread arbeiten können. Bei nicht zu komplexen Szenen hatte die gleichzeitige Verwendung der Suchfunktion durch nicht mehr als zwanzig Agenten keinen signifikanten Einfluss auf die Bildrate. Um seltene starke FPS-Verluste zu vermeiden, wurde die Rechenlast mithilfe von Coroutinen zeitlich verteilt. Dies verlangsamte die Suche, jedoch nicht wesentlich.
Bevor Sie ein Asset zur Moderation einreichen, müssen Sie den Code ordnen und eine detaillierte Dokumentation gemäß den
Anforderungen erstellen, Support-E-Mails registrieren und konfigurieren. Es ist auch ratsam, eine Projektwebsite zu erstellen, auf der Entwicklungsnachrichten und Demos bequem angezeigt werden. Dies ist sowohl während der Moderation als auch bei der Untersuchung Ihres Vermögens durch den Benutzer vor dem Kauf ein großes Plus. Hosting- und Postdienste wurden von uns bei
BeGet bestellt , da es zu diesem Zeitpunkt die günstigsten Angebote bot und uns 1000 R / Jahr kostete.
Die Asset-Moderation dauerte 22 Tage und verlief zum ersten Mal, da wir uns sehr sorgfältig mit der Dokumentation und dem Design der Asset-Seite im Unity Store befasst haben. Nach der Veröffentlichung fiel das Asset sofort auf den ersten Platz in der Kategorie Scripting / AI. Von diesem Moment an gingen Briefe an die Support-Mail, in denen um Hilfe bei der Lösung bestimmter Probleme gebeten wurde. Manchmal ein paar pro Tag, manchmal nicht einen Monat. Wenn Sie durchschnittlich sind, dann haben 2 Personen einen Monat lang Fragen gestellt, deren Korrespondenz insgesamt 2-3 Stunden dauerte. Nicht so sehr, aber es sollte bedacht werden, dass Sie unabhängig von Ihrer aktuellen Arbeitsbelastung sehr schnell reagieren müssen, damit verärgerte Benutzer keine schlechten Bewertungen über das Produkt schreiben, sondern im Gegenteil, wenn Sie von Qualitätsunterstützung begeistert sind, positive hinterlassen. Außerdem werden viele Fragen an die E-Mail gestellt, z. B. "Funktioniert Ihr Asset, wenn ...". Solche Briefe sollten auch nicht ignoriert werden, da dies ein potenzieller Käufer ist, der gehen kann.
Als Beschwerden von Erstkäufern eingingen, wurde klar, dass viele Benutzer Assets für komplexe Szenen verwenden, die die Konfiguration eines Labyrinths oder eines anderen verbundenen Hohlraums haben. In solchen Projekten war unser Pfadfindungsschema, das auf Kollisionsprüfungen und sogar im Hauptstrom basiert, nicht effektiv genug. Aus diesem Grund haben wir mit der Implementierung der frühen Konstruktion des Diagramms begonnen, damit der Pfad im Seitenstrom gesucht werden kann, ohne Physik zu verwenden und auf Szenenobjekte zuzugreifen.
Die Diskretisierung des dreidimensionalen Raums zerlegt ihn in Würfel. Das Speichern von Informationen zu allen Partitionswürfeln ist redundant und sehr speicherintensiv. Daher ist es logisch, nur die Koordinaten unpassierbarer Zellen zu speichern, was getan wurde.
Spielhindernisse sind polygonale Figuren und bestehen aus Dreiecken. Um Hindernisse im Suchdiagramm zu berücksichtigen, müssen Sie alle Würfel der Partition finden, die ein Dreieck eines Hindernisses schneiden. Bereits zu diesem Zeitpunkt wurde die Möglichkeit geschaffen, Hindernisse dynamisch zu entfernen und der Bühne hinzuzufügen, und es wurden nicht nur die Koordinaten der besetzten Würfel gespeichert, sondern auch die Kennungen der darin enthaltenen Hindernisse. Jetzt ist es möglich, vor Beginn des Spielprozesses ein Navigationsdiagramm zu erstellen. Aufgrund der Eliminierung einer großen Anzahl komplexer Berechnungen bei der Suche nach einem Pfad können mehr als zweihundert Agenten es gleichzeitig erstellen, ohne die Leistung zu beeinträchtigen.
Ein weiteres uns bekanntes Problem machte sich ebenfalls bemerkbar: Der A * -Algorithmus und seine Modifikationen funktionieren auf engstem Raum in Hochleistungsgraphen äußerst schlecht. Da ihr Algorithmus die Richtung der Route zur Annäherung an den Zielpunkt bevorzugt, verlangsamte jeder zum Ziel führende Deadlock die Suche nach dem Pfad erheblich, da der Algorithmus vor der Wahl einer anderen Richtung der „Keimung“ zunächst den gesamten Raum innerhalb der Sackgasse „ausfüllt“.
In solchen Situationen erweist sich der
Wellensuchalgorithmus (Lee-Algorithmus) aufgrund der
geringeren Anzahl von Operationen, die erforderlich sind, um den Raum zu „füllen“, als sehr effektiv. Daher wurde es alternativ zum Vermögenswert hinzugefügt. Beim Testen auf einer Bühne, die ein Labyrinth ist, wurde die Suchzeit für den Pfad um mehr als das 30-fache reduziert.
Um die vorläufige Verarbeitung der Szene zu beschleunigen und den Pfad zum Asset zu finden, wurde die Möglichkeit der parallelen Ausführung von Prozessen hinzugefügt. Die Parallelitätseffizienz war jedoch äußerst gering, da bei der Arbeit mit einem Container, in dem die Koordinaten der belegten Zellen gespeichert sind, die Flüsse synchronisiert werden müssen, die mithilfe von ausgeführt wurden Mutexe, da wettbewerbsfähige Sammlungen und viele andere Tools zur Gewährleistung einer effizienten Synchronisierung nur im .NET Framework 4.5-Standard und in Unity implementiert wurden, wurde die .NE-Version bis zur Version 2018 verwendet. T Framework 3.5. Wir haben versucht, dieses Problem mit den verfügbaren Tools zu lösen, aber sie hatten eine sehr mittelmäßige Leistung und wir haben das gewünschte Ergebnis erst nach dem Wechsel zur Unity-Version 2018 erhalten. Die Verwendung wettbewerbsfähiger Sammlungen eröffnete auch die Möglichkeit, den dynamischen Wandel der Hindernisse in der Szene zu realisieren.
Zu einem bestimmten Zeitpunkt kam es im Team zu Meinungsverschiedenheiten hinsichtlich der Gewinnverteilung, und eine dritte Person trat dem Team bei, die ein System zur Bewertung des Zeitaufwands jedes Teammitglieds einführte und sich auch mit Code-Inspektionen und -Tests befasste, wodurch die Qualität des Produkts erheblich verbessert wurde.
Das derzeitige System zur Schätzung der Zeitkosten wird in Form einer Excel-Tabelle erstellt und ist ein automatisiertes System, bei dem einmal im Monat Informationen zu Verkäufen und Aufgaben eingegeben werden müssen, die im letzten Monat ausgeführt wurden. Die Teammitglieder müssen bewerten, wie viel Zeit sie zur Lösung eines bestimmten Problems benötigen würden. Bei der Beurteilung der zeitlichen Komplexität von Aufgaben wird daher die Geschwindigkeit jedes Teilnehmers berücksichtigt. Eine abnormale Überschätzung oder Untertreibung durch einen der Teilnehmer wird sofort aus den gesammelten Statistiken seiner früheren Bewertungen ersichtlich. In Ermangelung einer zufriedenstellenden Erklärung wird dieses Problem vom gesamten Team entschieden. Dieser Ansatz erwies sich für sechs Monate als gut und ermöglichte es, interessante Statistiken zu sammeln. Wir haben keine fertige kostenlose Lösung gefunden, die die beschriebenen Funktionen bietet. Für kleine Teams erscheint uns daher die Implementierung in Form von Excel-Tabellen derzeit optimal. Bei relativ großen Teams müssen Sie höchstwahrscheinlich Ihre Datenbank entwerfen, den Serverteil und den Client entwickeln oder eine Erweiterung für eines der vorhandenen Projektmanagementsysteme implementieren.
Zusammenfassend. Seit Beginn der Entwicklung ist ein Jahr bis zur ersten Version mit der minimal erforderlichen Funktionalität und ausreichenden Leistung für den Einsatz in realen Projekten vergangen. Weitere sechs Monate wurden für die Verbesserung der Leistung und die Implementierung von Multithread-Arbeiten des Assets aufgewendet. Derzeit haben wir die Zeitkosten für dieses Projekt auf 1065 Mannstunden geschätzt (dies ist eine eher optimistische Schätzung), und der durchschnittliche Gewinn für den Monat beträgt 9,5 t. Es ist leicht zu berechnen, dass die durchschnittlichen Kosten einer Arbeitsstunde derzeit etwa 160 Rubel betragen, was nicht so viel ist. Die Hauptsache bei dieser Veranstaltung ist jedoch die Erfahrung, die jeder Teilnehmer gesammelt hat. Einschließlich Teamwork-Erfahrung und Erfahrung im Support von Softwareprodukten. Das Projekt kann als erfolgreich angesehen werden.
Jetzt hat unser Team begonnen, zusätzliche nützliche Funktionen zu implementieren: Überprüfung der algorithmischen Erreichbarkeit; die Fähigkeit, Spielobjekte Portalen zuzuweisen; dynamische Hindernisunterstützung; Lokale Navigation zwischen Agenten, um Kollisionen zu vermeiden und lokale Routen zu planen.
Wir hoffen, dass dieses Material jemandem hilft, sein Projekt ins Ziel zu bringen.