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:

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;
}
La fonction me génère un beau tableau avec pas mal de combos.

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