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


12

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?


2
Myślę, że nadal jest to istotne, jeśli masz napięty budżet procesora. Ale gdy chcesz dynamicznych ścieżek, nie jest to już przydatne. Przy okazji przyjrzałem się, skąd masz algorytm A * i możesz go jeszcze bardziej zoptymalizować za pomocą minheap i innych sztuczek. Zrobiłem kilka iteracji ulepszania A * w C #, które można zobaczyć tutaj: roy-t.nl/index.php/2011/09/24/… może być przydatne.
Roy T.

1
Dzięki, dodałem do zakładek i przyjrzę się temu, kiedy zacznę optymalizować moją aplikację. Prawie użyłem rozwiązania Erica Lipperta z kilkoma drobnymi modyfikacjami, ponieważ było tak czyste i łatwe do naśladowania ... I dla wszystkich moich przypadków testowych działało prawie „natychmiast”, więc nawet nie zawracałem sobie głowy optymalizacją.
David Gouveia,

1
BTW, jeśli zdecydujesz się na wstępne obliczenia, możesz przyjrzeć się algorytmowi Floyd-Warshall . Buduje matrycę „następnego kroku” wydajniej niż wielokrotnie przy użyciu Dijkstra / A *.
amitp

@amitp Dzięki za wskazówkę, zawsze dobrze jest wiedzieć o tych alternatywach! Chociaż, ponieważ w większości przypadków wstępne obliczenia byłyby wykonywane offline, nie byłoby wiele do zyskania dzięki zwiększeniu ich wydajności. Chyba że jesteś naprawdę niecierpliwy. :-)
David Gouveia,

Zgadzam się, chociaż Floyd-Warshall jest również znacznie prostszy do wdrożenia niż algorytm Dijkstry, więc jeśli jeszcze nie masz zaimplementowanego Dijkstry, warto to sprawdzić :)
amitp

Odpowiedzi:


3

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ć.


Jeśli chodzi o twoją edycję, tak naprawdę nie mówiłem o często używanych ścieżkach wstępnego obliczania, ale ściśle o technice przedstawionej na wstępnym obliczeniu każdej możliwej ścieżki . Jestem również trochę zdezorientowany, jak większość twojej odpowiedzi była przeciwna użyciu wcześniej obliczonego wyszukiwania ścieżek, ale na koniec powiedziałeś, że byłby to świetny pomysł. Czy byłby użyteczny w środowisku z ograniczonym procesorem, takim jak GBA?
David Gouveia,

1
Moja zła próbowałem wskazać, że odpowiedź na twój tytuł wyjęta z kontekstu brzmi „tak”. Podczas gdy odpowiedź dotycząca konkretnego algorytmu opisanego w pytaniu brzmi „nie”. Krótko mówiąc, wstępne obliczanie wszystkich możliwych ścieżek jest złym pomysłem, ale wstępne obliczanie kilku bardzo często używanych ścieżek może być dobrym pomysłem.
ClassicThunder

2
@ClassicThunder: Ta technika wstępnego obliczania wszystkich ścieżek z kilku punktów orientacyjnych jest często określana jako ALT : Gwiazda z punktami
Pieter Geerkens,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.