AI w grach - dlaczego boty są głupie? Cz I.

IP: *.neoplus.adsl.tpnet.pl 03.01.10, 04:17
AI w grach - dlaczego boty są głupie?

Cześć I,

Wszyscy o czymś robią tutoriale, zrobię i ja smile

Jakość AI w grach jest tematem wałkowanym od wielu lat. W tym poście chciałbym przybliżyć
typowe problemy związane z implementacją realnych zachowań przeciwników. Skupię się
głównie na tych grach, gdzie rzeczywiście mamy do czynienia z AI, a nie wyreżyserowanym
pojawieniem się aktora w punkcie X i odegraniu animacji Y bez głębszej logiki interakcji z
otoczeniem czy graczem (np. przygodówki, Heavy Rain taki np. czy inne point-and-clicki)

Nie będę tutaj za bardzo zagłębiał się w historię tematu, ponieważ zwyczajnie najfajniejsze
rzeczy dzieją się w nowożytnej historii gier: lata 2000-czne.

Generalnie rzecz biorąc AI w grach jest tematem bardzo szerokim, a przynajmniej takowym
było gdy na rynku istniało wiele gatunków gier. W tej chwili mówimy tak naprawdę dwóch
gałęziach, w których AI stanowi poważne wyzwanie dla programistów:

1) Strategie RTS i przede wszystkim AI grupowe
2) FPSy i TPSy

Zacznijmy jednak od czegoś prostego, np. takie Diablo. Typowy algorytm przeciwnika AI w
slasherze wygląda mniej-więcej tak:

a) znajdź gracza na mapie
b) zmierz odległość do niego i ustal czy zacząć atakować czy nadal odgrywać
animację "oczekiwania"
c) jeśli atakować to korzystając z algorytmów wyszukiwania ścieżki zmniejszaj odległość do
gracza
d) będąc w polu rażenia aktualnej broni sprawdź czy gracz nie walczy już z kimś innym
e) jeśli walczy: to albo używaj słabszego ataku albo "zakolejkuj" się czekając aż gracz pokona
aktualnego wroga
Najbardziej to można dzisiaj zaobserwować np. w Dante's Inferno, gdzie
przeciwnicy "tańczą" dookoła gracza czekając na okazję do ataku. Dlaczego nie atakują? Bo
zwyczajniej popsułoby to gameplay czyniąc grę trudniejszą i mniej przewidywalną dla gracza
(popsułoby, nie?). Z tego też względu AI sprawdza na bieżąco ile przeciwników zadaje
obrażenia graczowi w danej chwili. Zależnie od poziomu trudności (rzaaaaaaadko) i sztywnych
ustawień wynikających z określonego experiencu jaki gracze mają osiągać
(częęęęęęęęęęęęęęściej) AI albo pozwala na zadawanie obrażeń albo kolejkuje przeciwnika
aby się do czekał swojej szansy. Oczywiście gdy gracz zadaje atak grupowy to dostają
wszyscy, także ci w kolejce smile

f) jeśli gracz ucieka to podążaj za nim dopóki odległość nie zwiększy się do X jednostek (lub
ścigając go nie pokonasz X odległości) - wtedy zaprzestaj i przejdź w tryb oczekiwania.
Ten mechanizm ma za zadanie przede wszystkim stworzyć wrażenie presji na
gracza z jednej strony, z drugiej zaś minimalizować sytuacje gdzie za graczem podąża cała
horda, przez całą mapę (mało wydajne). W dzisiejszych grach jednak ten mechanizm jest
coraz rzadziej obserwowalny ponieważ gameplay tak naprawdę dzielony jest na poszczególne
areny walki, na których gracz jest przytrzymywany (np. zatarasowane przejście) po to aby
zwiększyć intensywność walki / doznań (nie możesz już uciekać przed Butcherem po całych
katakumbach) po drugie efektywnie zaimplementować wyreżyserowane przejścia pomiędzy
arenami, np.: przechodzisz dalej bo zatarasowane przejście nagle zostaje rozwalone przez
wielkiego kizia-mizia, z którym walczysz na następnej arenie.

Back-on-track, nazwijmy to algorytmem "Mięsa Armatniego", czyli ogólnie rzecz biorąc:
biegną ci pod topór tępe pały.

Jak widać jest to nieskomplikowany algorytm i w dużej mierze w podobnym kształcie był
stosowany w pierwszych FPSach lub w budżetówkach, np. Painkiller. Budżetowe FPSy z City-
Interactive to inna bajka gdyż korzystają oni z JupiterEx'a, który ma zaawansowane AI
(mechanizmy, a nie zaimplementowane przez CI), ale do tego jeszcze wrócimy.

Zajmijmy się na chwilkę RTSami. Jakie tam są największe wyzwania? W przeciwieństwie do
przypadku opisanego powyżej w RTSach dochodzi jeszcze jeden ważny element AI, który ma
wpływ na gameplay w stopniu bardziej zauważalnym niż w slasherach. Tym elementem jest
grupowa decyzyjność, działanie w grupie. Na czym to polega?

Otóż w RTSach przeważnie mamy do czynienia ze znacznie bardziej skomplikowaną strukturą
mapy, z punktu widzenia nawigacji AI, niż w slasherach, a czasami też i w FPSach. W tych
ostatnich walka jest praktycznie zawsze ograniczona do jakiegoś obszaru (patrz uwaga dot.
hord podążających za graczem przez całą mapę) zatem działania AI w dużej mierze są
lokalne, tzn. ograniczone do bezpośredniego sąsiedztwa gracza. W RTSach jest trudniej,
ponieważ "gracz", czyli cel ataku, to tak naprawdę każda jednostka przez "gracza" sterowana.
Po pierwsze mamy tutaj wiele lokalnych obszarów podejmowania decyzji przez AI - tak wiele,
jak wiele jednostek ma gracz. Dwa mapa jest bardziej złożona, bardziej dynamiczna (gracz
może postawić budowle praktycznie wszędzie i zablokować dany obszar mapy) i co więcej: w
tym przypadku jest porządane wręcz aby AI aktywnie poszukiwało jednostki / budowle gracza
na mapie i przeprowadzało ataki, nawet jeśli oznacza to przeprowadzić 20 zelotów na drugi
koniec mapy.

Teraz, jeśli zastosujemy patent ze slasherów ("Mięso Armatnie" to ruch takich jednostek będzie
wyglądał bardzo sztucznie, ponieważ będą np. iść gęsiego, krok w krok. Dlaczego? Bo każda
z nich wyliczyła tę samą, optymalną scieżkę dotarcia do gracza! W slasherach tego tak
bardzo nie widać ponieważ programiści załatwiają to początkowym rozstawieniem
przeciwników, np. w grupach po kilku do okoła gracza / miejsca, które wyzwala zdarzenie
generujące wrogów.

Co zatem możemy zrobić? Po pierwsze zróżnicować zachowanie AI: jeśli jednostka jest jedna
(np. special unit albo akurat gracz zaznaczył jedną) to stosujemy podobny algorytm do
slasherów. Jeśli gracz zaznaczył grupę jednostek to wykonuj obliczenia dla grupy, a nie
poszczególnych jednostek. Wiąze się to z następującymi problemami:

1) Rozmieszczenie jednostek w grupie tak, aby wyglądało to przekonowująco, np. żołnierze
ustawiają się w formacji, zeloty biegną w "kupie".
2) Wyszukanie jednej ścieżki dojścia do celu ataku dla całej grupy, biorąc pod uwagę wiele
czynników, np. to, że w grupie są jednocześnie jednostki lądowe jak i powietrzne; takie które
poruszają się szybko i takie, które poruszają się wolno, ale np. mogą niszczyć elementy
scenerii (takie jak drzewa), które te słabsze jednostki muszą omijać.
3) Zachować w miarę możliwości szyk formacji

Pierwszy problem jest kluczowy z kilku względów. Przede wszystkim gdy jednostki atakują w
grupie powinny ustawiać się tak, aby wyglądało, że każda z nich ma czyste pole strzału,
głównie po to aby uzyskać przekonujący efekt wizualny. Ten problem jest dość prosty do
rozwiązania: zajmij pozycję dookoła celu, w okreslonym promieniu zachowując
określoną "gęstość zaludnienia" na jednostce mapy: czyli zachowaj odpowiednią odległość od
sąsiada. W starcrafcie np. często widać jak atakujące zeloty pomimo tego, iż mają "manualny"
atak, a stojąc w pewnej odległości i tak zadają obrażenia. Dzieje się tak dlatego, iż algorytm
wyliczył, że nie da się "obstawić" cel ataku wszystkimi równo dookoła nie łamiąc w/w reguł,
zatem dopuszcza się pewne oszustwo: nawet ataki "manualne" mają pewien zakres
skuteczności, umożliwiający zadawanie obrażeń nawet gdy "nie dotykamy" wroga, ale
szczekamy w jego kierunku.

-
    • Gość: strzyka_w_kolanie Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.neoplus.adsl.tpnet.pl 03.01.10, 04:18
      -
      • Gość: smutny człek. Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.adsl.inetia.pl 03.01.10, 09:16
        Może kiedyś zrobią Mądrę al w FPS.
        • don_wroc_love Re: AI w grach - dlaczego boty są głupie? Cz I. 03.01.10, 19:16
          @strzykaweczka
          no proszę... jak chcesz to potrafisz wink

          fajny tekst smile
          • Gość: strzyka_w_kolanie Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.neoplus.adsl.tpnet.pl 04.01.10, 23:32
            Wez don_wroc_love, nie przesadzaj bo...kurna zaczne Cie lubic wink

            O FPSach bedzie wiecej fajnych rzeczy, m.in. AI Fear2 vs. MW2 smile
        • bzykacz0 Re: AI w grach - dlaczego boty są głupie? Cz I. 07.01.10, 17:53
          Pomimo tego że jestem graczem, a programowanie to raczej hobby (dobrze wiedzieć
          jak coś działa) , to wszystko tutaj zawarte wiedziałem, lata gry i trochę
          modingu i człowiek już może powiedzieć jak większość gier działa i samemu je
          przerabiać. AI to trudna kwestia dla tego że opiera się na schematach
          (algorytmach), dlatego trudno osiągnąć "inteligentne" AI w grach, gdy powtarzamy
          jakąś czynność AI najczęściej zachowuje się tak samo, albo jest czynnik losowy i
          po prostu delikatnie zmieni swą decyzje i zajdzie nas zamiast od lewej to od
          prawej, ale sytuacje będzie podobna. Trudno to dostrzec jeśli gramy w jakąś grę
          tylko raz, bo wtedy zapas schematów się nie skończy i sytuacje będą za każdym
          razem odrobinę inne, ale jeśli gramy długo automatycznie przewidujemy zachowanie
          AI. Ciekawe czy powstanie za mojego życia AI które będzie podpuszczać gracza,
          zwodzić, zmieniać swą decyzje na bieżąco, wykorzystywać świat gry na swoją
          korzyść, a to nie będą algorytmy. tongue_out
      • Gość: shalick Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.internetdsl.tpnet.pl 07.01.10, 14:47
        Nieźle!
        Zastanawiam się tylko, czy post nie jest za bardzo "po środku". Mam namyśli, za
        prosty dla programisty, zbyt skomplikowany dla nieprogramisty.
        Masz na przykład takie zdanie: "Gdy cel przestał istnieć to zastosuj
        zaawansowaną heurystykę adaptacyjną poszukiwania skorelowanych potencjalnych
        obszarów decyzyjnych". Whoa dude! Heurystyka? Obszary decyzyjne? Poważnie...

        Tak czy inaczej - czekamy na więcej.

        Swoją drogą - zastanawiam się ilu mamy tu programistów.
        • Gość: Babka z Marsa Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.chello.pl 12.01.10, 23:11
          shalick: czytaj ze zrozumieniem. Ten fragment to był dowcip.
    • lesfoj Re: AI w grach - dlaczego boty są głupie? Cz I. 04.01.10, 09:54
      > Teraz, jeśli zastosujemy patent ze slasherów ("Mięso Armatnie" to ruch takich j
      > ednostek będzie
      > wyglądał bardzo sztucznie, ponieważ będą np. iść gęsiego, krok w krok. Dlaczego
      > ? Bo każda
      > z nich wyliczyła tę samą, optymalną scieżkę dotarcia do gracza!

      Co bardzo dobrze widać choćby w C&C Generals wink
    • gary_joiner Re: AI w grach - dlaczego boty są głupie? Cz I. 07.01.10, 20:30
      Ciekawy art, bardzo techniczny, ale ciekawy. Gratulacje.

      Co do SI przeciwników w RTSach to z roku na rok tracę nadzieję na jakiś przełom
      w tej dziedzinie. Podczas rozgrywania kampanii dla pojedynczego gracza,
      najczęściej mocno fabularyzowanej, komputer zwyczajnie nie może być zbyt
      "sprytny", bo w większości misji to on rozpoczyna z pozycji siły. Człowiek
      zwyczajnie nie miałby szans, więc musi zadowolić się nudą i monotonią.

      Potyczki z botami, w których każdy początkowo ma równe szanse dają programistom
      większe szanse wykazania się kunsztem, ale tutaj pojawia się podobny problem.
      Komputerowy przeciwnik, który byłby w stanie na bieżąco adaptować strategię
      rozwoju i taktykę walki do sytuacji, płynnie reagować na zachowanie człowieka
      byłby na z góry wygranej pozycji. Bo jest w stanie robić wszystko na raz i jest
      w stanie zrobić to szybciej. To trochę tak jak z programami szachowymi: dobry
      gracz jest w stanie pokonać komputer jeżeli ma odpowiednio dużo czasu na
      zastanowienie. Podczas rozgrywania pięciominutowej partii szansa na sukces
      człowieka jest marginalna.

      Dobre RTSowe AI wyobrażam sobie następująco: Komputer dysponuje pewną, dużą,
      liczbą standardowych "otwarć", każdy jego ruch jest jedną z wielu
      alternatywnych, z góry uwzględnionych, reakcji na zachowania gracza. Gdy
      rozgrywka wychodzi poza zbiór standardowych "otwarć" komputer zaczyna "myśleć"
      samodzielnie, jest w stanie zlokalizować słabe strony przeciwnika i wykorzystać
      je do zwycięstwa. Nie wykorzystuje jednak wszystkich swoich możliwości. Na
      poczynania gracza reaguje z ludzkim opóźnieniem, koncentruje się na jednym
      aspekcie rozgrywki na raz.

      Zastanawiam się czy coś takiego byłoby możliwe do realizacji w czasach, kiedy
      liczy się tylko multiplayer. Jeżeli wypisuję głupoty to wybaczcie, nie mój
      konik. Jedyne SI jakie zaprogramowałem potrafiło grać w kółko i krzyżyk i
      opierało się na kilku if'ach wink
      • Gość: Logan Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.neoplus.adsl.tpnet.pl 08.01.10, 09:38
        Jeśli chodzi o AI w fpsach to już taki HL1 miał
        wg Mnie bd AI zwłaszcza żołnierzy, chłopaki potrafili
        zachodzic od tyłu, przegrupowywać się
        celnie miotac granaty, mimo upływu lat AI
        z HL1 nie ma się czego wstydzić. Zwłaszcza że
        niektóre nowsze fpsy nie mają czym się
        poszczycić, nawet osławione MW2. Tam w kompani, wsytarczyło
        lezeć plackiem koło jakiegos murka i można było bez obaw ostrzeliwywać
        idiotów którzy biegali po otwartym polu.
      • Gość: strzyka_w_kolanie Re: AI w grach - dlaczego boty są głupie? Cz I. IP: *.neoplus.adsl.tpnet.pl 08.01.10, 19:30
        gary_joiner napisał:

        > To trochę tak jak z programami szachowymi: dobry
        > gracz jest w stanie pokonać komputer jeżeli ma odpowiednio dużo czasu na
        > zastanowienie. Podczas rozgrywania pięciominutowej partii szansa na sukces
        > człowieka jest marginalna.

        Nie do końca. W szachach mamy do czynienia z inną mechaniką. Tutaj są bardzo sztywne
        reguły gry, ruchu figur, kto kogo i kiedy może załatwić. Dla komputera jest to wręcz
        wymarzona sytuacja: przebieg rozgrywki jest przewidywalny praktycznie w każdym momencie
        gry - wystarczy jedynie bardzo szybko liczyć smile Im dalej grasz w szachy tym bardziej
        zaburzasz początkowy szyk figur po obu stronach, z każdym ruchem figur ubywa, zatem?
        Zatem dla komputera oznacza to zawężanie zbioru możliwych rozwiązań do przetestowania.
        Big Blue właśnie tak wygrał z Kasparowem: patrząc na aktualny układ sił na szachownicy
        kumputer przelicza wszelkie możliwe scenariusze ruchu oponenta, aż do momentu gdy dalsza
        gra jest niemożliwa: brak figur albo zachodzą warunki przegranej / zwycięstwa. I tak miliardy
        razy na sekundę. Jeśli człowiek wygrywa z komputerem w szachy to tylko i wyłącznie dlatego,
        iż algorytm ma dziury (zgodnie z intencją progamistów lub też w wyniku błędu).

        Jednak tutaj nie mamy do czynienia z AI tak na prawdę, sztuczną inteligencją, tylko bardzo
        szybkim kalkulatorem smile zatem szachy nie są właściwym przykładem, chociaż na pewno
        bardzo interesującym etapem rozwoju AI.

        > Dobre RTSowe AI wyobrażam sobie następująco: Komputer dysponuje pewną, dużą,
        > liczbą standardowych "otwarć", każdy jego ruch jest jedną z wielu
        > alternatywnych, z góry uwzględnionych, reakcji na zachowania gracza. Gdy
        > rozgrywka wychodzi poza zbiór standardowych "otwarć" komputer zaczyna "myśleć"
        > samodzielnie, jest w stanie zlokalizować słabe strony przeciwnika i wykorzystać
        > je do zwycięstwa. Nie wykorzystuje jednak wszystkich swoich możliwości.

        Ależ w RTSach to właśnie tak działa, tylko nie do końca smile Taktyka AI to tak na prawdę
        rozgrywanie właśnie zaprogramowanych przez twórców scenariuszy, przeważnie
        zdefiniowanych dla każdej z map oddzielnie. Ogranicza się to jednak do rozwoju bazy i
        produkowania określonej ilości jednostek wg modelu, w którym np. lekka piechota stanowi tyle,
        a tyle % ogółu jednostek, bo CPU myśli właśnie w ten sposób. AI nigdy nie dobije Ciebie po
        ciężkim ataku, w którym straciło swoje najlepsze jednostki, ale sporo zniszczyło Twoich
        umocnień i teraz właśnie za ostatnią kasę zbuduje czołg, poświęcając wszystko wyślę go do
        Twojego HQ i dobije punkt dowodzenia wygrywają rundę tym samym. To są już przejawy
        owego myślenia, myślenia abstrakcyjnego, które dla AI jest na chwilę obecną niedostępne bo
        jeszcze nikt nie wynalazł algorytmu opisującego abstrakcyjne myślenie smile

        Trochę się rozpisałem, ale podsumowując AI może walczyć z człowiekiem tylko na dwa
        sposoby (przynajmniej jeśli chodzi o stan na 8 grudnia 2010 smile:

        1) gasić pożary - reagować w z góry określony sposób na poczynania gracza jeśli oczywiście
        rozpozna zdefiniowany wzorzec
        2) testować wiele liniowych hipotez celem "wyprzedzenia" ruchów gracza

        Wszystko to jednak sprawdza się tylko i wyłącznie w jednej sytuacji: gdy AI rozpoznaje
        wzorzec zachowań, który inicjuje taki, a nie inny algorytm. Aby rozpoznać taki wzorzec AI
        wielokrotnie testuje np. stan posiadania gracza, ruchy jego jednostek i próbuje dopasować je
        do zdefiniwanych przez programistów wzorców w swojej bazie danych.
    • Gość: strzyka_w_kolanie Trochę z innej beczki, ale też w temacie AI IP: *.neoplus.adsl.tpnet.pl 10.01.10, 00:10
      Weż spotkaj to w ciemnym zaułku...

      www.youtube.com/watch?v=W1czBcnX1Ww
      • toir Re: Trochę z innej beczki, ale też w temacie AI 16.01.10, 21:17
        Niesamowite, naprawdę...moment z kopnięciem tego stwora. Niby podejrzewałem, że
        ludzie robią zaawansowane maszyny, ale to jest coś, co mnie zdruzgotało.
Pełna wersja