Najpierw opisz, gdzie postać rzeczywiście może przejść
Algorytm planowania nie widzi grafiki tak jak człowiek. Potrzebuje modelu połączeń między dostępnymi miejscami. Dla gry kafelkowej może to być siatka, dla innego projektu sieć punktów lub obszarów. Model powinien uwzględniać rozmiar postaci i jej możliwości. Korytarz widoczny między przeszkodami nie jest przejściem, jeśli bohater fizycznie się w nim nie mieści. Zgodność danych nawigacji z mapą kolizji jest ważniejsza niż wybór modnego algorytmu.
W przykładzie dwóch rodzajów przeciwników mały robot przechodzi pod bramą, a większy musi ją ominąć. Wspólny graf bez ograniczeń może wysłać oba tą samą drogą i pozostawić drugiego zablokowanego. Zapisz wymagania krawędzi, takie jak szerokość lub możliwość pokonania schodka. Przy ruchu po skosie ustal, czy wolno przecinać narożnik między dwiema przeszkodami. Ta pozornie drobna reguła często tłumaczy trasę wyglądającą jak przechodzenie przez ścianę.
Koszt trasy nie musi oznaczać samej odległości
Podłoże może spowalniać ruch, niektóre przejścia wymagać otwarcia drzwi, a inne być niedostępne w danym stanie. Koszt powinien odpowiadać temu, co planujesz optymalizować. Najkrótsza droga geometryczna nie zawsze jest najszybsza. Nie mieszaj jednak dowolnych kar bez ustalonej skali. Gdy koszt jednego pola zawiera dystans, a innego przypadkową ocenę zagrożenia, wynik może być trudny do przewidzenia i strojenia.
Oddziel model nawigacji od decyzji taktycznej. Przeciwnik może najpierw wybrać cel, a dopiero potem poszukać drogi. Zmiana celu co chwilę może powodować nerwowe zawracanie, mimo że sam algorytm działa poprawnie. Zapisuj powód wyboru i moment ponownej oceny. Jeśli jednostka ma uciekać od zagrożenia, jasno określ warunek zakończenia ucieczki. Planowanie ścieżki nie odpowie samo, co postać chce osiągnąć.
Heurystyka pomaga szukać, ale ma warunki
A* łączy koszt dotychczasowej drogi z oszacowaniem pozostałego kosztu. Dla standardowych gwarancji optymalności potrzebne są odpowiednie założenia o kosztach, heurystyce i implementacji. Na siatce z ruchem wyłącznie poziomym i pionowym stosuje się inne oszacowanie niż przy dozwolonych przekątnych. Nie wybieraj wzoru tylko dlatego, że ma znajomą nazwę. Musi pasować do faktycznych przejść i jednostek kosztu w grze.
Silniejsze, lecz zawyżające oszacowanie może przyspieszyć szukanie kosztem gwarancji najlepszej trasy. To bywa świadomy kompromis, ale należy go nazwać i sprawdzić na mapach testowych. Nie opisuj każdego wyniku jako najkrótszego, jeśli projekt celowo dopuszcza przybliżenie. Przy małych poziomach zacznij od czytelnej wersji referencyjnej. Łatwiej później ocenić optymalizację, gdy można porównać koszt oraz poprawność znalezionych ścieżek z prostym punktem odniesienia.
Znaleziona ścieżka wymaga jeszcze wykonania
Lista punktów nie określa przyspieszenia, obrotu ani omijania innych postaci. Te zadania należą do ruchu i lokalnej reakcji. Jeśli kilka jednostek otrzyma tę samą trasę przez wąskie drzwi, mogą się wzajemnie blokować. Potrzebna jest zasada kolejności, ustępowania lub rezerwacji przejścia, dopasowana do skali projektu. Samo ponowne wywoływanie A* w każdej klatce może zwiększyć obciążenie, nie rozwiązując zachowania w tłumie.
Przy wygładzaniu ścieżki sprawdzaj widoczność i faktyczną przestrzeń dla całego kształtu jednostki. Usunięcie punktu zakrętu może skrócić linię wprost przez przeszkodę. Zachowaj rozróżnienie między trasą planowaną a bieżącym ruchem. W diagnostyce pokazuj obie informacje. Dzięki temu wiadomo, czy postać stoi, bo nie ma drogi, czy dlatego, że wykonawca ruchu nie potrafi osiągnąć kolejnego punktu w obecnych warunkach.
Zmiana mapy powinna unieważniać właściwy plan
Zamknięte drzwi lub nowa przeszkoda mogą uczynić dawną ścieżkę nieaktualną. Powiąż wynik wyszukiwania z wersją mapy albo sprawdzaj potrzebne odcinki przed użyciem. Nie każda drobna zmiana wymaga przeliczenia wszystkich tras. Ustal, które obszary zostały dotknięte i które jednostki faktycznie korzystają z tych przejść. Przy zadaniach asynchronicznych sprawdź, czy wynik nadal dotyczy aktualnego celu i pozycji, zanim zostanie przyjęty.
Brak drogi jest prawidłowym wynikiem, nie wyjątkiem do ukrycia. Przeciwnik może zaczekać, wybrać punkt pośredni albo zrezygnować zgodnie z regułą zachowania. Ustal limit ponowień i odstęp czasowy. Bez tego setka zablokowanych jednostek może bez przerwy liczyć ten sam niemożliwy problem. Gracz powinien widzieć spójne zachowanie, a nie chaotyczne drganie postaci na granicy przeszkody.
Budżet planowania powinien obejmować najtrudniejszą scenę
Rozłóż obliczenia w czasie albo obsługuj kolejkę żądań, jeśli wiele jednostek jednocześnie potrzebuje drogi. Ogranicz liczbę przeszukiwanych węzłów na etap i świadomie obsłuż wynik niepełny. Cache może pomóc przy wspólnych trasach, lecz jego klucz musi uwzględniać mapę, rodzaj jednostki i koszty. Wynik dla małego robota nie zawsze nadaje się dla dużego. Nie przechowuj tras bez kontroli ważności tylko dlatego, że kiedyś były poprawne.
Zestaw testowy powinien zawierać pustą mapę, labirynt, brak przejścia, różne koszty podłoża i dynamiczne drzwi. Sprawdź poprawność każdego odcinka oraz sumę kosztów. Mierz też czas w scenie z wieloma jednostkami, nie tylko pojedynczym bohaterem. Dobra nawigacja łączy reprezentację świata, planowanie i wykonanie ruchu. A* jest jednym z elementów tej całości, a nie automatyczną odpowiedzią na każde zachowanie przeciwnika, które wygląda na niezdecydowane.