Zgodnie z obietnicą z poprzedniego arta dzisiaj pokaże jak nauczyć naszego ludzika aby potrafił sam sobie szukać drogi miedzy platformami oraz sam między nimi się przemieszczał. Na początek może co warto wiedzieć.
1.To samo co w artykule nr 1 (“Jak ugryźć platformówkę”)
2.Pomocne może być jeśli ktoś rozumie podstawy teorii grafów, ale postaram się tak pisać aby nie było z tym problemów.
Ok, zaczynamy. Będziemy bazowali na programie, który napisałem ostatnio tylko go rozbudujemy. Jakie zmiany są wprowadzone każdy potrafi stwierdzić więc nie będę się rozpisywał co i gdzie dodałem. Skupimy się w pierwszej kolejności na zasadzie działania, a później omówię pokrótce co ciekawsze części kodu.
1. Idea.
Otóż każdą platformę potraktujemy jako węzeł grafu, albo mówiąc inaczej węzeł czyli coś do czego mogą prowadzić drogi lub skąd mogą prowadzić drogi. Skoro mamy kilka węzłów (bo jest kilka platform) to jasne jest, że będziemy tworzyli sieć połączeń między tymi węzłami. Drogi o których mowa będą jednokierunkowe (graf skierowany) czyli jeśli mamy drogę nr 1 z punktu A do B oznacza to, że możemy iść tylko z A -> B, powrót musi być realizowany inną drogą (np. drogą 2). Skoro mamy już węzły i drogi to trzeba będzie nauczyć program wyszukiwać drogi z zadanego punktu początkowego do zadanego punktu docelowego. Oczywiście może się okazać że droga taka nie istnieje (w zależności od tego jaki powstał graf) i nasz program też musi sobie z tym poradzić. Jak będziemy szukać ? Otóż najprościej jak się da oznacza to, że wyznaczona droga nie musi być optymalna pod względem długości (niekoniecznie będzie najkrótszą drogą), a algorytm który użyjemy będzie dosyć wolny, wyglądać toto będzie tak:
1.Stajemy w węźle początkowym i sprawdzamy czy prowadzi stąd droga do węzła końcowego. Jeśli tak zapamiętujemy tą drogę, kończymy szukanie.
2.Idziemy pierwszą drogą, którą znaleźliśmy w węźle początkowym i wykonujemy dla niego podpunkt 1.
3.Operacje z punktu 2 powtarzamy dla wszystkich dróg w analizowanym węźle.
4.Jeśli droga do celu jest odnaleziona to cofamy się drogą którą przyszliśmy i zapamiętujemy drogę prowadzącą do tego miejsca. Robimy to tak długo (cofamy się) aż dotrzemy do węzła początkowego.
Jak widać jest to algorytm rekurencyjny, żre dużo pamięci i niekoniecznie jest szybki ale jest prosty dlatego go wybrałem. W tym miejscu kończy się właściwie idea.
2. Implementacja
Ok aby zrealizować naszą ideę musimy zaimplementować następujące funkcje:
1.Tworzenie grafu na podstawie istniejących platform
2.Wyszukiwanie drogi w oparciu o graf
3.Poruszanie postaci w oparciu o odnalezioną drogę.
Zacznijmy od punktu 1 czyli tworzenia grafu. Metoda, która się tym zajmuje nazywa się Tplatform.CreateWebWay i przyjmuje jako parametr ludzika dlaczego ? Bo każdy ludzik może mieć swój graf poruszania się (ludziki mogą się różnić np wielkością, prędkością poruszania, wysokością skoku itp. dlatego po tych samych platformach różne postacie będą się różnie poruszały). Od czego zaczynamy ? Otóż plan jest prosty bierzemy pokoleji wszystkie platformy, stawiamy na nich ludzika i sprawdzamy gdzie spadnie (po lewej i po prawej), później stawiamy tego ludzika na krawędzi platformy i każemy mu skakać w lewo oraz prawo i zapamiętujemy gdzie spadł, później przesuwamy go w prawo o wartość równą prędkości jego chodzenie i znowu każemy mu skakać, robimy to tak długo aż dojdzie do drugiej krawędzi. W ten oto sposób dostajemy wszystkie drogi, które prowadzą z tej platformy na inne. Kolejnym krokiem jest optymalizacja znalezionych dróg. Dlaczego ? Otóż po wykonaniu tego algorytmu może się okazać że dostaniemy setki dróg prowadzących na np 3 platformy, po analizie okaże się, że da się to skompresować, robimy to tak:
1.Usuwamy drogi które prowadzą na platformę z której wyruszamy.
2.Jeśli na inną (tą samą platformę) prowadzą np 2 drogi które polegają na skoku w lewo, to łączymy te drogi w jedną ustalamy tylko odpowiedni fXStart i fXStop. Jeśli ludzik będzie w przedziale wyznaczonym przez te dwie zmienne oznacza to, że prowadzi stąd jedna droga.
Po zakończeniu tych operacji mamy stworzony graf dróg. Warto zerknąć na metodę TLudzik.Simulate zajmuje się ona symulacją chodzenia i skakania ludzika dzięki niej wiemy gdzie tak naprawdę doleci ludzik jeśli skoczy z zadanego miejsca na platformie.
Wyszukiwanie drogi w oparciu o graf realizują trzy metody: TLudek.GoToPlatform, oraz TLudek.FindWay oraz TLudek.WebWaySearch. Pierwsza z nich wywołuje właściwą procedurę szukającą, a po jej zakończeniu sprawdza czy droga została odnaleziona, jeśli tak to pobiera pierwszą daną potrzebną do rozpoczęcia ruchu i zapamiętuje ją w polu fNextWebWay. Druga metoda przygotowuje listę, w której będzie trzymana droga, wywołuje metodę wyszukującą drogę, a następnie odwraca kolejność w liście opisującej drogę. Metoda nr 3 jest właściwą metodą poszukującą drogi, została ona omówiona na samym początku.
Poruszanie ludzika. W tym momencie mamy już drogę więc czas zacząć chodzić. Sprawny umysł od razu zauważy zmiany jakie zaszły w procedurze Update. Pojawił się blok które sprawdza czy mamy ustalony jakiś cel gdzie będziemy szli, jeśli nie to szukamy sobie jakiejś losowej platformy na, którą się udamy. Druga część powoduje wywołanie metody TLudek.ExecuteDreptacz, która to metoda jest odpowiedzialna za właściwy ruch. Jej działanie jest następujące:
1.Jeśli stoimy na platformie to sprawdzamy gdzie znajduje się na niej punkt z którego rozpoczyna się droga do innej platformy, następnie poruszamy się w jego kierunku
2.Jeśli jesteśmy w miejscu pomiedzy fXStart fXStop to wykonujemy odpowiednie polecenie (np. skok, pionowy w lewo lub w prawo)
3.Lecimy i czekamy aż spadniemy na nowej platformie
4.Pobieramy kolejny punkt drogi.
I to z grubsza tyle. W programie jest kilka małych procek, które ułatwiają zrozumienie działania wszystkiego (np wyświetlanie drogi w ListBoxie, podświetlanie wybranej myszką platformy oraz pokazanie platform, do których prowadzą z niej drogi itp.). Mam nadzieje, że z artsa nie wyszedł jeden wielki bełkot, i że ktoś zrozumiał o co mi chodziło 🙂
Autor: Toster
