Mapa uszkodzeń

Mapa uszkodzeń

> Programowanie

Wraz z oceną ruchów i zarządzaniem kombinacjami ataków, mapa uszkodzeń jest bardzo istotna w LeekWars. Głównym celem jest możliwość oceny, w zależności od przeciwnika, poziomu zagrożenia każdego pola, aby móc wycofać się do pola mniejszego zagrożenia na koniec tury. Najprostszym sposobem jest utworzenie tablicy asocjacyjnej: dangerMap=[cell1:danger1 , cell2:danger2 , ... ], prawdopodobnie ograniczonej do dostępnych komórek. W tym celu możliwych jest kilka algorytmów

Algorytm „naiwny”.

Jest to zwykle pierwsza myśl, która przychodzi do głowy podczas tworzenia algorytmu oceny zagrożenia. Pomysł jest następujący:

/* -dla każdej z moich dostępnych komórek -za każdego przeciwnika -za każdą dostępną komórkę przeciwnika -za broń każdego przeciwnika -jeśli może wystrzelić moją komórkę ze swojej celi dodaj „wynik zagrożenia” do mojej komórki */

Wybór wyniku jest integralną częścią twojego algorytmu: możesz w nim umieścić „+1”, lub obliczyć potencjalne wyrządzone szkody… Sposobów na dopracowanie tej oceny jest tyle, ilu graczy 😉

Duży problem z tym algorytmem polega na tym, że jest on wyjątkowo zachłanny w operacjach! Dlatego generalnie konieczna jest bardzo szybka optymalizacja.

Ścieżki optymalizacji

Pierwszą rzeczą do zrobienia jest zapobieżenie „awarii” pora… Musisz więc gdzieś w kodzie wykonać test na getOperations() i wyjść z pętli, jeśli liczba operacji zbliży się do granica: będziesz miał tylko częściową ocenę zagrożenia, ale Twój por nadal będzie mógł ruszyć się minimalnie 😉

Jeśli chodzi o samą optymalizację, jedną z pierwszych zasad, która powinna przyświecać Twojemu podejściu, jest przede wszystkim unikanie kilkukrotnego powtarzania tych samych operacji w pętlach: lepiej w tym przypadku przygotować rzeczy w tabelach niż pamiętać. Na przykład w najbardziej wewnętrznej pętli, która oblicza „wynik zagrożenia”, jeśli wywołasz w niej getStrength(Enemy), wywołasz tę funkcję tysiące razy. Chodzi o to, aby obliczyć siłę wroga tylko raz i zapisać ją w zmiennej przed wykonaniem pętli wewnętrznych. Zaczniesz już zarabiać kilkaset tysięcy transakcji! Więc szukaj elementów pętli „wewnętrznych”, które nie zależą od zmiennej pętli, ale tylko od pętli „zewnętrznej”: możesz następnie prześledzić te elementy z powrotem do ich pętli.

Jeśli twój algorytm pozostaje drogi, innym dość estetycznym sposobem optymalizacji jest obniżenie rozdzielczości tej oceny. Możesz na przykład nie testować wszystkich dostępnych pól (twojego i/lub przeciwnika), ale np. tylko te, które wymagają parzystej liczby punktów ruchu. „Wystarczy” wówczas uzupełnić luki otrzymane przez interpolację wartości na sąsiednich kwadratach (średnia sąsiadów, maksimum sąsiadów, maksimum średniej między dwoma prostymi itp.). Takie podejście jest mniej dokładne, ale na przykładzie nawet PM zużywa około 4x mniej niż pierwszy algorytm.

Aby kontynuować optymalizacje, będziesz musiał pomyśleć o wstępnym obliczeniu rzeczy, zwykle w pierwszej rundzie, przechowywaniu w dużych (lub wielu) tablicach pewnych rzeczy, które musisz ponownie obliczyć i które nigdy się nie zmieniają, a nawet aktualizowaniu aktualizacji niektórych wartości co turę (w naszym przykładzie siła wrogich porów).

Algorytm „raz na zawsze”.

Algorytm ten wstępnie oblicza mapę zagrożenia raz na początku walki. Niedrogi, jest znacznie mniej precyzyjny, ale pozwala szybko mieć listę obszarów mapy walki, które są generalnie niebezpieczne. Polega na ocenie, na początku tury, dla każdej komórki mapy walki, wszystkich komórek, które pozwalają ci strzelać do niej bronią posiadaną przez wroga (wrogów): pole, do którego można dotrzeć tylko z 5 inne kwadraty będą miały wtedy wynik znacznie niższy niż kwadrat osiągalny przez 200 innych kwadratów! Rozsądne może być wycofanie się do obszarów „małego zagrożenia” i zmuszenie wroga do pozostania w obszarach „wysokiego zagrożenia”.