Skadekartan

> Programmering

Med utvärderingen av rörelser och hanteringen av attackkombinationer är skadekartan en stor väsentlighet i LeekWars. Huvudsyftet är att, beroende på motståndaren, kunna bedöma risknivån för varje box för att kunna dra sig tillbaka till en box med mindre fara i slutet av svängen. Det enklaste sättet är att skapa en associativ array: dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], möjligen begränsad till dina tillgängliga celler. För detta ändamål är flera algoritmer möjliga

Den "naiva" algoritmen

Detta är vanligtvis den första idén som kommer att tänka på när man skapar en algoritm för farobedömning. Tanken är följande:

/* -för var och en av mina tillgängliga celler -för varje motståndare -för varje tillgänglig cell hos motståndaren -för varje motståndares vapen -om han kan skjuta min cell från sin cell lägg till en "fara poäng" i min cell */

Valet av poäng är en integrerad del av din algoritm: du kan sätta "+1" i den, eller beräkna den potentiella skadan, ... Det finns lika många sätt att förfina den här utvärderingen som det finns spelare 😉

Det stora problemet med denna algoritm är att den är extremt girig i operationer! Det är därför i allmänhet nödvändigt att optimera den mycket snabbt.

Optimeringsspår

Det första du ska göra är att förhindra att din purjolök "kraschar"... Så du måste, någonstans i koden, göra ett test på getOperations() och avsluta loopar om antalet operationer kommer för nära gränsen: du kommer bara att ha en partiell bedömning av faran, men din purjolök kommer fortfarande att kunna röra sig ett minimum 😉

För själva optimeringen är en av de första principerna som bör styra ditt tillvägagångssätt framför allt att undvika att upprepa samma operationer flera gånger i slingorna: det är bättre i det här fallet att förbereda saker i tabeller och sedan komma ihåg. Så, till exempel, i den innersta slingan som beräknar "danger-poängen", om du lägger ett anrop till getStrength(Enemy) i den, kommer du att kalla tillbaka den funktionen tusentals gånger. Tanken är då att bara beräkna fiendens styrka en gång och lagra den i en variabel innan man gör de interna looparna. Du kommer redan att börja tjäna några hundra tusen affärer! Så leta efter element av "interna" loopar som inte är beroende av loopvariabeln, utan bara på en "extern" loop: du kan sedan spåra dessa element tillbaka till deras loop.

Om din algoritm förblir dyr är en annan ganska estetisk väg för optimering att nedgradera upplösningen för denna utvärdering. Du kan till exempel inte testa alla tillgängliga rutor (din och/eller motståndarens), utan till exempel bara de som kräver ett jämnt antal rörelsepoäng. Det "räcker" då att fylla i luckorna som erhålls genom interpolering av värdena på de angränsande kvadraterna (medelvärde för grannarna, maximalt av grannarna, maximum av medelvärdet mellan två linjer, etc.). Detta tillvägagångssätt är mindre exakt, men, med exemplet med jämna PM, förbrukar det ungefär 4 gånger mindre än den första algoritmen.

För att fortsätta optimeringarna måste du tänka på att förberäkna saker, vanligtvis i den första omgången, lagra i stora (eller många) arrayer vissa saker som du måste beräkna om och som aldrig ändras, eller till och med uppdatera uppdatera vissa värden varje tur (i vårt exempel styrkan hos fiendens purjolök).

Algoritmen "en gång för alla".

Denna algoritm förberäknar en farokarta en gång i början av kampen. Billigt, det är mycket mindre exakt men låter dig snabbt få listan över områden på stridskartan som är allmänt farliga. Den består av att utvärdera, i början av vändningen, för varje cell på stridskartan, alla celler som låter dig skjuta på den med de vapen som fienden/fienden har: en ruta som endast kan nås från 5 andra rutor kommer då att ha en poäng mycket lägre än en ruta som kan nås av 200 andra rutor! Det kan vara klokt att försöka dra sig tillbaka till områden med "låg fara", och få fienden att stanna i områden med hög fara.