Monte Carlo im Dungeon

vorhergehende Artikel in: Verschiedenes Video
30.07.2017

Der von mir neulich vorgestellte Dungeon-Generator war nur ein Schritt auf dem Weg: Ich wollte meine Studentenzeit aufleben lassen und einen Simulator bauen, in dem ich Monte-Carlo-Lokalisierung ausprobieren konnte...

Der Dungeon-Generator war erstellt - er musste aber noch visualisiert werden. Mein erster Versuch war in der Konsole und ergab etwas wie

 0 1 2 3 4 5 6 7 8 91011121314151617181920
|*******|*******|               ********|
|*-----*+------*| ------------- -------*|
|*|*|***|     |*| |*****|     | |*****|*|
|*|*|*--+     |*| +----*|     | |*---*|*|
|*|*|*|*|     |*|       |     | |*|*|*|*|
|*|*+-+*|     |*+------ |     | |*|*|*|*|
|*|*****|       ******| |       |*|***|*|
|*|*----+------ ------+ |       |*+---+*|
|*|*****        |     | |     | |*******|
|*+------ ----- |     | +-----+ |*------|
|*|     | |*****|     | |*|   | |***|   |
|*|     | |*----+     | |*|   | +---+   |
|*|     | |*****|     |   | | |     | | |
|*|     | +-----+-- --+-- | | +---- | | |
|       |                 | |@      | | |
| ------+ ----------------+ +-------+ | |
| |       |*********|     |           | |
| | ------+--***----+     | --------- | |
| | |*|     |*|*|***|     |*|*|     |*| |
| | |*|     |*+-+***|     |*|*|     |*| |
| |   |     |*****|*|     |***|     |*| |
| +-- |     +-----+*|     +--*|     |*| |
| |   |     |       |     |***|     |*| |
| | --+     | ----- +-- --+---+-- --+-+ |
| | |*|       |***| |*|                 |
| | |*+------ +--*| |*| ----- ----------|
| | |           |*    | |     |         |
| | | --------- +---- | |     | ------- |
| | | |*|     | |     | |     | |***|   |
| | | |*|     | |     | |     | |***|   |
| | |   |     | |     | |     | |*|*| |*|
| | +-- |     | |     | +-----+ |*|*| +-|
| | |*|       | |     |   ****| |*|*|   |
| | |*| ------+ +-----+-- ----+ |*+-+-- |
| | |***|       |       |       |*****| |
| | +---+ ----- | ----- | ------+----*| |
| |       |*****| |***| |*************| |
| +-------+-----+ |*--+ +-------------+ |
|                 |***                  |
+-----------------+---------------------|

Zweidimensional und bunt wurde daraus: Screenshot Beispiel für einen generierten Dungeon Dann erinnerte ich mich an eine Technik, die unter anderem bei den ersten Spielen eingesetzt wurde, die dem Spieler den Eindruck vermittelten, unmittelbar im Geschehen zu sein - Stichwort: First-Person-Perspective: Es geht natürlich um Raycasting. Das ist schnell implementiert - ich habe mich natürlich von dem einen oder anderen Quelltextschnipsel aus dem Internet inspirieren lassen.

Dann hatte ich alle Voraussetzungen zusammen: Ich trage mich schon Jahre mit dem Gedanken, einen Simulator für autonome Agenten zu bauen - ich weiß, dass es das bereits gibt, aber ich lerne eben gern und richtig lernen kann man nur, wenn man selber tätig wird! Der Simulator sollte die Umgebung des Agenten visuell erfahrbar machen, die Umgebung sollte einfach neu gestaltbar sein und ich wollte in der Lage sein, unkompliziert verschiedenste Algorithmen damit auszuprobieren.

Die Umgestaltung der Umgebung war durch den Dungeon-Generator erfüllt - schließlich produziert der jedesmal ein anderes Labyrinth.

Die visuelle Erfahrbarkeit war durch das Raycasting dieser Labyrinthe gegeben.

Die Einsetzbarkeit verschiedenster Algorithmen kommt dadurch zustande, dass ich das Projekt und damit die Architektur und sämtliche Quelltexte in der eigenen Hand habe.

Als Test habe ich eine Monte-Carlo-Lokalisierung umgesetzt: Der Agent wird irgendwo im Labyrinth abgesetzt und weiß zunächst nicht, wo er sich auf der Karte befindet, die ihm ebenfalls ausgehändigt wird. Das Ziel ist nun, irgendwie herauszufinden, wo er sich im Labyrinth befindet.

Dies wird dadurch erreicht, dass der Agent eine große Anzahl (konkret 200) Hypothesen aufstellt, die in der vorliegenden Aufgabe aus drei Parametern bestehen: zwei Koordinaten für die Position und ein Winkel für die Blickrichtung.

Der agent verfügt über eine Anzahl Entfernungssensoren, die den in Blickrichtung liegenden Bereich abtasten können.

Bewegt sich der Agent nun, kann er die Ergebnisse der Sensoren mit denen vergleichen, die sich für die Hypothesen ergeben. Sind sie sich ähnlich, könnte es sein, dass diese Hypothese stimmt und sie wird wertvoller. Stimmen sie nicht überein, besteht eine hohe Wahrscheinlichkeit dafür, dass die jeweilige Hypothese falsch ist und ihr Wert verringert sich.

Nachdem so alle Hypothesen bewertet worden sind, werden einige, die besonders wenig wert sind, verworfen und durch neue ersetzt die zufällig, aber in der Nähe der bisher besten initialisiert werden.

Dieser Zyklus von der Bewegung über die Messung der Sensoren und die Bewertung der Hypothesen wird immer wieder wiederholt. Irgendwann ballen sich Hypothesen an einer Stelle zusammen - das ist die aktuelle Position des Agenten.

In diesem Video sieht man ein Labyrinth in der Minimap, auf der auch die Hypothesen in Pink überlagert sind: Je länger eine Hypothese unter den besten ist, desto höher ist ihre Deckkraft bei der Darstellung.

Anfangs sieht man in der 3D-Darstellung, dass der Agent in einem Raum platziert worden ist - daher auch gleich zu Beginn die Ballung der Hypothesen in einigen der Räume des Labyrinths.

Nachdem sich der Agent aus dem Raum heraus und in einen Gang bewegt sieht man, dass die Hypothesen in den Räumen schnell sterben und durch neue ersetzt werden. In Sekunde 17 habe sich zwei ungefähr gleichstarke Rudel von Hypothesen herausgebildet, die aber beide vermuten, dass es am Ende des Ganges nach rechts geht.

Diese Hypothese stellt sich als falsch heraus. Nach 35 Sekunden haben sich wiederum zwei Rudel gebildet, die diesmal gegensätzliche Meinungen vertreten: Eines denkt, dass es am Ende des Ganges nach rechts geht und das andere ist fest davon überzeugt, dass der Gang nach links abbiegt.

Die Hypothesen beider Rudel müssen erkennen, dass sie falsch liegen. Nach 49 Sekunden hat sich wieder eine Meinung herausgebildet, der viele der Hypothesen anhängen (mittig oben in der Minimap).

Nach 55 Sekunden konkurrieren einige Rudel - alle nehmen an, dass man sich in einem langen Gang befindet.

Nach 63 Sekunden bleiben davon nur noch zwei übrig.

Am Ende des Videos hat der Agent seine Position korrekt in der rechten oberen Ecke der Minimap detektiert.

Artikel, die hierher verlinken

Visualisierung von Höhenfeldern mittels Voxeln

08.10.2017

Nachdem ich in letzter Zeit mit Visualisierungsalgorithmen aus meiner Jugend und alternativen Visualisierungen für generierte Landschaften experimentiert habe, habe ich nunmehr beides gleichzeitig getan und den guten alten Voxel-Algorithmus wieder entstaubt.

Alle Artikel rss Wochenübersicht Monatsübersicht Github Repositories Gitlab Repositories Mastodon Über mich home xmpp


Vor 5 Jahren hier im Blog

  • Nahtlos wiederholbare Rausch-Kacheln

    01.10.2017

    Und wieder einmal habe ich mich in die Untiefen der Erzeugung von Daten begeben, die man mit einiger Toleranz als au der Ferne aufgenommene geographische Features bezeichnen könnte

    Weiterlesen...

Neueste Artikel

  • RustDesk im Docker-Zoo

    Und wieder ist ein neuer Container in meinen Docker-Zoo aufgenomen worden.

    Weiterlesen...
  • dWb+ Version 4.4pre1 build 9756

    Eine neue Version der Dataflow Workbench dWb+ ist verfügbar!

    Weiterlesen...
  • CI/CD Deployment mittels docker-compose aus Gitlab heraus

    Ich habe bisher Projekte, aus denen ein Webdienst wurde immer von Hand auf den entsprechenden Docker-Server deployt. Das musste anders werden, daher habe ich mich entschieden, eine entsprechende CI/CD-Pipeline in Gitlab zu bauen, die das für mich erledigt.

    Weiterlesen...

Manche nennen es Blog, manche Web-Seite - ich schreibe hier hin und wieder über meine Erlebnisse, Rückschläge und Erleuchtungen bei meinen Hobbies.

Wer daran teilhaben und eventuell sogar davon profitieren möchte, muß damit leben, daß ich hin und wieder kleine Ausflüge in Bereiche mache, die nichts mit IT, Administration oder Softwareentwicklung zu tun haben.

Ich wünsche allen Lesern viel Spaß und hin und wieder einen kleinen AHA!-Effekt...

PS: Meine öffentlichen GitHub-Repositories findet man hier.