Posizionamento di strutture difensive in un gioco

Question

Sto lavorando su un robot AI per il gioco Defcon. Il gioco ha città, con popolazioni diverse e strutture difensive con raggio limitato. Sto cercando di elaborare un buon algoritmo per posizionare le torri di difesa.

• Città con popolazioni superiori sono più importanti per difendere
• Perdere una torre di difesa è un duro colpo, in modo da torri devono essere collocati ragionevolmente vicino insieme
• torri e città può essere eseguito solo su un terreno

Quindi, con queste tre regole, vediamo che il miglior tipo di posizionamento è che le torri siano poste in un anello attorno alle aree di popolazione più grandi (anche se non voglio un algoritmo solo per posizionare ciecamente un anello intorno alla più alta area della popolazione , a volte potrebbero esserci 2 set di citie È molto distanziato, nel qual caso l'algoritmo dovrebbe fare 2 cerchi, ognuno dei quali metà delle mie torri totali).

Mi chiedo quale tipo di algoritmi potrebbero essere utilizzati per determinare il posizionamento delle torri?

Answer 1

Non conosco il gioco ma dalla tua descrizione sembra che tu abbia bisogno di un algoritmo simile a quello per risolvere il problema (ponderato) dei k-centri. Beh, sfortunatamente, questo è un problema di NP, quindi nel migliore dei casi si otterrà un'approssimazione superiore delimitata da qualche fattore.

dare uno sguardo qui: http://algo2.iti.kit.edu/vanstee/courses/kcenter.pdf

Answer 2

Basta definire una funzione di utilità che prende una potenziale posizione di costruzione come input e restituisce un "rating" per quella posizione. Immagino che sarebbe simile:

utility(position p) = k1 * population_of_city_at_p + 
         k2 * new_area_covered_if_placed_at_p + 
         k3 * number_of_nearby_defences 

(k1, k2, e k3 sono costanti arbitrarie che avrete bisogno di sintonizzare)

Poi, solo casualmente campione del mazzo di diversi punti, e p scegli quello con la massima utilità.

Answer 3

Definirei una funzione determina il valore di una torre posizionata in quella posizione. Quindi cerca i massimi in quella funzione e posiziona una torre lì.

Uno schizzo per la funzione potrebbe essere il seguente:

if water return 0 

popsum = sum for all city over (population/distance) // it's better to have towers close by 

towersum = - sum for all existing towers (1/distance) // you want you towers spread somewhat evenly 

return popsum + towersum*f // f adjusts the relative importance of spreading towers equally and protecting the population centers with many towers 

dovrebbe dare un algoritmo ragionevole per iniziare. Per il miglioramento si potrebbe modificare la funzione 1/distanza a qualcosa di diverso, per ottenere una goccia di più veloce o più lento.

Answer 4

mi piacerebbe iniziare con l'implementazione di una funzione di fitness che calcola la protezione prevista fornita da una serie di torri su un determinato programma.

Calcolerai la quantità di popolazione all'interno dell'area "protetta" in cui le aree coperte da due torri sono classificate un po 'più in alto dell'area coperta da una sola torre (il fattore di scala esatto dipende molto dalle meccaniche di gioco, " anche se).

Quindi è possibile utilizzare un genetic algorithm per sperimentare diversi set di posizionamenti e lasciarli funzionare per diverse iterazioni (hundered?).

Se la funzione di fitness è una buona misura per la reale qualità del posizionamento e l'implementazione dell'algoritmo genetico è corretto, allora si dovrebbe ottenere un risultato ragionevole.

E una volta che hai fatto tutto ciò che è possibile iniziare a sviluppare un piano di attacco che cerca di ottimizzare le perdite per un dato insieme di posizionamenti di torre di difesa.Una volta ottenuto ciò, puoi impostare le due popolazioni una contro l'altra e raggiungere così piani di difesa ancora migliori in questo modo (questa è una delle idee di base di artificial life).