Gebietspatrouillenplanung

14

Ich entwickle ein Spiel / eine Simulation, in der Agenten um Land kämpfen. Ich habe die Situation in der Abbildung unten gezeigt:

Eine grün und rot gekachelte Fläche mit ähnlich gefärbten "Kreaturen"

Diese Kreaturen laufen umher und besetzen Landstücke, auf die sie treten, wenn sie frei sind. Um dies interessanter zu gestalten, möchte ich "Patrouillen" -Verhalten einführen, sodass Agenten tatsächlich in ihrem Land herumlaufen, um vor Eindringlingen zu patrouillieren, die es möglicherweise übernehmen möchten.

Auf der technischen Seite wird jedes Quadrat als x,yPosition sowie als Maß für seine Seitenlänge dargestellt. Es enthält auch Informationen darüber, wer den Platz belegt. Alle Quadrate werden in einem gespeichert ArrayList.

Wie kann ich Patrouillenverhalten einführen? Ich möchte, dass jeder Agent einen bestimmten Teil des Gebiets überwacht (sie teilen untereinander auf, welche Gebiete überwacht werden). Das Hauptproblem, das ich gefunden habe, ist wie folgt:

  • Die Landfläche ist sehr zufällig, wie auf dem Bild zu sehen. Es ist ziemlich schwer zu verstehen, wo die Grenzen in jeder Richtung liegen.
  • Wie sollten Agenten die Regionen aufteilen, um zu patrouillieren?
  • Landflächen können unzusammenhängend sein, da das gegnerische Team Gebiet von der Mitte aus einnehmen kann.

Ich hatte die Idee, das am weitesten entfernte Quadrat in jede Richtung zu nehmen, diese als die Grenzen des Gebiets zu behandeln und Regionen basierend auf diesen Grenzen zu unterteilen, aber dies könnte viele irrelevante Flächen einschließen.

Wie soll ich dieses Problem angehen?

Tohmas
quelle
1
Vielleicht könnten Sie sich einige Bildverarbeitungstechniken ansehen, um Ideen zu erhalten? Von jedem Agenten können verschiedene Regionenwachstumsalgorithmen ausgehen, die gleichzeitig ausgeführt werden, bis allen Kacheln, die zu ihrem Team gehören, ein Patrouillenagent zugewiesen wurde.
Quetzalcoatl
@Quetzalcoatl: Nette Idee, einfach umzusetzen, aber das würde zu sehr ungleichen Patrouillengebieten führen. Betrachten Sie die grünen Mittel im Bild oben. Der Agent oben rechts hätte ~ 15 Felder zu bedecken, das in der Mitte nur 2.
Junuxx
Ähm, das ist mehr oder weniger so, als würde man aus dem aktuellen Block den nächstgelegenen Block auswählen, der zu seinem Team gehört.
Tohmas
1
In der Tat ist es unvollkommen. Anstatt die Wirkstoffe als Samen für das Wachstum der Region zu verwenden, könnten die Samen anfangs zufällig gepflanzt werden (einer pro Wirkstoff). Sobald das Wachstum der Region abgeschlossen ist, könnte möglicherweise ein Ausgleichsschritt durchgeführt werden, bei dem jede Region wie ein Klassencluster mit Kacheln als Knoten behandelt wird. KNearestNeighbour oder KMean oder ähnliches könnte bis zu einer Art Konvergenz iterieren, woraufhin die Regionen als ungefähr ausgeglichen angesehen werden könnten, wobei jeder Agent dann dem nächsten Samen zugeordnet wird (euklidischer Abstand?). (Ich denke, ich bin wahrscheinlich zu kompliziert, es muss einen einfacheren Weg geben ...)
Quetzalcoatl
1
Vielleicht könnte jeder Agent damit beginnen, alle anderen Agenten wie Magnete abzuwehren. Das wird die Agenten in verschiedene Ecken der Region zwingen. Wenn die Agenten zur Ruhe kommen, teilen Sie das Land, wie es Quetzalcoatl vorschlug. Die Regionen sollten ungefähr eben sein.
Tyjkenn

Antworten:

9

Faszinierende Frage. Ich denke, eines der ersten Probleme, mit denen Sie sich befassen müssen, ist, ob Sie möchten, dass das Patrouillenverhalten "optimal" oder "lebensecht" ist. Ich erfinde nur diese Wörter, aber was ich meine ist:

Optimal : Die Agenten bewegen sich auf eine Weise, die ihren Erfassungsbereich für das gesamte System perfekt verteilt.

Lebensecht : Die Agenten bewegen sich und versuchen, sich so gleichmäßig wie möglich zu verteilen, aber jeder hat nur Zugriff auf Daten, die für seine Perspektive lokal sind.

Ich werde mich auf den zweiten Ansatz konzentrieren, den Sie meiner Meinung nach durch gewichtetes Mischen verschiedener Lenkmuster aus Craig Reynolds 'Lenkverhalten für autonome Charaktere lösen können . Die Grundidee des Lenkverhaltens besteht darin, einfache Kräfte einzusetzen, die zusammen eine improvisierte Navigation in einer Umgebung bewirken. In Ihrem Fall möchten Sie meines Erachtens das folgende Lenkverhalten kombinieren:

  • Vermeidung (außerhalb des Hoheitsgebiets) - Die Agenten versuchen, in ihrem Hoheitsgebiet zu bleiben und sich nicht außerhalb des Hoheitsgebiets zu bewegen. Für einen gewissen Realismus muss der Einfluss, das Territorium zu "verlassen", hier nicht 100% sein. Ein wenig "Schneiden" außerhalb des Bereichs würde wahrscheinlich zu einer realistischeren Bewegung führen.

  • Wandern - Die Agenten versuchen, sich weiter zu bewegen und zu erkunden. Dieses wird schwer zu wiegen sein, sonst werden die Agenten versuchen, einen optimalen Trennungspunkt voneinander zu finden und dann "stehen zu bleiben".

  • Trennung (andere Agenten) - Die Agenten versuchen, Abstand zu anderen Agenten zu halten (damit sie den maximalen Boden abdecken und sich nicht verklumpen).

  • Suchen (Eindringlinge) - Die Agenten versuchen, sich den von ihnen entdeckten Eindringlingen zu nähern.

Ich denke, Sie möchten mit der relativen Gewichtung dynamisch herumspielen. Wenn ein Agent beispielsweise einen Eindringling erkennt, sollte die Trennungsgewichtung nach unten fallen. (Mit anderen Worten, sie müssen sich nur ausbreiten, wenn sie jagen, und nicht, wenn sie jemanden finden.) Ich denke, wenn Sie mit den Gewichten der obigen vier Muster herumspielen würden, hätten Sie etwas, das Ihren Vorstellungen ziemlich nahe kommt. Ich suche.

Es gibt eine ganze Reihe von Online-Ressourcen zum Implementieren von "Boids", die den beschriebenen Verhaltensmustern folgen. Ich empfehle die Open-Source-Implementierung opensteer .

Cameron Fredman
quelle
2

Ein Ansatz besteht darin, für jede Zelle aufzuzeichnen, wann sie zuletzt von einer "Wache" besucht wurde, und die Wachen kontinuierlich zu der benachbarten Zelle zu bewegen, die am längsten nicht besucht wurde.

Dies setzt natürlich voraus, dass das Territorium verbunden ist.

Dies ist keine perfekte Lösung, sondern einfach zu codieren, an sich ändernde Umstände anzupassen und effizient. Ich habe diesen Algorithmus erfolgreich zum Aufspüren und Belästigen von Angriffen in einem Zeitraum eingesetzt, den ich vor einiger Zeit geschrieben habe.

Meriton - im Streik
quelle