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?