Soutenance 1 groupe 8

Objectif : Manipulation de fenètres

BOISSET Florian

Homme en fenètres qui se déplace

ROUBILLE Mathis

Goutte d'eau qui tombe

THOUMIN Maxime

Visage qui sourie et cligne de l'œil

Objectif : Manipulation de formes

BOISSET Florian

Carré soumis à la gravité

ROUBILLE Mathis

Jeu Snake

THOUMIN Maxime

Ouverture de rideaux au théatre

Objectif : Manipulation d'images

BOISSET Florian

Jeu du slime

ROUBILLE Mathis

Animation d'un slime

THOUMIN Maxime

Jeu d'un monstre

I. Création du graphe:

Génération des sommets:

- (Florian) Tirage du nombre de sommets aléatoire avec des bornes.
- (Mathis) Tirage d'angles aléatoire pour chaque sommet. Vérification que l'angle n'est pas trop proche d'un autre. (Version 1 "non en cercle" Florian)

Création du Graphe

- (Mathis) Fonction tab_to_graph : à la façon d'un "diviser pour reigner": découpe le tableau de sommets générés précédement et assigne les voisins.
- (Florian) Fonction make_new_links : Pour chaque couple de point, on ajoute une connexion avec une probabilité prédéfinie (10% en l'occurence).
- (Maxime, corrigé par Mathis) Affichage du graphe avec SDL.

II. Calcul des cycles non hamiltonnien:

(Mathis) Méthode des fourmis

L'algorithme des Fourmis utilise une fourmilière pour simuler le comportement des fourmis et des phéromones pour trouver le meilleur chemin pour le voyageur de commerce. Chaque jour, les fourmis de la fourmilière se déplacent sur toutes les zones et reviennent à la fourmilière. Les phéromones sont déposées sur les chemins que les fourmis parcourent, et elles sont prises en compte pour les fourmis du lendemain qui suivront les chemins avec le plus de phéromones. Les phéromones s'évaporent à la fin de chaque jour, ce qui signifie que les chemins les plus longs auront moins de phéromones. .

(Florian) Recuit Simulé

On prend une solution initiale, on la modifie aléatoirement. Soit elle est meilleure et on l'accepte, soit elle est moins bonne et on l'accepte avec une probabilité décroissante au long du processus.

(Florian) Recherche locale multistart

Pour chaque point, on applique l'algorithme suivant: on va sur le voisin le plus proche non encore visité. Si tout les voisins ont été visités, on cherche le plus proche au sens de Floyd-Warshall non déjà visité. On incrémente la taille du chemin à chaque changement de sommet. Finalement, on ajoute la distance de Floyd-Warshall reliant le dernier sommet au 1er pour simuler le retour. On garde la meilleure solution proposée par les différents point de départ.

III. Interraction Joueur:

Objectif:

Créer un petit jeu d'arcade basé sur les graphes précédements réalisés.
Une soucoupe volante dans l'espace doit se déplacer de planètes en planètes au milieu d'un champ d'astéroides. Des chemins se tracent ainsi devant elle. Elle devra visiter toutes les planètes le plus viite possible!

Florian:

- Génération du champ d'astéroïdes
       o choix de l'astéroïde aléatoire
       o choix du décalage aléatoire

- Génération des espaces libres (chemins)
       o l'astéroïde est-il sur un chemin?