Les sources de la solution sont disponibles [ ici ].
Le sous-répertoire advanced contient les solutions pour les améliorations demandées en fin de TP. Ci-dessous se trouvent des commentaires sur les fonctionnalités demandées.
NB : afin de faciliter l'écriture du code et de le rendre plus lisible, une classe LifeGame a été créée qui regroupe tout le moteur du jeu.
Sur le tirage sans doublons
Il existe plusieurs façons de gérer le tirage aléatoire de n couples disjoints.
Celle qui est utilisée dans la solution proposée est :
- créer une ArrayList d'entier (par ex. nommé indexes), contenant les nombres de 0 à taille_population -1.
- Dans le boucle qui fait les n rencontres, il suffit ensuite de tirer aléatoirement 2 entiers idx1, idx2, et ensuite de prendre les humains stockés dans la population, se trouvant en indexes[idx1] et indexes[idx2]. Enfin, on supprime de indexes les cases idx1 et idx2 => pour les rencontres suivantes, on ne pourra plus jamais retomber sur les valeurs que ces cases contenaient.
Le "problème" de cette solution est qu'elle nécessite la création d'un tableau/liste annexe, qu'il faut remplir à chaque tour de jeu. Ce n'est donc pas optimal en terme de ressources mémoire.
Autre solution :
- on mélange les éléments de la population (cf. Collections.shuffle() )
- dans la boucle des n rencontres, à l'itération i, on prend les humains stockés dans la population aux indices 2*i et 2*i+1.
Le "problème" de cette solution est qu'elle nécessite d'échanger des éléments dans la population. Cela dit, vu que la population est gérée par une ArrayList, un échange consiste juste à modifier l'adresse mémoire contenue dans les cellules de la liste que l'on veut échanger : l'échange ne provoque pas de déplacement d'objet Homme/Femme en mémoire. Encore faut-il accéder à deux cellules de la liste et cela peut être coûteux selon le type de liste (même dans une ArrayList). D'après la description de shuffle(), il va y avoir taille_liste -1 échanges qui vont avoir lieu. Comparé à la solution précédente, on est donc pas certain que l'appel à shuffle() va être vraiment plus rapide que de remplir la liste indexes. En revanche, comme dans la première solution, on retire des éléments de indexes, alors que dans cette solution on ne fait aucune opération supplémentaire, on peut raisonnablement supposer que cette dernière est plus rapide.
Solution "mixte" (optimale ?) :
- créer un tableau indexes (pas une liste) de taille taille_population, et le remplir avec des nombres allant de 0 à taille_population-1
- mélanger le tableau indexes : vu que l'on travaille sur un "vrai" tableau, cela sera plus rapide que shuffle().
- dans la boucle des n rencontres, à l'itération i, on prend les humains stockés dans la population aux indices indexes[2*i] et indexes[2*i+1].
Quand bien même on crée et remplit un tableau annexe, on peut supposer que cette solution sera quand même plus rapide que la précédente, justement parce que l'on travaille avec un vrai tableau.
On peut même optimiser un peu plus et ne recréer le tableau que si la taille de la population a augmenté par rapport au tour de jeu précédent.
Sur le contrôle de la population
Pour gérer les modes 1 et 2 de contrôle de la population, la solution la plus simple consiste à déterminer à quels indices sont les hommes et les femmes dans la population pour ensuite faire une liste avec en alternance un homme puis une femme. C'est la méthode findCouple() qui permet cela (cf. classe LifeGame)
Pour le mode 2, la solution propose de refaire nbRencontre si le nombre de bébés voulu n'a pas été atteint. Pour cela, on remet l'itérateur j à 0 et on réinitialise popId. En revanche, cela casse la contrainte de ne pas utiliser 2 fois le même humain pour produire un bébé dans un même tour. De ce fait, chaque fois qu'il crée un bébé, il va grossir. Selon les paramètres d'exécution, on peut aboutir à une population obèse au bout de quelques tour de jeu. Pour éviter cela, un paramètre a été ajouté à rencontre() afin de ne pas augmenter le poids lorsque l'on refait nbRencontre dans le même tour de jeu.
Sur les accidents
Gérer les accidents représente la fonctionnalité la plus compliquée à écrire. En effet, dès lors qu'on touche à la population alors que l'on est en train de faire les rencontres, il y a des conséquences sur la façon dont sont déterminées ces rencontres. En l'occurrence, le tableau popId sert à stocker les indices des humains qui vont se rencontrer. Il va devenir "faux" dès lors qu'un humain est retiré. Pour le corriger, il suffit de modifier les valeurs se trouvant dans popId qui sont supérieur à l'indice de l'humain supprimé.
Par exemple, si popId contient : 0,1,2,4,3,7,5,8,6,10 et que l'on supprime l'humain à l'indice 5 dans la population. Alors, le 5 doit être supprimé de popId et toutes les valeurs supérieures à 5 doivent être décrémentée de 1 afin de retomber sur les bons indices des humains dans la population. On obtient donc : 0,1,2,3,4,6,7,5,9
Par ailleurs, lorsque le mode de contrôle est 1 ou 2, popId contient une alternance d'indices d'homme et de femme. Si un homme meurt d'un accident et que son indice se trouve dans popId, il faut alors enlever celui de la femme avec qui il était prévu de se rencontrer. Idem si une femme a un accident.
NB : avec les accidents, la population ne changera jamais de taille.