Jak sprawić, by agenci A * unikali innych agentów?

Implementuję algorytm A * z wieloma agentami na mapie kafelków. Agenci poruszają się tylko w osiach X i Y. Unikam kolizji między nimi, sprawdzając, gdzie są inni podczas obliczania ścieżek.

Działa dobrze, z wyjątkiem sytuacji, gdy agenci muszą przekazać tę samą płytkę z różnych kierunków. W takich sytuacjach optymalnym rozwiązaniem byłoby oczekiwanie jednego agenta na przejście drugiego:

Ponadto, jeśli nie ma północnego korytarza, wyszukiwanie ścieżki kończy się niepowodzeniem.

Jak mogę zaimplementować taki algorytm?

Możesz zacząć od zezwolenia na znalezienie ścieżki. W przypadku niepowodzenia wybierz losowy czas w przyszłości, aby ponownie spróbować znaleźć ścieżkę. Niektóre protokoły sieciowe niskiego poziomu działają w ten sposób i całkiem dobrze. Musisz budować ścieżki pojedynczo i oznaczyć jako wykorzystane wszystkie płytki, przez które przejdzie agent. Gdy kolejne ścieżki zawiodą, losowy licznik czasu do ponownego uruchomienia pomoże w rozłożeniu nowych poszukiwań ścieżek i przełamie błędy zapętlenia.

Drugą część problemu można rozwiązać, zwracając dwie ścieżki. Pierwsza ścieżka to regularny powrót, nawet jeśli zawiedzie z bloku. Druga ścieżka to ścieżka, która całkowicie ignoruje wszystkich agentów. Następnie możesz wykorzystać wiedzę uzyskaną z tych dwóch ścieżek, aby zdecydować, czy lepiej byłoby czekać lub przejść długą drogę. Heurystyka tej decyzji wymaga trochę pracy, ale jest lepsza niż w ogóle nie próbowanie niczego.

W bardzo złym przypadku, gdy twoi agenci są często blokowani przez takie korytarze o pojedynczej szerokości, może być konieczne dodanie bezpiecznych miejsc, aby stać tam, gdzie agenci mogą szybko dotrzeć i poczekać, aż ich prawdziwa ścieżka się otworzy (więc agent nie poczekaj i zablokuj korytarz).

Zamiast rozwiązać problem, oto sposób na zabranie cytryn i zrobienie lemoniady.

Wiele lat temu mój przyjaciel pracował nad bardzo znanym FPS, który miał dokładnie opisany przez ciebie problem: ograniczony obszar miałby wiele postaci AI, które miały określone pożądane pozycje, a algorytm znajdowania ścieżki nieustannie ich spychał do siebie. W szczególności gracz rzuciłby granat do małego pokoju pełnego wrogów, a postacie AI znajdujące się w tym obszarze spróbowałyby uciec do wyjścia, ale wpadły na siebie i skończyłyby na pauzie, odwracając się, uderzanie kogoś innego, odwracanie się i tak dalej. To wygląda bardzo nierealnie.

Próby zbudowania lepszego algorytmu wyszukiwania ścieżek, które mogłyby działać pomyślnie, biorąc pod uwagę napięty budżet obliczeniowy, zakończyły się niepowodzeniem. Zamiast więc rozwiązać problem ze znalezieniem ścieżki, mój przyjaciel dodał do AI bardzo tani czek: jeśli AI wpadła na inną AI dwa razy w krótkim czasie, przestań próbować znaleźć wyjście i zamiast tego ukryj się. Tak więc teraz dzieje się, że komputer lobuje granat i widzi, jak grupa wrogów biegnie do wyjścia. Ci, którzy się uderzają, odwracają się i wygląda na to, że zdają sobie sprawę, że nie mogą się wydostać, więc schylają się i chowają głowy przed wybuchem. Jest to zarówno realistyczne, jak i bardzo satysfakcjonujące dla gracza.

Czy istnieje jakiś podobny sposób, aby zmienić wadę algorytmu powodującego kolizję i przekształcić go w zaletę?

Zwykle najlepiej jest uzupełnić ścieżkę A * innymi formami wyszukiwania ścieżki dla innych zlokalizowanych scenariuszy; unikanie jednostek jest zwykle jednym z nich, szczególnie w świecie, w którym wielu agentów porusza się jednocześnie, tworząc dynamiczne blokery).

Zasadniczo może do tego zadziałać technika podążania za krawędzią. Gdy podążasz ścieżką, napotkasz bloker, który nie był częścią pierwotnego obliczenia ścieżki, w zasadzie wybierasz kierunek (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara) i próbujesz przejść przez bloker, podróżując wokół niego w tym kierunku. Jeśli nie możesz, poczekaj, aż bloker sam się rozwiąże (chociaż może to doprowadzić do impasu).

Możesz także zaimplementować zdolność jednostek do wspólnej ścieżki; oznacza to, że jednostka może poprosić inną jednostkę o nieznaczne odsunięcie się na bok, aby mogła „przecisnąć się” obok jednostki blokującej. Nie działa to dobrze w grze opartej na kafelkach, w której jesteś ograniczony do ruchu opartego na kafelkach, ponieważ nadal możesz zakleszczyć się w korytarzach o pojedynczej szerokości, takich jak twój przykład. W takim przypadku możesz przewidzieć, aby jednostki prosiły się nawzajem o „zamianę miejsc”, co w większości przypadków skutkuje rozwiązaniem. Czasami jednak prowadzi to do wzajemnego przeskakiwania jednostek.

„Unikanie jednostek” jest dość powszechnym tematem podczas omawiania szukania ścieżek w grach, istnieje wiele trafień. W szczególności może chcesz sprawdzić to pytanie na „pola przepływu” Pathfinding stosowanych w Supreme Commandera 2. RTSS zwykle napotkasz tego problemu partii i rozwiązać go w różnego rodzaju ciekawych sposobów.

Jeśli masz system ruchu oparty na zakręcie / tiku, możesz utworzyć wykres 3D, w którym każde przejście przenosi agenta do wyglądu mapy w przyszłości. Następnie niech każdy agent zajmie się kafelkami, na których będzie w tym miejscu w przyszłości, i oznaczy je jako niedostępne. Następnie każdy agent ma dodatkową opcję „oczekiwania” na następny tik, jako trzeci sposób przejścia przez wykres. Będzie to trudniejsze dla twojego systemu, ale powinno dać ci lepsze wyniki niż czekanie losowo. Nawet lepiej, jeśli zezwolisz 2 agentom na komunikację, gdy jeden z nich wyśle ​​wiadomość „Chcę przekazać”, jeśli przez tę osobę przechodzi najkrótsza ścieżka,

Korzystając z algorytmu takiego jak A *, masz największą swobodę w pracy z heurystyką kosztów.

W tym konkretnym przypadku możesz dostosować heurystykę, aby zwiększyć koszt ruchów, które zabierają agenta blisko innego agenta, problemem jest to, że prawdopodobnie skończyłbyś zarówno próbą wybrania górnej drogi, jak i skończyłby się nimi oscylacja tam i z powrotem między ścieżkami, gdy zbliżają się do siebie w zależności od dokładnego czasu.

Inną możliwością jest śledzenie tras zaplanowanych przez agentów i dostosowanie kosztów w górę wzdłuż ścieżek innych agentów. To skutecznie umożliwia agentom koordynację ze sobą w ograniczonym zakresie. Główny problem polega na tym, że wszystkie trasy są zablokowane, a wyszukiwanie ścieżek może się nie powieść w przypadku ostatniego przeniesienia agenta.

W przypadku, gdy istnieje tylko jedna ścieżka, wyszukiwanie ścieżki albo się nie powiedzie, albo posunie się naprzód, aż do impasu.

Jeśli żadne z nich nie jest wystarczająco dobre, musisz zacząć śledzić czas przy obliczaniu kosztów. Koszt dla drugiego agenta powinien być czasem potrzebnym na wyczyszczenie pierwszego agenta plus normalny koszt podróży, w ten sposób agent będzie mógł prawidłowo zdecydować, kiedy poczekać, a nie pójść inną drogą.

Uzgodnienie czasu może być znacznie większym wysiłkiem, więc większość ludzi decyduje się na ulepszenie układu poziomu i wartości kosztów, aż wszystko będzie wystarczająco dobre.

Zwykle radziłbym ci używać zachowań kierowniczych do rozwiązywania takich problemów podczas podążania ścieżką. I nadal możesz wziąć wiele przy nich, aby uzyskać inspirację do zachowania grupowego. Ale niestety nie ma to bezpośredniego zastosowania do prostego ruchu opartego na płytkach.

Ponieważ masz już działające unikanie kolizji w większości sytuacji, skupmy się na tym konkretnym. Wydaje mi się, że ponownie odnajdujesz ścieżkę za każdym razem, gdy agent chce się poruszyć, bo inaczej nie widzę, jak zareagują na ruch innych. Po drugie, sądzę, że ci agenci są dla siebie przyjaźni.

Sugerujesz, aby jeden agent czekał na drugiego, a radziłbym ci to zrobić. Daj agentom dostęp do ścieżek innych, wyszukaj pierwszy kafelek własnej ścieżki, która nie jest częścią drugiej ścieżki, i idź tam. Problemy z tą techniką mogą być:

1. Jak decydujesz, czy istnieje inny dopuszczalny sposób obejścia innego agenta, czy nie? Nie chcesz czekać na drugiego agenta, jeśli jest wystarczająco dużo miejsca, aby go ominąć. Niepowodzenie odnajdywania ścieżki przy rozważaniu innego agenta jest wyraźną oznaką sytuacji, którą chcesz naprawić, ale w przykładzie, który przywołałeś, nie będzie niepowodzenia odnajdywania ścieżki. Ale możesz - przy odrobinie kalkulacji - zdecydować, czy alternatywna ścieżka A * omija po prostu innego agenta w małym kółku, czy też używa zupełnie innej ścieżki, jak korytarz północny.

2. Nie wiem, jak daleko agent może przebyć podczas jednej rundy / operacji, ale jeśli to nie wystarczy, lub jeśli wszyscy agenci poruszają się równolegle, obaj agenci zdecydują się poczekać na drugim końcu ścieżki. Można to naprawić, sygnalizując drugiemu agentowi, że zwalniasz jego ścieżkę.

Jednym z możliwych rozwiązań byłoby wyłączenie kolizji jednostek w tak ciasnych miejscach.

Na przykład w grze Starcraft pracownicy (SCV, sondy, drony) nie zderzają się ze sobą podczas wydobywania kryształów.