fr:cs:rapport_de_projet_d_algorithmique [Piment Noir Wiki]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.
====== Rapport du projet d'algorithmique : Jeu Othello ======

===== Analyse des problématiques algorithmiques du jeu ===== 

==== Classification de l'analyse ====
  * Descendante ou "top-down";
  * Diviser pour mieux régner : 
Découpage des problématiques algorithmiques en sous-problèmes dit simples autant au niveau complexité (on parle de la notation "big O" ici) que difficulté d'implantation. Une approche fonctionnelle a été choisie pour l'effectuer. 

==== Résultante de l'analyse ====

Cela a conduit à l'élaboration d'une liste de fonctionnalités à implanter et d'un planning de leurs implantations. 	

===== Les directives architecturales =====

==== Pas de "tripotage" direct des structures de données (c'est indécent :p) ====

    * Implantation de fonctions outils : get_*, set_*, print_*, print_all_*, dbg_mvprintw, etc. 
    * Indépendance de l'implantation par rapport aux définitions des structures;
    * Séparation claire entre le modèle de données et leurs présentations (architecture proche du MVC).  
==== "Small is beautiful" : ====

  * Création de modules de compilation par fonctionnalités : User Interface aka UI (entrées/sorties du terminal, affichage de l'othellier, affichage des pions, etc.), liste chaînée, AI, etc.
  * N'exporter que les fonctions strictement nécessaires;
  * Définitions et déclarations de fonctions simples et compactes pour couvrir une fonctionnalité. Faire une et une chose, et le faire **bien**;
  * Création d'une librairie partagée et statique des fonctions et des structures de données du jeu; 
  * Pas de sur-ingénierie : couvrir les fonctionnalités demandées sans penser à une hypothétique future fonctionnalité qui tue la mort.   

==== Ne pas réinventer la roue : ====
 
  * Utilisation de bibliothèques pour gérer l'affichage dans un terminal: [[https://www.gnu.org/software/ncurses/|ncurses]];
  * Réutilisation de code disponible en ligne couvrant une fonctionnalité de base demandée mieux que je ne l'implanterai : [[https://isis.poly.edu/kulesh/stuff/src/klist/|liste chaînée du noyau Linux]] portée en espace utilisateur, etc.
  * Réutilisation du système de construction (à base de Makefile) déjà implanté lors d'autres cours et amélioré (50% Gabriel / 50% modifications personnelles).

==== Style du code de l’implantation : ====

Calqué sur le style de Kernighan and Ritchie aka K&R avec de légères modifications sur le placement des parenthèses pour les déclarations de fonctions.\\
[[https://www.gnu.org/software/indent/|indent]] est votre ami.

===== Fonctionnalités implantées : =====

  * Affichage de l'othellier et des pions;
  * Saisie d'un coup;
  * Détection des conditions de fin de jeu : othellier plein ou plus de coups jouables pour un des deux joueurs;
  * Boucle de jeu complète;
  * Retournement des pions après un coup; 
  * Jeu pour deux joueurs humains. 

===== Fonctionnalités à implanter : =====
 
  - Listes des coups jouables;
  - Redéfinir plus proprement certains types de donnés;
  - Implantation de la fonctionnalité de retour en arrière dans la liste des coups joués;
  - IA (AI en anglais) MiniMax;
  - Graphical User Interface aka GUI avec [[https://www.libsdl.org|SDL]].

===== Problèmes rencontrés : =====

  * Gestion du tableau à deux dimensions : retour de fonctions conjointement avec passage par adresse, donc des chevauchements mémoires et autres bizarreries (le même objet était retourné deux fois par les fonctions ...)

  * Fonction d'exploration depuis un coup d'origine pour établir :
    * la liste des pions à retourner;
    * la liste des coups jouables pour un joueur.   
Problèmes avec l'implantation récursive de l'algorithme,\\
Remplacement par implantation d'une version itérative de l’algorithme. 

Au total, "perte" de temps proche de 3 cours de 3h.