Comparaison d'algorithmes

SAÉ S1.02 - Snake autonome et analyse de performance des algorithmes

C Algorithmes Analyse de performances

Présentation du projet

Suite au développement du jeu Snake (SAÉ S1.01), ce projet avait pour objectif de rendre le serpent autonome en programmant ses mouvements pour qu'il mange les pommes de manière optimale. L'efficacité de différents algorithmes a été mesurée par le nombre de déplacements nécessaires et le temps CPU.


Ce projet s'inscrit dans le cadre de la compétence "Appréhender et construire des algorithmes" et plus spécifiquement l'apprentissage critique "Analyser un problème avec méthode".

Informations clés

  • Module : S1.02
  • Compétence : Appréhender et construire des algorithmes
  • Apprentissage critique : Analyser un problème avec méthode
  • Langage : C
  • Organisation : Travail en binôme
  • Durée : 4 semaines
  • Livrables : Programme C, Fichiers ODS, Documentation

Versions du projet

1
Version de base
2
Version améliorée
3
Version avec obstacles
4
Version optimisée
Serpent autonome en action

Description détaillée

Contrairement à la première SAÉ où le serpent était contrôlé manuellement, ce projet s'est concentré sur l'implémentation d'algorithmes permettant au serpent de se déplacer de manière autonome. L'objectif était d'optimiser ses mouvements pour qu'il mange toutes les pommes présentes dans le jeu en un minimum de déplacements.


Ce projet m'a permis d'explorer plusieurs concepts clés en algorithmique :

Recherche de chemins

Implémentation d'algorithmes pour déterminer le chemin optimal vers les pommes.

Mesure de performances

Évaluation et comparaison des algorithmes selon le nombre de déplacements et le temps CPU.

Optimisation

Amélioration itérative des algorithmes pour contourner les obstacles et réduire les déplacements inutiles.

Environnement déterministe

Gestion d'un environnement non aléatoire pour permettre des comparaisons objectives entre algorithmes.

Méthodologie

Le développement de ce projet a suivi une approche incrémentale avec quatre versions, chacune ajoutant de la complexité et nécessitant des améliorations algorithmiques :

Version 1: Algorithme basique

Implémentation d'un algorithme simple permettant au serpent de se diriger vers la pomme la plus proche dans un environnement sans obstacle. Cette version a servi de référence pour les comparaisons ultérieures.

Version 2: Plusieurs pommes

Amélioration de l'algorithme pour gérer efficacement plusieurs pommes présentes simultanément dans le jeu. L'algorithme devait déterminer l'ordre optimal pour manger les pommes.

Version 3: Gestion des obstacles

Introduction d'obstacles statiques dans l'environnement, nécessitant une adaptation de l'algorithme pour trouver des chemins alternatifs et éviter les collisions tout en maintenant une bonne performance.

Version 4: Optimisation globale

Développement d'un algorithme avancé combinant les techniques des versions précédentes avec des optimisations supplémentaires pour minimiser le nombre total de déplacements nécessaires pour manger toutes les pommes.

Compétences acquises

Ce projet m'a permis de développer et renforcer plusieurs compétences clés en informatique et en analyse d'algorithmes :

Algorithmique avancée

Conception et implémentation d'algorithmes de recherche de chemins comme A*, Dijkstra ou des algorithmes gloutons personnalisés.

Analyse comparative

Développement de méthodes rigoureuses pour comparer l'efficacité de différents algorithmes en termes de temps et d'espace.

Programmation efficace

Implémentation d'algorithmes optimisés pour limiter le temps de calcul et améliorer les performances globales.

Résolution de problèmes

Analyse méthodique de situations complexes et élaboration de solutions algorithmiques adaptées.

↑