Bereits im Prozess der Erstellung von
The Witness ist eines meiner Lieblingsspiele geworden. Ich begann es von dem Moment an zu spielen, als
Jonathan Blow anfing, es zu entwickeln, und konnte es kaum erwarten, dass es veröffentlicht wurde.
Im Gegensatz zu John
Braids vorherigem Spiel war
die Ressourcen- und Programmierskala von
The Witness AAA-Projekten viel näher als Indie-Spielen. Jeder, der an solchen Projekten arbeitet, weiß, dass der Arbeitsaufwand bei der Auswahl dieses Pfades erheblich zunimmt. Es arbeiteten viel mehr Leute an
The Witness als an
Braid , aber wie bei jedem Projekt dieser Ebene gibt es viele Aspekte, die mehr Aufmerksamkeit erfordern, als sich das Projektmanagement leisten kann.
Deshalb wollte ich immer Freizeit finden, um
The Witness bei der Veröffentlichung des Spiels zu unterstützen. Eines Tages setzten sich Thanksgiving, John und ich zusammen und sahen uns die Liste der Dinge in der Codebasis an, die von zusätzlichen Anstrengungen eines anderen Programmierers profitieren würden. Nachdem wir uns für die relative Bedeutung der Elemente auf der Liste entschieden hatten, entschieden wir, dass das Gameplay am meisten davon profitieren wird, wenn wir den Bewegungscode des Spielers verbessern.
Walkmonster in der Wand
Im Kontext von
The Witness ist es das Ziel des Bewegungscodes eines Spielers, so unauffällig wie möglich zu sein. Der Spieler muss vollständig in eine alternative Realität eintauchen, und bei diesem Spielerlebnis ist jedes Detail wichtig. Das Letzte, was wir wollten, war, dass der Spieler bemerkte, dass er am Computer saß und die virtuelle Kamera bewegte.
Daher muss der Bewegungscode des Spielers absolut zuverlässig sein. Wenn sich ein Spieler an Ecken festhält, in Wänden steckt, durch den Boden fällt, von einem Hügel herabsteigt, ohne zurückgehen zu können usw., zerstört dies sofort die Illusion des Eintauchens und erinnert den Spieler daran, dass er sich in einem künstlichen Spielprozess befindet, der durch ein unzuverlässiges System gestört wird Verschiebungen. Unter bestimmten Umständen kann dies sogar zu katastrophalen Folgen für den Spieler führen, wenn er nicht die Möglichkeit hat, das Problem durch einen Neustart des Spiels oder ein erneutes Laden des (wahrscheinlich sehr alten) "Speicherns" zu lösen. Wenn Sie oft Spiele spielen, müssen Sie auf Probleme dieser Art gestoßen sein, und Sie wissen, was ich meine.
Nach unserer Diskussion begann ich mit der Arbeit an dieser Aufgabe. Zunächst habe ich beschlossen, integrierte Tools für die Arbeit mit dem Bewegungscode des Spielers zu schreiben, damit wir ihn analysieren und sein aktuelles Verhalten beobachten können. Nachdem ich das Projekt geöffnet hatte, stieß ich auf ein ernstes Problem, das mir bereits bekannt war: Wie soll ich die erste Quellcodedatei nennen? Dies ist immer der wichtigste Teil eines Projekts (
wie Bob Pollard einmal über die Namen von Musikgruppen und Alben sagte ). Wenn Sie der Quelldatei einen geeigneten Namen geben, ist die weitere Arbeit klar und reibungslos. Wählen Sie die falsche - Sie können das gesamte Projekt zerstören.
Aber wie heißt das System, um die Qualität des Bewegungscodes des Spielers sicherzustellen? Ich musste noch nie so einen Code schreiben. Als ich darüber nachdachte, wurde mir klar, dass ich persönlich nur einmal ein Beispiel für einen solchen Code gesehen habe: beim Spielen der frühen Beta von
Quake . Es enthielt Fehler mit der Position von Monstern, und im Konsolenfenster konnten Fehlermeldungen angezeigt werden, die besagten, dass Monster erstellt werden, anstatt auf der Erdoberfläche zu erstellen, die sich teilweise mit der Geometrie der Ebenen überschneiden. Jede Debug-Nachricht begann mit dem Satz "Walkmonster in Wall at ...".
Bingo! Es ist schwierig, einen besseren Namen für die Codedatei als "walk_monster.cpp" zu finden. Und ich war mir fast sicher, dass der Code von nun an ohne Probleme erstellt werden würde.
Bewegung auf den Punkt
Wenn Sie das System testen möchten, ist es am wichtigsten,
das System tatsächlich zu testen . Obwohl diese Regel einfach zu sein scheint, halten sich Personen, die Tests schreiben, häufig nicht daran.
In unserem speziellen Fall ist es sehr leicht
vorstellbar, dass wir den Bewegungscode eines Spielers testen, ohne ihn tatsächlich zu testen. Hier ein Beispiel: Sie können das Volumen von Kollisionen und Oberflächen analysieren, auf denen Sie sich im Spiel bewegen können, nach kleinen Oberflächen, Lücken usw. suchen. Nachdem wir all diese Probleme beseitigt haben, können wir sagen, dass der Spieler sich jetzt sicher bewegen und um die Welt gehen kann.
Tatsächlich haben wir die Daten getestet, nicht den Code. Es ist sehr wahrscheinlich, dass der Bewegungscode Fehler enthält, die selbst bei qualitativ hochwertigen Daten zu einem schlechten Verhalten führen.
Um eine solche Falle zu vermeiden, wollte ich, dass das Testsystem dem Verhalten der Person, die die Bewegung des Charakters im Spiel tatsächlich kontrolliert, so nahe wie möglich kommt. Ich begann damit, zwei Verfahren zu schreiben, die die Bausteine für solche Tests werden sollten.
Das erste Verfahren kommt echten menschlichen Handlungen am nächsten. Dies ist ein Aktualisierungsaufruf, der eine Verbindung zum Eingabeverarbeitungssystem von
The Witness herstellt und die synthetisierten Tastatur- und Mausereignisse an dieses übergibt. Es ist zu einfachen Dingen fähig, die eine Person tun kann: sich umsehen, zu einem Punkt gehen, einen Punkt betrachten und so weiter. Die Prozedur führt diese Aktionen aus, indem sie einfach die Interaktion des Benutzers mit der Tastatur und der Maus emuliert. Ich war mir also sicher, dass bei der Verarbeitung der Eingabe von
The Witness alles genau so ausgeführt wird, wie es beim Testen war. In den folgenden Artikeln werde ich mehr über dieses System und seine Verwendung sprechen.
Das zweite Verfahren ist ein Schritt, der auf dieser Ebene nicht verwendet wird. Dies ist eine Funktion namens
DriveTowardPoint , die zwei Punkte in der Welt erhält und aufgrund eines vorhandenen Kollisionssystems eines Spielers versucht, nahtlos von einem Punkt zum anderen zu gelangen. Bei der Rückgabe übermittelt sie Informationen über den Versuch: Auf welche Hindernisse sie unterwegs gestoßen ist und ob sie den Endpunkt erreicht hat.
Diese Funktion ist nicht so zuverlässig wie eine Testmethode mit synthetisierten Eingaben, da ein Teil des Bewegungssystems des Spielers nicht mehr getestet werden kann. Beispielsweise wirkt sich eine fehlerhafte Bedingung, die mit dem Standort des Spielers bei Problemen mit dem Kollisionssystem verbunden ist, nicht auf das Testen mit dieser Funktion aus. Trotzdem hielt ich diese Teststufe für wertvoll, da sie große Gebiete viel schneller testen kann, da nicht der gesamte Spielzyklus ausgeführt werden muss, dh sie kann weltweit viel häufiger verwendet werden und nicht nur in separaten Testläufen .
Es ist auch erwähnenswert, dass diese Funktion keine physischen Eingabedaten überträgt. Beispielsweise werden Geschwindigkeiten für den Startpunkt nicht angezeigt. Dies liegt daran, dass
The Witness kein Actionspiel ist und der Spieler daher nur wenige signifikante physikalische Eigenschaften hat. Spieler können nicht springen, an Wänden rennen oder die Kugelzeit einschalten. Sie können solche Verhaltensweisen mithilfe von Systemen unterstützen, die ich später beschreiben werde. Sie erhöhen jedoch die Komplexität, die in unserem Projekt nicht erforderlich waren.
Wie dem auch sei, nach der Implementierung von
DriveTowardPoint könnte ich beginnen, die erste Aufgabe des Systems zu lösen: zu bestimmen, wo der Spieler nach
The Witness Island ziehen kann.
Schnelle Erkundung zufälliger Bäume
Wohin können Spieler gehen? Dies scheint eine einfache Frage zu sein, aber Sie werden überrascht sein, wie viele Spiele veröffentlicht wurden, als das Entwicklerteam die richtige Antwort nicht kannte. Wenn dies möglich ist, wollte ich, dass
The Witness eines der wenigen Spiele ist, in denen Entwickler vor der Veröffentlichung genau wussten, wo ein Spieler hin konnte und was nicht - keine Überraschungen.
Dies macht die Problemstellung (aber wahrscheinlich nicht ihre Lösung) sehr einfach: Wenn es eine
DriveTowardPoint- Funktion gibt, die zuverlässig bestimmt, ob sich der Spieler in einer geraden Linie zwischen zwei Punkten bewegen kann, erstellen Sie eine Abdeckungskarte, die zeigt, wo sich der Spieler möglicherweise befindet.
Aus irgendeinem Grund, ohne eine einzige Codezeile zu schreiben, dachte ich aus irgendeinem Grund, dass es am besten wäre,
Rapidly Exploring Random Tree zu verwenden . Für diejenigen, die mit diesem Algorithmus nicht vertraut sind, erkläre ich: Dies ist ein sehr einfacher Prozess, bei dem wir alle Punkte, die wir besucht haben, in Bezug auf den Punkt aufzeichnen, von dem wir gekommen sind. Um dem Baum einen Punkt hinzuzufügen, nehmen wir einen zufälligen Zielpunkt irgendwo auf der Welt, wählen den Punkt aus, der ihm am nächsten liegt, bereits im Baum, und versuchen, von diesem Punkt zum Ziel zu gelangen. Der Ort, an dem wir gelandet sind, wird zum nächsten Probenahmepunkt.
Normalerweise wird dieser Algorithmus verwendet, um nach Pfaden zu suchen: Alternativ wählen wir für zufällige Punkte immer den gleichen Punkt wie das Ziel aus. Dies neigt die Erforschung des Weltraums zum Zielpunkt, und dies ist erforderlich, wenn unsere einzige Aufgabe darin besteht, das Ziel zu erreichen. In diesem Fall wollte ich jedoch eine vollständige Karte der Orte erstellen, in die der Spieler fallen könnte, daher verwende ich nur Zufallsstichproben.
Nach der Implementierung dieses Algorithmus (zum Glück ist er sehr einfach und benötigt nicht viel Zeit) stellte ich fest, dass er die Raumforschung ziemlich gut erkundet hat (die gezeigten Pfade sind durch weiße Pfade dargestellt und die vertikalen roten Linien zeigen die Stellen an, an denen der Algorithmus mit einem Hindernis kollidierte). ::
Nachdem ich sein Verhalten beobachtet hatte, wurde mir klar, dass ich tatsächlich keinen solchen Algorithmus brauche. Zum Beispiel ist er selbst nach vielen Iterationen trotz der dichten Abdeckung der Außenbereiche kaum in der Lage, die Räume zu erkunden, die den unten gezeigten ähnlich sind. Dies liegt daran, dass er einfach nicht in der Lage ist, ausreichend zufällige Punkte in den Räumen auszuwählen:
Wenn ich vor Beginn der Arbeit darüber nachdenken würde, würde ich verstehen, dass der Vorteil von Algorithmen wie Rapidly Exploring Random Tree darin besteht, dass sie hochdimensionale Räume effektiv erkunden. In der Tat ist dies normalerweise der Hauptgrund für ihre Verwendung. Aber
der Zeuge hat keine hochdimensionalen Räume. Wir haben einen zweidimensionalen Raum (ja, verteilt auf eine komplexe Vielfalt, aber dies ist immer noch ein zweidimensionaler Raum).
In diesem niedrigdimensionalen Raum sind die Vorteile von Rapidly Exploring Random Tree schwach, und sein Nachteil ist für meine Aufgabe von entscheidender Bedeutung: Der Algorithmus ist für die effizienteste Suche nach Pfaden zu verbundenen Punktpaaren im Raum und nicht für die effiziente Suche nach allen erreichbaren Punkten dieses Raums ausgelegt. Wenn Sie eine solche Aufgabe haben, wird die schnelle Erkundung eines zufälligen Baums tatsächlich sehr viel Zeit in Anspruch nehmen, um sie zu lösen.
So wurde mir schnell klar, dass ich nach einem Algorithmus suchen musste, der niedrigdimensionale Räume effektiv vollständig abdeckte.
3D-Hochwasserfüllung
Als ich wirklich über die Auswahl eines Algorithmus nachdachte, wurde mir klar, dass ich tatsächlich so etwas wie die gute alte zweidimensionale Füllung brauchte, mit der Bereiche der Bitmap gefüllt werden. Für jeden Ausgangspunkt musste ich nur den gesamten Raum ausfüllen und jeden möglichen Weg gründlich prüfen. Leider ist die Lösung für
The Witness aus vielen Gründen viel komplizierter als für eine zweidimensionale Bitmap.
Erstens haben wir kein klares Konzept für die endliche Verbundenheit eines Punktes. Der gesamte Raum ist durchgehend. Dies ist für ein Pixel, wir können leicht 4 mögliche Orte auflisten, die von einem bestimmten Punkt aus erreicht werden können, und jeden von ihnen nacheinander überprüfen.
Zweitens gibt es keine feste Größe der Position im Raum, wie ein Pixel auf einer Bitmap. Die Oberflächen, auf denen sich der Spieler bewegt, und Hindernisse können sich überall befinden. Sie haben keine maximale oder minimale topologische Größe und sind nicht an ein externes Gitter gebunden.
Drittens, obwohl die Bewegung durch
den Raum
The Witness lokal als Bewegung entlang einer Ebene betrachtet werden kann, ist der Raum selbst tatsächlich eine tief miteinander verbundene und sich verändernde Mannigfaltigkeit, in der sich die begehbaren Bereiche des Spielers direkt über anderen Bereichen befinden (manchmal können mehrere Ebenen übereinander liegen). . Darüber hinaus gibt es Verbindungen, die je nach Weltbedingungen variieren (offene / geschlossene Türen, Aufzüge, die steigen / fallen usw.).
Angesichts der beschriebenen Schwierigkeiten ist es sehr einfach, eine eigene Implementierungsoption für das Befüllen zu finden, die infolgedessen mit sich überschneidenden Bereichen, fehlenden wichtigen Routen und fehlerhaften Informationen über Verbindungen an komplexen Orten der Sorte gefüllt wird. Am Ende wird der Algorithmus zu umständlich zu verwenden sein, da er erneut ausgeführt werden muss, um Änderungen im Zustand der Welt zu berücksichtigen.
Ich dachte nicht sofort an eine gute Lösung, also beschloss ich, mit einfachen Experimenten zu beginnen. Mit dem von mir geschriebenen
Rapidly Exploring Random Tree- Code habe ich die Auswahl der Zielpunkte von zufällig auf sehr kontrolliert geändert. Jedes Mal, wenn dem Baum ein neuer Punkt hinzugefügt wurde, gab ich an, dass sich die Punkte in einem Einheitsabstand entlang der Hauptrichtungen von dem Punkt befinden, der als zukünftiger Zielpunkt betrachtet wird, wie dies bei einer einfachen zweidimensionalen Füllung der Fall ist.
Wenn Sie jedoch nicht vorsichtig sind, führt dies natürlich zu einem nutzlosen Abtastzyklus. Der Punkt verzweigt sich in die benachbarten 8 Punkte um ihn herum, aber diese 8 Punkte versuchen dann erneut, zum Startpunkt zurückzukehren, und dies wird für immer fortgesetzt. Daher benötige ich zusätzlich zur kontrollierten Auswahl von Zielpunkten eine einfache Einschränkung: Jeder Zielpunkt, der sich nicht innerhalb eines bestimmten Mindestabstands von einem vorhandenen Zielpunkt befindet, wird nicht berücksichtigt. Zu meiner Überraschung sorgen diese beiden einfachen Regeln für eine ziemlich erfolgreiche Füllung:
Nicht schlecht für ein ziemlich einfaches Experiment. Aber der Algorithmus leidet unter dem, was ich das "Grenzecho" nenne. Dieser Effekt ist im folgenden Screenshot zu sehen, der während des Studiums der Karte aufgenommen wurde:
In Gebieten ohne Hindernisse funktioniert der Algorithmus gut, indem er in relativ gleichen Abständen abtastet. Wenn der Schnittpunkt jedoch die Grenze berührt, erzeugen sie Punkte, die „außerhalb des Gitters“ liegen, dh sie werden nicht nach dem Muster der Stichproben ausgerichtet, nach dem der Algorithmus den benachbarten offenen Bereich ausfüllt. Der Grund dafür, dass die Punkte „im Raster“ keine übermäßig dichte Tessellation erzeugen, liegt darin, dass jeder neue Punkt, der versucht, zu einem der vorherigen zurückzukehren, den vorherigen Punkt dort findet und sich weigert, ihn erneut zu erzählen. Wenn Sie jedoch neue Punkte an der Grenze erstellen, sind diese völlig unausgerichtet, sodass nichts sie daran hindern kann, in den bereits erkundeten Raum zurückzukehren. Dies führt zur Erzeugung einer Welle von vorgespannten Abtastwerten, die fortgesetzt wird, bis sie eine zufällige Punktlinie an einer anderen Stelle erreicht, die nahe genug ist, damit der Algorithmus feststellen kann, dass sie mit der sich bewegenden Vorderseite der Punkte übereinstimmt.
Obwohl dies kein ernstes Problem zu sein scheint, ist es tatsächlich kritisch. Der Sinn solcher Algorithmen besteht darin, die Proben auf Bereiche zu konzentrieren, in denen sie am wahrscheinlichsten produktive Ergebnisse liefern. Je mehr Zeit wir mit dem Abtasten und erneuten Abtasten großer offener Bereiche verbringen, desto weniger Zeit werden wir damit verbringen, die Gesichter dieses Bereichs zu markieren, die die Informationen sind, die wir benötigen. Da es sich um einen kontinuierlichen Raum handelt und nur eine unendliche Anzahl von Proben seine wahre Form beschreiben kann, ist das Verhältnis von signifikanten zu nicht signifikanten Proben buchstäblich ein Maß für die Wirksamkeit des Algorithmus bei der Erstellung einer für einen Spieler passierbaren Oberfläche.
Es gibt jedoch eine einfache Lösung für dieses spezielle Problem: Sie müssen den Abstand vergrößern, in dem die beiden Punkte als "ziemlich nahe" betrachtet werden. Auf diese Weise reduzieren wir die Abtastdichte an Stellen, die
für uns
nicht wichtig sind, verlieren aber auch die Abtastdichte an Stellen, die
für uns
wichtig sind, z. B. in den Bereichen um die Grenzen, die wir sorgfältig auf das Vorhandensein von "Löchern" prüfen möchten.
Lokalisierte Richtungsabtastung
Wahrscheinlich, weil ich mit dem Rapidly Exploring Random Tree angefangen habe, hat mein Gehirn alle anderen Ideen außer der Idee der Nähe verdrängt. Alle vorherigen Algorithmen verwendeten die Nähe für ihre Aufgabe, um beispielsweise einen neuen Punkt zu bestimmen, der als nächstes berücksichtigt werden muss, oder um einen Punkt auszuwählen, von dem aus begonnen werden soll, um zu einem neuen Zielpunkt zu gelangen.
Aber nachdem ich einige Zeit über die Aufgabe nachgedacht hatte, wurde mir klar, dass alles logischer wird, wenn wir nicht nur an Nähe, sondern auch an
Richtung denken. Dann wird es offensichtlich, aber wenn Sie an ähnlichen Aufgaben gearbeitet haben, wissen Sie, dass es leicht ist, in die Falle des engstirnigen Denkens zu geraten und das große Ganze nicht zu sehen, selbst wenn es sich als einfacher herausstellt. Genau das ist mir passiert.
Als ich meine Sicht der Dinge änderte, schien der richtige Ansatz für die Probenahme offensichtlich. Jedes Mal, wenn ich meine Erforschung des Weltraums von einem Punkt aus erweitern wollte, beantragte ich die Existenz von nahe gelegenen Punkten in der lokalen Umgebung. Anstatt den Abstand zu diesen Punkten für Forschungszwecke zu verwenden, werde ich sie nach ihren Richtungen klassifizieren (vorher habe ich nur acht Hauptrichtungen verwendet, aber ich wollte mit anderen Kerneln experimentieren).
In jeder Richtung, in der ich den Punkt nicht „sehe“, gehe ich durch die angegebene Entfernung und füge an jeder Stelle, an der ich angehalten habe, einen Punkt hinzu (unabhängig davon, ob ich auf etwas gestoßen bin oder nicht). Wenn ich einen Punkt in einer der Richtungen sehe, bewege ich mich dorthin und überprüfe, ob ich dorthin gelangen kann. Wenn ich kann, füge ich einfach eine sichtbare Kante hinzu, damit der Benutzer leicht sehen kann, dass die Punkte verbunden sind. Wenn ich nicht kann, füge ich am Kollisionspunkt einen neuen Punkt hinzu, der die Grenze des Hindernisses definiert.
. , , :
, , , :
, . , , . , , .
, . , ? . , ( - ).
, , , , . , , , , .
, , . , , . , , , , .
. , :
:
, , .
, , Walk Monster , . , :
, . , . , , , .
The Witness , , , , , . , , - . , , , , .
, Walk Monster , . — Walk Monster , - ( — ), . , ( ). !
, , . , , ! , , . , .
-, , ? , , , , .
-, , «»? , , ?
-, — ? , , , , , .
-, , ? , , , - , . ? ?
, Walk Monster , , . , , . . , , - , Walk Monster .