20150209:TP:C:mpc:Donjon:Partie00

Introduction Partie 0

Le TP de cette semaine servira d'introduction au mini-projet de C du semestre. Le sujet complet du projet sera disponible en fin de semaine. Cette semaine l'objectif est de découvrir le format des fichiers et de construire la représentation en mémoire des donjons. Attention, plusieurs vieille version du sujet sont déjà disponible sur le wiki mais quelques détails changent chaque année.

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
• Taniè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 (entraînant la mort de l'explorateur s'il a le malheur de s'y rendre.)
• Gargote: les gargotes des donjons sont tenues par les gnomes de la guilde et permettent aux explorateurs de retrouver des forces pendant leur exploration. Chaque gargote 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 gargotes. 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 (ou en dessous) dans la salle d'arrivée. Notamment, lorsque l'explorateur arrive dans une gargote, il ne meurt que si son niveau de vie n'est plus positif après avoir mangé.

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 gargote 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’existence 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.

TP de la semaine

Vous devez construire le graphe correspondant à un donjon. Pour ça vous avez besoin:

• la structure interne du graphe contenant toutes les informations nécessaires à la suite du projet
• une fonction qui lit le fichier d'un donjon et construit le graphe correspondant.

Le graphe

Pour fournir les informations pertinentes vous devez construire un graphe qui contient les informations suivantes:

• le nombre de sommet (ordre) du graphe
• la liste des salles (sommets) du graphe

De plus pour chaque sommet, vous aurez besoin de représenter:

• les informations sur le type de salle (normal, piège, monstre, gargote … )
• la liste des successeurs du sommet

Vu que le nombre de sommet est connu dès le début, il est fortement conseillé de stocker les sommets dans un tableau (plus simple et plus efficace) de structure. La liste des successeurs étant de taille variable, vous pouvez choisir de faire une liste chaînée ou un vecteur dynamique (tableau avec sa taille), par contre, si votre liste de sommet est un tableau, vous n'aurez pas besoin d'une structure aussi compliquée que celle du TD. Vous devez également penser à la façon dont vous allez représenter les différents coûts (arcs, monstres, gargotes … )

Dans la suite, vous devrez pouvoir:

• simuler un chemin: à partir d'une liste de sommet calculer le nombre de point de vie restant
• trouver un chemin

Lecture du fichier

Pour la lecture du fichier, il vous faut une lecture la plus simple possible (pensez à fscanf(3)) et des fonctions de constructions du graphe.

Outils complémentaires

Pour la suite, il peut être pertinent de commencer à construire les structures de données dont vous aurez besoin après, comme (attention ce sont des exemples):

• file FIFO classique
• tas
• table de hash …