search

rhoentier / ss22_fp_mapc-group_5

4 stars 0 forks source link

Grenzen der Karte finden #25

Open rhoentier opened 2 years ago

rhoentier commented 2 years ago

Die Grenzen der Karte sind keine festen Grenzen, sondern verbinden beide Seiten einer Karte. Die Karte bildet sozusagen eine Kugel.

Es muss implementiert werden, dass die Kartenbreite erkannt wird, damit die Repräsentation nicht "unendlich" groß wird, also die Karte nicht mehrmals nebeneinander angelegt wird. Mögliche Ideen:

seblod90 commented 2 years ago

Infos zu Punkt 3: Anhand eines einzelnen Agenten können die Grenzen nicht mit voller Sicherheit erkannt werden. Hierzu kann man sich ein Spielfeld vorstellen, dass sich z.B. in x-Richtung tatsächlich wiederholt, ohne dass es aber das Ende des Spielfelds ist (z.B. wenn alle Hindernisse mit x-Wert 0...7 gleich sind zu denen von 8...15. Das Ende des Spielfelds ist aber erst bei 15 und nicht bei 7.). Um die Grenzen sicher festzustellen, benötigt es mindestens 2 Agenten.

Die meisten Teams der vergangenen Jahre: Wenn sich zwei Agenten treffen, mergen sie ihre Karte und arbeiten später auf derselben Karte / demselben Nullpunkt. Wenn sie sich im Verlauf des Spiels nochmal treffen, jedoch an unterschiedlichen Positionen stehen, kann die Karte prinzipiell abgeschätzt werden. An dieser Stelle kann es noch passieren, dass man um mehrere Kartenbreiten falsch liegt.

Vorgehen MLFC: Einführen einer Cartographer-Rolle für 4 Agenten zu Beginn des Spiels. Jeder Agent läuft in jeweils eine Richtung (N,E,S,W). Die beiden Agenten in N<->S-Richtung bzw. E<->W sollten sich treffen und können dann die Größe berechnen. Hier ist zu beachten, dass die Agenten nicht aneinander vorbeilaufen dürfen (Bei den Agenten in N<->S-Richtung z.B. durch einen x-Versatz. Ein Agentenpaar muss sich also vor Beginn der Cartographer-Rolle schon mal gesehen haben.

Idee von mir, welche einfach ist, aber nur bei komplexeren Karten funktioniert: Karte eines Agenten in Spalten (für x-Dimension) und Zeilen (für y-Dimension) analysieren. Sobald sich eine Spalte bzw. Zeile in ihrer Anordnung von Obstacles, Dispensern und freien Flächen wiederholt, kann die jeweilige Dimension abgeschätzt werden. Der Abgleich, ob sich die Karte wiederholt, müsste eine Ungenauigkeit beinhalten, da sich Obstacles ja auch ändern können. Je dynamischer die Karte, desto schlechter würde das funktionieren. Beispiel: Gäbe es gleich viele Obstacles wie freie Flächen, liegt die Wahrscheinlichkeit für eine bestimmte Formation mit n Feldern bei 1/(2^n). Bei einem 20er Feld immerhin schon 1/1 Mio.

rhoentier commented 2 years ago

Ich finde sowohl deine Idee, als auch das vorgehen von MLFC gut.

Zu MLFC: Man kann ja durchaus regeln definieren, wie: Gehe immer Horizontal, außer du triffst auf ein Objekt, dann gehe einen Schritt hoch. Wenn du dich deiner horizontalen Ursprungslinie wieder annähern kannst, dann mache das. So müssten sich die Agenten auf jeden Fall wieder treffen.

Zu deiner Idee: So hatte ich das auch gedacht. Ich glaube nur, dass das ziemlich schwierig zu implementieren ist.Allerdings würde man richtig viele Schritte sparen.

Ein Vorschlag: Wir starten mit der Taktik von MLFC. Das kann man auch umsetzen, wenn nicht alle Agenten bei der Bearbeitung von Aufgaben gebraucht werden. Deine Idee kann man ja auch unabhängig vom anderen Code umgesetzt werden.

Allerdings würde ich damit warten, bis wir alle Aufgaben für das jetztige Turnier erledigt haben, oder? :-)