MiniProjC2009

I Want Out !

Doctor Stein grows funny creatures and let them run into the night ! ...

Le docteur Stein élève des droles de créatures dont l'objectif est d'explorer des donjons. Il a décidé de se limiter aux donjons de la guilde des explorateurs amateurs pour lesquels une carte est fournie. Mais la carte n'est pas toujours suffisante, il faut que le docteur fournisse un chemin à suivre à ses créatures !

Votre objectif est de fournir au Docteur Stein un chemin sûr (c'est à dire un chemin où il ne perd pas la vie) dans le donjon entre deux salles particulières du donjon. L'idéal étant que ce chemin soit le plus court.

Présentation des donjons

Les donjons de la guilde des explorateurs amateurs ont une forme commune: il dispose de certains types de salles (voir plus loin) reliées entre elles par des couloirs. La traversée d'un couloir est plus ou moins difficile et la difficulté est indiquée sur la carte. La difficulté d'un couloir peut dépendre du sens de parcours, il est même possible que certains couloirs ne puissent être franchis que dans un sens. Chaque salle porte un numéro unique dans le donjon qui permet de les identifier facilement. Les différents types de salles sont les suivants:

• Salle ordinaire
• Tannière de monstre: un monstre se cache dans ces salles, la carte indique le coût du combat contre le monstre.
• Piège mortelle: ces salles sont des culs-de-sac dont il est impossible de repartir (entrainnant la mort de l'explorateur s'il a le malheur de s'y rendre.)
• Gargotte: les gargottes des donjons sont tenues par les gnomes de la guilde et permettent aux explorateurs de retrouver des forces pendant leur exploration. Chaque gargotte propose un menu unique (toujours disponible) dont l'effet revigorant est indiqué sur la carte.

Le niveau de vie de l'explorateur

Chaque explorateur de donjons dispose d'un certain niveau de vie au début de sa quête. L'unité de mesure des niveaux de vie a été unifiée avec les niveaux de difficultés des couloirs, le niveau des monstres et l'apport des repas des gargottes. Par conséquent, il est très simple de calculer le coût d'un chemin d'une salle à une autre dans le donjon et de le comparer au niveau de vie de l'explorateur.

L'explorateur meurt lorsque son niveau de vie tombe à 0.

Le mini-projet

Comme vous l'aurez compris il s'agit ici de trouver des chemins dans un graphe. Le projet se découpe en trois phases (plus une spéciale):

1. Lecture du graphe à partir du fichier de description (4 points);
2. Évaluation du coût d'un chemin dans le graphe (4 points);
3. Recherche d'un chemin valide dans le graphe (10 points).

En outre, deux points seront accordés au respect des règles de rendu (rendu dans les temps et au format attendu.)

Format du fichier de description du donjon

Le format de description est un format texte relativement simple:

• Les salles sont numérotées de manière continue à partir de 1
• Les lignes commençant par le caractère "#" sont des commentaires et doivent être ignorées
• Les lignes vides doivent être ignorées
• La première ligne ayant du sens (ni vide, ni commentaire) doit avoir la forme "ROOMS: n" où n est un entier strictement positif représentant le nombre de salle du donjon.
• Les lignes suivantes indiquent quelles types de salles sont disponibles. Elles ont la forme suivante:
  • "MONSTER: s c" indique que la salle s contient un monstre de niveau c.
  • "DEAD: s" indique que la salle s est un piège mortelle.
  • "BREWERY: s c" indique que la salle s est une gargotte qui sert un menu de niveau c
  • Les salles qui n'apparaissent pas dans l'une des catégories sont des salles ordinaires.
• Une fois que toutes les salles sont décrites, on peut lister les couloirs. La partie couloirs est introduites par la ligne "ARCS"
• Chaque couloir est décrit par une ligne de la forme: "ARC: s1 c s2" indiquant l'existance d'un couloir de la salle s1 jusqu'à s2 avec pour coût c.

Un donjon

Voici un exemple de description de donjon:

# Salles
ROOMS: 10
MONSTER: 4 4
MONSTER: 9 20
BREWERY: 7 5
DEAD: 3

# couloirs
ARCS
ARC: 1 1 2
ARC: 1 1 3
ARC: 2 1 4
ARC: 2 1 5
ARC: 3 30 6
ARC: 4 1 5
ARC: 5 6 2
ARC: 5 1 6
ARC: 6 1 7
ARC: 7 1 8
ARC: 8 1 6
ARC: 8 1 9
ARC: 9 1 10

Remarque: la guilde garantie des cartes bien formées, vous n'aurez donc pas à gérer les erreurs de parsing.

Format des chemins

Les chemins seront représenté par le format suivant: [s1;...;sn] (sans espace) où les si sont les numéros des salles traversées par le chemin dans l'ordre (bien sûr.)

Affichage du coût d'un chemin

Lorsque l'utilisateur rentre la commande COST v [s1;..;sn], vous devez calculer le coût du chemin avec v points de vie au départ. L'affichage se fera de la manière suivante:

• c si le nombre de points de vie était suffisant, c est le nombre points de vie restant à la fin du chemin.
• DEAD si le nombre de point de vie n'était pas suffisant, où si le chemin contient un piège mortel.
• NP si le chemin n'est pas valide (salle inexistante, pas de couloir permettant le parcours ... )

Recherche de chemin

La commande PATH v s e demande à votre programme de chercher un chemin entre la salle s et la salle e avec v point de vie au départ. Votre programme devra alors soit afficher le chemin, soit afficher NP s'il n'existe pas de chemin possible (pas de couloir, pas assez de point de vie ... )

Votre programme

Votre programme devra s'appeler stein et prendra en paramètre le nom du fichier de description du donjon. Une fois le donjon lu, il devra attendre une commande sur son entrée standard:

• COST [s1;...;sn] lui demandera de calculer le coût du chemin.
• PATH c s e lui demandera la recherche d'un plus court chemin.

Après l'exécution de la commande, votre programme affiche le résultat (en fonction de la commande) et attend une nouvelle entrée. Le programme devra quitter à la réception du caractère de fin de fichier (que l'on peut envoyer depuis le shell en faisant ^D.)

Comme d'habitude, vous devez respecter les formats d'affichage pour que la moulinette reconnaisse votre résultat (attention aux espaces et aux majuscules/minuscules.)

Exemple de session de tests

On considère le graphe décrit précédemment sauvé dans le fichier graphe.dj. On regroupera les tests dans le fichier test-graphe dont le contenu est le suivant:

COST 10 [1;2;5;6;7;8;9;10]
COST 10 [1;2;5;6;7;8;6;7;8;6;7;8;6;7;8;6;7;8;6;7;8;6;7;8;6;7;8;9;10]
COST 10 [1;3;6;7;8;9;10]
COST 10 [1;2;6;8;9;10]
PATH 10 1 4

Enfin, le test du programme donnera les résultats suivants:

> ./stein graphe.dj < test-graphe
DEAD
2
DEAD
NP
[1;2;4]
>

Votre rendu

Vous rendrez une archive sous la forme: login-miniprojc.tar.bz2 cette archive doit se décompresser dans un répertoire dont le nom est login-miniprojc contenant:

• Un fichier AUTHORS au format déjà spécifier dans le TP d'OCaml.
• Un makefile qui accepte les cibles all, stein et clean
• Votre code source.

Pour information la moulinette procedera comme suit:

tar xf login-miniprojc.tar.bz2
cd login-miniprojc
make clean
make

Puis effectuera les tests sur le binaire stein.

Conseils

Cette partie présente quelques conseils d'implantation (files, graphes, algorithmes ... ) mais ce ne sont que des conseils que vous êtes libre de suivre ou pas.

Des files en C

Voici une implantation des files d'entier en C qui pourraient vous servir pour certains algorithmes.

Fichier queue.h

/* simple fifo queue */
 
#ifndef _QUEUE_H
#define _QUEUE_H
 
typedef struct s_queue *t_queue;
 
struct s_queue
{
  int		cont;
  t_queue	next, prev;
};
 
#define qempty() NULL
#define qis_empty(q) !(q)
 
int   qtake(t_queue *q);
t_queue qput(int x, t_queue q);
 
#endif

Fichier queue.c

/* simple fifo queue */
 
#include <stdlib.h>
#include <unistd.h>
#include "queue.h"
 
int qtake(t_queue *pq)
{
  int		x;
  t_queue	q;
  q = *pq;
  x = q->prev->cont;
  if (q==q->prev)
    {
      free(q);
      q = NULL;
    }
  else
    {
      q = q->prev;
      (*pq)->prev = q->prev;
      (*pq)->prev->next = *pq;
      free(q);
      q = *pq;
    }
  *pq = q;
  return x;
}
 
t_queue qput(int x, t_queue q)
{
  t_queue tmp;
  tmp = malloc(sizeof(struct s_queue));
  tmp->cont = x;
  if (q)
    {
      tmp->next = q;
      tmp->prev = q->prev;
      tmp->prev->next = tmp;
      q->prev = tmp;
    }
  else
    tmp->prev = tmp->next = tmp;
  return tmp;
}

Représentation des graphes

Il existe plusieurs façon de représenter les graphes, notamment les versions vues en TD d'algo. Je vous propose ici une version plus compacte et plus pratique basée sur la version full-dynamique du TD mais utilisant des tableaux pour la liste de sommet.

typedef struct s_graph *t_graph;
typedef struct s_som   *t_som;
typedef struct s_adj   *t_adj;
 
struct s_som
{
  int	som;
  t_adj	succ, pred;
};
 
struct s_adj
{
  float	cost;
  int	vsom;
  t_adj	next;
};
 
struct s_graph
{
  int		order;
  t_som		lsom[1];
};

Le graphe est composé d'un tableau de pointeur de sommet (dont la taille est donné par le champ order) et chaque sommet contient deux listes d'adjacence (listes d'arcs) pour les successeurs et les prédecesseurs. Les éléments des listes d'adjacence indique le coût (avec un float) et le numéro du sommet (sa case dans le tableau.)

Voici quelques fonctions/macros utiles:

#define GSIZE(o) (sizeof(int) + sizeof(t_som)*(o))
#define room(g,s) (g->lsom[(s)])
#define succ(g,s) (room(g,s)->succ)
#define pred(g,s) (room(g,s)->pred)
#define next(p) ((p)=(p)->next)
 
t_graph create_graph(int order)
{
  t_graph	g;
  int		i;
  g = malloc(GSIZE(order));
  g->order = order;
  for (i=0; i<order; i++)
    {
      room(g,i) = malloc(sizeof(struct s_som));
      room(g,i)->som = i;
      succ(g,i) = pred(g,i) = NULL;
    }
  return g;
}
 
void add_arc(t_graph g, int s, int d, float c)
{
  t_adj		pa;
  pa = malloc(sizeof(struct s_adj));
  pa->cost = c;
  pa->vsom = d;
  pa->next = succ(g,s);
  succ(g,s) = pa;
  pa = malloc(sizeof(struct s_adj));
  pa->cost = c;
  pa->vsom = s;
  pa->next = pred(g,d);
  pred(g,d) = pa;
}

Plus courts chemins

Il existe de nombreux algorithme de plus court chemin, mais si vous observez bien notre problème, ces algorithmes ne s'applique pas bien. En effet, Dijkstra et ses variantes ne marchent pas avec des coûts négatifs, or les salles permettant de gagner des points de vie impliquent l'existence de coûts négatifs. L'algorithme de Bellman basé sur le demi-degré intérieur supporte les coûts négatifs mais pas les cycles, or dans certains donjons il peut être nécessaire d'utiliser les circuits absorbants pour arriver à la sortie, ce qui exclut non-seulement Bellman mais aussi Bellman-Ford.

Comment faire ?

La solution est plus simple qu'il n'y parait. En réalité, ce n'est pas un problème d'algorithme, mais un problème de données. En effet, le plus court chemin qui nous intéresse ne dépend pas réellement du coût du chemin (sauf pour rester en vie) mais du nombre de salles traversées.

La solution consiste à effectuer la recherche dans un graphe dérivé de l'original que l'on appelle graphe d'états. Le principe est simple, chaque sommet (ou état) du graphe représente une salle du donjon et le nombre de point de vie de l'explorateur lorsqu'il a visité cette salle. Les arcs décrivent le passage d'une salle à une autre (avec la modification de point de vie correspondante) et ont un coût unique de 1.

Ce graphe représente donc l'ensemble des situations possibles où l'explorateur reste en vie. Il est bien évidement beaucoup plus grand que le donjon. L'avantage de cette méthode est que la recherche du plus court chemin ne fait plus intervenir de coût, on peut donc utiliser Dijkstra ou une de ses variantes (comme A*), voir un simple parcours largeur.

Le graphe d'état étant relativement important (possiblement infini) et dépendant du nombre de points de vie de l'explorateur, on ne cherchera pas à la représenter concrètement, on utilisera plutôt une fonction de transition qui à partir d'une salle et d'un nombre de point de vie fournira un ensemble de couple (salle,point de vie) à partir du graphe du donjon.

Ce graphe peut avoir des circuits: il est tout à fait possible qu'un chemin dans le graphe du donjon nous ramène à une salle déjà visitée avec le même nombre de point de vie. Il est forcément orienté (chaque marque la traversée d'un couloir et le gain ou la perte de points de vie correspondant, la traversée dans l'autre sens n'inverse pas ce gain ou cette perte.)

Exemple

Soit le donjon suivant:

ROOMS: 6
MONSTER: 5 13
BREWERY: 3 6

ARCS
ARC: 1 1 2
ARC: 2 1 3
ARC: 3 1 4
ARC: 4 1 2
ARC: 4 1 5
ARC: 5 1 6

On veut aller de la salle 1 à la salle 6 avec 10 points de vie. Il va nous falloir passer plusieur fois par la taverne de la salle 3 avant d'avoir suffisamment de points de vie pour passer le monstre de la salle 5. Plus exactement le chemin sera: [1;2;3;4;2;3;4;5;6] ce qui correspond aux états: (1,10), (2,9), (3,14), (4,13), (2,12), (3,17), (4,16), (5,2), (6,1).

Algorithmes exploitables

Parcours largeur

donne les plus courts chemins (mais tests beaucoup trop de sommets);

Bellman

non applicable (présence de cycle);

Dijkstra

donne les plus courts chemins et en testant moins de sommets qu'un parcours largeur;

A*

au moins aussi bon que Dijkstra, mais il faut faire attention aux heuristiques choisies, toutes ne permettent pas de trouver le plus court chemin;

Bellman-Ford

il n'y a pas de circuit absorbant (pas de coût négatif) donc il est applicable mais reste plus couteux que Dijkstra;

Les autres ...

il existe beaucoup d'autre algorithme de recherche de chemins, notamment, il existe peut être des algorithmes pouvant répondre sur le graphe du donjon ... à vous de voir et de chercher.

Le tournoi de la guilde des donjons

Si votre projet est satisfaisant (il répond lorsqu'on lui demande d'afficher un chemin), il pourra participer au tournoi de la guilde des donjons.

Le tournoi est un classement des temps de recherche des plus court chemin qui sera publier en même temps que les notes des projets. Le classement se fera sur une liste de donjons relativement "évolué" pour lesquels la moyenne des temps d'exécution de votre programme déterminera votre classement. Pour chaque chemin non minimal, le temps de la recherche sera multiplié par le nombre du sommet du chemin, enfin si le chemin n'est pas valide le temps sera multiplié par 50 fois le nombre de sommet du graphe.

(attention, les règles de classements pourraient changer d'ici le rendu.)

Pour exemple, voici un donjon qui pourrait être utilisé pour le tournoi:

# Salles
ROOMS: 22
MONSTER: 4 4
MONSTER: 9 80000
MONSTER: 12 12
MONSTER: 14 30
MONSTER: 17 10
MONSTER: 22 80000
BREWERY: 16 1
BREWERY: 18 10
BREWERY: 7 6
BREWERY: 11 17
DEAD: 3

# couloirs
ARCS
ARC: 1 1 2
ARC: 1 1 3
ARC: 2 1 4
ARC: 2 1 5
ARC: 3 30 6
ARC: 4 1 5
ARC: 5 6 2
ARC: 5 1 6
ARC: 6 1 7
ARC: 7 1 8
ARC: 8 1 5
ARC: 8 1 13
ARC: 8 10 9
ARC: 6 2 18
ARC: 9 1 20
ARC: 9 1000 10

ARC: 5 1 11
ARC: 11 1 12
ARC: 12 1 13
ARC: 13 1 5
ARC: 13 1 14
ARC: 14 1 15
ARC: 15 1 16
ARC: 16 1 17
ARC: 17 1 15
ARC: 17 1 18
ARC: 18 1 15
ARC: 17 1 19
ARC: 19 1 9

ARC: 20 1 19
ARC: 20 1 18
ARC: 18 20 20
ARC: 20 1 21
ARC: 21 1 22
ARC: 22 1000 10

Avec le chemin de 1 à 10 et 10 points de vie au départ. Pour information, le plus court chemin (ou les plus courts chemins) font exactement 162008 sommets.

Ce donjon (variation du précédant) est aussi assez intérressant. Le chemin est plus court (27667 sommets de 1 à 10 avec 3 points de vie), mais les possibilités de boucle sont plus complexes (la différence entre un Dijkstra classique et un A* modifié devient vraiment flagrante.)

# Salles
ROOMS: 22
MONSTER: 4 4
MONSTER: 9 400000
MONSTER: 12 12
MONSTER: 14 30
MONSTER: 17 10
MONSTER: 22 400000
BREWERY: 16 1
BREWERY: 18 50
BREWERY: 7 6
BREWERY: 11 17
DEAD: 3

# couloirs
ARCS
ARC: 1 1 2
ARC: 1 1 3
ARC: 2 1 4
ARC: 2 1 5
ARC: 3 30 6
ARC: 4 1 5
ARC: 5 6 2
ARC: 5 1 6
ARC: 6 1 7
ARC: 7 1 8
ARC: 8 1 5
ARC: 8 1 13
ARC: 8 10 9
ARC: 6 2 18
ARC: 9 1 20
ARC: 9 1000 10

ARC: 5 1 11
ARC: 11 1 12
ARC: 12 1 13
ARC: 13 1 5
ARC: 13 1 14
ARC: 14 1 15
ARC: 15 1 16
ARC: 16 1 17
ARC: 17 1 15
ARC: 17 1 18
ARC: 18 1 15
ARC: 17 1 19
ARC: 19 1 9

ARC: 20 1 19
ARC: 20 1 18
ARC: 18 20 20
ARC: 20 1 21
ARC: 21 1 22
ARC: 22 1000 10