Listes chaînées 2/2

5.7 Listes chaînées 2/2

Une liste chaînée permet d’implanter files et piles.
Implantation d’une file :
- ajout en queue de liste, suppression en tête de liste ;
- opérations enfiler, défiler, premier ;
- implantation efficace avec un pointeur de queue.
Implantation d’une pile :
- ajout en tête de liste, suppression en tête de liste ;
- opérations empiler, dépiler, sommet, taille ;
- implantation efficace (temps constant).
Exercice "jeu classique Centipede" :
- reprenez votre programme implanté avec des listes contigües ;
- implantez la file en utilisant des listes chaînées.
Exercice "jeu classique Invaders" :
- créez un répertoire Projets/Invaders ;
- créez deux sous-répertoires ListeChainee et Invaders ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique GraphiqueJeux.tgz ;
- implantez la bibliothèque de liste chaînée ;
- réalisez le programme principal :
  - créez des structures pour représenter monstres, bombes et missiles ;
  - les structures comprennent la position et l’état des objets ;
  - créez trois listes chainées pour les monstres, les bombes et les missiles ;
  - écrivez une fonction pour initialiser la liste monstres suivant le niveau ;
  - écrivez une fonction pour faire déplacer les monstres ...
  - ... cette fonction indique si un monstre est arrivé au sol ;
  - écrivez une fonction de lancement aléatoire de bombe ;
  - écrivez une fonction de gestion des bombes :
    - la fonction gère la trajectoire des bombes ;
    - les bombes sortant de l’écran sont supprimées de la liste ;
    - la fonction indique en retour si le canon a été touché.
  - écrivez une fonction de gestion des missiles :
    - la fonction gère la trajectoire des missiles ;
    - les missiles sortant de l’écran sont supprimées de la liste ;
    - la collision avec tous les monstres est testée ;
    - une collision entraine la suppression du missile et du monstre ;
    - la fonction indique en retour s’il ne reste plus aucun monstre.
  - écrivez la fonction principale :
    - le canon est déplacé suivant les touches pressées ;
    - le cas échéant un missile est ajouté dans la liste correspondante ;
    - appel de la fonction de déplacement des monstres ;
    - appels des fonctions de gestion des missiles et des bombes ;
    - si le canon est détruit par les monstres ou une bombe arrêter le jeu ;
    - s’il ne reste plus de monstre, il y a changement de niveau ;
    - la surface est intégralement re-dessinée à chaque itération.
Exercice "génération de labyrinthe" :
- créez un répertoire Projets/Labyrinthe ;
- créez deux sous-répertoires ListeChainee et Construire ;
- écrivez les trois fichiers de configuration makefile ;
- récupérez la bibliothèque graphique Graphique.tgz ;
- implantez la bibliothèque de liste chaînée ;
- réalisez le programme principal :
  - utilisez la bibliothèque fournie pour réaliser l’affichage ;
  - tracez le sol en blanc, laissez les murs en noir ;
  - utilisez l’algorithme aléatoire de Prim :
    - considère l’image découpée en pavés en 8x8 pixels ;
    - les pavés du bord de l’image sont des murs non destructibles ;
    - les pavés de coordonnées toutes deux paires sont des chemins ;
    - les autres pavés sont des murs destructibles ;
    - choisissez comme départ un pavé de type chemin en seconde colonne ;
    - ajoutez ce pavé dans la liste chaînée des chemins à traiter ;
    - tirez un chemin dans la liste chaînée au hasard (fonction rand) ;
    - détruisez un mur entre ce chemin et un autre chemin déjà traité ;
    - ajoutez à la liste des chemins, les chemins adjacents non encore visités ;
    - recommencez jusqu’à ce que la liste des chemins soit vide.
  - n’oubliez pas de sauvegarder votre labyrinthe pour la souris.
Exercice "génération de courbes 3D paramétriques en STL" :
- le programme prend un argument : le nom des fichiers résultats ;
- deux fichiers sont produits : un fichier STL ASCII .ast et un fichier STL binaire .stl ;
- les courbes 3D sont définies dans un tableau de structures dans le fichier courbes.c :
```
struct fonction_s {
  float (*x)(float);
  float (*y)(float);
  float (*z)(float);
  float t_min;
  float t_max;
  float t_pas;
  float taille;
  }
```
- les courbes sont pixélisées avec des cubes identiques d’arêtes parallèles aux axes ;
- les cubes des courbes sont accumulés dans une liste chaînée ;
- créez un répertoire pour votre projet, par exemple Courbes3D ;
- votre projet comporte des sous-répertoires :
  - Liste, contient la bibliothèque de gestion de liste chaînée ;
  - Geometrie, contient la bibliothèque des opérations 3D sur les cubes ;
  - STL, contient la bibliothèque de convertion des cubes en format STL ;
  - Courbes, contient l’exécutable utilisant les bibliothèques.
- écrivez les cinq fichiers de compilation automatique Makefile ;
- l’incrémentation du paramétre entre deux cubes peut se faire par dichotomie :
  - les valeurs minimale et maximum du paramètre sont précisés dans la structure de la fonction ;
  - le pas d’incrémentation de base est précisé dans la structure de la fonction ;
  - la distance entre deux cubes est définie comme le minimum des distances sur les trois axes ;
  - le pas réel est trouvé par dichotomie entre le pas de base et 0 avec la distance comme critère.
- Les courbes ne doivent pas comprendre de cubes en collision :
  - à chaque ajout de cube dans la liste, vérifier la collision avec tous les autres ;
  - retirer tous les cubes en collision, les mettre dans une liste de collision ;
  - scinder chaque cube dans la liste de collision en 8 sous-cubes ;
  - procéder avec les sous-cubes comme avec les nouveaux cubes ;
  - si la nouvelle liste de collision est non vide, scinder à nouveau les sous-cubes ;
  - ne pas scinder des sous-cubes en collision de taille trop faible : les détruire.
- Trouvez un ensemble de courbes paramétrique esthétique et imprimable par une imprimante 3D.