Czy wstępne obliczanie ścieżki jest nadal istotne?

Kontekst

Old Lucas Arts (era ScummVM) przygodowe gry graficzne typu „wskaż i kliknij” wykorzystywały obliczenia wstępne. Oto ogólny zarys techniki.

Krok 1

Podłoga w każdym pokoju była podzielona na tak zwane „chodziki”, które były prawie równoważne węzłom w siatce nawigacyjnej, ale ograniczały się do kształtów trapezowych. Na przykład:

 ______ _____ _________ _____
\   A  |  B  |    C    |  D   \
 \_____|     |         |_______\
       |_____|         |
             |_________|

Krok 2

Algorytm offline (np. Dijkstra lub A *) obliczy najkrótszą ścieżkę między każdą parą węzłów i zapisze pierwszy krok ścieżki w macierzy 2D, indeksowanej w każdym wymiarze przez użyty węzeł początkowy i końcowy. Np. Używając powyższych pól spacerowych:

      ___ ___ ___ ___
     | A | B | C | D | <- Start Node
  ___|___|___|___|___|
 | A | A | A | B | C |  ---
 |___|___|___|___|___|     |
 | B | B | B | B | C |     |
 |___|___|___|___|___|     |-- Next node in shortest path
 | C | B | C | C | C |     |   from Start to End
 |___|___|___|___|___|     | 
 | D | B | C | D | D |  ---
 |___|___|___|___|___| 
   ^
   |
End Node

Jak można się domyślić, wymagania dotyczące pamięci szybko rosną wraz ze wzrostem liczby węzłów (N ^ 2). Ponieważ skrót byłby zwykle wystarczająco duży, aby przechowywać każdy wpis w macierzy, przy złożonej mapie 300 węzłów, która spowodowałaby przechowywanie dodatkowej:

300^2 * sizeof(short) = 176 kilobytes

Krok 3

Z drugiej strony, obliczenie najkrótszej ścieżki między dwoma węzłami było niezwykle szybkie i trywialne, tylko seria wyszukiwań w macierzy. Coś jak:

// Find shortest path from Start to End
Path = {Start}
Current = Start
WHILE Current != End
    Current = LookUp[Current, End]
    Path.Add(Current)
ENDWHILE

Zastosowanie tego prostego algorytmu w celu znalezienia najkrótszej ścieżki od C do A zwraca:

1) Path = { C }, Current = C
2) Path = { C, B }, Current = B
3) Path = { C, B, A }, Current = A, Exit

Pytanie

Podejrzewam, że przy dzisiejszym wydajnym sprzęcie, w połączeniu z wymaganiami dotyczącymi pamięci, aby robić to na każdym poziomie, wszelkie korzyści, jakie kiedyś miała ta technika, są teraz ważniejsze, po prostu wykonując A * w czasie wykonywania.

Słyszałem również, że obecnie wyszukiwanie pamięci może być nawet wolniejsze niż ogólne obliczenia, dlatego tworzenie tabel wyszukiwania sinus i cosinus nie jest już tak popularne.

Ale muszę przyznać, że nie jestem jeszcze zbyt dobrze poinformowany w tych kwestiach dotyczących wydajności sprzętu na niskim poziomie, dlatego korzystam z okazji, aby zapytać o opinię tych bardziej zaznajomionych z tym tematem.

W moim silniku potrzebowałem także możliwości dynamicznego dodawania i usuwania węzłów do wykresu w czasie wykonywania ( zobacz to ), więc wstępnie obliczona trasa tylko komplikowała sprawy, więc zeskrobałem ją (nie wspominając o moim środowisku uruchomieniowym Rozwiązanie * * działało już idealnie ). Nadal zastanawiałem się ...

Podsumowując, czy ta technika jest nadal aktualna w jakimkolwiek scenariuszu?

W moim silniku potrzebowałem także możliwości dynamicznego dodawania i usuwania węzłów do wykresu w czasie wykonywania (zobacz to), więc wstępnie obliczona trasa tylko komplikowała sprawy, więc zeskrobałem ją (nie wspominając o moim środowisku uruchomieniowym Rozwiązanie * * działało już idealnie ). Nadal zastanawiałem się ...

Podsumowując, czy ta technika jest nadal aktualna w jakimkolwiek scenariuszu?

Nie widzę korzyści z zastosowania takiej techniki.

Brakuje mi elastyczności wykresu (możesz mieć różne LOD, nie muszą one mieć żadnego określonego kształtu, itp.). Również każdy użytkownik twojego silnika będzie wiedział, co to jest wykres i jak go używać. Jeśli więc chcą dodać dodatkową funkcjonalność, będą musieli nauczyć się, jak zaimplementować swoje rozszerzenie, korzystając z zupełnie nowej sytuacji.

Jak wspomniałeś, wygląda na to, że skalowałby się strasznie. Warto również zauważyć, że jeśli wykres zmieści się na gotówce i przejrzysz wszystkie znalezione ścieżki z powrotem do tyłu, to naprawdę skróci czas IO. Wygląda na to, że Twoja implementacja wkrótce stanie się zbyt duża, aby zmieściła się w dowolnej pamięci podręcznej.

Słyszałem również, że obecnie wyszukiwanie pamięci może być nawet wolniejsze niż ogólne obliczenia, dlatego tworzenie tabel wyszukiwania sinus i cosinus nie jest już tak popularne.

O ile nie zmieścisz całego programu i jego potrzebnej pamięci w pamięci podręcznej, zamierzasz butelkować szyjkę podczas wyciągania rzeczy z pamięci na długo przed butelkowaniem procesora.

Podejrzewam, że przy dzisiejszym wydajnym sprzęcie, w połączeniu z wymaganiami dotyczącymi pamięci, aby robić to na każdym poziomie, wszelkie korzyści, jakie kiedyś miała ta technika, są teraz ważniejsze, po prostu wykonując A * w czasie wykonywania

Pamiętaj też, że wiele gier ma osobne pętle do aktualizacji AI. Uważam, że sposób, w jaki skonfigurowałem mój projekt, polega na tym, że istnieje pętla aktualizacji dla wprowadzania danych przez użytkownika przy 60 Hz, AI wynosi tylko 20 Hz, a gry losują tak szybko, jak to możliwe.

Na marginesie, zrobiłem trochę programowania GBA dla zabawy i nic nie przełożyło się na używanie nowoczesnego urządzenia. W przypadku GBA chodziło o zminimalizowanie obciążenia procesora (ponieważ było to żałosne). Musisz także zdać sobie sprawę, że większość języków wysokiego poziomu C # i Java (nie tyle C ++ czy C) robi dla Ciebie mnóstwo optymalizacji. Jeśli chodzi o optymalizację kodu, nie ma wiele do zrobienia poza dostępem do pamięci tak mało, jak to możliwe, a kiedy wykonasz na niej jak najwięcej obliczeń przed wprowadzeniem nowej pamięci, która wyrzuci ją z pamięci podręcznej i upewni się, że jesteś robiąc rzeczy tylko raz.

Edycja: Również, aby odpowiedzieć na swój tytuł, tak jest. Często używane ścieżki do obliczeń wstępnych to doskonały pomysł i można to zrobić za pomocą A * w dowolnym miejscu poza pętlą gry. Na przykład od ciebie do zasobu w RTS, aby zebrani nie musieli ponownie obliczać za każdym razem, gdy chcą odejść lub wrócić.