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.
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!
źródło
if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue;powinno być łatwiejsze niż wdrożenie „skomplikowanej” struktury pamięci, JEŚLI jest wystarczająco wydajna. (Powiązane: Może nam pomóc, jeśli opublikujesz trochę więcej kodu w wewnętrznej pętli)Odpowiedzi:
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ń.
źródło
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.
źródło
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.
źródło
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
źródło
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:
źródło