Poprawianie funkcji O (N ^ 2) (wszystkie jednostki iterujące się po wszystkich innych jednostkach)

Trochę tła, koduję grę ewolucyjną z przyjacielem w C ++, używając ENTT dla systemu encji. Stworzenia chodzą po mapie 2D, jedzą zielenie lub inne stworzenia, rozmnażają się, a ich cechy mutują.

Dodatkowo wydajność jest w porządku (60 klatek na sekundę bez problemu), gdy gra jest uruchomiona w czasie rzeczywistym, ale chcę móc ją znacznie przyspieszyć, aby nie musieć czekać 4 godziny, aby zobaczyć znaczące zmiany. Więc chcę uzyskać to tak szybko, jak to możliwe.

Staram się znaleźć skuteczną metodę dla stworzeń, aby znaleźć swoje pożywienie. Każde stworzenie powinno szukać najlepszego jedzenia, które jest im wystarczająco blisko.

Jeśli chce jeść, stworzenie przedstawione na środku ma rozejrzeć się w promieniu 149,64 (odległość widzenia) i ocenić, które jedzenie powinien realizować na podstawie żywienia, odległości i rodzaju (mięso lub roślina) .

Funkcja odpowiedzialna za odnalezienie każdego stworzenia, które je pożywienie, pochłania około 70% czasu pracy. Upraszczając sposób, w jaki jest obecnie napisany, wygląda mniej więcej tak:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

Ta funkcja jest uruchamiana co tyknięcie dla każdego stworzenia szukającego pożywienia, dopóki stworzenie nie znajdzie jedzenia i nie zmieni stanu. Jest także uruchamiany za każdym razem, gdy nowe jedzenie odradza się dla stworzeń, które już gonią za danym jedzeniem, aby upewnić się, że wszyscy sięgają po najlepsze dostępne dla nich jedzenie.

Jestem otwarty na pomysły, jak usprawnić ten proces. Chciałbym zmniejszyć złożoność z , ale nie wiem, czy to w ogóle możliwe.$O(N^2)$

Jednym ze sposobów, które już poprawiłem, jest posortowanie all_entities_with_food_valuegrupy, aby gdy stworzenie przechodziło przez jedzenie zbyt duże, aby je zjeść, zatrzymywało się na nim. Wszelkie inne ulepszenia są mile widziane!

EDYCJA: Dziękuję wszystkim za odpowiedzi! Zaimplementowałem różne rzeczy z różnych odpowiedzi:

Po pierwsze i po prostu to zrobiłem, aby funkcja winy działała tylko raz na pięć tyknięć, dzięki czemu gra była 4x szybsza, nie zmieniając widocznie niczego w grze.

Następnie zapisałem w systemie wyszukiwania żywności tablicę z jedzeniem spawnowanym w tym samym tiksie, w którym działa. W ten sposób muszę tylko porównać jedzenie, które ściga stworzenie z nowymi, które się pojawiły.

Wreszcie, po badaniach nad podziałem przestrzeni i rozważeniem BVH i quadtree, poszedłem z tym drugim, ponieważ uważam, że jest to znacznie prostsze i lepiej dostosowane do mojego przypadku. Wdrażam to dość szybko i znacznie poprawia wydajność, wyszukiwanie żywności prawie nie zajmuje czasu!

Teraz renderowanie spowalnia mnie, ale to problem na kolejny dzień. Dziękuję wam wszystkim!

Wiem, że nie traktujesz tego jako zderzenia, jednak to, co robisz, to zderzanie się koła wokół istoty z całym jedzeniem.

Naprawdę nie chcesz sprawdzać jedzenia, o którym wiesz, że jest odległe, tylko to, co jest w pobliżu. To jest ogólna rada dotycząca optymalizacji kolizji. Chciałbym zachęcić do szukania technik optymalizacji kolizji i nie ograniczać się do C ++ podczas wyszukiwania.

Stworzenie znajduje jedzenie

W twoim scenariuszu sugerowałbym postawienie świata na planszy. Ustaw komórki co najmniej w promieniu okręgów, które chcesz zderzyć. Następnie możesz wybrać jedną komórkę, na której znajduje się stworzenie, i jego maksymalnie ośmiu sąsiadów i przeszukać tylko te do dziewięciu komórek.

Uwaga : możesz utworzyć mniejsze komórki, co oznaczałoby, że poszukiwany krąg rozciągałby się poza pośrednich sąsiadów, wymagając od ciebie iteracji. Jeśli jednak problem polega na tym, że jest za dużo pożywienia, mniejsze komórki mogą oznaczać iterację łącznie mniejszą ilością bytów, co w pewnym momencie zmienia się na twoją korzyść. Jeśli podejrzewasz, że tak jest, przetestuj.

Jeśli jedzenie się nie porusza, możesz dodawać byty żywności do siatki podczas tworzenia, aby nie trzeba było wyszukiwać, które byty są w komórce. Zamiast tego przeszukujesz komórkę i ma ona listę.

Jeśli sprawisz, że rozmiar komórek będzie potęgą dwóch, możesz znaleźć komórkę, na której znajduje się stworzenie, po prostu obcinając jego współrzędne.

Możesz pracować z odległością do kwadratu (czyli nie rób sqrt), porównując, aby znaleźć najbliższą. Mniej operacji sqrt oznacza szybsze wykonanie.

Dodano nowe jedzenie

Kiedy dodaje się nowe jedzenie, tylko pobliskie stworzenia muszą się obudzić. To ten sam pomysł, tyle że teraz zamiast tego musisz pobrać listę stworzeń w komórkach.

O wiele bardziej interesujące jest to, że jeśli zauważysz w stworzeniu adnotację, jak daleko jest od jedzenia, które ściga ... możesz bezpośrednio sprawdzić tę odległość.

Kolejną rzeczą, która Ci pomoże, jest uświadomienie sobie jedzenia, które goni je stworzenia. To pozwoli ci uruchomić kod znajdujący pożywienie dla wszystkich stworzeń, które gonią kawałek jedzenia, który właśnie został zjedzony.

W rzeczywistości rozpocznij symulację bez jedzenia, a wszystkie stworzenia mają opisaną odległość nieskończoności. Następnie zacznij dodawać jedzenie. Aktualizuj odległości w miarę przemieszczania się stworzeń ... Kiedy jedzenie jest spożywane, weź listę stworzeń, które go gonią, i znajdź nowy cel. Poza tym, wszystkie inne aktualizacje są obsługiwane po dodaniu jedzenia.

Pomijanie symulacji

Znając szybkość stworzenia, wiesz, ile to kosztuje, dopóki nie osiągnie celu. Jeśli wszystkie stworzenia mają tę samą prędkość, ta, która osiągnie pierwszą, będzie miała najmniejszą odległość z adnotacjami.

Jeśli znasz również czas, zanim dodasz więcej jedzenia ... I mam nadzieję, że masz podobną przewidywalność dla rozmnażania i śmierci, to znasz czas na następne wydarzenie (albo jedzenie, albo stworzenie jedzące).

Przejdź do tego momentu. Nie musisz symulować poruszających się stworzeń.

Należy zastosować algorytm podziału przestrzeni, taki jak BVH, aby zmniejszyć złożoność. Aby być specyficznym dla twojego przypadku, musisz zrobić drzewo, które składa się z wyrównanych do osi obwiedni zawierających kawałki żywności.

Aby stworzyć hierarchię, umieść kawałki żywności blisko siebie w AABB, a następnie umieść te AABB w większych AABB, ponownie, według odległości między nimi. Zrób to, aż będziesz mieć węzeł główny.

Aby skorzystać z drzewa, najpierw wykonaj test przecięcia okręgu-AABB względem węzła głównego, a następnie, jeśli dojdzie do kolizji, przetestuj na elementach potomnych każdego kolejnego węzła. Na koniec powinieneś mieć grupę kawałków jedzenia.

Możesz także skorzystać z biblioteki AABB.cc.

Chociaż opisane metody podziału przestrzeni rzeczywiście mogą skrócić czas, twoim głównym problemem nie jest tylko wyszukiwanie. To sama liczba wyszukiwań sprawia, że ​​twoje zadanie jest powolne. Więc optymalizujesz wewnętrzną pętlę, ale możesz również zoptymalizować zewnętrzną pętlę.

Problem polega na tym, że ciągle odpytujesz dane. To trochę tak, jakby dzieci na tylnym siedzeniu pytały po raz tysięczny „jesteśmy jeszcze”, nie ma potrzeby, aby kierowca poinformował cię, kiedy tam będziesz.

Zamiast tego powinieneś starać się, jeśli to możliwe, rozwiązać każdą akcję do jej zakończenia, umieścić ją w kolejce i wypuścić te bąbelkowe zdarzenia, może to wprowadzić zmiany w kolejce, ale to jest w porządku. To się nazywa symulacja zdarzeń dyskretnych. Jeśli możesz zaimplementować swoją symulację w ten sposób, to szukasz znacznego przyspieszenia, które znacznie przewyższa przyspieszenie, jakie możesz uzyskać dzięki lepszemu wyszukiwaniu partycji kosmicznej.

Aby podkreślić punkt poprzedniej kariery, stworzyłem symulatory fabryczne. Metodą tę symulowaliśmy tygodnie dużych fabryk / lotnisk w całym przepływie materiałów na każdym poziomie pozycji w niecałą godzinę. Podczas gdy symulacja oparta na timestepie mogła symulować tylko 4-5 razy szybciej niż w czasie rzeczywistym.

Również jako bardzo nisko wiszący owoc rozważ oddzielenie procedur rysowania od symulacji. Mimo że twoja symulacja jest prosta, nadal istnieje pewien narzut związany z rysowaniem. Co gorsza, sterownik ekranu może ograniczać Cię do x aktualizacji na sekundę, podczas gdy w rzeczywistości Twoje procesory mogą robić rzeczy setki razy szybciej. To podkreśla potrzebę profilowania.

Możesz użyć algorytmu linii przeciągnięcia, aby zredukować złożoność do Nlog (N). Teoria polega na diagramach Voronoi, które dzielą obszar otaczający stworzenie na regiony składające się ze wszystkich punktów bliższych temu stworzeniu niż jakiemukolwiek innemu.

Tak zwany algorytm fortuny robi to za Ciebie w Nlog (N), a strona wiki na tym pseudo-kodzie do jego implementacji. Jestem pewien, że istnieją również implementacje bibliotek. https://en.wikipedia.org/wiki/Fortune%27s_alameterm

Najłatwiejszym rozwiązaniem byłoby zintegrowanie silnika fizyki i użycie tylko algorytmu wykrywania kolizji. Po prostu zbuduj okrąg / kulę wokół każdej istoty i pozwól, aby silnik fizyki obliczył kolizje. W przypadku 2D sugerowałbym Box2D lub Chipmunk i Bullet dla 3D.

Jeśli uważasz, że zintegrowanie całego silnika fizyki to zbyt wiele, sugerowałbym przyjrzenie się konkretnym algorytmom kolizji. Większość bibliotek wykrywania kolizji działa w dwóch krokach:

• Wykrywanie fazy szerokiej: celem tego etapu jest uzyskanie listy kandydujących par obiektów, które mogą kolidować tak szybko, jak to możliwe. Dwie typowe opcje to:
  • Przeciągnij i przycinaj : posortuj obwiednie wzdłuż osi X i zaznacz te pary obiektów, które się przecinają. Powtórz dla każdej innej osi. Jeśli para kandydatów przejdzie wszystkie testy, przechodzi do następnego etapu. Ten algorytm jest bardzo dobry w wykorzystywaniu spójności czasowej: możesz przechowywać listy posortowanych jednostek i aktualizować je co każdą klatkę, ale ponieważ są one prawie posortowane, będzie to bardzo szybkie. Wykorzystuje również spójność przestrzenną: ponieważ byty są sortowane w rosnącej kolejności przestrzennej, podczas sprawdzania kolizji możesz zatrzymać się, gdy tylko byt nie zderzy się, ponieważ wszystkie następne będą dalej.
  • Struktury partycjonowania danych przestrzennych, takie jak czwórki, ośmioboki i siatki. Siatki są łatwe do wdrożenia, ale mogą być bardzo marnotrawne, jeśli gęstość jednostek jest niska i bardzo trudne do wdrożenia w przypadku nieograniczonej przestrzeni. Statyczne drzewa przestrzenne są również łatwe do wdrożenia, ale trudne do wyważenia lub aktualizacji w miejscu, więc trzeba będzie przebudować je w każdej ramce.
• Faza wąska: pary kandydatów znajdujące się w fazie szerokiej są dalej testowane za pomocą bardziej precyzyjnych algorytmów.