cours17
Nous avons menti en vous disant que les objets et les tableaux sont des variables comme les autres. Enfin, nous n'avons pas dit toute la vérité. Cet « oubli » nous a permis de nous concentrer sur l'essentiel, mais maintenant il est temps d'expliquer tous les détails techniques. Contrairement aux variables de type primitif, les objets et les tableaux sont des références. Ils ne contiennent pas directement une valeur, mais l'adresse d'une zone de mémoire qui à son tour contient les valeurs. L'opérateur new alloue une zone de taille nécessaire pour stocker un objet ou un tableau et renvoie l'adresse de cette zone que nous plaçons dans une variable.
int x = 3;
int[] tab = new int[3];
tab[0] = 2; tab[1] = 5; tab[2] = 3;
Ball ball = new Ball(0, 0, 20);
Cela peut vous sembler un détail sans importance, mais si vous l'ignorez, vous pouvez avoir des mauvaises surprises.
Commençons par une manipulation simple de variables de type primitif :
int x;
int y;
x = 2;
y = x;
y++;
println(x, y);Sans surprise, x vaut 2 et y vaut 3.
Tentons maintenant une manipulation équivalente avec des tableaux.
int[] tx, ty;
tx = new int[3];
tx[0] = 1; tx[1] = 2; tx[2] = 3;
ty = tx;
for (int i = 0; i < ty.length; i++) {
ty[i]++;
}
println(tx);
println(ty);Sans surprise, les valeurs dans ty changent, mais aussi celles dans tx, ce qui pourrait nous paraître étrange au début. L'affectation ty = tx fait exactement ce qu'elle est censé faire : elle recopie dans ty le contenu de tx. Sauf que ce contenu n'est pas le tableau lui-même mais une référence (l'adresse du tableau). Ainsi il n'y a pas de nouveau tableau crée et les deux variables « pointent » vers le même tableau.
Si notre but est de recopier un tableau dans un autre, voici comment il faut s'y prendre :
ty = new int[tx.length];
for (int i = 0; i < tx.length; i++) {
ty[i] = tx[i];
}Maintenant nous avons deux tableaux différents qui contiennent les mêmes valeurs. Si on modifie l'un des deux
for (int i = 0; i < ty.length; i++) {
ty[i]++;
}l'autre ne change pas.
La même chose se passe avec les objets :
Ball b1, b2;
void setup() {
size(200, 200);
b1 = new Ball(0, 100);
b2 = b1;
}
void draw() {
background(255);
b2.bouger();
b1.dessiner();
b2.dessiner();
}
class Ball {
int x, y;
Ball(int x, int y) {
this.x = x;
this.y = y;
}
void bouger() {
x = (x + 1) % width;
}
void dessiner() {
ellipse(x, y, 20, 20);
}
}On peut s'attendre de voir 2 balles, une immobile et une qui bouge, mais en réalité les deux variables pointent vers le même objet qu'on bouge une fois et on dessine deux fois dans draw().
Exercice 17.1 Prédisez le résultat de l'exécution de chaque morceau de code. Testez votre prédiction et expliquez le résultat.
Rappel : Les arguments d'une fonction sont des variables locales qu'on initialise avec les paramètres passées dans l'appel.
void modifInt(int arg) {
arg++;
}
void setup() {
int x = 10;
modifInt(x);
println(x);
}void modifTab(int[] arg) {
for (int i = 0; i < arg.length; i++) {
arg[i]++;
}
}
void setup() {
int[] tab = {1, 2, 3};
modifTab(tab);
println(tab);
}void modifObj(Ball arg) {
arg.bouger();
}
void setup() {
Ball b = new Ball(0, 50);
b.dessiner();
for (int i = 0; i < 50; i++) {
modifObj(b);
}
b.dessiner();
}void modifTab(int[] arg) {
arg = new int[3];
for (int i = 0; i < 3; i++) {
arg[i] = 1;
}
}
void setup() {
int[] tab = {1, 2, 3};
modifTab(tab);
println(tab);
}Exercice 17.2 Dessinez un schéma (avec papier et crayon) permettant de visualiser un tableau d'objets dans la mémoire.
Ball[] balls = new Ball[3];
for (int i = 0; i < 3; i++) {
balls[i] = new Ball(10 * i, 10 * i);
}
Source xkcd
Nous avons encore menti. Enfin, en quelque sorte. Il est définitivement vrai que lorsqu'un tableau est créé, sa taille ne peut plus varier. Nous avons indiqué à Processing combien nous avions besoin de mémoire, et il a alloué cette taille précisément. Cependant, rien ne nous empêche, si on a besoin de plus de place par exemple, de recréer un autre tableau, de copier l'ancien dedans, et d'utiliser les nouvelles cases pour y stocker plus de valeurs.
int[] scores = new int[2];
...
// un nouveau joueur arrive
int n = scores.length;
int[] nouveauxScores = new int[n + 1];
for (int i = 0; i < n; i++) {
nouveauxScores[i] = scores[i];
}
nouveauxScores[n] = 0;
scores = nouveauxScores;Avec nos nouvelles connaissances sur les références, il n'est pas difficile de comprendre ce qu'il se passe. La dernière ligne est la plus importante. C'est elle qui nous permet de continuer à utiliser la même variable pour stocker les scores.
Processing nous offre de nombreuses fonctions permettant de manipuler les tableaux et leur taille : shorten() (raccourcir), concat() (joindre deux tableaux), append() (ajouter à un tableau), splice() (découper des tableaux), expand() (agrandir). Ces fonctions nous évitent d'écrire plusieurs lignes de code à chaque fois qu'on veut faire ce genre de manipulation. Par exemple le code ci-dessus peut être remplacé par :
scores = append(scores, 0);Utilisez ces fonctions, mais n'oubliez pas que derrière chaque appel se cache une ré-allocation et copie des éléments, opérations qui peuvent coûter cher sur des tableaux de grande taille.
Il existe aussi des fonctions pour changer l'ordre des éléments stockés dans les tableaux : sort() pour réaliser des tris et reverse() pour inverser l'ordre par exemple. Nous vous laissons regarder les détails de ces opérations dans la documentation.
Ici nous allons voir un exemple simple d'utilisation de append() pour agrandir un tableau. Cet exemple commence avec un tableau d'un unique objet. Chaque fois que la souris est pressée, un nouvel objet est créé et ajouté à la fin du tableau.
Exemple 17.1 Redimensionner un tableau avec append().
Balle[] balles = new Balle[1];
void setup() {
size(200, 200);
frameRate(30);
balles[0] = new Balle(50, 0, 10);
}
void draw() {
background(100);
for (int i = 0; i < balles.length; i++) {
balles[i].bouger();
balles[i].dessiner();
}
}
void mousePressed() {
Balle b = new Balle(mouseX, mouseY, 10);
balles = (Balle[]) append(balles, b);
// Voici la fonction append() qui ajoute un élément (ici b) à la fin d'un tableau donné
// (ici balles). Il faut faire très attention à remplacer l'ancien tableau (qui n'a pas
// changé de taille) par le nouveau créé par append() et renvoyé en résultat, ce qui
// explique le signe = utilisé. De plus si les éléments du tableau sont des objets,
// il faut re-préciser le type du tableau avec une projection (plus souvent appelée "cast"),
// en plaçant ce type entre parenthèses après le signe =.
}float gravite = 0.1;
class Balle {
float x;
float y;
float v;
float w;
Balle(float x, float y, float w) {
this.x = x;
this.y = y;
this.w = w;
v = 0;
}
void bouger() {
// Ajoute la gravite à la vitesse.
v += gravite;
// Ajouter la vitesse à la position
y += v;
if (y > height) {
v = v * -0.95;
y = height;
}
}
void dessiner() {
fill(255);
noStroke();
ellipse(x, y, w, w);
}
}Un autre moyen d'avoir un tableau « redimensionnable » consiste à utiliser une classe spéciale nommée ArrayList qui fait partie de la bibliothèque standard de Java. Elle « cache » à l'intérieur un tableau et s'occupe à le redimensionner quand c'est nécessaire. Ainsi on peut aisément ajouter ou retirer des éléments n'importe où dans la liste. On déclare et initialise une liste ainsi :
ArrayList<Voiture> voitures = new ArrayList();ArrayList est ce qu'on appelle un type générique. Le type entre < et > est celui des objets stockés dans la liste. Si on veut une liste de balles, on utilisera ArrayList<Balle> bien sûr. Petite particularité, on ne peut pas stocker des valeurs des types primitifs dans une ArrayList. Par exemple, ArrayList<int> ne marche pas. Pour stocker des nombres, on peut utiliser les classes IntList et FloatList de Processing qui ont un fonctionnement similaire.
Pour ajouter un élément à la fin de la liste, on utilise la méthode add :
Voiture v = new Voiture();
voitures.add(v);ou simplement
voitures.add(new Voiture());La méthode size() nous donne la taille (le nombre d'éléments) d'une liste. Pour accéder à un élément à une position donnée, on utilise la méthode get(). Comme pour les tableaux, les positions vont de 0 à size() - 1. Ainsi, pour parcourir tous les éléments d'une liste, on peut utiliser la boucle suivante :
for (int i = 0; i < voitures.size(); i++) {
Voiture v = voitures.get(i);
v.bouger();
v.dessiner();
}Pour retirer des éléments, on utilise la méthode remove(). Par exemple, pour retirer le premier et le dernier élément d'une liste, on peut faire :
if (!voitures.isEmpty()) {
voitures.remove(0);
}
if (!voitures.isEmpty()) {
voitures.remove(voitures.size() - 1);
}La classe ArrayList possède beaucoup d'autres méthodes utiles. La documentation complète se trouve ici.
Exercice 17.3 Refaites l'exemple 17.1 en utilisant une ArrayList à la place du tableau.
Nous nous sommes déjà habitués de parcourir les tableaux (et maintenant les listes) avec une boucle for qui fait varier un indice :
int[] nombres = {1, 2, 3, 4, 5};
int somme = 0;
for (int i = 0; i < nombres.length; i++) {
somme += nombres[i];
}La boucle for existe sous une autre forme permettant d'écrire la même chose de façon plus concise et élégante :
for (int x : nombres) {
somme += x;
}On lit « pour chaque x appartenant à nombres, ajouter x à somme ». Cette boucle fait nombres.length itérations. À chaque itération x prend la valeur d'un élément du tableau. Attention, x est juste une variable locale qui est initialisée avec la valeur d'une cellule du tableau au début de chaque itération. Si vous la modifiez, cela n'a aucun effet sur le tableau. Par exemple, si vous voulez mettre à zéro tous les éléments du tableau, la boucle
for (int x : nombres) {
x = 0;
}ne fera pas l'affaire. Pour faire cela, il faut utiliser la bonne vieille boucle for avec indice.
La boucle for-each marche également avec des tableaux d'objets, par exemple :
for (Voiture v : voitures) {
v.bouger();
v.dessiner();
}De la même façon que pour les types primitifs, à chaque itération v est une copie d'une cellule du tableau, c'est-à-dire une référence vers le même objet. N'essayez donc pas d'initialiser votre tableau avec quelque chose comme
for (Voiture v : voitures) {
v = new Voiture();
}Cela ne marche pas !
On peut utiliser la même boucle for-each pour parcourir des listes. L'exemple suivant illustre cela.
Exemple 17.2 Collier de perles rouges et bleues.
class Perle {
color couleur;
Perle() {
if (random(1) < 0.5) {
couleur = color(255, 0, 0);
} else {
couleur = color(0, 0, 255);
}
}
color getCouleur() {
return couleur;
}
}ArrayList<Perle> collier = new ArrayList();
void setup() {
size(800, 200);
for (int i = 0; i < 50; i++) {
collier.add(new Perle());
}
}
void draw() {
background(255);
float taille = float(width) / collier.size();
float x = taille / 2;
noStroke();
for (Perle perle : collier) {
fill(perle.getCouleur());
circle(x, height / 2, taille);
x += taille;
}
}Quand vous utilisez une boucle for-each pour parcourir une liste, vous ne devez ni ajouter ni retirer des éléments à l'intérieur de la boucle. Pour illustrer cela, supposons que nous voulons supprimer toutes les perles rouges de notre collier lorsque l'utilisateur clique avec la souris. Faisons une première tentative :
void mousePressed() {
for (Perle perle : collier) {
if (perle.getCouleur() == color(255, 0, 0)) {
collier.remove(perle);
}
}
}En exécutant, on constate que le programme plante avec une ConcurrentModificationException. Peut-être qu'une bonne vieille boucle for classique fera l'affaire ?
void mousePressed() {
for (int i = 0; i < collier.size(); i++) {
if (collier.get(i).getCouleur() == color(255, 0, 0)) {
collier.remove(i);
}
}
}Maintenant on supprime certaines mais pas toutes les perles rouges. Avant de continuer à lire, essayez d'expliquer pourquoi.
En effet, supposons que les perles i et i + 1 sont toutes les deux rouges. En supprimant la perle i, les perles suivantes sont décalées à gauche. Ainsi la perle i + 1 prend la position i et elle ne sera pas supprimée. Il ne faut donc pas que notre i avance si on supprime la perle :
void mousePressed() {
int i = 0;
while (i < collier.size()) {
if (collier.get(i).getCouleur() == color(255, 0, 0)) {
collier.remove(i);
} else {
i++;
}
}
}Une autre façon de ne pas sauter des perles rouges est de faire le parcours de droite à gauche :
void mousePressed() {
for (int i = collier.size() - 1; i >= 0; i--) {
if (collier.get(i).getCouleur() == color(255, 0, 0)) {
collier.remove(i);
}
}
}Nous ne pouvons pas résister à la tentation de vous montrer une dernière façon de supprimer les perles rouges sans même utiliser une boucle explicitement :
void mousePressed() {
collier.removeIf(p -> p.getCouleur() == color(255, 0, 0));
}Nous nous passerons d'explications car la technique de programmation fonctionnelle utilisée ici est au-delà de la portée de ce cours.
Exercice 17.4 Utilisez la classe suivante :
class Cercle {
float x, y, rayon;
color couleur;
Cercle(float x, float y, float rayon, color couleur) {
this.x = x;
this.y = y;
this.rayon = rayon;
this.couleur = couleur;
}
Cercle (float x, float y) {
this(x, y, random(10, 50), color(random(255), random(255), random(255)));
}
void dessiner() {
noStroke();
fill(couleur);
ellipseMode(RADIUS);
circle(x, y, rayon);
}
boolean estDedans(float mx, float my) {
return dist(x, y, mx, my) < rayon;
}
}Stockez des cercles dans une liste initialement vide et dessinez-les. Lorsque l'utilisateur clique avec le bouton gauche de la souris, un nouveau cercle apparaît. S'il clique sur un cercle existant avec le bouton droit, il disparaît.
void mousePressed() {
if (mouseButton == LEFT) {
// TODO: ajouter un cercle à la position de la souris
} else if (mouseButton == RIGHT) {
// TODO: supprimer les cercles sur lesquels on a cliqué
}
}Exercice 17.5 Reprenez la classe Snake de l'exemple 16.4. Remplacez les deux tableaux xpos et ypos par une ArrayList<Cercle>. Ajoutez des méthodes qui permettent à la créature de s'allonger ou de se raccourcir. Faites-la manger quelque chose et changez sa taille en fonction de sa satiété.
Un automate cellulaire est fait d'un ensemble de cellules ayant un ensemble fini d'états et d'un ensemble fini de règles d'évolution sur ces cellules en fonction de leur état de celui des cellules voisines.
Les cellules sont en général organisées en grille en une, deux, trois dimensions, mais d'autres types de pavage ou d'organisation existent. Nous allons nous intéresser à la version la plus simple en une dimension où la grille n'est qu'un tableau linéaire de cellules. Chaque cellule aura donc deux voisines (mais des versions plus avancées peuvent regarder le voisinage à plus d'une cellule de distance). De plus nous allons nous restreindre à deux états, allumé ou éteint. Notre représentation sera donc un tableau d'entiers dont les valeurs seront soit 0 (éteint) soit 1 (nous aurions pu utiliser des booléens, mais pour des raisons pratiques, et pour l'évolution future du code, les entiers seront plus pratiques).
L'automate évolue dans le temps : à chaque étape on regarde l'état de chaque cellule et de son voisinage, et on applique les règles d'évolution. Par exemple une règle pourrait être "quand une cellule éteinte est entourée de deux cellules allumée, elle s'allume".
Si on part d'un tableau de cellules éteintes avec une seule cellule allumée au centre, et qu'on dessine l'évolution du tableau en lignes successives, on peut obtenir ce genre de motif (chaque ligne représente une étape de temps) :
Ou encore :
Ce genre de motif se retrouve dans la nature et peuvent donc être simulés par les automates cellulaires 1D :
Pour définir les règles d'évolution, on peut noter l'état d'une cellule et de ses deux voisines, ainsi que l'état que devrait prendre la cellule en fonction :
| 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
Notre règle d'évolution serait ici 10100000 comme le montre la seconde ligne de la table, et les valeurs de la
première ligne indiquent les voisinages. Ainsi la valeur 101 par exemple correspondrait à l'état d'une cellule
éteinte et deux voisines allumées. La règle dirait alors de d'allumer la cellule au temps t+1 car il y a un 1 dans
la colonne 101 de la table.
On peut noter ques les valeurs de cette table correspondent à des chiffres en binaire. Ceux de la première ligne sont
les chiffres de 0 à 7. Ceux de la seconde ligne forment un nombre binaire sur 8 bits, dans cet exemple 10100000 en
binaire vaut 160 en décimal.
Ainsi, si on a le voisinage 101, soit 5 en décimal, on va chercher le bit 5 du nombre 160 qui est à 1 donc on
allume la cellule à l'étape t+1. De ce fait nos règles d'évolutions peuvent être définies avec des nombre entre 0 et
255 puisqu'on a 8 bits.
La question qui se pose désormais est comment travailler en binaire avec Java ?
L'opérateur << permet de faire un décalage de bits. 1 << 2 va décaler tous les bits de la valeur 1 de deux rangs
vers la gauche. Ainsi, la 1 en décimal s'écrit aussi 001 en binaire, mais 1 << 2 vaudra 100 en binaire, soit 4
en décimal.
L'opérateur | permet de faire un ou bit à bit sur deux opérandes. L'opération ou est appliquée sur chaque bit
pour produire le résultat. Par exemple 0110 | 0101 vaudra 0111, en d'autres termes dès qu'il y a un 1 dans l'un ou
l'autre des opérandes, le résultat contient un 1 :
| résultat | 0 | 1 | 1 | 1 |
|---|---|---|---|---|
| opérande 1 | 0 | 1 | 1 | 0 |
| opérande 2 | 0 | 1 | 0 | 1 |
De la même façon, l'opérateur & permet de faire le et bit à bit, il faut qu'il y ait un 1 dans les deux opérandes
pour que le résultat contienne un 1 :
| résultat | 0 | 1 | 0 | 0 |
|---|---|---|---|---|
| opérande 1 | 0 | 1 | 1 | 0 |
| opérande 2 | 0 | 1 | 0 | 1 |
Ainsi, si nous avons un tableau de cellules t ne contenant que des 0 ou des 1, et que nous considérons la cellule i
l'opération (si i-1 et i+1 sont des cellules valides) :
int bit = (t[i-1] << 2) | (t[i] << 1) | (t[i+1]);Produira dans bit une valeur entre 0 et 7. t[i-1] est la cellule voisine de gauche, t[i+1] celle de droite. Si
t[i-1] vaut 1, alors t[i-1]<<2 vaudra en binaire 100. Si t[i] vaut 1, alors t[i] << 1 vaudra en binaire 010
et si t[i+1] vaut 1, alors en binaire il vaudra 001. L'opération 100 | 010 vaut 110 et l'opération 110 | 001
vaut 111 en binaire.
Nous avons désormais le numéro du bit dans la règle, mais comment savoir si il vaut 0 ou 1 ? On peut utiliser une fois
de plus le décalage, mais dans l'autre sens. L'opérateur >> réalise le décalage de bits vers la droite. Ainsi si bit
vaut 5, et que regle contient la règle en binaire, par exemple 10100001, alors regle >> bit donnera en binaire
00000101 (5 bits à droite disparaissent, 5 bits à gauche apparaissent et valent automatiquement 0). Le cinquième bit
est désormais le premier.
Comment isoler ce bit pour l'obtenir ? On peut utiliser le et binaire : (regle >> bit) & 1. Dans notre exemple,
cela reviendrait à faire :
| résultat | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|
| opérande 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| opérande 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Le code complet pour obtenir la valeur d'évolution d'une cellule connaissant son voisinage et la règle d'évolution serait donc :
int bit = (t[i-1] << 2) | (t[i] << 1) | (t[i+1]);
int resulat = (regle >> bit) & 1;Nous pouvons représenter l'état de l'automate avec un tableau à une dimension, mais nous ne pouvons pas calculer l'état
suivant "sur place" dans ce tableau. En effet, chaque cellule à besoin de la valeur des ses deux voisines et au moins
l'un des voisins serait "écrasé" durant l'opération. Il nous faudra donc deux tableaux : l'un avec l'état courant au
temps t et l'autre avec le résultat pour l'état suivant au temps t+1. Nous pourrons ensuite "échanger" les
références de ces deux tableaux pour continuer.
De plus la première cellule et la dernière n'ont pas de voisines à gauche ou respectivement à droite. Il serait intéressant d'avoir ce que l'on appelle des conditions périodiques c'est à dire que la voisine de la dernière cellule est la première et inversement. En d'autres termes, notre tableau pourrait apparaître comme faisant une boucle sur lui même. Pour cela, nous pouvons utiliser notre ami modulo. Par exemple la fonction :
int cellule(int[] etat, int i) {
return etat[(i + etat.length) % etat.length];
}Retourne toujours des valeurs de cellules existantes. Si i vaut -1 elle renverra la cellule etat.length-1, et si
i vaut etat.length, elle renverra 0.
Exercice 17.6 Mettez en oeuvre les techniques vues ci-dessus pour, étant donné une règle sous la forme d'un entier entre 0 et 255, réaliser son développement en automate cellulaire 1D. Vous pouvez par exemple tester la règle 86 :
