Gebietspatrouillenplanung

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

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?

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 .

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.