INSTITUT DE LA

UNIVERSITE DE LA ROCHELLE

FRANCOPHONIE POUR

LABORATOIRE L3I

L’INFORMATIQUE

MEMOIRE DE FIN D’ETUDES
Master Informatique
Option Intelligence artificielle & multimédia

Sujet : Pilote pour la narration interactive
Apport des bigraphes
Encadrants : Michel AUGERAUD
Ronan CHAMPAGNAT
HO Tuong Vinh
Réalisé par : DANG Kim Dung
Promotion 13, IFI

Hanoi, Septembre 2009


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

TABLE DES MATIERES
REMERCIEMENTS...............................................................................................................3
RESUME................................................................................................................................4
ABSTRACT ...........................................................................................................................5

LISTE DES ACRONYMES ...................................................................................................6
LISTE DES FIGURES............................................................................................................7
CHAPITRE 1 – Introduction ...............................................................................................8
1.1. Motivation et problématique ........................................................................................8
1.2. Objectifs à atteindre et travaux concrets à réaliser ........................................................9
1.3. Environnement de travail .............................................................................................9
1.4. Plan de ce mémoire....................................................................................................10
CHAPITRE 2 – Pilote pour la narration interactive.........................................................11
2.1. Narration interactive ..................................................................................................11
2.1.1. Approches orientés scénarios .............................................................................12
2.1.2. Approches en narration émergente .....................................................................14
2.2. Pilote pour la narration interactive..............................................................................15
2.2.1. Ontologie pour les jeux vidéo.............................................................................16
2.2.2. Système de production .......................................................................................17
2.2.3. Le jeu de rôle comme exemple de narration interactive ......................................18
CHAPITRE 3 – Brève description sur les bigraphes ........................................................22
3.1. Notation et convention ...............................................................................................22
3.2. Bigraphe = graphe des places et graphe des liens........................................................22
3.3. Classification de nœuds par signature et contrôle .......................................................25
3.4. Opérations algébriques sur les bigraphes ....................................................................26
3.4.1. Composition.......................................................................................................26
3.4.2. Produit tensoriel .................................................................................................26
3.4.3. Produit parallèle .................................................................................................26
3.5. Construction de bigraphe par interfaces et opérations algébriques ..............................26
3.6. Règle de réaction composée de deux bigraphes ..........................................................27
3.7. Modélisation d’un système au moyen de bigraphes ....................................................28
CHAPITRE 4 – Construction de deux éditeurs de bigraphes...........................................30
CHAPITRE 5 – Réalisation d’un pilote d’exécution adaptative pour la narration
interactive pour un jeu exprimée par bigraphes ...............................................................35
5.1. Construction du pilote d’exécution adaptative pour la narration interactive : Apports

du modèle des bigraphes ...................................................................................................35
5.2. Application au jeu de neuf pièces ...............................................................................38
5.2.1. Description du jeu ..............................................................................................38
5.2.2. Modélisation du jeu au moyen de bigraphes .......................................................39
5.2.3. Construction d’un récit dynamique en cours d’exécution....................................45
CHAPITRE 6 – Conclusions et perspectives .....................................................................56
REFFERENCES ...................................................................................................................58

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

2


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

REMERCIEMENTS
Avant de vous présenter ce mémoire, je tiens à remercier tous ceux qui m’ont aidé à
réaliser le stage de fin d’études. Je voudrais en particulier remercier :
M. Michel AUGERAUD et M. Ronan CHAMPAGNAT, mes superviseurs de stage au
laboratoire L3I de l’Université de La Rochelle, pour tout : l’encadrement, l’aide,
l’encouragement et la sympathie qu’ils m’ont réservés. Grâce à eux, j’ai pu finaliser
mon travail ;
M. HO Tuong Vinh, responsable de la recherche, professeur d’informatique de l’IFI,
qui a accepté d’être mon superviseur de stage à l’IFI ; par ailleurs, ses transparents sur
la rédaction et la soutenance d’un mémoire de fin d’études m’ont inspiré beaucoup de
bonnes idées ;
M. Guylain DELMAS, doctorant au L3I, dont les conseils, les réponses et les
documents m’ont apporté l’approfondissement de connaissances concernant le stage ;
M. Nicolas REMPULSKI, doctorant au L3I, qui m’a aidé à résoudre les problèmes
que j’ai déjà rencontrés sur la technologie GMF qui est très compliqué pour les

débutants ;
les autres membres du L3I, qui créent un environnement idéal dans lequel j’ai
travaillé pendant le stage de six mois ;
toutes les personnes à l’IFI, surtout les professeurs, pour les enseignements, les cours,
les TPs, le TPE, les aides, les amitiés,… que j’ai reçus.
DANG Kim Dung
La Rochelle, France, août 2009

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

3


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

RESUME
L’objectif du stage est de construire, pour la narration interactive, un pilote qui utilise
un modèle de jeu dont la sémantique s’exprime par des bigraphes. Le pilote étant inspiré du
jeu de rôle (qui atteint un niveau de résultat proche de celui que nous cherchons), est fabriqué
sur les bases d’un système multi-agents, qui permet la gestion de l’exécution adaptative du
déroulement d’une application interactive de type jeu, c’est-à-dire qu’il construit
dynamiquement un récit en cours d’exécution, selon des paramètres définis a priori (le
scénario, la structure du récit) tout en tenant compte d'événements extérieurs (actions du
joueur) ou intérieurs (événements provoqués par le jeu) dans un environnement interactif.
Pour cela, nous avons utilisé une technique de dérivation de modèles qui part d’un méta
modèle des bigraphes. Il nous a permis de développer deux éditeurs aidant à modéliser la
narration d’un jeu (qui est définie par tout ce que le joueur perçoit (musique, images,
dialogues,...) au cours du déroulement de la partie) en définissant son ensemble de règles de
réactions et ses situations (qui sont des abstractions de l’état du système). Ces deux éditeurs
ont été créés grâce à la technologie GMF (Graphical Modeling Framework), c’est pourquoi

tous les schémas de situations et de règles de réactions définis en terme de bigraphes
généreront automatiquement les fichiers XML (eXtensible Markup Language)
correspondants. Nous pouvons donc exécuter facilement le pilote en lisant et traitant ces
fichiers XML. En fin, une implémentation du jeu de neuf pièces est également réalisée pour
valider notre proposition ainsi que le fonctionnement de la démarche. Cet exemple montrera
concrètement comment appliquer le modèle des bigraphes à la narration interactive pour un
jeu afin de réaliser un pilote d’exécution adaptative pour lui. Les travaux dans le cadre du
stage apportent aussi de grandes perspectives menant à la capacité de conception
d’application interactive par transformation de modèles et à la proposition d’un langage de
description d’une narration et de la narration interactive qui est basé sur XML dans l’avenir.
MOTS-CLÉS : jeu, narration interactive, pilote, bigraphe

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

4


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

ABSTRACT
The aim of the probation is to build for the interactive storytelling, a control which
uses a model of game whose semantics is expressed by bigraphs. The control being inspired
from role-playing game (whose description is close to our requirements), is made on the bases
of a multi-agent system, which allows the management of the adaptive execution during the
course of an interactive application of game type, i.e. it dynamically builds a plot in the
course of execution, according to parameters defined a priori (the scenario, the structure of the
plot), with the attention to external events (actions of the player) or internal events (caused by
the game) in an interactive environment. To do this, we used a technique based on model
derivation from a bigraph meta-model. It allows developing two editors helping to model the
storytelling of a game (which is defined by what the player perceives (music, images,

dialogues,...) during the course of the play) by defining its set of reaction rules and its
situations (which are abstractions of the system state). These two editors were created through
the GMF (Graphical Modeling Framework) technology, so all schemas of situations and of
reaction rules designed in terms of bigraphs will be automatically translated into the
corresponding XML (eXtensible Markup Language) files. Therefore, we can easily perform
the control by reading and processing these XML files. Finally, an implementation of the
game of nine rooms is also realized to validate our proposition and the functioning of the
process. This example will concretely show how to apply the bigraph model to the interactive
storytelling for a game to realize an adaptive execution control for it. The works of the
probation also bring great perspectives leading to the capacity of design of interactive
application by model transformation and to the proposition of a description language for the
storytelling and the interactive storytelling, which is based on XML in the future.
KEYWORDS: game, interactive storytelling, control, bigraph

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

5


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

LISTE DES ACRONYMES
Acronyme

Mot complet

CCS

Calculus of Communicating Systems


EIAH

Environnements Informatiques pour l'Apprentissage Humain

EMF

Eclipse Modeling Framework

GEF

Graphical Editing Framework

GMF

Graphical Modeling Framework

IDA

Interactive Drama Architecture

IFI

Institut de la Francophonie pour l’Informatique

ImagIN

Images et Interactivité Numérique

L3I


Laboratoire Informatique, Image et Interaction

PJ

Personnage-Joueur

PNJ

Personnages-Non-Joueurs

UTI

Université de Technologies de l’Information

XML

eXtensible Markup Language

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

6


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

LISTE DES FIGURES
Figure 1.1. Problème posé dans le cadre du stage ................................................................. 9
Figure 3.1. Hypergraphe..................................................................................................... 22
(
Figure 3.2. Bigraphe réduit G avec sa forêt et son hypergraphe correspondants................. 23

(
Figure 3.3. Bigraphe réduit F ........................................................................................... 23
(
Figure 3.4. Le graphe des places et le graphe des liens du bigraphe réduit F ..................... 24
Figure 3.5. Bigraphe F : ε → (3, {x y}) .............................................................................. 24
Figure 3.6. Bigraphe G et ses constituants .......................................................................... 25
Figure 3.7. Bigraphes F et G avec leurs contrôles............................................................... 25
Figure 3.8. Bigraphe H et ses constituants .......................................................................... 27
Figure 3.9. Bigraphe H avec ses contrôles .......................................................................... 27
Figure 3.10. Règle de réaction « Se_déplacer_Ri_Rj » ......................................................... 28
Figure 3.11. Système de l’UTI modélisé par les bigraphes ................................................... 28
Figure 4.1. Processus de construction de l’éditeur de bigraphes.......................................... 30
Figure 4.2. Modèle de domaine de l’éditeur représentant le concept de bigraphe ................ 31
Figure 4.3. Modèle de domaine de l’éditeur représentant le concept de règle de réaction.... 32
Figure 4.4. Modèle de définition graphique ........................................................................ 32
Figure 4.5. Modèle de définition d’outillage (tooling definition)......................................... 33
Figure 4.6. Modèle de cartographie (mapping model)......................................................... 33
Figure 4.7. Modèle de générateur ....................................................................................... 34
Figure 4.8. Exemple sur une règle de réaction et son fichier XML correspondant............... 34
Figure 5.1. Processus de construction d’un récit dynamique en cours d’exécution .............. 36
Figure 5.2. Architecture d’exécution adaptative du système ............................................... 37
Figure 5.3. Disposition du jeu de neuf pièces ..................................................................... 38
Figure 5.4. Exemple sur un récit construit dynamiquement en cours d’exécution ............... 54

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

7


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes


CHAPITRE 1 – Introduction
1.1. Motivation et problématique
Contrairement aux médias traditionnels, tel que le cinéma, qui basent leur narration
sur une approche pré-déterminée par l’auteur, les utilisateurs de jeux vidéos eux exigent
actuellement un approfondissement sur le fond (richesse dans le contenu, élaboration du
scénario du jeu, plus grande liberté d’action et d’expression). En un autre terme, ils attendent
des jeux qu’ils leur fassent vivre des histoires dans lesquelles leurs avatars aient une
implication importante. C’est pourquoi depuis plusieurs années, des expériences ont eu lieu
afin de permettre aux joueurs d'influencer le cours du récit de l'histoire à laquelle ils
participent. L'intérêt d'avoir une telle narration (qui s'adapte aux réactions du joueur) est
qu'elle permet une bien meilleure implication du joueur. Ceci favorise son immersion dans
l’histoire et son intérêt pour l'activité qu'il mène.
Grâce à cela, les jeux vidéo suscitent également beaucoup d’intérêt pour leurs apports
éducatifs ou thérapeutiques. En effet la communauté des Environnements Informatiques pour
l'Apprentissage Humain (EIAH) vise à une utilisation des jeux et de la narration comme
support à l'enseignement. [22] a montré que, grâce à son interactivité, le jeu vidéo procure un
support d'apprentissage plus efficace que les supports classiques (texte, présentation orale,
vidéo). Dans ce cadre, la communauté EIAH travaille à l’élaboration de jeux employant des
scénarios pédagogiques comme bases de récit interactif [5]. En effet via des acquisitions
vidéo, on peut interpréter le comportement de l'apprenant et adapter le déroulement de
l'activité d'apprentissage en fonction de l'analyse de la situation, des objectifs pédagogiques et
des capacités du système.
Dans le cadre des jeux, il est intéressant de souligner que les jeux, tout comme les
EIAH, permettent au joueur de développer des stratégies et de les expérimenter.
Contrairement au monde réel auquel le joueur est confronté, lors d’un jeu, il peut être mis en
échec et élaborer d'autres stratégies. Une règle communément admise en conception de jeu est
de considérer que le jeu est un ensemble de problèmes à résoudre, les premiers étant facile
puis les problèmes deviennent de plus en plus complexes (nécessitent une dextérité ou une
connaissance de l'environnement du jeu plus grande) mais le joueur finit toujours par terminer

le jeu (et donc résoudre le problème même s’il est très complexe).
Cette gestion du déroulement du jeu, l'adaptation de l'application en fait, constitue un
élément de plus en plus important dans la création du jeu et dans la mesure de sa qualité. Par
conséquent il n'est pas rare que les nouveaux jeux s'annoncent offrir à la fois liberté et
scénarisation. Néanmoins ils ne sont généralement que l'un ou l'autre. Nous trouvons ainsi
d'une part des jeux aux scénarios très développés, mais dans lesquels le joueur se trouve
contraint de suivre l'histoire proposée, et d'autre part des jeux offrant une réelle liberté au
joueur, mais qui peinent à fournir une histoire construite et intéressante.
La gestion de l'exécution adaptative est rendue complexe de par le fait que l'utilisateur
dispose d'une grande influence sur le déroulement de l'application grâce à ses interactions
avec l'application. Or ces applications sont spécifiées par un expert (concepteur de jeu,
pédagogue, thérapeute) qui définit un ou plusieurs déroulements en fonction de ses objectifs
(compétences à acquérir, contenu à parcourir, scénario, courbe dramatique,...).
Il nous faut ainsi définir un pilote pour la narration interactive permettant la gestion de
l’exécution adaptative du déroulement d’une application interactive de type jeu. L'adaptativité
de l'exécution se fait au travers d'un moniteur qui intervient pendant le déroulement afin de
s’assurer que l’utilisateur suit une exécution conforme aux règles du jeu. Un jeu peut donc
être vu comme un processus interagissant avec un utilisateur (le joueur), et contrôlé par un
programme de conduite du déroulement du jeu.
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

8


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
Pour représenter des situations comportant plusieurs aspects nécessaires au suivi d’un
jeu (localisation des éléments, la notion de contexte, la notion de règles applicables dans un
contexte,…) nous proposons de représenter ces situations par des bigraphes. Le problème
posé est donc suivant : Etant donné un système comportant deux composants un jeu et un
pilote de ce jeu, comment définir le pilote du jeu sachant que outre ces interactions avec le

jeu, celui-ci dispose d’un modèle du jeu représenté au moyen de bigraphes. Ce modèle permet
de représenter l’évolution des interactions entre les différents agents considérés dans le jeu
selon des règles exprimées à l’aide de bigraphes.

Figure 1.1. Problème posé dans le cadre du stage

1.2. Objectifs à atteindre et travaux concrets à réaliser
Le travail est mené en commençant par définir et réaliser un outil implémentant les
bigraphes adapté à l’expression de narrations. Ce travail est réalisé en utilisant une technique
de dérivation de modèles qui part d’un méta modèle des bigraphes pour construire l’outil
permettant de dériver les bigraphes. Cette technique nous permet d’obtenir un éditeur de
bigraphes et de définir un gestionnaire de bigraphes.
Ensuite, à partir de la réalisation d’un jeu nous mettons en évidence l’opérationnalité
de la démarche et nous pouvons rechercher pour ce jeu les modalités d’interaction permettant
le pilote d’adapter l’exécution selon des paramètres définis a priori (le scénario, la structure
du récit) tout en tenant compte d'événements extérieurs (actions du joueur) ou intérieurs
(événements provoqués par le jeu). Le pilote supervise ainsi l’exécution et joue le rôle d’un
meneur de jeu. Pour se faire il utilise des représentations du jeu et des contraintes qui dirigent
son fonctionnement tel que le modèle du récit, le modèle du joueur,…
Ainsi, les travaux concrets à réaliser dans le cadre du stage sont suivants :
Aspects théoriques :
o étudier et synthétiser ce que sont la narration interactive et un pilote pour la
narration interactive ainsi que les approches existantes ;
o étudier en bref la description du modèle des bigraphes et comment
modéliser un système au moyen de bigraphes.
Productions d’applications :
o construire des éditeurs de bigraphes adaptés à l’expression de narration ;
o réaliser un pilote d’exécution adaptative pour la narration interactive pour
un jeu exprimée par bigraphes.


1.3. Environnement de travail
Le stage est réalisé au Laboratoire Informatique, Image et Interaction (L3I) de
l’Université de La Rochelle, France. Le cadre de ce stage et du sujet en découlant renforce
l’axe de narration interactive du projet ImagIN (Images et Interactivité Numérique) du L3I. Il
constitue le cœur de l’apport du laboratoire au projet européen de réseaux d’excellence IRIS.
Par ailleurs, concernant également ce domaine, le L3I et l’Hôpital de La Rochelle travaillent
depuis plusieurs années sur la conception de jeux vidéo éducatifs pour enfants autistes, dont
l’objectif est de définir et concevoir des logiciels permettant la spécification d’activités
interactives ludiques et pédagogiques, et le suivi de leur déroulement par un praticien, suivant
l’idée qu’un jeu à récit peut s’avérer plus prenant pour le joueur et que plus un joueur jouera
longtemps au jeu, plus il en tirera de bénéfices pédagogiques. On utilise un modèle du jeu
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

9


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
réalisé par un système à état sous forme d’un réseau de Petri. Néanmoins, cette approche ne
prend pas en compte la notion de localité et ne possède pas les propriétés algébriques
nécessaires à la compositionalité, ce à quoi répond le modèle des bigraphes.

1.4. Plan de ce mémoire
•

•

•

•


•

Chapitre 2 – Pilote pour la narration interactive : Ce chapitre présentera une
analyse de différents aspects concernant le pilote pour la narration interactive,
comprenant une introduction aux recherches récentes en termes de narration
interactive, et une présentation des besoins, enjeux et méthodes mis en œuvre dans le
pilotage des applications interactives.
Chapitre 3 – Brève description sur les bigraphes : Ce chapitre donnera une brève
description sur le modèle des bigraphes et un exemple concret illustrant comment
modéliser un système au moyen de bigraphes.
Chapitre 4 – Construction de deux éditeurs de bigraphes : Ce chapitre décrira les
étapes pour construire les deux éditeurs qui aident à définir les schémas des états au
moyen de bigraphes et les schémas des règles de réaction composées de deux
bigraphes.
Chapitre 5 – Réalisation d’un pilote d’exécution adaptative pour la narration
interactive pour un jeu exprimée par bigraphes : Ce chapitre présentera tout
d’abord le processus de construction du pilote d’exécution adaptative pour la narration
interactive avec l’apport du modèle des bigraphes. Ensuite, une l’implémentation du
jeu de neuf pièces sera introduite pour valider la proposition ainsi que le
fonctionnement de la démarche dans le cadre du stage.
Chapitre 6 – Conclusions et perspectives : Ce chapitre donnera des conclusions sur
les travaux ayant été réalisés et des perspectives de ces travaux dans l’avenir.

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

10


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes


CHAPITRE 2 – Pilote pour la narration interactive
Ce chapitre présente une analyse de différents aspects concernant le pilote pour la
narration interactive proposés par la communauté sur ces sujets. Tout d’abord, une
introduction aux recherches récentes en termes de narration interactive, qui décrit les grandes
approches présentées dans ce domaine. Ensuite c’est une présentation des besoins, enjeux et
méthodes mis en œuvre dans le pilotage des applications interactives.

2.1. Narration interactive
On commence dans cette section par présenter une terminologie des différents
concepts entrant dans le cadre du stage, principalement les notions de histoire, récit, narration
et narration interactive [6]. La notion de narration interactive est née de la volonté d’associer
plus étroitement jeu et histoire. En effet elle essaie de lier le processus de l’histoire à celui de
l’interaction, le plus souvent sous la forme de jeu vidéo (bien qu’il existe des formes de
narration interactive détachées de la notion de jeu, comme le film interactif). Afin de mieux
comprendre ce qu’est la narration interactive, il convient de distinguer ce que sont une
histoire, un récit et une narration, et leur relation possible au jeu et à l’interactivité.
• Notion 1 : Une histoire définit « ce dont on parle ». Elle est un ensemble fini d’entités
(comme des événements, des personnages,…), et de contraintes (comme une évolution
concernant une personne ou une chose) qui se situe dans un cadre spatio-temporel
limité. Par exemple, l’histoire du Petit Chaperon Rouge nous raconte comment un
loup tente de dévorer le petit chaperon qui apporte une galette, un pot de beurre et de
la confiture à sa grand-mère. Cette histoire se déroule dans une forêt, et implique
forcément le loup, le chaperon et sa grand-mère.
• Notion 2 : Un récit est un déroulement possible de l’histoire. C’est « ce qu’on en dit ».
Il s’agit d’une suite ordonnée d’événements impliquant un ou plusieurs personnages
dans un ou plusieurs lieux. Une même histoire peut ainsi donner lieu à plusieurs récits
différents. Dans l’exemple du Petit Chaperon Rouge, on peut obtenir plusieurs récits
différents tels que, le loup peut finalement réussir ou non à manger le petit chaperon,
ou le chasseur intervient pour sauver le chaperon et sa grand-mère.
• Notion 3 : Un scénario est un ensemble des récits possible pour une histoire.

• Notion 4 : Une ressource peut être active (on lui associe un comportement) ou inerte
(son état est constant tout au long du jeu). Qu’elle soit active ou inerte, elle peut être
locale (elle appartient à un seul acteur) ou partagée (cette ressource peut être utilisée
par tout ou partie des acteurs et support d’une itération).
• Notion 5 : Une narration constitue « la façon dont on le raconte ». Une narration est
un ensemble de techniques mises en place pour représenter un récit. Elle touche à la
façon dont le contenu de l’histoire et ses événements sont présentés au spectateur. Elle
peut ainsi se distinguer par l’emphase mise sur certains personnages ou lieux de
l’histoire, l’ordre de présentation des événements (chronologique ou non), le support
de narration (oral, écrit, vidéo, etc.) et le ton employé (comédie, drame, tragédie,
farce). Par exemple, le récit du Petit Chaperon Rouge a été dérivé en utilisant de
nombreux formats différents (conte oral, nouvelle, film, dessin animé), et en utilisant
des tons variés. Le récit peut ainsi être racontée en mettant l’accent sur certains
personnages uniquement (c’est-à-dire que l’on pourrait narrer le même récit en se
focalisant uniquement sur le point de vue du chasseur, ou faire du loup le personnage
principal).
• Notion 6 : La narration dans un jeu est définie par tout ce que le joueur perçoit
(musique, images, dialogues,...) au cours du déroulement de la partie. Elle est
généralement composée d'une phase où le joueur reçoit la quête à résoudre, et puis une
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

11


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

•

•


phase d'acquisition de compétences, ensuite une phase d'épreuve et se termine par une
phase de récompense.
Notion 7 : L’interactivité se définit par la capacité de communication et d’action
réciproque de deux ou plusieurs intervenants (humains, logiciels ou matériels). Ainsi
un jeu vidéo est interactif dans la mesure où le déroulement du jeu est en partie
dépendant des actions du joueur, et où la stratégie employée par le joueur s’adapte en
fonction des informations qui lui sont communiquées par le jeu.
Notion 8 : La narration interactive étudie les méthodes de représentation de récit et
d’événements impliquant une interaction avec le spectateur. En permettant à celui-ci
d’agir sur la narration (la représentation du récit), il peut personnaliser l’expérience
narrative et s’approprier le récit plus facilement. La narration interactive permet au
spectateur d’interagir avec l’histoire qui lui est présentée, c’est-à-dire pouvoir influer
sur celle-ci de la même manière que l’histoire peut influer sur lui. Il passe alors d’un
rôle simplement passif (il subit le récit), à un rôle actif (il en détermine le
déroulement, ou tout du moins la présentation). La narration interactive donc permet
au spectateur d’agir sur le déroulement du récit en effectuant divers choix au cours de
celui-ci (on appelle un tel récit le récit interactif). Ces choix peuvent s’exprimer de
diverses façons en fonction du support. Par exemple, la fiction hypertexte permet au
lecteur de naviguer d’un paragraphe à un autre en fonction de ses décisions. Sa
transposée audio-visuelle, le film interactif, applique le même principe en permettant
au spectateur de décider par le biais de sa télécommande de la prochaine séquence à
diffuser, parmi un ensemble correspondant aux suites possibles de la séquence en
cours. Dans le cadre des jeux vidéo, la proposition la plus courante est de permettre au
joueur de diriger le protagoniste du jeu (et donc du récit), et de contribuer au récit à
travers ses actions et ses attitudes.

Dans le cadre de ce stage, notre objectif principal est d’assurer la structure du récit
ainsi que l’attractivité du jeu, et en même temps d’offrir au joueur le moyen de tenir un rôle
déterminant dans le déroulement du jeu, en lui permettant d’influer (par ses actes) sur ce
déroulement et sa conclusion. C’est-à-dire, notre objectif est de permettre au joueur de définir,

au moins partiellement, la teneur et l’ordre des événements se déroulant dans le jeu.
Néanmoins, cet objectif, qui place le joueur en protagoniste du jeu, est tout à fait propre aux
dynamiques du jeu vidéo, mais il n’est pourtant pas simple à réaliser. En effet nous pouvons
constater que la narration répond à des structures précises de déroulement. Ceci est
difficilement conciliable avec les concepts de liberté d’action et d’interactivité propres au jeu.
Deux approches de jeux sont alors apparus : d’un coté des jeux dits orientés scénarios mettant
l’accent sur la richesse du scénario présenté au joueur, quitte à restreindre sa liberté d’action,
et d’un autre coté des jeux dits à narration émergente, qui misent sur la liberté d’interaction du
joueur pour générer des éléments de récits. La section suivante présente donc une analyse sur
quelques travaux récents concernant ce domaine.

2.1.1. Approches orientés scénarios
Les approches orientés scénarios ont pour objectif d’assurer la cohésion du scénario à
l’exécution, malgré les choix du joueur qui peut parfois s’y opposer [6]. Ces approches sont
basées sur une réflexion autour de la définition du scénario et de sa représentation, du
pilotage, et des possibilités de prédiction sur le comportement du joueur. Elles assimilent le
mécanisme de narration à un système de production : le jeu est un procédé piloté par le
système, qui définit un plan d’exécution, le décompose, l’exécute, et éventuellement le
redéfini en fonction des événements remontant du jeu. Elles partagent un concept
d’architecture commun : employer un système (simple ou complexe) de pilotage extérieur au
système de présentation qui intervient sur le déroulement du récit en fonction d’une
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

12


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
modélisation du scénario. Nous présenterons en bref dans la section ci-dessous les travaux
réalisés selon ces approches par le Liquid Narrative Group, par l’Oz Project et Façade, par
l’Interactive Drama Architecture, et par le PAPOUS.

• Le Liquid Narrative Group (Université de Caroline du Nord) travaille sur un projet
baptisé Mimesis consistant à piloter un moteur de jeu 3D par un système d’exécution
adaptative [24]. Ils définissent un scénario comme un ensemble d’actions réalisées par
différents acteurs et agencées par des liens de causalité. Le système proposé par ce
groupe estime les effets des actions du joueur, les compare au plan scénaristique prévu
et, en cas d’incompatibilité, peut soit redéfinir partiellement le plan, soit empêcher
l’action du joueur de suivre son cours (en l’interrompant ou en la faisant déboucher
sur un résultat non prévu).
• Michael Mateas de l’équipe de l’Oz Project a orienté ses recherches sur le segment du
drame interactif (vision théâtrale du récit, centrée sur l’évolution des relations et des
états émotionnels des personnages) [14]. Dans son logiciel baptisé « Façade », il
propose un scénario représenté comme un ensemble d’éléments atomiques dotés d’un
ordre partiel, dans lequel le joueur va suivre un chemin différent à chaque partie.
• L’équipe de l’Université du Michigan reprend cette notion de drame interactif, et
propose une architecture (IDA – Interactive Drama Architecture) basée sur un
scénario écrit par un auteur humain puis formalisé sous la forme d’un graphe d’états
avec un ordre partiel [12, 13]. Le système comporte un agent directeur qui pilote le jeu
en surveillant le joueur et les conséquences de ses actions sur l’évolution du scénario.
En cas de détection « d’erreur », il altère l’état du monde de façon à le faire à nouveau
coïncider avec le scénario prévu. Le principal intérêt de leur démarche est la capacité
d’anticiper les problèmes éventuels en établissant des prédictions sur le comportement
du joueur.
• Avec le projet PAPOUS, l’Intelligent Agent and Synthetic Characters Group
(Université de Lisbonne) travaille à la conception d’un conteur virtuel [20]. Ils
rajoutent à ce conteur la capacité d’adapter son histoire en fonction de la perception de
l’intérêt du public (de jeunes enfants) capturé à l’aide d’un système d’acquisition
vidéo. Ils conçoivent un modèle de récit comme un ensemble d’éléments atomiques
hiérarchisés. Chaque atome décrit un morceau du récit et est doté de propriétés
reprenant les fonctions de Propp [17]. Un récit est un parcours de l’arbre dans lequel
pour chaque niveau le directeur choisi l’élément le plus approprié en établissant des

corrélations entre les propriétés de l’élément et les désirs perçus dans l’assistance.
Les différentes modélisations de scénarios emploient ainsi des méthodes diverses :
graphes dotés d’ordre partiel, ensembles d’événements atomiques assortis d’un modèle de
déroulement, modélisation arborescente. L’objectif de chacune de ces modélisations est de
créer un espace de variations autour du récit initial pensé par l’auteur, permettant de produire
un récit adapté à l’utilisateur. Toutes ces approches apportent un ensemble de fonctionnalités
additionnelles facilitant le pilotage et l’appropriation du récit : interface intuitive (cartes,
saisie de texte en langage naturel), expressivité des personnages virtuels, capture d’expression
et de comportement, prévention des situations à risque, capacité de redéfinition du plan de
récit originel. L’intégration de ces technologies nous semble une étape importante pour la
conception d’un système de récit interactif définitif.
Cependant, ces travaux présentent une limite dans leur approche initiale. De par leur
volonté de faire coïncider le déroulement du récit avec un modèle pré-établi, ils restreignent
nécessairement les possibilités offertes à l’utilisateur. Partant d’une représentation directe du
scénario proposé à l’utilisateur, ces approches ne peuvent que le restreindre dans ses
possibilités d’action. Il n’est en effet ni possible de gérer les cas non prévus par le système, ni
de couvrir à la conception la totalité des possibilités de récits. C’est donc par opposition à
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

13


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
cette approche qui limite les possibilités aux seuls récits prévus en amont qu’est apparue la
théorie de la narration émergente.

2.1.2. Approches en narration émergente
Les approches émergentes constituent une réponse viable aux approches
scénaristiques classiques, dans le sens où elles réussissent effectivement à offrir une réelle
liberté d’interaction à l’utilisateur, et à intégrer son comportement et ses actions dans le

déroulement du récit [6]. Elles ne considèrent le récit que comme une conséquence indirecte
de l’interaction du joueur avec le jeu. En plongeant le jeu dans un univers interactif autonome,
elles lui permettent une véritable liberté d’action, avec la certitude que ses choix se
répercuteront sur le déroulement du jeu. Cette théorie part du principe que, de la même
manière que les interactions entre humains sont génératrices de récits, il est possible d’obtenir
de la narration en faisant interagir un utilisateur humain avec un ensemble de personnages
virtuels autonomes, pour peu que ceux-ci soient doté d’un comportement suffisamment
complexe, crédible et individualisé. Son fondement est de ne plus chercher à représenter
directement le récit, mais décrire des personnages autonomes et faire émerger le récit de leurs
interactions. Nous présenterons ci-dessous des points principaux des études concernant la
narration émergente réalisées par le Center for Virtual Environment, par l’Interactive
Storytelling, et par l’ID Tension.
• Constatant le manque de liberté inhérent aux scénarios conventionnels, le Center for
Virtual Environment de l’Université de Salford a développé les bases de la narration
émergente : ne plus chercher à représenter directement le récit, mais décrire des
personnages autonomes et faire émerger le récit de leurs interactions [2]. S’inspirant
des pratiques du jeu de rôle, ils proposent un modèle basé sur trois niveaux de
description : le « game master level » qui définit le schéma global des interactions
entre personnages, le « groupe level » qui définit des dynamiques à l’intérieur d’un
groupe de personnages liés et le « character level » qui précise la description et les
motivations de chaque personnage individuellement. Ils constatent qu’avec ce modèle,
le récit généré n’est jamais celui prévue par le concepteur, signe de l’impact réel du
joueur dans la narration.
• L’équipe d’Interactive Storytelling de l’Université de Teeside propose un système de
narration interactive par le biais d’agents autonomes dirigés par des réseaux de tâches
hiérarchisées [3]. Ce modèle permet de mettre en scène des sitcoms employant des
agents autonomes et est complété par un système de planification des tâches qui assure
un comportement cohérent des acteurs dans la durée. Ils introduisent également une
possibilité d’interaction par l’utilisateur qui peut agir sur l’environnement et adresser
des consignes vocales aux acteurs virtuels. Récemment, le système a été complété par

un agent de gestion intelligente des interactions acteur-environnement qui détermine
les réactions des objets manipulés par les acteurs en fonction des besoins de la
narration [10].
• L’équipe d’ID Tension, quant à elle, part du constat qu’une expérience narrative ne
peut se résumer à la simple juxtaposition de personnages autonomes, mais doit
répondre à des objectifs narratifs définis [21]. Elle propose donc un modèle dans
lequel les actions des personnages sont guidées non seulement par leur comportement,
mais aussi selon l’intérêt de chaque possibilité pour la narration en cours. Ainsi, à
chaque étape importante du récit, le système détermine le comportement de chaque
acteur pour produire des effets narratifs.
On peut trouver qu’en renonçant au contrôle du récit au profit d’une logique de
personnages, la narration émergente se prive de la capacité de valider les récits générés, et
donc d’assurer la qualité de l’expérience narrative offerte à l’utilisateur. Il peut donc en
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

14


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
résulter la génération d’un ensemble de récits pauvres en contenu, au déroulement bancal, ou
manquant de rythme ou de structure. Si dans le cas d’utilisateurs courants cette possibilité
reste dans le cadre des nuisances acceptables (car compensées par la liberté offerte, et la
possibilité de générer autant de bons récits que de récits peu satisfaisants), cette faiblesse
s’avère beaucoup plus cruciale dans les cas où la qualité du récit est un élément critique, soit
du fait du peu de tolérance de l’utilisateur aux dysfonctionnements (cas de l’enfant autiste),
soit du fait du contexte même de l’application (simulateur d’apprentissage pour formation de
secours, etc.).
Remarque : Les travaux présentés ci-dessus (approches orientées scénarios et approches en
narration émergente) ne suffisent pas évidemment à répondre à notre problème.
Principalement sur le fait que si les approches présentées fournissent des éléments

intéressantes soit du coté de la validation du récit, soit de celui de la capacité d’action de
l’utilisateur, aucune ne réussit encore à concilier ces deux aspects de façon satisfaisante. Pour
cela, notre objectif est de concevoir un système chargé du pilotage du récit interactif qui gère
l’exécution adaptative du déroulement de celui-ci, c’est pourquoi nous étudierons des
problèmes concernant le pilote pour la narration interactive dans la section suivante.

2.2. Pilote pour la narration interactive
Dans le cadre du suivi de l’exécution d’un jeu nous devons garantir une cohérence de
l’exécution vis-à-vis des choix antérieurs et des choix a priori du concepteur de jeu. Ce
problème est central dans le cas des applications interactives. Il s’agit de rendre actif
l’utilisateur en lui permettant de laisser une trace dans le « réseau narratif » tout en évitant des
typologies réductrices. Gérer la flexibilité d’un scénario devient un problème d’une grande
complexité du fait de la prise en compte du joueur. Il est nécessaire de mettre en place des
mécanismes garantissant une terminaison acceptable pour tous les récits. Mais également de
prévoir une robustesse du scénario vis-à-vis du joueur dont une particularité est d’essayer de
faire des choses impossibles ou non recommandées.
Ainsi, nous avons besoin d’une gestion des récits mêlant à la fois les concepts de
liberté du joueur, comme pour les approches à histoires émergentes, en les complétant par un
système de pilotage de l’exécution du scénario. Ce pilotage a pour fonction d’observer le
déroulement du jeu, d’analyser les actions du joueur et d’y apporter des réponses appropriées
pour faire progresser le récit. Ce système ne se base pas sur un schéma d’exécution précis,
mais sur un modèle générique de narration, dont il se sert comme référence pour générer son
récit. Afin de ne pas entraver la liberté du joueur, les actions du système ne peuvent pas
directement contredire ou invalider celles du joueur. Le système doit donc composer avec un
champ d’action limité [6].
En général, le pilote pour la narration interactive a pour but de gérer l’exécution
adaptative du déroulement d’un jeu. L'adaptativité de l'exécution se fait au travers d'un
moniteur qui intervient pendant le déroulement afin de s’assurer que l’utilisateur suit une
exécution conforme aux règles du jeu. Ainsi, il doit maîtriser l’interaction pour permettre une
évolution adaptative du récit en :

• fonction du comportement du joueur ;
• respectant les consignes du concepteur ;
• tenant compte de l’état des ressources.
En plus, dans le cadre de la validation des scénarios de jeu, c’est-à-dire définir si un
récit généré est correct et si un jeu est amusant, le pilote doit également assurer les propriétés
suivantes [1] :
• Sûreté : exprime que sous certaines conditions, un évènement ne peut jamais se
produire.
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

15


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
•
•
•

•

•
•
•
•

•

•

•


Accessibilité : assure que tous les états du système peuvent être atteints.
Absence de blocage : exprime que le système ne se trouvera jamais dans une situation
où il ne peut plus progresser.
Symétrie : les conditions initiales des joueurs sont équivalentes. C’est-à-dire que les
conditions initiales du jeu font que les joueurs ont accès, dans des conditions
symétriques, aux mêmes ressources et informations.
Justice : N joueurs ont des possibilités équivalentes de remporter la partie en regard de
la disposition des ressources sur le terrain. Lors de l’analyse des récits du jeu, il faut
garantir que l’ensemble des séquences victorieuses est équivalent pour chaque joueur.
Séquencement : respect des contraintes de précédence entre évènements.
Complexité : le déroulement du jeu ne contient pas d’exécutions qui mènent à la
victoire trop rapidement.
Complétude : un jeu complet est un jeu pour lequel les joueurs ne peuvent pas
atteindre d’états où les fonctionnalités ou le jeu sont compromis.
Fréquence des évènements dramatiques : au cours du jeu, un ensemble d’évènements
provoquant une modification de l’état émotionnel du joueur peuvent apparaître. Tous
ces évènements ont pour objectif d’accroître la sensation d’immersion du joueur. Il
peut s’agir, par exemple, de situation de danger direct. Nous devons nous assurer que
ce type de situation est suffisamment fréquent au cours du récit.
Variété de l’intensité dramatique : Tous les évènements dramatiques énoncés
précédemment peuvent être organisés en catégories car ils ne traitent pas des mêmes
émotions. On trouvera alors des évènements liés à la peur, au stress, au bonheur. Il est
important de diversifier ces évènements au cours du récit pour mélanger les sentiments
ressentis par le joueur.
Équilibre : les niveaux de ces évènements dramatiques sont eux aussi variés. Il n’est
pas nécessaire de conserver le joueur dans un état de stress permanent. Il faut s’assurer
d’un équilibre entre les situations avec forte tension dramatique et les situations
calmes.
Terminaisons locales : le jeu n’est pas seulement défini par la quête finale, mais

également par un ensemble de quêtes locales qu’il doit atteindre afin de progresser
vers la fin du jeu. Il faut prévoir un ensemble suffisant de quêtes de ce type.

Dans les sections ci-dessous, nous présentons les approches existantes dans le cadre du
contrôle du déroulement de récit. Tout d’abord nous introduisons les travaux sur l’ontologie
pour les jeux vidéo.

2.2.1. Ontologie pour les jeux vidéo
Les travaux dans le cadre du Game Ontology Project [25] visent à définir un cadre
pour décrire et analyser un jeu. Leur approche est basée sur l’étude de jeux existants dont ils
ont extrait un ensemble de concepts et méthodes utilisés par les jeux. L’ontologie proposée
par les auteurs est structurée autour des notions d’interface, règles, objectifs, entités et entités
jouables.
• L’interface décrit l’ensemble des moyens que le joueur peut utiliser pour interagir
avec le jeu, et ainsi, influer sur le déroulement du récit.
• Les règles déterminent les interactions élémentaires du joueur avec le jeu. Elles
permettent de réguler le déroulement du récit.
• Les objectifs correspondent aux conditions que le joueur doit remplir pour gagner une
partie.
• Enfin les entités et les entités jouables couvrent tous les éléments du jeu en les
séparant entre éléments passifs (entités) et éléments manipulables (entités jouables).
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

16


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
Cette description permet de donner les éléments du jeu, mais elle ne donne aucune
information sur la façon dont le récit se construit, or le pilote est chargé de réaliser cette
construction. Dans la section suivante, nous présentons une autre approche décrivant le

pilotage des systèmes de production.

2.2.2. Système de production
Une vision commune est de considérer un système de production est un ensemble de
transformations produisant un produit fini à partir de pièces fournies en entrée. Il travaille en
suivent les directives d’une commande qui lui est appliquée. La commande sert à piloter le
système en fonctions des quantités de produits nécessaires, et à s’adapter aux perturbations
qui peuvent frapper le système (défaillance, absence d’un opérateur, manque d’une matière
première) [6].
Les systèmes de production doivent pour cela assurer une flexibilité potentielle
(capacité propre de changement) et opérationnelle (capacité d’employer la flexibilité
potentielle pour répondre aux variations du contexte). Cette capacité d’adapter son
fonctionnement selon ses objectifs et des variations externes est très proche des
problématiques d’exécution adaptative qui sont traitées dans ce stage. On retrouve dans ces
deux domaines l’idée centrale de piloter l’exécution en fonction d’objectifs, de ressources et
d’événements. Dans le cadre des systèmes de production, les objectifs sont les produits
attendus, les ressources sont les matières premières à disposition, et les événements sont les
défaillances pouvant survenir. Dans celui du pilotage de récit, les objectifs sont la conclusion
souhaitée, les ressources décrivent l’état courant du récit, et les événements sont les
interventions du joueur sur le déroulement du jeu. Ainsi, les systèmes de production
proposent des solutions à des problématiques comparables à celles que nous cherchons à
traiter dans ce stage. Leur étude fait ressortir les points suivants comme particulièrement
pertinents :
• un découpage hiérarchique du pilotage, permettant d’arranger les opérations, en
niveaux autonomes, et de développer ainsi une certaine marge de flexibilité dans la
commande ;
• la mise en place d’un niveau d’ordonnancement qui sert à définir, contrôler, et
éventuellement redéfinir à la volée le plan d’exécution ;
• un niveau de supervision qui assure le contrôle, la commande du système et la
surveillance de l’application.

Les méthodes mises en œuvre dans le cadre du pilotage des systèmes de production
fournissent une base théorique sur laquelle concevoir des outils de pilotage de récit pour jeux
interactifs. Dans les systèmes de production, les contraintes du système figurent des capacités
de machine (en nombre et en capacité propre), des temps d’opération, et des séquences
d’opérations à effectuer lors du traitement global. Dans le cadre d’une application de récit
interactif, ces contraintes sont appelées à être remplacées par une structure de récit à respecter
lors de l’exécution. La définition d’une telle structure, si elle emploie un formalisme
informatique, repose avant tout sur une compréhension des structures et modèles mis en
œuvre dans les jeux de rôle, une catégorie particulière de jeu de société centré sur le théâtre et
la narration, font référence aux structures de récit dans leur fonctionnement. Dans la section
suivante, nous étudierons ces jeux qui centrent sur un processus de récit interactif non
numérique pour fournir une piste intéressante sur le fonctionnement possible d’une
application de pilotage de récit.

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

17


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

2.2.3. Le jeu de rôle comme exemple de narration interactive
Le fondement du jeu de rôle est de donner possibilité à un groupe de joueurs de créer
collectivement leur propre récit, dont ils interprètent les personnages principaux [6]. Pour
cela, ce loisir mêle des mécanismes purement ludiques (permettant d'assurer un aspect
simulation dans le jeu) à des dynamiques de théâtre d'improvisation. Le jeu de rôle a servi
d’inspiration à une catégorie de jeux vidéo qui en reprennent certains mécanismes
(progression des personnages par l’expérience, richesse de l’environnement, importance du
dialogue dans la progression), mais qui ne réussissent pas à émuler l’aspect central qu’est
l’interprétation théâtrale.

Le jeu de rôle permet d'obtenir à son échelle le même type de résultats que ceux que
nous visons dans le domaine informatique : la construction dynamique d'un récit, centré
autour des actions des joueurs, et satisfaisant pour ceux-ci.
Les différents jeux de rôle existant sur le marché reposent tous sur un modèle de
fonctionnement commun. Celui-ci fait intervenir un ensemble de joueurs, chacun interprétant
un personnage (dit Personnage-Joueur, ou PJ), et un meneur de jeu, chargé des fonctions
cumulées d'arbitre et de metteur en scène. Tous se retrouvent dans un lieu donné, et
construisent un récit autour des actions des personnages-joueurs dans l'univers décrit par le
meneur de jeu. L'ensemble des possibilités des joueurs et des mécanismes de résolution étant
décrits dans un corpus de règles, spécifique à chaque jeu. Si les joueurs ont le contrôle de
leurs personnages, et à travers eux une emprise sur le déroulement du récit, c'est l'intervention
du meneur de jeu qui s'avèrera déterminante dans le bon déroulement de la partie. Afin de
guider son action, celui-ci doit se baser sur un ensemble de connaissances liées au jeu, aux
joueurs et au récit.
2.2.3.1. Fonctionnement de la génération de récit en jeu de rôle
Le jeu de rôle fait intervenir deux catégories de participants : joueur et meneur de jeu.
Le rôle de chacun au sein du jeu est définit de la façon suivante :
• Le Joueur est l'interprète d'un personnage dans le récit. Il décide des actions de son
personnage, interprète ses dialogues et fixe son comportement. Dans la plupart des
jeux, le joueur est à l'origine le créateur du personnage (bien que certaines parties
puissent se jouer en employant des personnages fixés par le meneur de jeu, on parle
alors de personnages prétirés) pour lequel il a définit une apparence, une histoire, un
tempérament, et un ensemble de capacités.
• Le Meneur de jeu est à la fois l'arbitre et le metteur en scène du récit. D'une part il
assure l'arbitrage des actions des personnages des joueurs. Il indique ainsi quelles
actions réussissent ou échouent, et avec quel résultat. Pour cela, il s'appuie sur les
règles du jeu, qu'il a à sa charge d'interpréter et d'appliquer. D'autre part il est
responsable de la gestion du récit et de la mise en scène de celui-ci. C'est à lui de
décrire les décors, l'environnement, et d'interpréter l'ensemble des Personnages-NonJoueurs (PNJ), ce qui lui permet de générer un cadre autour des joueurs, et de faire
réagir le récit aux actions de ceux-ci.

Le cadre général du jeu et ses règles sont généralement définis par le jeu en lui-même,
le plus souvent présenté sous la forme d'un livre ou ensemble de livres expliquant les règles et
présentant l'univers de jeu. C'est à partir de cet ensemble d'information que joueurs et meneur
de jeu pourront effectuer leur partie.
En début de partie, le meneur de jeu décrit une situation initiale aux joueurs. Celle-ci
correspond à un état précis de l’univers de jeu, perçu du point de vue des personnagesjoueurs. Chaque joueur décrit alors les actions de son personnage au meneur de jeu. Celui-ci
résout les différentes actions (en appliquant les règles adéquates), fait intervenir selon son
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

18


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
envie les personnages-non-joueurs et événements de son choix, et décrit la situation qui en
résulte. Les joueurs peuvent donc ainsi interagir avec les éléments présentés par le meneur de
jeu afin d'influer sur l’univers de jeu qui leur est présenté et faire progresser la situation.
En fonction de l’évolution de la situation le meneur de jeu choisit alors une amorce
d’histoire à proposer aux joueurs. Celle-ci se manifeste sous la forme d’un événement qui
déstabilise la situation et présente un problème que les joueurs sont invités à résoudre.
Comme il appartient aux joueurs de décider de se lancer ou non dans la résolution du
problème, et donc d’entamer le récit, le meneur de jeu doit veiller à choisir un événement et
un problème qui attirent l'intérêt des joueurs.
Les joueurs sont seuls responsables de la façon dont ils abordent le problème, et de
leurs décisions, bien que le meneur de jeu puisse parfois les conseiller par le biais
d'événements ou d'informations. Au fur et à mesure des actions des joueurs, le meneur de jeu
suit la progression du récit et estime quelles sont les conclusions les plus probables. Il a alors
pour tache d’aiguiller le récit vers une de ces conclusions, en ajoutant progressivement à la
situation les éléments nécessaires pour la faire avancer (et qui ne dépendent pas des actions
des joueurs). Il veille aussi à ce que le récit reste cohérent, ne reste pas bloqué suite à des
choix hasardeux, et gère le rythme et la progression de la tension dramatique.

C'est ainsi par l'interaction entre les joueurs et le meneur de jeu que le groupe crée
progressivement un récit qui lui est propre. Ce fonctionnement souvent difficile, peut être
décomposé en une série de tâches accomplies par le meneur de jeu à partir d'un ensemble de
ressources que nous allons détailler plus avant.
Tâches effectuées par le meneur de jeu
La méthode employée par chaque meneur de jeu pour gérer la construction de récit
avec ses joueurs est très personnelle et empirique. Nous pouvons cependant identifier dans ce
travail quatre tâches essentielles :
• Une tâche d'Analyse qui représente la récupération des informations provenant des
joueurs. Le meneur de jeu doit ainsi identifier en quoi les actions décrites par les
joueurs peuvent se répercuter sur le déroulement du récit, et identifier les
informations apportées sur le comportement du joueur et de son personnage.
• Une tâche de Gestion de profil qui correspond à l’assimilation des informations sur le
joueur. Le meneur de jeu tient ainsi à jour une connaissance du joueur, qui lui permet
de guider son choix dans la gestion du récit.
• Une tâche de Gestion de scénario qui constitue le cœur du travail de meneur de jeu.
Elle consiste en mettre à jour de l'état de jeu, identifier les récits possibles, et
déterminer une suite d’événements à mettre en place dans le récit.
• Une tâche de Réalisation qui représente la description et le développement des
événements déterminés dans la gestion de scénario.
Ressources mises en œuvre
La mise en œuvre des tâches présentées ci-dessus nécessite l’emploi de diverses
connaissances sur le jeu et les joueurs. Nous trouvons généralement trois catégories de
connaissances employées par le meneur de jeu pendant la partie :
• Une connaissance du jeu : Le meneur de jeu doit connaître autant les règles du jeu que
le cadre qu’il propose aux joueurs. Cela va lui permettre de résoudre les interactions
des joueurs, ainsi que d’estimer par avance les résultats possibles de certaines actions.
La connaissance du cadre est elle nécessaire pour déterminer proprement la situation,
et savoir quelles sont les ressources narratives (personnages, événements, etc.) qu’il a
à sa disposition pour intervenir sur l’histoire.


DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

19


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
•

•

Une connaissance des structures de récit : Elle est nécessaire pour assurer à la partie
une forme cohérente, et la valider en tant que récit. C’est avec cet outil que le meneur
de jeu va pouvoir structurer les événements du jeu et savoir quand intervenir. Il
apportera ainsi au récit interactif la structure dont il a besoin, et renforcera
l’expérience des joueurs.
Une connaissance des joueurs : Dans une troisième catégorie, connaître les joueurs
sera toujours une aide utile dans le développement du récit. En connaissant ses
joueurs, le meneur de jeu pourra d’une part connaître leurs forces et faiblesses, de
façon à adapter les défis qu’ils rencontreront. Il connaîtra aussi leurs goûts, ce qui lui
servira à sélectionner des événements qui répondront aux attentes des joueurs.

2.2.3.2. Jeu de rôle et gestion de l'interactivité
Le jeu de rôle étant par définition un jeu à caractère social (puisqu'il fonctionne par
dialogue entre ses acteurs), son déroulement et son organisation peuvent varier en fonction du
rapport social qui réside entre le meneur de jeu et ses joueurs. Il existe ainsi des variations
dans lesquelles le meneur de jeu est particulièrement contraignant, et ne laisse que peu
d'initiatives au joueurs (jeu linéaire), et en opposition des variations dans lesquelles les
joueurs sont particulièrement actifs, et où le meneur de jeu se cantonne à un rôle de gestion du
déroulement du récit.

[23] présente une proposition de classification des jeux de rôle selon leur façon de
mettre en œuvre la notion d’interactivité entre le joueur et le meneur de jeu. Il définit quatre
types, qu’il nomme Illusionnisme, Participationnisme, Esprit pionner et Jeu de basse.
• L’Illusionnisme : Dans ce cadre, le joueur n’a en réalité aucun contrôle sur le
déroulement du jeu, et ses choix ne sont qu’illusoires. Le jeu fonctionne selon une
trame linéaire, établie à l’avance, et quelles que soit les décisions prises par le joueur
pendant le jeu, il ne pourra que suivre la même progression vers une fin inéluctable.
• Le Participationnisme : Cette catégorie est une variante particulièrement évoluée de
l’illusionnisme, dans laquelle l’impression faussée de contrôle du joueur est renforcée
par l’emploi d’éléments annexes à l’histoire.
• L’Esprit pionnier : L’objectif de ces jeux n’est pas tant de créer l’histoire que de la
découvrir. Dans ces jeux encore une fois l’histoire est écrite à l’avance et immuable.
Cependant au lieu de placer le joueur dans une position d’élément constitutif du récit,
on le met dans une position où il doit comprendre le récit et le découvrir peu à peu.
• Le Jeu de basse : La quatrième et dernière catégorie identifiée est celle qui correspond
le plus aux attentes des joueurs actuels en termes de jeux à histoire. Elle est nommée
« jeu de basse » en référence au rôle du bassiste dans un groupe de musique. Par
analogie, ce genre de jeu propose au joueur un ensemble composé d’un monde auquel
il influe une certaine dynamique, mais ne prévoit pas de déroulement d’histoire a
priori, laissant au joueur le soin de composer une histoire par lui-même avec les
éléments qui lui sont offerts. L’intervention du jeu se limitera alors à la résolution des
actions du joueur et à l’apport de rythme et rebondissements, tandis que le processus
même de narration sera supporté par le joueur. C’est à la fois le concept le plus
intéressant pour le joueur et le plus difficile à atteindre pour un jeu vidéo. Cependant
l’implantation de ce genre dans le domaine du jeu vidéo n’est pas aboutie. En effet les
fonctionnalités présumées du contrôleur ne sont pas complètes, et s’il propose
effectivement la liberté de détermination du joueur dans son histoire, le pilotage du
rythme et de la qualité de l’exécution n’est pas encore opérationnel.
Nous venons ainsi de voir que le jeu de rôle a depuis longtemps servi de référence au
développement des jeux vidéo. Il remplit dans un cadre humain les objectifs que nous nous

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

20


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
sommes fixés dans le cadre informatique : proposition d'un jeu permettant la construction d'un
récit interactif autour des actions des joueurs. Il s'agit donc d'une source d'inspiration non
négligeable dans la réalisation d'un système de pilotage pour récit interactif. A partir de
l’observation des mécanismes de construction de récit interactif en jeu de rôle, nous avons
décrit un ensemble de propriétés à respecter pour un jeu à récit interactif :
• Le joueur ne doit pas se sentir contraint par le jeu : Le joueur doit avoir accès à un
ensemble de commandes suffisant pour s’exprimer à travers son avatar dans le jeu.
Ces commandes doivent être persistantes, c'est-à-dire ne pas pouvoir être contrariées
ou inhibées pendant l'exécution. Le joueur doit trouver le résultat de ses actions
cohérent et celles-ci doivent avoir un réel impact sur le déroulement de l’exécution et
son résultat final (la conclusion).
• Le jeu doit proposer un environnement cohérent : Le cadre du jeu doit sembler
suffisamment cohérent au joueur pour permettre son immersion dans le jeu. Les
éléments présents dans le jeu doivent donc suivre des règles de fonctionnement
logiques par rapport au cadre dépeint. Le comportement des entités présentées dans le
jeu doit avoir du sens et être compréhensible par le joueur.
• Le déroulement du jeu doit suivre une structure narrative : S’il existe plusieurs
schémas de narration différents, ils ont en commun de comporter une introduction, un
problème à résoudre, un développement par étapes, une résolution finale et une
conclusion. Une histoire se centre sur un thème principal et se conclue quand son
problème central est résolu (bien que l’on puisse enrichir le récit de problèmes
auxiliaires). Le jeu doit donc proposer un déroulement respectant ce schéma global
d’exécution, ainsi que les spécificités du type de récit choisi.
Nous avons ainsi dans ce chapitre présenté un ensemble de travaux et d’analyses

relatifs aux différents aspects de la narration interactive et le pilote pour la narration
interactive. Tout d’abord, c’est la terminologie de différents concepts délimitant le cadre du
stage, principalement les notions d’histoire, de récit, de narration et de narration interactive.
Et puis, une introduction aux deux approches de jeux étant les jeux dits orientés scénarios et
les jeux dits à narration émergente. Ensuite nous avons étudié les besoins, enjeux et méthodes
mis en œuvre dans le pilote pour la narration interactive comme l’ontologie pour les jeux
vidéo, le système de production et surtout le jeu de rôle qui nous a apporté un modèle de jeu à
récit interactif. Dans le cadre du stage, nous construirons un système avec les telles
fonctionnalités dont l’entrée est des schémas de bigraphes qui sont présentés dans le chapitre
suivant.

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

21


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

CHAPITRE 3 – Brève description sur les bigraphes
La théorie de bigraphe a été développée par James J. Leifer, O. Jensen et R. Milner au
laboratoire Computer de l’université de Cambridge [9, 15, 18, 19]. Un bigraphe est une
structure mathématique destinée à la modélisation distribuée et aux systèmes mobiles. Le
modèle des bigraphes est un calcul de processus permettant la compositionalité (composition
parallèle et composition hiérarchique). Il est un cadre dans lequel les calculs de processus
existants et de nouveaux modèles de comportement peuvent être formulés, en particulier les
réseaux de Petri, le calcul des systèmes communicants CCS (Calculus of Communicating
Systems), le calcul des Ambients et le Pi calcul. Il aide à esquisser la structure et les schémas
d’interaction d’un système composé de plus d’un composant en modélisant sa structure de
localisation, à préciser les dépendances entre des différents composants d’un programme, à
décrire une expression dans des calculs de processus pour modéliser le comportement d'un

système concurrent, et à spécifier une image plus claire de propriétés du système. Ce chapitre
donne une brève présentation sur les bigraphes et un exemple concret illustrant comment
modéliser un système au moyen de bigraphes.

3.1. Notation et convention
On écrit S S’ pour l’union des ensembles S et S’ connus ou supposés être disjoints.
On considère un entier non négatif k comme un ordinal fini k = {0, 1,…, k – 1}. On note par
ORD la catégorie dont les objets sont les ordinaux finis.
Dans un graphe avec les nœuds V et les arêtes E, une arête relie une paire de nœuds.
Un hypergraphe est une généralisation dans laquelle une arête peut joindre n’importe quel
nombre de nœuds. Etant donné un hypergraphe avec l’ensemble des nœuds V et l’ensemble
des arêtes E, chacun des nœuds v ∈ V est associé à un nombre (sa cardinalité) ar(v) qui
indique le nombre de ports qu’il possède. Les ports d’un nœud v constituent un ensemble Pv =
{(v, i) | i ∈ ar(v)}. Ainsi, l’ensemble des ports de l’hypergraphe est PV = v∈VPv. On définit
donc un hypergraphe par un quadruple (V, ar, E, link) où :
• ar : V → ORD qui définit les cardinalités ;
• link : PV → E qui assigne chaque port à une arête.
Par exemple, voici ci-dessous un hypergraphe avec V = {v0, v1, v2, v3, v4, v5}, E =
{e0, e1, e2} où v0 possède 1 port, v1 possède deux ports, v2 possède zéro port, v3 possède
deux ports, v4 possède deux ports et v5 possède un port. Dans une représentation graphique,
les nœuds sont représentés par des cercles, les ports par des taches circulaires (blobs), et
l’arête représente un lien entre les ports :

Figure 3.1. Hypergraphe

3.2. Bigraphe = graphe des places et graphe des liens
Etant donné un hypergraphe avec les nœuds V et les arêtes E, et une forêt (ensemble
des arbres) avec les nœuds V, à partir de ces deux structures complètement indépendantes, on
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI


22


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
construit un bigraphe réduit unique en gardant les nœuds V, les arêtes E et en représentant la
hiérarchie des nœuds dans la forêt par des inclusions des nœuds correspondants dans le
bigraphe réduit. En revanche, un bigraphe réduit avec l’ensemble des nœuds V et l’ensemble
des arêtes E peut évidemment être associé à un hypergraphe avec les nœuds V et les arêtes E,
( (
et une forêt avec les nœuds V. On utilise les notations F , G, … pour ces bigraphes réduits.
(
Voici ci-dessous le bigraphe réduit G ayant l’ensemble des nœuds V = {v0, v1, v2, v3, v4,
v5} et l’ensemble des arêtes E = {e0, e1, e2}, avec sa forêt et son hypergraphe correspondants
(
(des inclusions des nœuds dans le bigraphe réduit G sont représentées par la hiérarchie des
nœuds correspondants dans la forêt) :

(
Figure 3.2. Bigraphe réduit G avec sa forêt et son hypergraphe correspondants
(
(
Maintenant on considère un bigraphe réduit F étant informellement une partie de G
(
(
(on peut l’appeler une sous-structure de G ), c’est-à-dire que F a seulement quelques nœuds
(
de G et un hyperlien « ouvert » comme suit :

(
Figure 3.3. Bigraphe réduit F


(
Ensuite on ajoute les interfaces au bigraphe réduit F pour qu’il devienne un bigraphe
complet F (désormais on l’appelle un bigraphe), on fait cela indépendamment pour sa forêt et
son hypergraphe ; la forêt avec les interfaces s’appelle le graphe des places, l’hypergraphe
avec les interfaces s’appelle le graphe des liens. Il y a deux types d’interfaces : sortantes et
entrantes.
L’interface du graphe des places est normalement l’ordinal fini n = {0, 1,…, n – 1}.
Les interfaces sortantes et entrantes du graphe des places sont respectivement ses racines et
DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

23


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes
sites, ils sont disjoints de ses nœuds. Les racines peuvent être les parents des nœuds et sites
mais il n’y a pas le parent pour eux ; les sites peuvent être les fils des racines et nœuds mais il
n’y a pas le fils pour eux. Les interfaces sortantes et entrantes du graphe des liens sont
normalement des ensembles des noms : respectivement ses noms sortants et entrants. Par
(
exemple, retournons au bigraphe réduit F :
• pour sa forêt, on choisit l’interface sortante 3 = {0, 1, 2} fournissant les racines
distinctes comme les parents des nœuds v1, v3 et v4 ; pour l’interface entrante, on
choisit 0, c’est-à-dire qu’elle n’a pas de sites. On écrit le graphe des places comme FP :
0→3;
• pour son hypergraphe, on choisit l’interface sortante {x y} qui est nommée aux parties
des hyperliens « ouverts », et l’interface entrante Ø, c’est-à-dire qu’il n’a pas
l’interface entrante. On écrit le graphe des liens comme FL : Ø → {x y}.

(

Figure 3.4. Le graphe des places et le graphe des liens du bigraphe réduit F
Le bigraphe est ainsi une paire B = (BP, BL) du graphe des places et du graphe des
liens avec le même ensemble des nœuds, ces deux graphes sont ses constituants. Son interface
sortante est une paire (n, Y), où n et Y sont respectivement les interfaces sortantes de BP et
BL. Son interface entrante est une paire (m, X), où m et X sont respectivement les interfaces
entrantes de BP et BL. Pour notre exemple, F = (FP, FL), ces paires sont respectivement
(3, {x y}) et (0, Ø). On appelle l’interface banale ε = (0, Ø) l’origine. On écrit le bigraphe F :
ε → (3, {x y}) et le dessine comme suit :

Figure 3.5. Bigraphe F : ε → (3, {x y})
Les rectangles dans F représentent ses racines. Le graphe des liens FL possède quatre liens :
deux sont les arêtes e1 et e2 qui s’appellent également les liens fermés, deux autres sont
nommées x et y qui s’appellent les liens ouverts.
(
De même façon, on ajoute les interfaces au bigraphe réduit G pour qu’il devienne le
bigraphe G. Il n’a pas de liens ouverts, c’est-à-dire que tous ses liens sont les arêtes,
l’ensemble des noms dans son interface sortante sera donc vide. On lui donne deux racines
comme les parents de v0 et v4. Voici ci-dessous le bigraphe G et ses constituants :

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

24


Mémoire de fin d’études – Pilote pour la narration interactive : Apport des bigraphes

Figure 3.6. Bigraphe G et ses constituants

3.3. Classification de nœuds par signature et contrôle
Une signature К est un ensemble dont les éléments s’appellent des contrôles. Pour

chaque contrôle M, elle fournit un ordinal fini – cardinalité ar(M).
Les nœuds du bigraphe peuvent appartenir à des types différents. Chacun des nœuds
est assigné à un type, c’est le contrôle. Pour chaque application, on a des contrôles différents,
spécifiés avec leurs cardinalités dans une signature. Par exemple, une signature К = {K : 2, L :
0, M : 1}, où K, L, M sont les contrôles ; et 2, 0, 1 sont respectivement leur cardinalité.
Ainsi, dans n’importe quel bigraphe sur la signature К, la cardinalité d’un nœud est
celle de son contrôle. Si on ne s’intéresse pas au nom v de chacun des nœuds, mais seulement
à son contrôle, on peut omettre son nom dans le bigraphe et le remplacer par son contrôle. Par
exemple, pour les bigraphes F et G ci-dessus, on a :
F : ε → (3, {x y})

G : ε → (2, Ø)

Figure 3.7. Bigraphes F et G avec leurs contrôles

DANG Kim Dung, Option « Intelligence artificielle & multimédia », P13, IFI

25