Planowanie patroli terytorium

Rozwijam grę / symulację, w której agenci walczą o ziemię. Mam sytuację pokazaną na poniższym obrazku:

Te stworzenia chodzą i zajmują fragmenty ziemi, po których nadepną, jeśli są wolne. Aby uczynić to bardziej interesującym, chcę wprowadzić zachowanie „patrolujące”, tak że agenci faktycznie chodzą po swojej ziemi, aby patrolować od intruzów, którzy mogą chcieć ją wziąć.

Po stronie technicznej każdy kwadrat jest reprezentowany jako x,ypozycja oraz wymiar reprezentujący jego długość boku. Zawiera także informacje o tym, kto zajmuje plac. Wszystkie kwadraty są przechowywane w ArrayList.

Jak mogę wprowadzić zachowanie patrolujące? Chcę, aby każdy agent patrolował określoną część obszaru (dzielą między sobą, które obszary będą patrolować). Główny problem, który znalazłem, jest następujący:

• Obszar lądu jest bardzo przypadkowy, jak widać na zdjęciu. Trudno jest zrozumieć, gdzie są granice w każdym kierunku.
• Jak powinni rozdzielić regiony na patrole?
• Obszary lądowe mogą być rozłączne, ponieważ drużyna przeciwna może zajmować terytorium od środka.

Wpadłem na pomysł, by obrać najbliższy kwadrat w każdym kierunku, traktując je jak granice obszaru i podzielić regiony na podstawie tych granic, ale może to obejmować wiele nieistotnych gruntów.

Jak mam podejść do tego problemu?

Fascynujące pytanie. Myślę, że jednym z pierwszych problemów, które należy rozwiązać, jest to, czy chcesz, aby zachowanie patrolujące było „optymalne” lub „realistyczne”. Po prostu wymyślam te słowa, ale mam na myśli:

Optymalne : agenci poruszają się w sposób, który doskonale rozdziela ich zasięg dla całego systemu.

Realistyczne : agenci poruszają się i starają się dystrybuować tak równo, jak to możliwe, ale każdy z nich ma dostęp tylko do danych lokalnych zgodnie z ich perspektywą.

Skupię się na drugim podejściu, które, jak sądzę, można rozwiązać, stosując ważone mieszanie różnych wzorców sterowania z Zachowań sterujących Craiga Reynoldsa dla postaci autonomicznych . Podstawową ideą zachowań sterujących jest użycie prostych sił, które łączą się w celu stworzenia improwizacji nawigacji wokół środowiska. W twoim przypadku myślę, że chcesz połączyć następujące zachowania kierownicze:

• Unikanie (poza terytorium) - agenci próbują pozostać na swoim terytorium i unikać poruszania się poza nim. Jednak dla pewnego realizmu wpływ „wyjścia poza terytorium” nie musi być tutaj w 100%. Odrobina „skracania zakrętów” wychodzenia poza ten obszar prawdopodobnie zapewniłaby bardziej realistyczny ruch.

• Wędrówka - agenci próbują się poruszać i eksplorować. Ten, który będziesz chciał ważyć, w przeciwnym razie agenci będą próbowali znaleźć optymalny punkt oddzielenia od siebie, a następnie „pozostać na miejscu”.

• Separacja (inni agenci) - agenci próbują trzymać się z daleka od innych agentów (aby pokryli maksymalną powierzchnię i nie zbijali się).

• Szukaj (najeźdźcy) - agenci próbują zbliżyć się do każdego wykrytego najeźdźcy.

Myślę, że chciałbyś dynamicznie analizować względne ważenie. Na przykład, jeśli agent wykryje najeźdźcę, waga separacji powinna spaść. (Innymi słowy, muszą się rozłożyć tylko wtedy, gdy polują, a nie kiedy kogoś znajdą). Myślę, że gdybyś bawił się ciężarkami dla powyższych czterech wzorów, miałbyś coś bardzo zbliżonego do tego, co masz ” szukam.

Istnieje wiele zasobów online na temat wdrażania „boidów” zgodnych z opisanymi wzorcami zachowań. Polecam implementację openstera opensteer .

Jednym podejściem jest zapisanie, dla każdej celi, kiedy była ostatnio odwiedzana przez „strażnika”, i ciągłe przechodzenie przez strażników do sąsiedniej celi, która nie była odwiedzana najdłużej.

Oczywiście zakłada to, że terytorium jest połączone.

To nie jest idealne rozwiązanie, ale łatwe do kodowania, przystosowujące się do zmieniających się okoliczności i wydajne. Z powodzeniem wykorzystałem ten algorytm do zwiadu i nękania w rts ai, które napisałem jakiś czas temu.