Al momento sto sviluppando un plugin per World of Warcraft in LUA per ottimizzare una parte del gioco introdotta di recente, ovvero le missioni di Garrison.
A Warcraft Garrison (fondamentalmente una strongzza per giocatore) ha un posto dove puoi assegnare i tuoi follower per andare in missione per te. Se queste missioni avranno successo, i tuoi follower avranno una certa esperienza e otterrai una piccola ricompensa, che spazia da un po 'di soldi a un equipaggiamento potente per te o per i tuoi follower. Una guarnigione ha 20-25 follower e ha circa 25-30 missioni tra cui scegliere al giorno.
Una missione ha i seguenti attributi:
- Un livello compreso tra 90 e 100, incluso.
- (per le missioni di livello 100) Un livello di equipaggiamento tra 615 e 645, a intervalli di 15.
- tra 1 e 3 slot per inviare follower con.
- tra 0 e 6 minacce di missione. Esistono circa 10 categorie di minacce, i cui nomi sono irrilevanti. Ciò che è rilevante è che un follower può avere 1 o 2 abilità in grado di contrastare queste minacce. Una missione può avere la stessa minaccia due volte.
- Un tipo di zona in cui si verifica questa missione.
- un tipo nemico a cui sta combattendo questa missione.
- Una durata.
Un follower ha i seguenti attributi:
- la razza del follower.
- Un livello compreso tra 90 e 100, inclusi. i seguaci di livello uguale o superiore contribuiscono maggiormente al successo della missione. Un follower che è di un livello al di sotto del livello della missione è meno efficace, ma ha comunque un effetto. Un follower di 2 o più livelli sotto il livello della missione non ha influenza sul successo della missione e non può contrastare alcuna minaccia.
- (A partire dal livello 100) Un livello di equipaggiamento tra 600 e 655 inclusi. Come il livello normale, i follower con livello di equipaggiamento uguale o superiore sono più efficaci.
- 1 o 2 abilità che sono segnalini per le minacce alla missione. Una minaccia contraria aumenta la possibilità di successo. se tutte le minacce vengono neutralizzate con follower di livello superiore, una missione ha una probabilità del 100% di successo. Un follower può avere 2 abilità che contrastano la stessa minaccia.
- 1, 2 o 3 tratti che possono dare minori possibilità di successo in determinate condizioni di missione. Questi non danno più possibilità di bonus di un contatore completo, ma sono utili per ottimizzare. Un tratto può contrastare una zona, una durata o un tipo nemico. Possono anche dare un bonus per avere un tipo specifico di follower nella stessa missione, o anche dare un bonus di successo sempre attivo.
Quello che capisco da alcuni breve chat con Gamedev.SE , questo è fondamentalmente il Problema di imballaggio del contenitore , con le missioni come pacchetti e i follower come contenitori. Tuttavia, in questo caso, i raccoglitori possono combinare e sono di diverse dimensioni.
L'algoritmo che sto cercando ha lo scopo di fare quanto segue nel minor tempo possibile:
- Massimizza la quantità di missioni con il 100% di possibilità di successo;
- Massimizza le possibilità individuali di successo di ogni missione che non ha il 100% di possibilità;
Probabilmente potrei rafforzarla, ma spero in una soluzione un po 'più sofisticata.
Quale algoritmo dovrei usare per questo?