DeletedUser1170
Gość
Gość
Pierwszy prototyp Instancji Multiplayerowych miał już niedźwiedzia z zaimplementowanym działającym systemem znajdowania ścieżki. Niestety działał on tylko dlatego, że był niedokończony, a sam niedźwiedź mniejszy. Teraz został on przemodelowany i jego rozmiar się zwiększył - z objektu 2x2 do 2x3. Niestety ta zmiana doprowadziła do problemu, którego się wcześniej spodziewaliśmy, ale którego rozwiązanie odkładaliśmy na później. Na czym on polega? Otóż obiekty mogą się się obracać, ale także mają “przód” (przeważnie twarz). Teraz spróbujcie obrócić kwadrat wokół własnej osi - będzie w tej samej pozycji, mimo że jego przód będzie skierowany w inną stronę. A teraz spróbujcie zrobić to samo z dużym obiektem 2x3 - jego pozycja się zmieni.
Stary niedźwiedź się nie obracał. Zawsze był skierowany w jednym kierunku i szedł do przodu, tyłu lub na boki, ale nigdy by się nie obracał - bo nie musiał, w pierwotnej wersji jego pole widzenia miało 360 stopni, a nie - jak teraz - 90 stopni. To, nad czym pracowaliśmy ostatnie kilka dni to sprawienie, by niedźwiedź się obracał - dzięki temu jego ścieżka wyglądałaby dużo lepiej i bardziej naturalnie.
Okazało się to dużo trudniejsze niż moglibyście pomyśleć. Stary algorytm działał, ale miał kilka wad. Szukanie ścieżek w praktyce sprowadza się do przejrzenia sąsiadujących pól i określenia ich pozycji względem aktualnego celu. Zanim będzie można ocenić każde z pól, trzeba sprawdzić czy nie są zajęte. W starym systemie zajmowało to sporo czasu, bo de facto próbował on przesunąć duży obiekt i postawić go w nowym miejscu - jeśli się to udało, to było ono oceniane pozytywnie, w przeciwnym wypadku pole było odrzucane. Im więcej pól zajmował obiekt, tym więcej czasu zajmowało ich sprawdzenie. Było to bardzo nieefektywne, więc zaczęliśmy szukać zastępczego rozwiązania, którym okazała się być metoda zwana clearance-based pathfindingiem.
Według artykułu, wartość komórki definiuje rozmiar obiektu, który się w nim zmieści. Jeśli ta wartość wynosi 8, to każdy obiekt wielkości 8x8 lub mniejszy może zostać do niej przeniesiony. Dzięki temu zamiast sprawdzania każdego pola z osobna wystarczy porównać wielość obiektu z wartością pola docelowego.
Jest jednak jeden haczyk: działa to tylko z kwadratowymi obiektami, a nasz niedźwiedź zdążył już urosnąć do rozmiarów 2x3. Użycie wartości komórki 3 nie zawsze działa, bo są miejsca gdzie obiekt 3x3 się nie zmieści, ale 2x3 już tak. Wartość komórki nie dawałaby więc kompletnych informacji.
Bazując na tej wartości myśleliśmy o sposobach prekalkulowania tego, czy obiekt zmieści się w konkretnym miejscu. Skończyło się na wyliczaniu wartości pola dla każdego możliwego układu mapy. Układ 2x3 jest przenoszony do każdej niezablokowanej komórki w celu sprawdzenia, czy się zmieści. Jeśli tak, to komórce przyznawana jest wartość 1, w przeciwnym wypadku 0. Nie wystarcza to jednak w pełni, bo gdy obiekt 2x3 się obróci, to będzie obiektem 3x2 dla którego osobno trzeba przeliczyć wszystkie pola. Na końcu trzeba połączyć obie wartości - jeśli zarówno 3x2 jak i 2x1 zmieszczą się do danej komórki, to jej wartość wynosi 3, jeśli mieści się tylko 2x3 wynosi 1, a jeśli tylko 3x2 to ma wartość 2 - w ostatnich dwóch przypadkach niedźwiedź będzie mógł przejść do danej pozycji tylko po obróceniu się w odpowiednim kierunku.
Następnym problemem na liście było blokowanie obiektów. Obiekty blokują się nawzajem, co oznacza, że muszą być brane pod uwagę przy przeliczaniu wartości komórek. W chwili obecnej działa to tylko dla statycznych elementów, takich jak budynki (ponieważ są rozmieszczane z wyprzedzeniem i się nie ruszają). Mapa wartości musi być aktualizowana za każdym razem gdy obiekt (np. gracz) pojawia się na mapie lub przesuwa w inne miejsce. Na szczęście aktualizacja jest stosunkowo prosta, i tylko komórki w lewej górnej części muszą być ponownie przeliczane.
Jedną z rzeczy, na którą do tej pory nie zwracaliśmy uwagi było rozstawianie obiektów na siatce. Każdy obiekt ma środek rotacji, który definiuje także jego położenie. Niestety, wartość komórki nie uwzględnia środka rotacji, tylko lewą górną komórkę zajmowaną przez obiekt. Rozwiązanie było proste: należało przesunąć punkt obliczania wartości komórki do środka obiektu lub pozwolić układowi mapy na branie pod uwagę lewego górnego rogu obiektu dla każdego kierunków. Wybraliśmy to drugie, problem rozwiązany.
Dzięki tym wszystkim prekalkulowanym i dynamicznie aktualizowanym wartościom mogliśmy wrócić do właściwego problemu: umożliwienie niedźwiedziowi obracania się. Jak napisałem wcześniej, wszystko sprowadza się do sprawdzania sąsiednich komórek. Rozważane są nie tylko komórki znajdujące się w kierunku, na które patrzy niedźwiedź, ale także wszystkie pozostałe. Znacznie zwiększyliśmy więc szansę na wybranie jednego z bocznych pól, dzięki czemu niedźwiedź obraca się i idzie w lewo zamiast bokiem.
(zielony: idzie na północ, żółty: idzie na wschód, niebieski: idzie na południe, czerwony: idzie na zachód; żółty teren na początku jest tylko punktem startowym)
Czy to już wszystko? Niestety nie, algorytm nadal ma trochę błędów - na przykład niedźwiedziowi w trakcie drogi zdarza się czasem nagle zrobić obrót o 360 stopni, a potem iść dalej jakby nic się nie stało.
Dodatkowo w obecnej wersji mamy problem z AI, które nie potrafi wybrać sobie celu, do którego ma dojść, mimo że wytyczanie ścieżki działa bez problemu. W ostatnim miesiącu jednak bardziej skupialiśmy się na aspektach wizualnych, co mogliście zobaczyć w ostatnim odcinku InnoGames TV.
Stary niedźwiedź się nie obracał. Zawsze był skierowany w jednym kierunku i szedł do przodu, tyłu lub na boki, ale nigdy by się nie obracał - bo nie musiał, w pierwotnej wersji jego pole widzenia miało 360 stopni, a nie - jak teraz - 90 stopni. To, nad czym pracowaliśmy ostatnie kilka dni to sprawienie, by niedźwiedź się obracał - dzięki temu jego ścieżka wyglądałaby dużo lepiej i bardziej naturalnie.
Okazało się to dużo trudniejsze niż moglibyście pomyśleć. Stary algorytm działał, ale miał kilka wad. Szukanie ścieżek w praktyce sprowadza się do przejrzenia sąsiadujących pól i określenia ich pozycji względem aktualnego celu. Zanim będzie można ocenić każde z pól, trzeba sprawdzić czy nie są zajęte. W starym systemie zajmowało to sporo czasu, bo de facto próbował on przesunąć duży obiekt i postawić go w nowym miejscu - jeśli się to udało, to było ono oceniane pozytywnie, w przeciwnym wypadku pole było odrzucane. Im więcej pól zajmował obiekt, tym więcej czasu zajmowało ich sprawdzenie. Było to bardzo nieefektywne, więc zaczęliśmy szukać zastępczego rozwiązania, którym okazała się być metoda zwana clearance-based pathfindingiem.
Według artykułu, wartość komórki definiuje rozmiar obiektu, który się w nim zmieści. Jeśli ta wartość wynosi 8, to każdy obiekt wielkości 8x8 lub mniejszy może zostać do niej przeniesiony. Dzięki temu zamiast sprawdzania każdego pola z osobna wystarczy porównać wielość obiektu z wartością pola docelowego.
Jest jednak jeden haczyk: działa to tylko z kwadratowymi obiektami, a nasz niedźwiedź zdążył już urosnąć do rozmiarów 2x3. Użycie wartości komórki 3 nie zawsze działa, bo są miejsca gdzie obiekt 3x3 się nie zmieści, ale 2x3 już tak. Wartość komórki nie dawałaby więc kompletnych informacji.
Bazując na tej wartości myśleliśmy o sposobach prekalkulowania tego, czy obiekt zmieści się w konkretnym miejscu. Skończyło się na wyliczaniu wartości pola dla każdego możliwego układu mapy. Układ 2x3 jest przenoszony do każdej niezablokowanej komórki w celu sprawdzenia, czy się zmieści. Jeśli tak, to komórce przyznawana jest wartość 1, w przeciwnym wypadku 0. Nie wystarcza to jednak w pełni, bo gdy obiekt 2x3 się obróci, to będzie obiektem 3x2 dla którego osobno trzeba przeliczyć wszystkie pola. Na końcu trzeba połączyć obie wartości - jeśli zarówno 3x2 jak i 2x1 zmieszczą się do danej komórki, to jej wartość wynosi 3, jeśli mieści się tylko 2x3 wynosi 1, a jeśli tylko 3x2 to ma wartość 2 - w ostatnich dwóch przypadkach niedźwiedź będzie mógł przejść do danej pozycji tylko po obróceniu się w odpowiednim kierunku.
Następnym problemem na liście było blokowanie obiektów. Obiekty blokują się nawzajem, co oznacza, że muszą być brane pod uwagę przy przeliczaniu wartości komórek. W chwili obecnej działa to tylko dla statycznych elementów, takich jak budynki (ponieważ są rozmieszczane z wyprzedzeniem i się nie ruszają). Mapa wartości musi być aktualizowana za każdym razem gdy obiekt (np. gracz) pojawia się na mapie lub przesuwa w inne miejsce. Na szczęście aktualizacja jest stosunkowo prosta, i tylko komórki w lewej górnej części muszą być ponownie przeliczane.
Jedną z rzeczy, na którą do tej pory nie zwracaliśmy uwagi było rozstawianie obiektów na siatce. Każdy obiekt ma środek rotacji, który definiuje także jego położenie. Niestety, wartość komórki nie uwzględnia środka rotacji, tylko lewą górną komórkę zajmowaną przez obiekt. Rozwiązanie było proste: należało przesunąć punkt obliczania wartości komórki do środka obiektu lub pozwolić układowi mapy na branie pod uwagę lewego górnego rogu obiektu dla każdego kierunków. Wybraliśmy to drugie, problem rozwiązany.
Dzięki tym wszystkim prekalkulowanym i dynamicznie aktualizowanym wartościom mogliśmy wrócić do właściwego problemu: umożliwienie niedźwiedziowi obracania się. Jak napisałem wcześniej, wszystko sprowadza się do sprawdzania sąsiednich komórek. Rozważane są nie tylko komórki znajdujące się w kierunku, na które patrzy niedźwiedź, ale także wszystkie pozostałe. Znacznie zwiększyliśmy więc szansę na wybranie jednego z bocznych pól, dzięki czemu niedźwiedź obraca się i idzie w lewo zamiast bokiem.
(zielony: idzie na północ, żółty: idzie na wschód, niebieski: idzie na południe, czerwony: idzie na zachód; żółty teren na początku jest tylko punktem startowym)
Czy to już wszystko? Niestety nie, algorytm nadal ma trochę błędów - na przykład niedźwiedziowi w trakcie drogi zdarza się czasem nagle zrobić obrót o 360 stopni, a potem iść dalej jakby nic się nie stało.
Dodatkowo w obecnej wersji mamy problem z AI, które nie potrafi wybrać sobie celu, do którego ma dojść, mimo że wytyczanie ścieżki działa bez problemu. W ostatnim miesiącu jednak bardziej skupialiśmy się na aspektach wizualnych, co mogliście zobaczyć w ostatnim odcinku InnoGames TV.
Ostatnio edytowane przez moderatora:
