Ich möchte natürlich die Gems finden. Punkt. Nun sehe ich sie aber leider nicht immer sofort, weil sie entweder hinter einer Wand sind (vgl. Stage-1), oder meine Sichtweite zu kurz ist (Stage-2). Dafür empfange ich nun ein Signal von jedem Gem, klingt erst einmal prima. Leider empfange ich aber nur das Summen-Signal aller Gems. Mein Ziel ist es nun, in möglichst wenigen Ticks aus dem Summen-Signal (mehr oder weniger) exakt auf die Gems zu schließen.
Algorithmen zur Wegfindung gibt es fast so viele wie Sandkörner im Ganges. Besonders bekannt und beliebt sind BFS und A*. (Ich habe für den Blog nachgeschaut, wie diese arbeiten und ob sie nicht identisch sind.) Wir wollen hier gemeinsam einen einfachen Algorithmus entwickeln, der schneller ist als BFS und mehr Informationen bereitstellt.
Im Teil 1 dieses Blogs wurde erläutert, wie das vom JSON-string mitgeteilte Summensignal sich aus mehreren Einzelsignalstärken zusammensetzt und wie diese mit den sog. Zielvektoren und den daraus abgeleiteten genauen Zielvektoren zusammenhängen. Ein Vergleich der genauen Zielvektoren in einem bestimmten Tick mit denjenigen aus dem Vorgängertick erlaubt nun, wie wir sehen werden, eine zuverlässige Lokalisierung von plötzlich auftauchenden Gems.
Im »Hidden Gems«-Wettbewerb müssen Gems, die an nicht vorhersehbaren Positionen auf dem Spielfeld zu nicht vorhersehbaren Zeiten (»ticks«) erscheinen, so rasch wie möglich eingesammelt werden. Je schneller der eigene Bot diese Positionen nacheinander erreicht, desto mehr Punkte landen auf seinem Konto (»score«).
Das Hauptproblem der aktuellen Stage Dark Signal ist es, die Positionen der Gems zu bestimmen. Hierzu gibt es verschiedenste Ansätze. Ich habe mich für einen “naiven” Ansatz entschieden: Raten :)
Informatiklehrer am Gymnasium Steglitz und Organisator des »Hidden Gems«-Wettbewerbs.
AnleitungBlog
Willkommen zu unserem Blog für den »Hidden Gems«-Wettbewerb! Hier veröffentlichen Teilnehmerinnen und Teilnehmer ihre Beiträge: spannende Analysen, Strategieskizzen, Erklärungen zu Algorithmen oder Erfahrungsberichte aus dem Wettbewerb.
