CSC 4103 – Programmation système

Devoir hors présentiel: Peacefull goblin army

L'objectif de ce projet est de créer les briques de bases pour un jeu de type RTS à la Warcraft III. Dans ce type de jeux, le joueur crée des unités chargées de collecter des ressources ou d'attaquer les ennemis.

Afin de limiter la quantité de travail pour ce DM, et pour promouvoir la paix entre les peuples, le présent jeu se concentrera sur la collecte de ressources. Par ailleurs, seule la partie simulation du monde sera développée, et la partie "jeu" sera ignorée.

L'objectif de ce projet est de vous faire implémenter diverses structures de données (liste, arbres, hashmap, etc.). il vous est donc demandé de les implémenter vous même plutot que de vous reposer sur des implémentations existantes.

Synopsis

Le but du jeu est d'organiser la vie d'un pacifique village de gobelins. Ces créatures ont une vie simple: chaque gobelin est en charge de collecter un type de ressource (fer, bois, pierre) et l'apporter sur un lieu de production (forge, scierie, chantier de construction d'une cathédrale). Un gobelin passe donc sa vie à:

Récolter une ressource et remplir son sac
Porter son sac plein jusqu'à un lieu de production
Vider son sac
Porter son sac vide jusqu'au lieu où trouver des ressources

Puisque chaque gobelin est en charge d'un type de ressource, il passera son temps à faire des aller-retour entre:

Une mine et une forge
Une forêt et une scierie
Une carrière de pierre et une cathédrale

Téléchargez le fichier goblin_army_sujet.tgz et étudiez le code source qui vous est fourni. Ce code source est constitué des fichiers suivants:

goblin_army.h: définit les principales structures de données du projet
goblin_army.c: définit la fonction main. Cette fonction initialise le monde, puis effectue plusieurs tours de jeu.
ga_world.[ch]: est en charge de créer le monde.
ga_goblin.[ch] gère les actions des gobelins.
ga_route.[ch] gère les déplacement des gobelins.

Compilez le programme et exécutez le. Le programme affiche la carte du monde et les emplacements spéciaux:

G: gobelin
M: mine
f: forêt
Q: carrière de pierre (en anglais: quarry)
F: forge
S: scierie (en anglais: sawfill)
C: cathédrale
R: rocher

Round 0          Nb goblins: 15 duration of last round: 0.006506 ms
+--------------------------------+
|                                |
|                              G |
|                            Q   |
|              G         G       |
|                                |
|                                |
|   Q   M                        |
|                                |
|                           G    |
|                               G|
|                                |
|                          f     |
|          f                     |
|         f        G             |
|                                |
|                                |
|       G                        |
|                    G  S        |
|      G                         |
|         M                      |
|  G                        C  G |
|                                |
|             G                  |
|                                |
|                    F  G        |
|                                |
|                                |
|                  Q             |
|                                |
| G   G                          |
|                                |
|                 M              |
+--------------------------------+
	    

Plusieurs mecanismes manquent au projet. Il vous est demandé de les implémenter

Création de montagnes

Pour rendre la gestion des déplacements plus intéressante, on souhaite créer des montagnes que les gobelins ne peuvent pas parcourir. Une montagne est un ensemble de case adjacentes de type rock.

Implémentez la fonction static void create_mountains(struct world* w) (dans ga_world.c). Cette fonction doit créer NB_ROCKS montagnes à des positions aléatoires de la carte. Chaque montagne est constituée de ROCK_SIZE rochers.

Vous êtes libre de choisir la forme des montagnes. Elles peuvent être de forme régulière (eg. rectangulaire ou circulaire), ou de forme aléatoire.

Déplacement des gobelins

La fonction goblin_action gère les actions d'un gobelin. A chaque pas de temps, la fonction peut déplacer le gobelin d'une case en appelant goblin_move. La position actuelle d'un gobelin g est g->location, et sa destination est g->cur_dest.

Implémentez la fonction goblin_move. Dans un premier temps, nous vous conseillons d'ignorer les batiments et montagnes et d'implémenter un algorithme de déplacement très simple:

Pour se déplacer de la case A(i_a, j_a) à la case B(i_b, j_b), déplacez le gobelin verticalement jusqu'à atteindre la case de coordonnées (i_a, j_b), puis déplacez le horizontalement jusqu'à (i_b, j_b). Vous obtiendrez alors le chemin suivant (symbolisé par les *):

+--------------------------------+
|                                |
|                              G |
|                            Q   |
|   ***********A         G       |
|   *                            |
|   *                            |
|   *   M                        |
|   *                            |
|   *                       G    |
|   *                           G|
|   *                            |
|   *                      f     |
|   *      f                     |
|   *     f        G             |
|   B                            |
|                 M              |
+--------------------------------+
	    

La gestion des déplacements (notamment à la question suivante) risque de nécessiter beaucoup de code. Nous vous conseillons de l'implémenter dans le fichier ga_route.c. Vous êtes libres de d'ajouter des champs aux structures de données existantes et de modifier les autres fonctions du projet, si besoin.

Déplacement des gobelins avec détection d'obstacles

Vous devez maintenant faire en sorte que les gobelins prennent en compte les batiments et montagnes lors de leurs déplacements. Un gobelin ne peut pas se déplacer sur une case contenant un rocher. Il ne peut pas non plus se déplacer sur une ressource (foret, mine, carrière) ou un batiment (forge, scierie, cathédrale), sauf s'il s'agit de l'endroit où il vide/remplit son sac.

Implémentez l'algorithme de recherche de chemin A*.

Vous pouvez vérifier visuellement que votre algorithme fonctionne en lançant le programme goblin_army et en observant les déplacements des gobelins.

Pour évaluer les performances de votre algorithme, vous pouvez lancer le programme goblin_army_no_display qui simule les déplacements des gobelins sans les afficher. Nous vous conseillons également de définir MAP_SIZE à 2 dans goblin_army.h.

Pour aller plus loin

Si vous souhaitez aller plus loin, vous pouvez compléter le projet avec d'autres fonctionnalités. Parmi les fonctionnalités intéressantes à implémenter:

Lors de la création du monde, créer des rivières des manière procédurale (vous pouvez par exemple recherche "random midpoint displacement algorithm" sur votre moteur de recherche préféré)
Implémentez une interface graphique. C'est l'occasion de tester une bibliothèque graphique en C (par exemple SDL, CSFML, ou RayLib).