Gestion des quêtes d'un scénario - Page 1

Je développe un jeu où le scénario peut se décomposer en quêtes, chacune faisant avancer l'histoire, en demandant au protagoniste de réaliser certaines actions.
Je me demande par quel moyen je pourrais gérer la détection de l'accomplissement d'une quête. J'ai besoin que cette méthode soit souple.
Par exemple, si une des quêtes consiste à détruire un pont, il faut que lorsque le pont en question est détruit, le moteur de jeu le détecte et fasse avancer l'histoire comme il se doit (séquence vidéo, dialogue, etc.). Je peux imaginer plusieurs méthodes pour cela.
Par exemple, le moteur de jeu conserve en mémoire la liste des quêtes actives (c'est-à-dire entamées et non accomplies), et à chaque tour invoque une méthode "Quête::estAccomplie()" sur chaque quête. C'est à la quête d'implémenter le code correspondant. Dans notre exemple précédent, ça peut consister à tester si le pont en question est détruit ou non...
Une autre méthode pourrait être de gérer des sortes de triggers attachés aux "actions" possibles dans le jeu, qui permettraient de mettre à jour les quêtes lorsque c'est nécessaire. Toujours pour continuer notre exemple, ça pourrait consister à attacher un trigger au pont qui se déclencheraient lorsqu'il serait détruit, et ferait ensuite avancer l'histoire.
Il y a sûrement plein d'autres méthodes, plus ou moins ingénieuses, plus ou moins bien conçues, et je fais appel à votre expérience dans ce domaine (pour ceux qui en ont) pour me conseiller et m'aider à choisir une implémentation efficace.
Merci

Méthode événementielle c'est une bonne idée je pense.
Tu peux faire une table avec les différents messages possibles (Pont détruit, Action du joueur, Ennemi mort...).
Une fonction qui récéptionne les messages et applique un événement en conséquence.
Cet événement correspond à l'appel d'une fonction si et seulement si elle répond à une liste complète de message emis.

Pour que ça soit plus souple tu peux réaliser des fichiers scriptés, genre (tout dépend comment tu veux gérer ça):

[QUETE1]
PONT.1 = destroy
ENNEMY.ALL = dead
CHARACTER.1 = give_object
DOOR.2 = visited

Merci, je note.
Cependant, cette méthode me laisse un peu dubitatif, car je risque de faire transiter une tonne de messages, alors que seulement une très faible minorité sera intéressante. Et cette méthode limite les possibilités du scénario aux types de messages possibles.

En effet c'est un handicap les messages mais ça peut être optimisé avec des priorités..., la gestion de zones...

De plus rien ne t'empêche de créer de nouveaux messages qui n'existent pas. Exemple tu dois visiter un personnage qui doit te remettre un objet précis. Si tu visites ce personnage en question, cela déclenche un événement et celui-ci renvoi un message comme quoi le joueur a récpétionné l'objet en question.

Après je pense qu'il faut découper les messages (messages correspondant à un objet, messages correspondant au joueur, messages correspondant à des personnages, à la carte...).

Devoir détruire un pont ne peut absolument pas être qualifié de « quête », mission à la rigueur

Ca dépend du pont

Alors il y a effectivement ce que propose geogeo, à savoir une liste statique d'événements prédéfinis pour chaque quête. Si ça ne te suffit pas, tu peux peut-être faire un truc style OS multitâche coopératif, avec des sémaphores (attente bloquante) :

void QueteDuPont() {
  if (!map[mypont.pos].is_destroyed)
    wait(map[mypont.pos].destroyed);
  while (money<42)
    wait(money_changed);
}

L'intérêt étant que si tu as une map gigantesque, le thread QueteDuPont ne ralentira le programme que si tu touches au pont en question...



Le problème, c'est par contre que tu peux oublier de wait()er sur un sémaphore, et du coup tu peux avoir des bugs subtils qui font qu'une quête "oubliera" de s'accomplir dans certains cas tordus... Ca peut être très difficile à trouver (et particulièrement frustrant pour le joueur qui se retrouve bloqué sans comprendre pourquoi ), donc il faut peut-être réfléchir à un système qui, "by design" ne serait pas sujet à ce genre de bugs.

Par exemple tu peux faire en sorte qu'aucune variable globale ne soit directement accessible, et qu'il faille passer par un wrapper qui logge les accès :

void QueteDuPont_VerifierAccomplissement() {
  int pont = getvar(pont_a_detruire);
  if (getmap(getobjectposition(pont))!=PONT)
    return;
  if (getvar(player_money)<42)
    return;
  QueteDuPont_Accomplir();
}

L'idée c'est que tu exécutes une fois chaque vérification de quête entièrement au début du programme, puis tu notes de quelles variables elle dépend, et enfin si une de ces variables changent tu réexécutes la quête. En l'occurrence si le pont à détruire change, ou que sa position change, ou que le contenu de la map à cet endroit change, la quête est rappelée. Si ensuite le pont est effectivement détruit (et seulement dans ce cas-là), la quête sera rappelée quand l'argent du joueur change, jusqu'à ce que la quête soit réalisée. Bref, pas moyen de se planter (à moins d'introduire du non-déterminisme), et ça m'a l'air plutôt efficace.

Ca donnerait un code du style :

/* context est une variable globale identifiant la quête : c'est utile pour qu'on sache comment la rappeler */
int getvar(Var *ptr) {
  if (!list_contains(ptr->references,context))
    list_add(ptr->references,context);
  return ptr->value;
}
int getmap(int pos) {
  Var *ptr = &map[pos];
  if (!list_contains(ptr->references,context))
    list_add(ptr->references,context);
  return ptr->value;
}
void notifyvar(Var *ptr) {
  foreach (context,ptr->references) {
    if (!list_contains(need_reexecute,context))
      list_add(need_reexecute,context);
  }
  list_clear(ptr->references);
}
void setvar(Var *ptr,int newvalue) {
  notifyvar(ptr);
  ptr->value = newvalue;
}
void setmap(int pos,int newvalue) {
  notifyvar(map);
  notifyvar(&map[pos]);
  ptr->value = newvalue;
}


/* à appeler à chaque tour */
void ReexecuterLesQuetes() {
  foreach (mycontext,need_reexecute) {
    context = mycontext;
    list_del(need_reexecute,context);
    context->callback();
    context = NULL;
  }
}

Très intéressant l'idée du multitâche coopératif, déjà pour gérer une animation dans un RPG ça doit être l'idéal
Par contre si je fais ça:

RPG_THREAD TaQuete()
{
	wait(map[mypont.pos].is_destroyed);
	//Code d'après
	MessageBox("Fallait pas le détruire");
	return NULL;
}

Là il devrait attendre sur les conditions et après lancer un messagebox... et là il n'y a pas d'autre choix que tout sauver/restaurer les registres, etc. comme en préemptif non?
Donc pas l'idéal si on a peu de ressources... dans ce cas un système par messages comme Windows ce serait mieux j'imagine, mais alors je comprends pas du tout la manière de gérer ça (proprement du moins), genre comment tu implémenterais cette quête: tu parles à un perso, qui va détruire le pont devant toi avec l'animation et tout?
Bref, si tu pouvais éclairer ma lanterne, ce serait sympa merci

Brunni :
Là il devrait attendre sur les conditions et après lancer un messagebox... et là il n'y a pas d'autre choix que tout sauver/restaurer les registres, etc. comme en préemptif non?

Ben oui, c'est le but de setjmp()/longjmp()

Donc pas l'idéal si on a peu de ressources...

Oui, et surtout ce qui prendra le plus de place c'est sans doute la pile (enfin remarque ça doit être possible de la compresser et de la décompresser quand on change de thread)

dans ce cas un système par messages comme Windows ce serait mieux j'imagine, mais alors je comprends pas du tout la manière de gérer ça (proprement du moins), genre comment tu implémenterais cette quête: tu parles à un perso, qui va détruire le pont devant toi avec l'animation et tout?
Bref, si tu pouvais éclairer ma lanterne, ce serait sympa merci

Par exemple :

void ParlerAuPerso() {
  MessageBox("Je vais détruire le pont, muahaha!");
  map[mypont.pos].value = DESTROYED;
  SEMAPHORE *sem = map[mypont.pos].is_destroyed;
  signal(sem);
}

DEFINE_LISTENER(AttendrePontDétruit) {
  SEMAPHORE *sem = map[mypont.pos].is_destroyed;
  return Listener(sem,CodePontDétruit,NULL);
}
DEFINE_LISTENER(CodePontDétruit) {
  MessageBox("Fallait pas le détruire");
  return NULL;
}

Grosso modo un listener est appelé quand une certaine condition se produit, et il doit renvoyer un nouvel ensemble de listener, qui seront à leur tour appelés quand d'autres conditions se seront produites

Merci pour tes réponses Pollux.
En fait, c'est pour un petit jeu, je ne compte pas développer un moteur trop complexe (c'est pour un TP), donc l'idée du multithread avec sémaphores, ça risque d'être complexe à implémenter.
Mais merci pour avoir nourri ma réflexion.

Hm oui la pile ça pue ça, je me disais "peut-être qu'il va trouver un moyen magique de contourner ça"
Au pire on peut en faire une toute petite et limiter le nombre de threads, histoire qu'avec genre 8 ko on ait assez, mais il faut que les fonctions standard (genre bougeSprite, trouveSprite, etc.) soient optimisées pour consommer très peu et utiliser un pool pour les grosses données.
PS: je pige pas vraiment ton truc de sémaphores, je crois que j'ai encore beaucoup de chemin à faire
C'est un pointeur sur une condition? Si on fait signal, ça fait quoi exactement (je comprends que ça va exécuter CodePontDetruit, mais comment tu vas savoir que c'est cette fonction à partir d'une simple valeur? is_destroyed est un booléen?).
Bref, pardonne mon ignorance, mais c'est un sujet qui m'intéresse beaucoup

Si tu veux faire des vrais threads avec une vraie pile, le plus simple est de recopier la pile du thread dans une grosse pile temporaire, puis de recopier juste qu'il faut quand on veut passer au thread suivant ^^


Pour la deuxième idée, c'est simplement qu'au lieu d'avoir une quête dans un thread spécial qui appellerait une fonction d'attente style wait(), on fait en sorte que la quête retourne tout de suite en disant ce qu'elle attend : ensuite on mémorise 1) la condition qu'elle attend (en l'occurrence, que le pont soit détruit), et 2) ce qu'il faudra faire quand cette condition sera remplie (en l'occurrence, passer à la fonction CodePontDetruit()). Ca nous donne une liste de paires (condition,fonction= qu'on peut appeler "listeners". Ensuite signal(bidule) se contente de regarder quelle conditions de "listeners" correspondent à "bidule", et exécuter les fonctions correspondantes. Et quand chacune de ces fonctions se termine, on ajoute sa valeur de retour à "listeners".

Exemple :

1. listeners = []
2. on initialise la quête du pont en appelant AttendrePontDétruit() et en rajoutant sa valeur de retour à listeners
3. listeners = [(map[mypont.pos].is_destroyed,CodePontDétruit)]
4. le joueur joue, gnagnagna : arrive un moment où ParlerAuPerso() est appelée
5. du coup signal(map[mypont.pos].is_destroyed) recherche map[mypont.pos].is_destroyed dans listeners, le trouve, et trouve que la fonction correspondante est CodePontDétruit(); et on efface cet élément de listeners (qui devient donc vide)
6. CodePontDétruit() est exécutée, et comme elle renvoie NULL, listeners est inchangé 7. listeners = []

Evidemment tu peux faire en sorte que ça soit bien plus général que des quêtes, par exemple :

listeners = [(keys[KEY_LEFT].pressed,BougerPerso), (keys[KEY_ENTER].pressed,Parler), (objects[UNTEL].discussion,ParlerAvecUntel), (map[mypont.pos].is_destroyed,CodePontDétruit)]

Bon, après réflexion j'ai choisi (pour l'instant) un truc du même genre que ./12, à savoir une liste de listeners qui sont en attente qu'un évènement particulier se produise pour exécuter leur code.
Ces listeners sont stockés dans le gestionnaire d'évènements, qui se charge de regarder à chaque évènement émis s'il existe un listener attendant cet évènement (et le cas échéant appelle la fonction du listener).
Les évènements sont émis par le système de contrôle du personnage : à chaque fois qu'une action est demandée par le joueur (se déplacer, prendre un objet, pousser, appuyer, etc.) celle-ci est transmise au personnage, mais également envoyée au gestionnaire d'évènements sous la forme d'un évènement.
Ceci introduit une limitation : les listeners ont pour condition d'attente des actions du personnage seulement. Donc pour détruire un pont ce n'est pas très adapté.
En fait, pour gérer facilement un évènement du type "pont détruit", il faudrait que je permette aux objets d'envoyer eux aussi des évènements. Mais pour cela, il faudrait soit que j'utilise une fonction globale permettant de "poster" un évènement, soit que je transmette à tous les objets du monde le gestionnaire d'évènements pour qu'ils puisse lui transmettre leurs évènements.
Or je trouve que la première solution n'est pas cohérente avec une modélisation objet et que la deuxième solution est un poil lourde.
Cela dit, je pense que le moteur de jeu serait bien plus flexible si les objets pouvaient envoyer des évènements. Peut-être que je n'ai pas pensé à une solution bien plus commode pour réaliser cela ?

Tiens ca me fait penser a Golden Sun ca ^^

Parenthese a part : un mix d'un gestionnaire d'evenements et d'une entrée de scripts sur ce meme gestionnaire d'evenement suffiraient pas a resoudre ton probleme ?
Parce que sur un certain evenement causé par le joueur un script pourrait ensuite generer une suite d'evenements "pont detruit" et par la meme occasion interagir avec les evenements a proprement parler (coté joueur)...M'enfin c'est qu'une idée, y'en a peut-etre d'autres.

Sasume :
En fait, pour gérer facilement un évènement du type "pont détruit", il faudrait que je permette aux objets d'envoyer eux aussi des évènements. Mais pour cela, il faudrait soit que j'utilise une fonction globale permettant de "poster" un évènement, soit que je transmette à tous les objets du monde le gestionnaire d'évènements pour qu'ils puisse lui transmettre leurs évènements. Or je trouve que la première solution n'est pas cohérente avec une modélisation objet et que la deuxième solution est un poil lourde.

(ah tu fais du C++ ^^)
Ben je ne vois pas en quoi la 2è solution serait mauvaise... Je veux dire, si ton pont est un objet de classe Bridge, ça me paraît assez normal qu'il y ait une référence vers le monde extérieur si les méthodes de Bridge ont effectivement une influence sur le monde extérieur ?

Non, ce sera en Python
OK pour ta remarque.
Merci pour ton aide, j'ai beaucoup de difficultés à concevoir les applications... Je ne sais pas trop pourquoi. Pourtant je trouve ça intéressant en plus.