TP Algorithmes – Projet Jeu de Stratégie Temps Réel
L'objectif principal est de fournir un exemple d'analyse et de conception d'un projet complet : un jeu de stratégie temps réel. Les autres objectifs sont de mettre en oeuvre les différentes structures de données et algorithmes abordés en cours en les appliquant à un problème concret.
Le principal problème de ce projet est de le définir ! Vu le temps alloué à sa réalisation, quelques simplifications seront certainement nécessaires.
Jeu de Stratégie Temps Réel ?
Les jeux de ce type sont assez bien représentés par
la série WarCraft créée par Blizzard. Des démos
sont disponibles, pour Windows :
http://www.clubic.com/demo-jeux-video-267-0-warcraft-3-reign-of-chaos.html
L'essentiel du jeu consiste à gérer les ressources disponibles (bois, nourriture, or, etc.) afin de développer un village. Le joueur peut exploiter les ressources disponibles à l'aide d'ouvriers et construire de nouveaux batiments qui permettront, plus ou moins directement, d'accroitre les capacités de production ou d'exploitation. Chaque type de batiment à un rôle déterminé : les fermes produisent de la nourriture et permettent d'embaucher d'avantage d'ouvriers. Les mines permettent de spécialiser les ouvriers et d'augmenter le rendement de l'exploitation d'or ou de minerai, etc.
L'économie simulée est relativement simple : le joueur peut amasser des ressoures et les dépenser en enbauchant de nouveaux ouvriers ou en construisant de nouveaux batiments qui lui permettront d'améliorer sa capacité d'exploitation ou de production.
L'objectif de la série WarCraft est de développer, dans un temps limité et assez court, une armée pour défendre le village ou attaquer un envahisseur.
Description du projet
La série WarCraft propose une économie de guerre, il est possible de choisir un autre modèle économique. Dans tous les cas, les éléments manipulés pendant le jeu sont similaires : des ressources, des ouvriers, des batiments et éventuellemnt des soldats.
La première chose à créer est l'économie et les éléments sur lesquels elle repose. En restant dans le contexte médieval : un chateau (collecteur des ressources pour une économie féodale), des paysans, des fermes, du bois, des bucherons. On peut sans doute ajouter des pierres et du métal pour des constructions plus avancées. L'évolution “technologique” peut également faire partie du développement. On peut envisager qu'un tailleur de pierre et qu'un forgeron permettent de construire des batiments plus importants, que l'agriculture peut évoluer afin de nourrir plus de personnes, que des artisans puissent produire des biens échangeables contre une monnaie, etc.
Au minimum : une ressource, le bois, un exploitant, le bucheron, et une cabane. Pour définir une économie, il faut fixer :
la capacité d'exploitation du bucheron
le prix de la construction d'une cabane et de l'embauche d'un nouveau bucheron.
La monnaie serait dans ce cas la seule ressource disponible : le bois (même s'il n'est pas très pratique de se promener avec des buches dans les poches pour faire ses courses !).
Si l'on souhaite limiter le nombre de bucherons en fonction du nombre de cabanes, il faut créer une nouvelle ressource : la nourriture ou la capacité d'hébergement. Une cabane produira de la nourriture/hébergement que chaque bucheron consommera.
Le plus simple est sans doute de découper le temps en intervalles et de faire le bilan économique au début de chaque intervalle. Un bucheron en train d'exploiter la forêt ramènera du bois et consommera de la nourriture (qu'il travaille ou non). Une cabane produira de la nourriture.
Lorsque le joueur souhaite créer une cabane ou embaucher un nouveau bucheron, il faudra vérifier que les ressources nécessaires sont disponibles.
Il est relativement simple d'ajouter des contraintes supplémentaires à la construction de nouveau bâtiments ou à l'embauche de main d'oeuvre spécialisée. Par exemple : embaucher un charpentier pour construire plus rapidement un batiment peut nécessiter de construire dans un premier temps un atelier ou une scierie. Ces contraintes se décrivent très simplement sous la forme d'un arbre de dépendances :
cabane nécessaire pour un bucheron,
bucheron et cabane nécessaires pour une scierie,
scierie nécessaire pour un charpentier,
charpentier nécessaire pour une ferme,
ferme nécessaire pour un éleveur ou un paysan.
Donner des ordres à la main d'oeuvre suppose de construire un système permettant de désigner l'ouvrier, de décrire l'action à réaliser (“- va couper du bois la bas”) et de la réaliser. Une solution consiste à créer un couple de fonctions :
bucheron_demander(entree: bucheron, entree: demande, description) bucheron_action(entree: bucheron)
La fonction demander permet au bucheron de se rappeller l'action à réaliser lors du/des prochains intervalles de temps. La fonction action réalise effectivement la demande, elle est appellée au début de chaque intervalle de temps :
declaration bucheron collecte // quantite de ressource exploitée file d'attente de demandes et d'objets etat // demande à réaliser objet // objet de la demande à réaliser fin // bucheron_demander(entree: bucheron, entree: demande, objet) ajouter la demande et l'objet à la file d'attente fin // bucheron_action(entree: bucheron) si etat=stop recuperer une demande et son objet dans la file d'attente etat= demande objet= objet de la demande fin si // réaliser la demande si etat=exploiter bucheron_exploiter(bucheron, objet) etat= stop sinon si etat=deplacer bucheron_deplacer(buceron, objet) etat= stop fin si fin // exploiter le bois encore disponible bucheron_exploiter(entree: bucheron, entree: arbre) si rendement du bucheron > quantite de bois de l'arbre collecte= quantite de bois de l'arbre quantite de bois de l'arbre= 0 sinon collecte= rendement du bucheron enlever la quantite de bois exploitée à l'arbre fin // deplacement == etat non productif bucheron_deplacer(entree: bucheron, entree: destination) // eventuellement ne rien faire ou modifier l'affichage fin
Si chaque catégorie d'ouvrier est décrite de cette façon, il est très simple de parcourir l'ensemble des ouvriers et d'éxécuter leur fonction action au début de chaque intervalle de temps. La solution présentée suppose que les actions sont réalisées en un seul intervalle de temps. Il est également envisageable de rajouter des compteurs afin de déterminer la fin réelle d'une action longue (il faudra probablement transmettre le temps actuel à la fonction action).
La description des couts (création et entretien) et du rendement d'un ouvrier peut se faire de manière générale pour chaque type de ressource. On peut également décrire les propriétés communes à tous les bucherons dans une structure catégorie_bucheron et un bucheron particulier (ses ressources collectées, sa file d'attente de demandes, etc) dans une structure bucheron. De même pour les catégories de ressources (bois, nourriture, etc.).
La boucle principale de gestion, en plus de faire agir les ouvriers, devra également réaliser le bilan de l'économie et accepter ou refuser les demandes du joueur.
comptabiliser les ressources produites (nourriture, etc.) comptabiliser les ressources exploitées par chaque ouvrier remettre à zéro les ressources exploitées par les ouvriers comptabiliser les couts d'entretien appeler action pour tous les ouvriers (pour toutes les catégories)
[ressources] or bois fer pierre nourriture
[unites] ouvrier mine_fer mine_or scierie carriere chateau ferme
Les notations . et : indiquent la quantité et la durée. Par exemple l'embauche d'un ouvrier est facturée 50 ressources or et nécessite 1 ressource nourriture en entretien.
[unite] nom=ouvrier creation=or.50 requis=chateau entretien=nourriture.1 comportement=ouvrier [commandes] stop deplace=bois,or,fer,pierre,chateau,mine_fer,mine_or,scierie,carriere produit=chateau:100,mine_fer:50,mine_or:50,scierie:40,ferme:20 exploite=bois,or,fer,pierre [unite] nom=ferme creation=or.100,bois.20,pierre.20 requis=chateau.1,ouvrier proprietaire comportement=ferme [commandes] produit=nourriture.5:-1 [unite] nom=chateau creation=or.400,bois.200,pierre.200 requis=ouvrier racine proprietaire comportement=chateau [commandes] stop produit=ouvrier.1:1 exploite=bois.10:5,pierre.10:5,or.10:5,fer.10.5 [unite] nom=mine d'or creation=or.100,bois.50,pierre.20 requis=chateau,ouvrier.1 proprietaire comportement=mine [commandes] stop exploite=or.20:2 [unite] nom=scierie creation=or.100,bois.50,pierre.20 requis=chateau,ouvrier.1 proprietaire comportement=mine [commandes] stop exploite=bois.20:5 [unite] nom=carriere creation=or.100,bois.50,pierre.20 requis=chateau,ouvrier.1 proprietaire comportement=mine [commandes] stop exploite=pierre.20:5