Odnajdowanie drogi w grach

Ostatnio wracając do domu zastanowiłem się nad sposobem znajdowania drogi przez ludzi. Powody ku temu były dwa. Pierwszym z nich jest fakt, że podczas spaceru nie ma specjalnie co robić. Drugim natomiast powodem jest niezadowalający poziom rozpoznawania drogi przez komputerowe ludki w różnych grach.

Dlaczego jest niezadowalający? Ano dlatego, że takie ludki potrafią dojść wszędzie bez mrugnięcia okiem. Choć zwykle nie mogą mrugać bo szkoda trójkątów na powieki… Tak czy inaczej faktem jest, że bardzo często żeby dojść do jakiegoś miejsca w grze RTS wystarczy wskazać je jednostce na mapie, a ta – mimo iż mapa jest nieodkryta – bez problemu ruszy od razu na miejsce. Jest to, jak na mój gust, trochę zbyt piękne. Przecież po to świat jest zakryty, żeby nie było wiadomo jak dojść, prawda? Dlaczego więc taki ludzik od razu wie?!

Wyobraźmy sobie, że jesteśmy w miejscu, którego dobrze nie znamy. Wiemy jedynie że trzeba iść w "TĘ" stronę. No i teraz dochodzimy w pewnym momencie do muru. Trzeba wybrać – prawo, lewo. Jeśli nie znamy miejsca to to nie ma najmniejszego znaczenia. Idziemy w lewo. Okazuje się, że natrafiliśmy na ślepy zaułek i trzeba się cofnąć.To wracamy i idziemy w prawo i tam później powiedzmy udaje nam się dojść do tego upragnionego WC. Po drodze oczywiście skrupulatnie rysowaliśmy sobie wszystko na mapie, żeby znajomi nie musieli się męczyć.

Bardzo interesującym byłoby zastosowanie tego typu rozwiązania w grze. Powiedzmy, że mamy jakąś część mapy odkrytą. Jednostka może w obrębie odkrytego obszaru korzystać z algorytmów wyszukiwania takich jak A* czy wariacje na jego temat. Jednak kiedy chcemy wysłać jednostkę w przestrzeń jeszcze nie zbadaną – powinna iść zwyczajnie na chybił trafił. Takie coś zwiększyłoby jeszcze bardziej znaczenie jednostek zwiadowczych, które i tak poruszają się jak mucha po oknie…

Reklamy

4 myśli nt. „Odnajdowanie drogi w grach

  1. …I tak i nie. Rozumiem, że jeśli już poruszamy się w komputerowym świecie, to na myśl przychodzą algorytmy, np.: pseudolosowanie (chybił-trafił), ale „nie tędy droga”.
    Po pierwsze, nie możemy patrzeć na mapę jak na płaski 2-wymiarowy labirynt. Człowiek idąc obserwuje otoczenie, rozwiązuje jego strukturę, która notabene została zaprojektowana przez innego człowieka, a więc jest absolutnie przewidywalna. Poruszajmy się w trzech wymiarach, dojrzyły wierzchołek nadawczy oddalony o 10 minut drogi od nas, przypatrzymy się cieniom, a nawet wiatrom gnającym poprzez zabudowę.
    Po drugie, taki ludek, jeśli już będzie upodabniany do człowieka, na pewno nie skorzysta z wyboru drogi na „chybił-trafił” (tak to można robić w erpegach). W rzeczywistości korzystamy jednak z jakichś zawiłych mogłoby się wydawać nieracjonalnych algorytmów, których po prostu jeszcze nie znamy, a większość z nich nazywamy /intuicją, 6 zmysłem, orientacją w terenie, szczęśliwym trafem/ – nie bez powodu przecież mówi się o „ludziach urodzonych w czepku”…
    No cóż, dużo tu cudzysłowów, co jedynie świadczy o naszym mglistym (przynajmniej w sensie matematycznym) pojęciu o sposobie podejmowania decyzji przez człowieka – dostajemy wiele sygnałów, które przetwarzamy wielotorowo, a tego tak łatwo odwzorować się nie da.
    Rozwiązanie, półśrodkiem mogłoby być zdefiniowanie ów „farta” danej jednostki w swojej podróży, i tak jedne trafiałyby regularnie do celu szybciej od innych, a dla rozmydlenia tego prostego rozwiązania możnaby dodać jednostkę z parametrem losowym, która zachowywałaby się raz tak raz owak.
    Już czekam na odzew w postaci przepisów na „idealne niedoskonałości wędrówek po drzewach (chmurach?) binarnych” 🙂

    • Całkiem zgrabnie to ująłeś 🙂

      Zdaję sobie oczywiście sprawę z tego, że nasze postrzeganie jest niezbadane i trudno wyznaczyć jakiś algorytm jakim się posługujemy. Jednakże moim celem nie jest symulacja człowieka, a jedynie stworzenie pozorów jakiegoś stopnia realizmu.

      Jeśli patrzyłbym na kogoś poruszającego się po nieznanym mu terenie to mógłbym jego ruchy określić jako zwykłe łażenie w prawo i lewo szukając odpowiedniej drogi. Myślę, że coś takiego dałoby się osiągnąć stosunkowo małym kosztem.

      Interesujące wydało mi się natomiast rozwiązanie ze współczynnikiem „farta” 😉 Ciekawie by wyglądało gdyby szła sobie grupka robotników i nagle wszyscy się rozłażą i każdy idzie po swojemu. To też by trochę przypominało ludzkie zachowania 🙂

  2. Jeszcze jedno. Zarówno w grach, np. RTS czy normalnym życiu poruszamy się nie bez powodu. Kiedy idziemy zmierzamy do jakiegoś celu, miejsca. I to właśnie ono definiuje nasze poczynania i wybory podczas marszu.
    Jest to zasadnicza różnica w stosunku do chłopka CPU poruszającego się po omacku po pewnym terenie – ten ma w zasadzie równe szanse błąkać się w nieskończoność, co trafić do celu bezbłędnie, dla człowieka natomiast oczywistym jest, iż w końcu dokądś dojdzie, a przy tym kilkukrotnie się zgubi (aż się nauczy).
    Trzeba by przemyśleć wszelkie ważniejsze aspekty ruchu, drogi, punktu startowego, celu i niezbadanego terenu… a to wiąże się z „odnajdywaniem” (zgadywaniem) drogi w czasie rzeczywistym i to z powrotami. Hmm, póki co brzmiało nierealnie, ale rozwiązanie jest podane wręcz jak na tacy 🙂
    Dobrze rozumuję, wystarczy działać na, no, dość skomplikowanym algorytmie z powrotami w RT zamiast obliczać najkrótszą (najszybszą) trasę z checkpoint’ami, jak to ma miejsce we współczesnych grach (logistyka się kłania)?

    • Nie chodziło mi o losowe błąkanie się po całej mapie. Ja myślałem o błąkaniu się tylko po nieodwiedzonych terenach. Dla znanych (wcześniej odwiedzonych) możnaby już stosować jakieś dokładniejsze algorytmy.

      Wówczas ludek błąka się tylko przy granicy obszaru, który zna. Jeśli kazałbym mu pójść gdzieś gdzie mapa jest już odkryta to trafiłby tak jak to ma miejsce w teraźniejszych grach.

      Co do pomysłu z algorytmem z powrotami – nie sądzę aby był konieczny. Jeśli istnieje droga to ludek – idąc tam gdzie go jeszcze nie było – w końcu ją odkryje 🙂

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s