Autor Wątek: Wyszukiwanie drogi dla przeciwników w środowisku 3d.  (Przeczytany 2009 razy)

Offline Silther

  • Użytkownik

# Maj 01, 2010, 11:22:40
Napisałem w swojej grze AI dla przeciwników, w sumie nieskomplikowane, ponieważ ich jedyną rolą jest losowe chodzenie po dostępnym dla nich obszarze albo gonienie przeciwnika jeżeli znajdzie się on wystarczająco blisko. Problem w tym, że moje rozwiązanie nakłada zbyt duże ograniczenia na przeciwników (każdy z nich może się poruszać tylko po wyznaczonym prostokącie lub elipsie.

Szukam rozwiązania, które pozwoli mi zrealizować te dwa podstawowe zadania AI (losowe chodzenie, gonienie przeciwnika) w miarę szybki sposób uwzględniając:
  • nieregularną strukturę mapy - nie składa się z żadnych kafli o identycznym kształcie, ale z trójkątów
  • dynamiczną zmianę mapy - jeżeli w danej chwili krata jest zamknięta przeciwnik nie będzie usiłował przez nią przejść tylko poszuka innej drogi

Jak radzicie mi zrealizować taki AI? Jak takie coś robi się w profesjonalnych produkcjach?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Vx-x.

  • Użytkownik
    • Vx-x. Page

# Maj 01, 2010, 11:37:23
Do AI to i tak będziesz musiał podzielić obiekty na coś większego niż trójkąty, bo to znajdowanie drogi wydajność zabije.
Myślałeś o rzucaniu pojedynczych promieni w losowym kierunku od przeciwnika i jeśli w nic nie uderzył to znaczy że przeciwnik może udać się w tamtą stronę. Wtedy byś też widział, że jeśli np. promień uderzy w drabinę, to przeciwnik ma po niej wejść na górę. Co do szukania najkrótszej drogi - od tego masz już konkretne
algorytmy - google i "pathfinding".

@Edit: swego czasu używałem waypointów (najszybsze i najprostsze), ale nie wiem czy dałoby się automatycznie liczyć ich pozycje.
« Ostatnia zmiana: Maj 01, 2010, 11:45:00 wysłana przez Vx-x. »

Offline Silther

  • Użytkownik

# Maj 01, 2010, 12:03:02
Do AI to i tak będziesz musiał podzielić obiekty na coś większego niż trójkąty, bo to znajdowanie drogi wydajność zabije.
Z trójkątów zbudowana jest mapa, która jest wyświetlana (modele, ściany itp.) to jasne, że powinna być jakoś uproszczona zanim zajmie się nią AI.

Myślałeś o rzucaniu pojedynczych promieni w losowym kierunku od przeciwnika i jeśli w nic nie uderzył to znaczy że przeciwnik może udać się w tamtą stronę.
Myślałem, takie coś jest wystarczające do "błądzenia" po mapie, ale jeżeli w pobliżu pojawi się przeciwnik to całe rozwiązanie leży. Wystarczyłoby, że gracz schowa się za róg, a przeciwnik już zgłupieje.

Co do szukania najkrótszej drogi - od tego masz już konkretne
algorytmy - google i "pathfinding".
Znam algorytmy szukania najkrótszej drogi, z tym, że wszystkie one znajdują najkrótszą drogę w grafie, a ja mam tutaj "polygon soup".

Wymyśliłem wcześniej jeszcze inny system, mianowicie: podzielenie mapy na figury geometryczne (oznaczające pomieszczenia - wierzchołki grafu) oraz portale (oznaczające drzwi/przejścia - krawędzie grafu). Sposób działałby całkiem nieźle, problem w tym, że automatyczne generowanie takiego grafu raczej nie wchodzi w grę (a przynajmniej byłoby ciężkie do zrealizowania) a jeżeli miałby to robić człowiek to byłoby to mnóstwo pracy dla level designera jak i dla mnie.
Nie zaimplementowałem go, ponieważ znacznie wydłużyłoby to czas tworzenia gry, a właśnie tego chcę uniknąć.

Offline voytech

  • Użytkownik

# Maj 01, 2010, 12:05:11
Losowe chodzenie moim skromnym zdaniem jest mało realistyczne. Mało kto porusza się losowo. Kiedy wykonujemy czynność chodzenia to przeważnie mamy określony cel, gdzie chcemy dotrzeć.

- Jeżeli dana jednostka wykonuje patrol to najczęściej odbywa się ona wzdłuż z góry określonej ścieżki. Można ją ustawić na mapie ręcznie w jakimś edytorze. Do tego dołożył bym jakieś punkty przystankowe, żeby przeciwnik mógł się zatrzymać na chwilę, rozejrzeć, potupać w miejscu i kontynuować dalej spacer po wyznaczonej trasie.
Przechowywanie różnych ścieżek nie powinno być pamięciożerne. Żeby wprowadzić jakąś losowość można np. jeden punkt przestankowy na danej ścieżce postawić w tym samym miejscu co inna ścieżka i pozwolić postaci wylosować czy chce dalej podążać bieżącą ścieżką, czy przełączyć się na inną.

- Jeżeli chodzi o gonienie przeciwnika to na pewno przyda się coś w rodzaju navamesh (http://geck.bethsoft.com/index.php/Bethsoft_Tutorial_Navmesh), czyli maksymalnie uproszczony obszar po którym może się poruszać przeciwnik. Dodatkowo można uzupełnić go o ściany za którymi może się chować, itp.
Chyba najprościej gonienie można zrealizować poprzez nagrywanie pozycji gracza i tworzenie z nich ścieżki po której poruszałby się przeciwnik. Dodatkowo można robić wygładzanie takiej ścieżki, bo głupio by wyglądało gdybyśmy uciekali zygzakiem a npc podążał za nami takim samym ruchem. Oczywiście taka ścieżka pościgowa miałaby duża liczbę punktów, dlatego należałoby wybierać niektóre z nich, ale trzeba by było sprawdzać, czy połączenie między punktem N a N+1 jest do pokonania.

Przy prostej siatce navamesh nie powinno być to czasochłonne.

Offline Silther

  • Użytkownik

# Maj 01, 2010, 17:00:59
Celne uwagi voytech. Są może jakieś gotowe biblioteki z rozwiązaniami w stylu navmesh albo narzędzia ułatwiające budowanie takiej siatki do własnych gier?

Offline toxic

  • Użytkownik

# Maj 01, 2010, 17:49:33
Celne uwagi voytech. Są może jakieś gotowe biblioteki z rozwiązaniami w stylu navmesh albo narzędzia ułatwiające budowanie takiej siatki do własnych gier?
Nie wiem co to jest warte (bo nie używałem), ale jakiś czas temu na forum tutaj ktoś zwrócił uwagę na Detour i Recast

cytując:
Cytuj
Dla niezorientowanych recast to kod autorstwa Mikko Mononena, potrafiący generować siatki nawigacyjne ze statycznej geometrii etapu (wykorzystując rastry voxelowe). Do tego dochodzi Detour, zajmujący się 'rozumowaniem przestrzennym', czyli mamy tam A* ładnie śmigającą na grafie siatki nawigacyjnej, plus parę pomocnych metod.

W sumie kluczową zaletą Recast'a jest właśnie automatyczne tworzenie navmesha, z czym radzi sobie naprawdę nieźle i daje duże możliwości dostrajania. Do statusu pełnego silnika pathfindingu jednak sporo brakuje. Na przykład, przydałby się format pliku z navmeshem, by móc wyciągnąć generację siatek do preprocessingu, czy omijanie dynamicznych przeszkód.