Autor Wątek: AI omijanie przeszkód  (Przeczytany 8324 razy)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 28, 2007, 20:40:43
Cytuj
Jesli sprawdzamy kolizjie z prostokatem to po cholere robic 8 kolizji zamiast 1? I marnowac moc obliczeniowa, pisac wiecej kodu itd. itp. Troche logiki by wam sie przydalo ;]
W przypadku mapy z kafli to podejście sprawdza się całkiem fajnie, tyle że testujemy punkty znajdujące się na narożnikach prostokata otaczającego. Wtedy mamy gwarancję, że nic nie przegapimy, o ile postać jest mniejsza niż kafel. Sama kolizja punkt-tilemapa jest banalna do zaimplementowania. :)

Offline Mr. Spam

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

upshader

  • Gość
# Lipiec 28, 2007, 20:47:28
Cytuj
Jesli sprawdzamy kolizjie z prostokatem to po cholere robic 8 kolizji zamiast 1? I marnowac moc obliczeniowa, pisac wiecej kodu itd. itp. Troche logiki by wam sie przydalo ;]
W przypadku mapy z kafli to podejście sprawdza się całkiem fajnie, tyle że testujemy punkty znajdujące się na narożnikach prostokata otaczającego. Wtedy mamy gwarancję, że nic nie przegapimy, o ile postać jest mniejsza niż kafel. Sama kolizja punkt-tilemapa jest banalna do zaimplementowania. :)
Jesli wielkosc postaci odpowiada jednemu kaflowi, i jeden bit na mapie zajetosci odpowiada jednemu kaflowi, oraz postac przemieszcza sie skokowo "co kafel", to mozemy przyjac, ze reprezentujemy postac jako punkt i sprawdzac na mapie zajetosci tylko kolizje punkt-punkt, na ktory ma zamiar przemiescic sie postac w aktualnej klatce. Nie widze potrzeby robienia wiecej niz 1 testu.

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 28, 2007, 21:33:41
postac przemieszcza sie skokowo "co kafel"
W takim przypadku ciężko mówić wogóle o jakimkolwiek teście kolizji z prawdziwego zdarzenia, tylko o sprawdzeniu warunku wejścia na pole. :)

upshader

  • Gość
# Lipiec 28, 2007, 22:02:59
postac przemieszcza sie skokowo "co kafel"
W takim przypadku ciężko mówić wogóle o jakimkolwiek teście kolizji z prawdziwego zdarzenia, tylko o sprawdzeniu warunku wejścia na pole. :)
No wlasnie. Problem w tym, ze autor tematu nie wyspecyfikowal zadnych zalozen odnosnie swojej gry. Nie wiemy w ilu kierunkach ma poruszac sie postac, czy ma poruszac sie skokowo czy plynnie, czy mapa bedzie skladala sie z kafli a nawet ilo wymiarowa bedzie przestrzen gry. Mozemy sobie tylko zgadywac i snuc przypuszczenia :)

Btw. zwal jak zwal. Kazdy test kolizyjny jest tak naprawde "warunkiem wejscia na pole", z tym, ze stopien skomplikowania tych warunkow rozni sie od siebie :)
Pomijam oddzialywania fizyczne ktore moga towarzyszyc temu testowi ;)
« Ostatnia zmiana: Lipiec 28, 2007, 22:07:21 wysłana przez upshader »

Offline dx0ne

  • Użytkownik
    • Pierdoły od dx0ne'a

# Lipiec 28, 2007, 22:41:08
@upshader:
tylko nie pogryź klawiatury. i sam się zastanów zanim coś napiszesz.

postaram się wytłumaczyć Ci to jak 7 latkowi... który myśli że wszystkie rozumy pozjadał, potem widać zwymiotował.
Detektory stosuje się w grach np we flashówkach w połączeniu z hittestem (+ shape flag) co daje taki można powiedzieć per pixel tylko uproszczony.
I nie muszą one być punktem. Ale po cóż taki "kretyński debilizm"?! Ano np żeby testować kolizję spriteów o złożonym kształcie lub po prostu złożonych obiektów. Wystarczy zwiększyć promień detektora(i/lub jego geometrię) aby nie było tego nad czym się tak trzęsiesz czyli przestrzałów. Ale po co kilka testów jak można jeden? np żeby wiedzieć gdzie dokładnie zachodzi kolizja i zareagować odpowiednio animacją (inna dla upadku na ziemie, inna dla przesuwania pudła, inna reakcja przy trafieniu głowy inna dla dajmy na to odwłoka). I chyba najpierw się robi aabb, a potem bardziej złożone.
I tak już na koniec: Twoja mapa bitów dla dużych obiektów to nic innego jak kilka detektorów(obiekt jeden - testów kilka).

Cytuj
Nie widze potrzeby robienia wiecej niz 1 testu.
parafrazując: trochę wyobraźni by Ci się przydało
tylko nie pisz już o tym jak to "będziesz" robił. i na bogów eterni nie myśl sobie że to co napisałeś jest skomplikowane.
CZŁOWIEKU!

upshader

  • Gość
# Lipiec 28, 2007, 23:03:51
Cytuj
"kretyński debilizm"?!
Widac probujesz manipulowac moimi slowami, wpychajac mi w usta slowa ktorych nie wypowiedzialem. Niby kogo cytujesz? Bo na pewno nie mnie. Mysle, ze na tym poziomie konwersacji jaki reprezentujesz w ogole nie powinienem polemizowac z Toba. Ale zrobie ten jeden wyjatek i odpowiem.

Cytuj
Wystarczy zwiększyć promień detektora(i/lub jego geometrię) aby nie było tego nad czym się tak trzęsiesz czyli przestrzałów.
Jesli zakryjesz "detektorami" cala powierzchnie do okola obiektu, to nie ma w ogole powodow aby cos takiego stosowac, zamiast bryly otaczajce obiekt lub jego czesci (czytaj nizej).
A jesli nie zakryjesz calej powierzchni, to zawsze beda szpary przez ktore moga wejsc male obiekty - takze takie rozwiazanie jest niepoprawne.

Cytuj
Ale po co kilka testów jak można jeden? np żeby wiedzieć gdzie dokładnie zachodzi kolizja i zareagować odpowiednio animacją (inna dla upadku na ziemie, inna dla przesuwania pudła, inna reakcja przy trafieniu głowy inna dla dajmy na to odwłoka).
Dokladnie to sie robi na brylach otaczajacych czesci obiektu. Jakbys troche pomyslal zamiast sie pienic to moze bys zrozumial, ze mozesz rece obiektu zamknac w boxy(albo inne bryly), tlow, glowe i co tam chcesz i osiagnac dokladnie to samo co swoimi "detektorami". Ta technike uzyto w Counter Strike'u i wielu innych grach.

Cytuj
I chyba najpierw się robi aabb, a potem bardziej złożone.
Test sfera-sfera jest najprostszy bo wymaga tylko sprawdzenia czy suma promieni jest wieksza niz odleglosc srodkow. I liczac odleglosc nie trzeba nawet liczyc pierwiastka. Mozna porownywac kwadraty odleglosci ;]

Cytuj
I tak już na koniec: Twoja mapa bitów dla dużych obiektów to nic innego jak kilka detektorów(obiekt jeden - testów kilka).
Owszem jest to co innego. Przemysl zanim napiszesz. Ilosc testow nie ma tu znaczenia (pomijam fakt, ze testowanie masek bitow odbywa sie przy uzyciu minimalnej ilosci cykli procesora) tylko to czy testujesz powierzchnie obiektu, czy przestrzen do okola niego.
Cytuj
i na bogów
A jesli juz musisz powolywac sie na sily wyzsze w swojej argumentacji to powinienes przynajmniej przyjac do wiadomosci, ze slowo to piszemy z wielkiej litery.

Cytuj
tylko nie pogryź klawiatury.
Cytuj
myśli że wszystkie rozumy pozjadał, potem widać zwymiotował.
Tych i innych zaczepek na poziomie przedszkolaka nie bede nawet komentowal. Nie jest to poprostu moj poziom, takze nie licz na jakiekolwiek nastepne moje odpowiedzi na Twoje posty. Powinienes miec swiadomosc, ze bedziesz konwersowal sam ze soba :)

Pozdrawiam.
« Ostatnia zmiana: Lipiec 28, 2007, 23:20:12 wysłana przez upshader »

upshader

  • Gość
# Lipiec 28, 2007, 23:58:10
[OT]
Cytuj
Cytuj
i na bogów
A jesli juz musisz powolywac sie na sily wyzsze w swojej argumentacji to powinienes przynajmniej przyjac do wiadomosci, ze slowo to piszemy z wielkiej litery.
AFAIK "Bog" jako konkretna osoba z duzej, "bogowie" raczej z malej :).
[/OT]

Offline Solus

  • Użytkownik

# Lipiec 29, 2007, 00:05:38
Ludzie ludzie zaczynacie schodzic z tematu ...
załozyciel tematu miał w zamysle stworzenie w przestrzeni trójwymiarowej tzw przez niego         " detektorów kolizji " - grzecznie dopytując czy macie mu cos lepszego do zaoferowania

zadne kafelki ani inne duperele tu niepomogą

moge tylko nakierowac by rozejrzec sie u pana google za raytracingiem albo sciezki ruchu (tu trzeba sie zastanowic) moze jakos pomogłem ... w kazdym badz razie zamiast narzekac na niewiedze innych postarałem sie cos zaproponowac ... jesli wiecie wiecej na ten temat rozwijajcie go...  ;)

upshader

  • Gość
# Lipiec 29, 2007, 01:25:57
Dobra, to teraz bardziej merytorycznie. Chociaz i tak za duzo niewiadomych pozostawil autor aby dobrze cos doradzic.
Podstawowym pytaniem jest czy potrzebujesz wykrywania kolizji (pomysl z "detektorami" tylko do tego moze sie nadawac), czy wyszukiwania drogi. Wspominales cos o tym, ze to przeciwnik ma sie ruszac (AI), dlatego obstawiam, ze bardziej Ci sa potrzebne "decyzjo_podejmowacze" niz "detektory" :P
Wiec potrzebujesz dwoch rzeczy:

1) po pierwsze musisz miec jakas reprezentacje wezlow i polaczen miedzy nimi - na ktorych bedzie dzialal algorytm wyszukujacy droge. Czyli odpowiednio zaprojektowana strukture danych. Kratki wcale nie sa takim zlym pomyslem. Nawet w swiecie 3D, mozesz podzielic swiat na male kratki (np. 1x1cm wedle uznania), a nastepnie sprawdzac czy na dane pole nachodzi jakis obiekt, jesli tak, to stawiasz 1, a jesli nie to 0. Jesli masz spora plansze, to tych kratek rowniez bedzie duzo. Mozliwe, ze za duzo abys przetrzymywal to na raz w ramie, albo za duzo aby optymalnie szukac drogi. W takim przypadku zastosuj drzewa czworkowe co znacznie poprawi oba czynniki. Metoda ta ma takie zalety, ze stworzenie mapy zajetosci moze byc automatyczne (nie jest potrzebna ingerencja leveldesignera), i dosc prosto to zaimplementowac. Jesli mimo wprowadzenia drzew czworkowych okaze sie, ze kratek jest i tak za duzo aby sprawie wyszukiwac droge proponuje drugie rozwiaznie: punkty widocznosci.
Polega to na tym, ze rozkladasz sobie odpowiednia ilosc punktow na mapie (prawdopodobnie bedzie musial zrobic to leveldesigner, jesli nie opracujesz metody samoistnego rozkladania punktow. A mimo, iz wiem, ze sa takie metody polecam zrobienie tego samodzielnie. Zaowocuje to mniejsza iloscia punktow i lepszym rozlozeniem. A algorytm ktory bedzie robil to automatycznie wcale nie musi byc taki prosty) a nastepnie laczysz owe punkty ze soba. Dwa punkty mozesz polaczyc tylko wtedy kiedy jest bezposrednie przejscie z jednego do drugiego po lini prostej (czyli zaden obiekt nie blokuje przejscia). Jak to zrobisz prawidlowo powstanie pewien graf. Plusy tej metody? Mniejsza ilosc wierzcholkow=szybszy czas odnajdywania drogi, za to minusem jest to, ze ktos bedzie musial rozlozyc te punkty.
Gdyby oba rozwiazania Ci nie pasowaly mozesz zapoznac sie jeszcze z technika siatek nawigacyjnych (Perelki Programowania Gier tom 1)

2) Potrzebny Ci algorytm odnajdywania drogi. Czyli cos co przeszuka polaczenia pomiedzy wierzcholkami (czy to beda kratki, czy way-pointy) a nastepnie wybierze najkrotsza (badz najlepsza z taktycznego punktu widzenia) droge. Najpopularniejszym z algorytmow jak juz ktos wspomnial jest A*.  Polecam uzycie go. Jednak powinienes wiedziec, ze w pewnych wypadkach A* nie jest najlepszy. Nie jest najlepszy wtedy kiedy zalezy Ci aby MAKSYMALNY czas wyszukiwania drogi byl jak NAJMNIEJSZY. Przypadek taki wystapi wtedy, kiedy np. drogi w ogole nie bedzie. Powiedzmy przeciwnik jest poza domkiem, ktorego drzwi sa zamkniete a chce dojsc do postaci gracza ktora jest wewnatrz. Jesli w Twojej grze beda wystepowac takie sytuacje powinienes pomyslec nad algorytmem dzialajacym najszybciej w pesymistycznych sytuacjach - BFS (przeszukiwanie grafu wszerz).
Powinienes takze wiedziec, ze przy duzej ilosci wierzcholkow wyszukiwanie drogi moze troche trwac. Nawet kilka/kilkanascie sekund. Aby nie zatrzymywac calej gry na ten czas (grafika powinna byc caly czas renderowana) powinienes wyszukiwac droge w osobnym watku (przez ten czas mozesz odgrywac np. animacje zastanawiania sie przeciwnika).
Jesli piszesz gre sieciowa, poprawnosc odnalezionej drogi musi byc zweryfikowana po stronie serwera, ale to juz troche inny temat (jak piszesz gre sieciowa to daj znac).
« Ostatnia zmiana: Lipiec 29, 2007, 01:30:25 wysłana przez upshader »

Offline Moriturius

  • Użytkownik

# Lipiec 29, 2007, 11:08:58
Echh, upshader, zastanawiales sie kiedys nad tym, ze moze kto inny [ dodam, ze nie zgadzajacy sie z Toba ] moze miec racje? Nie wyglada mi na to. Ile nie dostarczyc argumentow i tak wymyslisz cos, zeby bylo na Twoje. IMHO nie ma glupich/niepotrzebnych rozwiazan - sa tylko takie, ktore sa wystarczajace w danej sytuacji bądź nie.

Na koniec skomentuję jeszcze coś:
Cytuj
I chyba najpierw się robi aabb, a potem bardziej złożone.
Test sfera-sfera jest najprostszy bo wymaga tylko sprawdzenia czy suma promieni jest wieksza niz odleglosc srodkow. I liczac odleglosc nie trzeba nawet liczyc pierwiastka. Mozna porownywac kwadraty odleglosci ;]

Test sfera-sfera jest często BARDZO niedokładny i nie warto się cieszyć ilością obliczeń bo w teście dwóch AABB jest ich tyle samo jak nie mniej. Zauważ, że w teście o ktorym piszesz musisz cośtam pomnożyć cośtam dodać i potem porównywać. W teście AABB wystarczą 2 odejmowania i 2 dodawania żeby sprawdzić czy na siebie nachodzą.

Oczywscie mowie o prostym tescie AABB jesli jest on przedstawiony jako Środek i połowa wysokości oraz połowa szerokości. Więcej informacji o czymś takim napisałem tutaj: http://wiki.warsztat.gd/AABB_(_Axis_Aligned_Bounding_Box)http://
« Ostatnia zmiana: Lipiec 29, 2007, 11:30:22 wysłana przez Moriturius »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Lipiec 29, 2007, 12:21:48
Cytuj
Test sfera-sfera jest często BARDZO niedokładny i nie warto się cieszyć ilością obliczeń bo w teście dwóch AABB jest ich tyle samo jak nie mniej.
Zależy, jaki obiekt testujesz. Poza tym sfera ma tą przewagę, że możesz ją dowolnie obracać i pozostaje nadal sferą. Jeżeli obiekty obracają się tylko w jednej osi (np. potwory i gracze) można iść na kompromis między sferą i zrobić test cylindra. :)

Offline Krolik

  • Użytkownik

# Lipiec 29, 2007, 19:14:36

W grze będą elementy ucieczki przed zombiakami. Chodzi o to , że kiedy zombiak nas zobaczy zacznie gonic , jezeli schowamy sie w budynku to on ma do niego wejsc i nas szukac ( nie biec od razu najkrótszą drogą ) , a jezeli wbiegnie zaraz za nami wtedy nie szuka nas tylko biegnie tam gdzie jestesmy.

Może ktoś mi wyjaśnić jak sie używa tego A* i mapek z 1 i 0. Czy trzeba je zapisywac w tablicach czy jakos inaczej i jak sie to sprawdza . Byłbym wdzięczny za pseudokod.

Już widze jak piszecie że i tak tego nie zrobie , ze za trudne i takie tam...

jak pisać to na temat ;)

Offline Nevermind77

  • Użytkownik

# Lipiec 29, 2007, 22:28:47
Pan Google wytłumaczy zapewne z przyjemnością odnośnie A*.

A co do tych mapek to cóż... Tworzysz po prostu mapę. Na przykład:

1111111111111111
1000100000000001
1000100000000001
1000100000000001
1000000000000001
1000100000000001
1000100000000001
1111111111111111

I teraz 1 oznacza przeszkodę a 0 brak przeszkody. Najwygodniej to przechowywać w tablicy.

Co do szukania przez zombiaków... Możesz im dać jakieś pole widzenia... Możesz losować co jakiś czas punkt w ich pobliżu żeby tam przeszły, takie proste do zaimplementowania rozwiązania dające namiastkę "poszukiwania".
« Ostatnia zmiana: Lipiec 29, 2007, 22:54:03 wysłana przez Nevermind77 »