Bonjour à tous,
je joues depuis quelques semaines à un jeu ou l'on doit programmer des IA de poireaux qui ensuite se combattent entre eux. ( https://leekwars.com). Le language ressemble à du javascript
A mon niveau, mon poireau a 2 armes équipées et 7 puces, ce qui me fait un arsenal de 9 items. Chacun peut etre utilisé moyennant un cout en points de tour (= TP). Et a chaque tour, j'ai à ma disposition 10 TP.
Je cherche à déterminer l'ensemble des combos disponibles que j'ai avec mes 10 TP
Exemple:
Si j'ai l'arme A qui coute 4 TP a chaque utilisation
l'arme B qui coute 3 TP
la puce C qui coute 2 TP
mes combos pourraient etre :
2 x arme A + 1 x puce C
1 x arme A + 2 x arme B
5 x arme C
1 x arme B + 3 x puce C
...
Je sais à peu près bien coder, mais je n'ai jamais vraiment pratiquer d'algorithme combinatoire. J'ai essayer de me faire une fonction récursive( cest ce qui m'est venu en tete en premier), mais de meme la recursivité est quelque chose de très nouveau pour moi.
En m'inspirant d'une fonction que j'ai trouvé sur internet j'ai codé ceci:
La fonction me génère un beau tableau avec pas mal de combos.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 global elements = arrayFlatten([getChips(), getWeapons()]); //Fonctions natives qui me renvoient toutes mes armes/puces équipées global totalTP = 10; //Mon total de points de tour global arrayCombos; //Mon tableau ou je veux stocker mes combos if (arrayCombos == null) { arrayCombos = []; } ///////////////////////////// MAIN //////////////////////////////// if (getTurn() == 1) { arrayCombos = combinaisonsFn(elements, 5); debug('c: ' + count(arrayCombos)); } debug(getOperations()); //////////////////////////// FUNCTIONS ///////////////////////////////// function combinaisonsFn(tab, taille) { //Cas de base if (taille == 1) { return arrayMap(tab, function(@x) { return [x]; }); } else { var result = []; var combinaisons = combinaisonsFn(tab, taille - 1); for (var item in tab) { //Item=item à rajouter for (var combinaison in combinaisons) { //Combinaison=debut du combo deja existant var sumTp = 0; for (var elm in combinaison) { sumTp += getCostItem(elm); } sumTp += getCostItem(item); if (sumTp <= totalTP) { push(result, arrayFlatten([item, combinaison])); } } } result = arrayConcat(combinaisons, result); return result; } } ///////////////// OUTILS //////////////////////////////// function getCostItem(elm) { if (typeOf(elm) == TYPE_ARRAY) { var cost = 0; for (var item in elm) { cost += getCostItem(item); } return cost; } else if (isChip(elm)) { return getChipCost(elm); } else { return getWeaponCost(elm); } } //----------------------------------------------------------------------------------------------- //Renvoit un tableau d'items triés par leur cout en TP //Prend un paramètre un tableau d'items' //array[0] est le moins couteux function sortElementsByCost(array) { array = arraySort(array, function(x, y) { if (getCostItem(x) > getCostItem(y)) { return 1; } else if (getCostItem(x) < getCostItem(y)) { return -1; } else { return 0; } }); return array; }
Mais j'ai deux soucis.
D'une, en partant du principe que le combo composé du plus grand nombre d'éléments sera celui qui sera compose de l'item le moins cher utilisé au maximum de fois. (Dans mon exemple, 5 fois la puce C).
Du coup, mon parametre taille qui correspond au nombre d'éléments de mon combo devrait avoir une valeur seuil au dela de laquelle, on a plus de combo qui ne depassent pas le nombre total de TP. (dans mon exemple, il n'y aura jamais un combo avec 6 é"léments puisque ca depasserait forcément le nombre de TP total).
Hors, ma fonction continue de générer des combos supplémentaires quand je passe au dessus de cette valeur seuil(j'ai pas comparé les combos un par un, juste comparer la taille du tableau) et je ne comprends pas pk.
Mon deuxième problème est que le jeu impose une limite de 20M d'opérations par tour . Or ici pour générer mes combos avec 9 armes/puces, une limite de 5 éléments et un total de 10 TP, j'utilise deja 4M d'opérations.
Hors en augmentant mon niveau de joueur, je vais passer de 2 a 4 armes et de 7 a 15 puces avec un total avoisinant les 20 TP. Autrement dit, je dépasserai surement les 100M d'opérations :/
Je suis à l'écoute de conseils pour améliorer cette fonction ou bien carément en refaire une nouvelle. N'oubliez pas que je suis novice en récursivité
Merci d'avoir lu
Partager