El mapa de daños

> Programación

Con la evaluación de movimientos y la gestión de combinaciones de ataques, el mapa de daño es un gran imprescindible en LeekWars. El objetivo principal es poder valorar, en función del adversario, un nivel de peligrosidad de cada casilla para poder retirarse a una casilla de menor peligrosidad al final del turno. La forma más sencilla es crear una matriz asociativa: dangerMap=[ cell1:danger1 , cell2:danger2 , ... ], posiblemente limitada a sus celdas accesibles. Para este propósito, varios algoritmos son posibles

El algoritmo "ingenuo"

Esta suele ser la primera idea que viene a la mente al crear un algoritmo de evaluación de peligros. La idea es la siguiente:

/* -para cada una de mis celdas accesibles -por cada oponente -por cada celda accesible del oponente -para el arma de cada oponente -si puede dispararme al celular desde su celular añadir una "puntuación de peligro" a mi celda */

La elección de la puntuación es una parte integral de tu algoritmo: puedes poner "+1" en ella, o calcular el daño potencialmente infligido... Hay tantas formas de refinar esta evaluación como jugadores 😉

¡El gran problema con este algoritmo es que es extremadamente codicioso en las operaciones! Por lo tanto, generalmente es necesario optimizarlo muy rápidamente.

Pistas de optimización

Lo primero que debe hacer es evitar que su puerro se "bloquee"... Por lo tanto, debe, en algún lugar del código, hacer una prueba en getOperations() y salir de los bucles si el número de operaciones se acerca demasiado a el límite: solo tendrá una evaluación parcial del peligro, pero su puerro aún podrá moverse un mínimo 😉

Para la optimización en sí, uno de los primeros principios que debe guiar su enfoque es, sobre todo, evitar repetir las mismas operaciones varias veces en los bucles: es mejor en este caso preparar las cosas en tablas que recordar. Entonces, por ejemplo, en el ciclo más interno que calcula el "puntaje de peligro", si agrega una llamada a getStrength (Enemy), llamará a esa función miles de veces. La idea es entonces calcular la fuerza del enemigo una sola vez y almacenarla en una variable antes de hacer los bucles internos. ¡Ya comenzarás a ganar unos cientos de miles de operaciones! Así que busque elementos de bucles "internos" que no dependan de la variable de bucle, sino solo de un bucle "externo": luego puede rastrear estos elementos hasta su bucle.

Si su algoritmo sigue siendo costoso, otra vía bastante estética para la optimización es degradar la resolución de esta evaluación. Puede, por ejemplo, no probar todas las casillas accesibles (las suyas y/o las del oponente), pero, por ejemplo, solo aquellas que requieren un número par de puntos de movimiento. "Basta" entonces con rellenar los huecos obtenidos por interpolación de los valores de los cuadrados vecinos (media de los vecinos, máximo de los vecinos, máximo de la media entre dos líneas, etc.). Este enfoque es menos preciso, pero, con el ejemplo de PM uniformes, consume alrededor de 4 veces menos que el primer algoritmo.

Para continuar con las optimizaciones, tendrá que pensar en precomputar cosas, generalmente en la primera ronda, almacenar en matrices grandes (o muchas) ciertas cosas que debe volver a calcular y que nunca cambian, o incluso actualizar ciertos valores. cada turno (en nuestro ejemplo, la fuerza de los puerros enemigos).

El algoritmo "de una vez por todas"

Este algoritmo precalcula un mapa de peligro una vez al comienzo de la pelea. Económico, es mucho menos preciso pero te permite tener rápidamente la lista de áreas del mapa de combate que generalmente son peligrosas. Consiste en evaluar, al inicio del turno, para cada casilla del mapa de combate, todas las casillas que te permitan dispararle con las armas que tiene el o los enemigos: una casilla a la que solo se puede llegar desde 5 ¡Otros cuadrados tendrán entonces una puntuación mucho más baja que un cuadrado alcanzable por otros 200 cuadrados! Puede ser conveniente tratar de retirarse a áreas de "bajo peligro" y hacer que el enemigo permanezca en áreas de "alto peligro".