Jak zoptymalizować funkcję odległości?

Opracowując dość prostą grę podobną do RTS, zauważyłem, że moje obliczenia odległości miały wpływ na wydajność.

Przez cały czas sprawdzane są odległości, aby dowiedzieć się, czy jednostka znajduje się w zasięgu celu, czy pocisk osiągnął swój cel, czy gracz przejechał podbicie, kolizję itp. Lista jest długa i sprawdza często stosuje się odległość między dwoma punktami.

Moje pytanie dotyczy właśnie tego. Chcę wiedzieć, jakie alternatywy mają twórcy gier do sprawdzania odległości, inne niż zwykłe podejście sqrt (x * x + y * y), które jest dość czasochłonne, jeśli wykonujemy je tysiące razy na klatkę.

Chciałbym zauważyć, że jestem świadomy porównań odległości na Manhattanie i kwadratowych odległości (pomijając wąskie gardło sqrt). Coś jeszcze?

TL; DR; Twój problem nie polega na wykonywaniu funkcji odległości. Twoim problemem jest wykonywanie funkcji odległości tak wiele razy. Innymi słowy, potrzebujesz optymalizacji algorytmicznej, a nie matematycznej.

[EDYCJA] Usuwam pierwszą część mojej odpowiedzi, ponieważ ludzie jej nie znoszą. Tytuł pytania wymagał alternatywnych funkcji odległości przed edycją.

Korzystasz z funkcji odległości, w której za każdym razem obliczasz pierwiastek kwadratowy. Możesz jednak po prostu zastąpić to bez używania pierwiastka kwadratowego i zamiast tego obliczyć odległość do kwadratu. Pozwoli ci to zaoszczędzić wiele cennych cykli.

Odległość ^ 2 = x * x + y * y;

to właściwie wspólna sztuczka. Ale musisz odpowiednio dostosować swoje obliczenia. Można go również wykorzystać jako kontrolę wstępną przed obliczeniem rzeczywistej odległości. Na przykład zamiast obliczać rzeczywistą odległość między dwoma punktami / sferami dla testu przecięcia, możemy zamiast tego obliczyć Odległość do kwadratu i porównać z promieniem do kwadratu zamiast promienia.

Edytuj, dobrze po tym, jak @ Byte56 zwrócił uwagę, że nie przeczytałem pytania i że byłeś świadomy optymalizacji kwadratu odległości.

W twoim przypadku niestety zajmujemy się grafiką komputerową prawie wyłącznie zajmującą się przestrzenią euklidesową , a odległość jest dokładnie zdefiniowana jak Sqrt of Vector dot itselfw przestrzeni euklidesowej.

Odległość do kwadratu to najlepsze przybliżenie, jakie uzyskasz (pod względem wydajności), nie widzę niczego, co przewyższyłoby 2 pomnożenia, jeden dodatek i zadanie.

Więc mówisz, że nie mogę zoptymalizować funkcji odległości, co powinienem zrobić?

Twój problem nie polega na wykonywaniu funkcji odległości. Twoim problemem jest wykonywanie funkcji odległości tak wiele razy. Innymi słowy, potrzebujesz optymalizacji algorytmicznej, a nie matematycznej.

Chodzi o to, aby zamiast sprawdzać skrzyżowanie gracza z każdym obiektem w scenie, każdą klatką. Możesz z łatwością wykorzystać spójność przestrzenną na swoją korzyść i sprawdzać tylko obiekty znajdujące się w pobliżu gracza (które najprawdopodobniej uderzą / przecinają się).

Można to łatwo zrobić, przechowując te informacje przestrzenne w strukturze danych z podziałem przestrzennym . W przypadku prostej gry sugerowałbym siatkę, ponieważ jest ona w zasadzie łatwa do zaimplementowania i ładnie pasuje do dynamicznej sceny.

Każda komórka / pudełko zawiera listę obiektów, które otaczają obwiednia siatki. I łatwo jest śledzić pozycję gracza w tych komórkach. A do obliczeń odległości sprawdzasz odległość gracza tylko z tymi obiektami w tej samej lub sąsiednich komórkach zamiast wszystkiego w scenie.

Bardziej skomplikowanym podejściem jest użycie BSP lub Octrees.

Jeśli potrzebujesz czegoś, co pozostaje liniowe na dowolnym dystansie (w przeciwieństwie do distance^2), a jednocześnie wydaje się niejasno okrągłe (w przeciwieństwie do kwadratowych odległości Czebyszewa i diamentów na Manhattanie), możesz uśrednić te dwie ostatnie techniki, aby uzyskać przybliżone przybliżenie odległości w kształcie ośmiokąta:

dx = abs(x1 - x0)
dy = abs(y1 - y0)

dist = 0.5 * (dx + dy + max(dx, dy))

Oto wizualizacja (wykres konturowy) funkcji, dzięki Wolfram Alpha :

A oto wykres jego funkcji błędu w porównaniu do odległości euklidesowej (radiany, tylko pierwsza ćwiartka):

Jak widać, błąd waha się od 0% na osiach do około + 12% w płatach. Trochę modyfikując współczynniki, możemy obniżyć go do +/- 4%:

dist = 0.4 * (dx + dy) + 0.56 * max(dx, dy)

Aktualizacja

Przy zastosowaniu powyższych współczynników maksymalny błąd będzie wynosił +/- 4%, ale średni błąd nadal będzie wynosił + 1,3%. Zoptymalizowany pod kątem zerowego średniego błędu, możesz użyć:

dist = 0.394 * (dx + dy) + 0.554 * max(dx, dy)

co daje błędy od -5% do + 3% i średni błąd + 0,043%

Podczas wyszukiwania w Internecie nazwy tego algorytmu znalazłem podobne przybliżenie ośmiokątne :

dist = 1007/1024 * max(dx, dy) + 441/1024 * min(dx, dy)

Zauważ, że jest to w zasadzie równoważne (chociaż wykładniki są różne - te dają błąd od -1,5% do 7,5%, ale można je zmasować do +/- 4%), ponieważ max(dx, dy) + min(dx, dy) == dx + dy. Za pomocą tego formularza połączenia mini maxmożna rozdzielić na korzyść:

if (dy > dx)
    swap(dx, dy)

dist = 1007/1024 * dx + 441/1024 * dy

Czy to będzie szybsze niż moja wersja? Kto wie ... zależy od kompilatora i jego optymalizacji dla platformy docelowej. Domyślam się, że trudno byłoby dostrzec jakąkolwiek różnicę.

Czasami to pytanie może powstać nie z powodu kosztów wykonywania obliczeń odległości, ale z powodu liczby przeprowadzanych obliczeń.

W dużym świecie gry z wieloma aktorami nie można skalować sprawdzania odległości między jednym aktorem a wszystkimi pozostałymi. Ponieważ coraz więcej graczy, NPC i pociski wejść w świat, liczba porównań, które muszą być wykonane będzie rosnąć kwadratu z O(N^2).

Jednym ze sposobów ograniczenia tego wzrostu jest zastosowanie dobrej struktury danych, aby szybko odrzucić niechcianych aktorów z obliczeń.

Szukamy sposobu na skuteczne iterowanie wszystkich aktorów, którzy mogą znajdować się w zasięgu, z wyłączeniem większości aktorów, którzy są zdecydowanie poza zasięgiem .

Jeśli twoi aktorzy są dość równomiernie rozmieszczeni w przestrzeni świata, siatka wiader powinna być odpowiednią strukturą (jak sugeruje przyjęta odpowiedź). Zachowując odniesienia do aktorów na grubej siatce, wystarczy sprawdzić tylko kilka pobliskich wiader, aby objąć wszystkich aktorów, którzy mogą być w zasięgu, ignorując resztę. Kiedy aktor się porusza, może być konieczne przeniesienie go ze starego wiadra do nowego.

W przypadku aktorów, które są mniej równomiernie rozmieszczone, cztero-drzewo może być lepsze dla dwuwymiarowego świata, lub oktawa byłaby odpowiednia dla trójwymiarowego świata. Są to struktury bardziej ogólnego przeznaczenia, które mogą skutecznie dzielić duże obszary pustej przestrzeni oraz małe obszary zawierające wiele aktorów. Dla aktorów statycznych istnieje partycjonowanie przestrzeni binarnej (BSP), które jest bardzo szybkie w wyszukiwaniu, ale o wiele za drogie, aby aktualizować w czasie rzeczywistym. BSP oddzielają przestrzeń za pomocą płaszczyzn, aby wielokrotnie przecinać ją na pół i mogą być stosowane do dowolnej liczby wymiarów.

Oczywiście istnieją koszty ogólne, aby utrzymać twoich aktorów taką strukturę, szczególnie gdy poruszają się między partycjami. Ale w dużym świecie z wieloma aktorami, ale o niewielkim zakresie zainteresowań, koszty powinny być znacznie niższe niż koszty poniesione przez naiwne porównanie ze wszystkimi przedmiotami.

Rozważenie, jak rośnie koszt algorytmu, gdy otrzymuje on więcej danych, ma kluczowe znaczenie dla skalowalnego projektu oprogramowania. Czasami wystarczy po prostu wybrać odpowiednią strukturę danych . Koszty są zwykle opisywane za pomocą notacji Big O .

(Zdaję sobie sprawę, że nie jest to bezpośrednia odpowiedź na pytanie, ale może być przydatna dla niektórych czytelników. Przepraszam, jeśli zmarnowałem twój czas!)

Co powiesz na odległość Czebyszewa? Dla punktów p, q jest on zdefiniowany następująco:

Tak więc dla punktów (2, 4) i (8, 5) odległość Czebyszewa wynosi 6, ponieważ | 2-8 | > | 4-5 |.

Ponadto, niech E będzie odległością euklidesową, a C będzie odległością Czebyszewa. Następnie:

Górna granica prawdopodobnie nie jest zbyt przydatna, ponieważ musiałbyś obliczyć pierwiastek kwadratowy, ale dolna granica może być pomocna - ilekroć odległość Czebyszewa jest wystarczająco duża, aby być poza zasięgiem, odległość euklidesowa musi być zbyt duża, ratując cię z konieczności obliczania.

Kompromis oczywiście polega na tym, że jeśli odległość Czebyszewa jest w zasięgu, i tak musisz obliczyć odległość euklidesową, marnując czas. Tylko jeden sposób, aby dowiedzieć się, czy to będzie wygrana netto!

Bardzo prostą lokalną optymalizacją jest po prostu sprawdzenie najpierw jednego wymiaru.

To jest :

distance ( x1, y1 , x1, y2) > fabs (x2 - x1)

Tak więc samo sprawdzenie fabs (x2 - x1)jako pierwszego filtra może dać znaczny wzrost. Ile będzie zależeć od wielkości świata w porównaniu z odpowiednimi zakresami.

Ponadto można użyć tego jako alternatywy dla struktury danych partycjonowania przestrzennego.

Jeśli wszystkie odpowiednie obiekty są posortowane na liście w współrzędnej x, wówczas obiekty znajdujące się w pobliżu muszą znajdować się w pobliżu na liście. Nawet jeśli lista przestanie być uporządkowana z powodu niepełnego utrzymywania w miarę przemieszczania się obiektów, to biorąc pod uwagę znane granice prędkości, nadal możesz zmniejszyć odcinek listy, który ma być przeszukiwany w pobliżu obiektów.

W przeszłości starano się zoptymalizować sqrt. Chociaż nie dotyczy już dzisiejszych maszyn, oto przykład z kodu źródłowego Quake, który używa magicznej liczby 0x5f3759df :

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;  // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 ); // what the hell?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
  // y  = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration (optional)
  // ...
  return y;
}

Szczegółowe wyjaśnienie tego, co się dzieje tutaj można znaleźć na Wikipedii.

Krótko mówiąc, jest to kilka iteracji metody Newtona (algorytm numeryczny, który iteracyjnie poprawia oszacowanie), z magiczną liczbą wykorzystaną do zapewnienia rozsądnego wstępnego oszacowania.

Jak podkreśla Travis, tego rodzaju optymalizacja nie jest już użyteczna w nowoczesnych architekturach. I nawet gdyby tak było, może jedynie zapewnić stałe przyspieszenie wąskiego gardła, podczas gdy przeprojektowanie algorytmu może osiągnąć lepsze wyniki.