De schadekaart

De schadekaart

> Programmeren

Met de evaluatie van bewegingen en het beheer van aanvalscombinaties is de schadekaart een essentieel onderdeel van LeekWars. Het belangrijkste doel is om, afhankelijk van de tegenstander, het gevaarsniveau van elke doos te kunnen beoordelen om aan het einde van de beurt terug te kunnen trekken naar een doos met minder gevaar. De eenvoudigste manier is om een associatieve array te maken: dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], mogelijk beperkt tot uw toegankelijke cellen. Hiervoor zijn verschillende algoritmen mogelijk

Het "naïeve" algoritme

Dit is meestal het eerste idee dat in je opkomt bij het maken van een algoritme voor gevarenbeoordeling. Het idee is het volgende:

/* -voor elk van mijn toegankelijke cellen

-voor elke toegankelijke cel van de tegenstander -voor het wapen van elke tegenstander -als hij mijn cel uit zijn cel kan schieten voeg een "gevaarscore" toe aan mijn cel */

De keuze van de score is een integraal onderdeel van je algoritme: je kunt er "+1" in zetten, of de potentieel toegebrachte schade berekenen, ... Er zijn net zoveel manieren om deze evaluatie te verfijnen als er spelers zijn 😉

Het grote probleem met dit algoritme is dat het extreem hebzuchtig is in operaties! Het is daarom over het algemeen noodzakelijk om het zeer snel te optimaliseren.

Optimalisatiesporen

Het eerste dat u moet doen, is voorkomen dat uw prei "crasht"... U moet dus ergens in de code een test doen op getOperations() en loops verlaten als het aantal bewerkingen te dicht bij de limiet: je hebt maar een gedeeltelijke inschatting van het gevaar, maar je prei zal nog minimaal kunnen bewegen 😉

Voor de optimalisatie zelf is een van de eerste principes die uw aanpak zou moeten leiden, vooral om te voorkomen dat dezelfde bewerkingen meerdere keren in de lussen worden herhaald: in dit geval is het beter om dingen in tabellen voor te bereiden en dan te onthouden. Dus, bijvoorbeeld, in de binnenste lus die de "danger score" berekent, als je een oproep naar getStrength(Enemy) erin plaatst, roep je die functie duizenden keren terug. Het idee is dan om de kracht van de vijand slechts één keer te berekenen en deze op te slaan in een variabele voordat de interne loops worden uitgevoerd. U begint al met het verdienen van een paar honderdduizend transacties! Zoek dus naar elementen van "interne" lussen die niet afhankelijk zijn van de lusvariabele, maar alleen van een "externe" lus: je kunt deze elementen dan herleiden naar hun lus.

Als uw algoritme duur blijft, is een andere nogal esthetische manier voor optimalisatie het downgraden van de resolutie van deze evaluatie. Je kunt bijvoorbeeld niet alle toegankelijke velden testen (die van jou en/of die van de tegenstander), maar bijvoorbeeld alleen die waarvoor een even aantal bewegingspunten nodig is. Het "volstaat" dan om de hiaten op te vullen die zijn verkregen door interpolatie van de waarden op de aangrenzende vierkanten (gemiddelde van de buren, maximum van de buren, maximum van het gemiddelde tussen twee lijnen, enz.). Deze benadering is minder nauwkeurig, maar verbruikt, met het voorbeeld van even PM's, ongeveer 4x minder dan het eerste algoritme.

Om door te gaan met optimalisaties, moet u nadenken over het vooraf berekenen van dingen, meestal in de eerste ronde, het opslaan in grote (of veel) arrays van bepaalde dingen die u opnieuw moet berekenen en die nooit veranderen, of zelfs het updaten van bepaalde waarden elke beurt (in ons voorbeeld de kracht van vijandelijke prei).

Het algoritme "voor eens en voor altijd".

Dit algoritme berekent vooraf een gevarenkaart aan het begin van het gevecht. Goedkoop, het is veel minder nauwkeurig, maar stelt je in staat om snel de lijst met gebieden van de gevechtskaart te hebben die over het algemeen gevaarlijk zijn. Het bestaat uit het evalueren, aan het begin van de beurt, voor elke cel van de gevechtskaart, alle cellen waarmee je erop kunt schieten met de wapens die de vijand(en) hebben: een vierkant dat alleen kan worden bereikt vanaf 5 andere vierkanten zullen dan een veel lagere score hebben dan een vierkant dat bereikbaar is met 200 andere vierkanten! Het kan verstandig zijn om te proberen je terug te trekken naar gebieden met "weinig gevaar" en de vijand zover te krijgen dat hij in gebieden met "hoog gevaar" blijft.