tito

Suite à une augmentation notable mon activité professionnelle, je suis dans l'incapacité de poursuivre la rédaction d'articles pour le moment.

Dès que cela ce sera un peu calmé, je reprendrai en main ce blog.

Les fondamentaux relatifs à l'écriture d'un scénario de jeu vidéo restent les mêmes que pour d'autres supports, comme les livres ou les films. La seule vraie différence est la possibilité que peut avoir le scénariste, de profiter de l'aspect interactif du jeu, pour proposer une trame plus complexe. Mais il dispose aussi d'une contrainte supplémentaire : tous les scénarios n'ont pas le même rendu en fonction du jeu auquel ils sont destinés.

Dans l'absolu, le scénario se base donc sur une ou plusieurs intrigues, qui se suivent ou se déroulent en parallèle. Chaque intrigue se décomposant elle-même en trois étapes distinctes :

- La pose du problème : il s'agit dans un premier temps d'amener l'intrigue au joueur, ou le joueur à l'intrigue. Cette phase initiale doit permettre au joueur de prendre conscience de la mission qui lui incombe. Celle-ci peut-être plus ou moins progressive en fonction du type de jeu. Dans un jeu de baston, l'intrigue ne constitue pas un élément clef du jeu, il sera généralement formalisé par des cinématiques : le joueur sera rapidement et relativement brutalement confronté à cette dernière. Par contre, dans un RPG, la mise en place de l'intrigue peut-être beaucoup plus progressive, passant par la collecte d'informations, la rencontre avec des PNJ ou des évènements particuliers.

- La réalisation de l'intrigue : cette phase, généralement la plus développée, est une phase pendant laquelle le joueur va collecter des informations complémentaires sur l'intrigue afin de lui trouver une solution. L'accent peut être mis autant sur la recherche de la solution que sur ça mise en oeuvre. Là encore, le type de jeu auquel est destiné le scénario va influencer le contenu : pour un jeu orienté action, la phase de recherche de solution sera généralement plus simple, alors que pour un jeu plus porté sur la réflexion, la phase de recherche sera nettement plus développée, tout cela tenant au fait que le gameplay et les possibilités d'actions entre ces jeux sont différents.

- La conclusion : la conclusion de l'intrigue sert à poser la nouvelle situation. Elle doit surtout permettre au joueur de comprendre s'il a réussi ou échoué dans sa mission. Tout comme pour la première phase de l'intrigue, cela peut se faire plus ou moins en douceur en fonction du jeu : une cinématique montrant le joueur victorieux peut-être suffisante, mais proposer au joueur de parcourir un monde libéré ou de constater sa notoriété auprès de PNJ peut-être plus valorisant.

La structure la plus employée est celle de l'intrigue principale, fil conducteur du jeu, autour de laquelle viennent graviter des intrigues secondaires, avec un rapport plus ou moins ténu avec l'intrigue principale, et devant participer à l'immersion du joueur.

Voici, plus ou moins brut, la structure d'un fichier bitmap (BMP).
Un second article viendra en complément pour éclaircir certains points.

Octets 1-2 : Signature
Elle permet d'identifier l'origine ou la nature du BMP. Les valeurs admises sont les suivantes :
- BM pour une image Bitmap Windows.
- BA pour une image Bitmap OS/2.
- CI pour une une icone couleur OS/2.
- CP pour un pointeur de couleur OS/2.
- IC pour une icone OS/2.
- PT pour un pointeur OS/2.

Octets 3-6 : taille du fichier.
Il s'agit de la taille totale du fichier, exprimée en octets.

Octets 7-10 : doivent être à 0.

Octets 11-14 : offset de l'image
Cela correspond à  la taille de la première partie du fichier, y compris la palette, jusqu'au début du codage de l'image proprement dite.

Octets 15-18 : nombre d'octet jusqu'à la palette, ou l'image s'il ny a pas de palette.

Octets 19-22 : largeur de l'image en pixels.

Octets 23-26 : hauteur de l'image en pixels.

Octets 27-28 : nombre de plans.
Cette valeur est toujours 1.

Octets 29-30 : nombre de bits servant au codage de la couleur dans l'image.
Les valeurs admises sont 1, 4, 8 et 24.
Avec :
1 pour une image monochrome
4 pour une image en 16 couleurs
8 pour une image en 256 couleurs
24 pour une image en 16 millions de couleurs, on ne compte pas l'octet réservé (voir ci-dessous)

Octets 21-34 : type de compression.
Les valeurs admises ont les suivantes :
0 : pas de compression
1 : codage RLE de 8 bits par pixel
2 : codage RLE de 4 bits par pixel
3 : codage bitfields

Octets 35-38 : taille de l'image proprement dite en octets, soit le nombre d'octets entre la fin de l'entête s'il ny a pas de palette, ou la fin de la pallette, jusqu'à la fin du fichier.

Octets 39-42 : résolution horizontale, en pixels par mètre, peut-être laissé à 0

Octets 43-46 : résolution verticale, en pixels par mètre, peut-être laissé à 0

Octets 47-50 : nombre de couleurs de la palette.

Octets 51-54 : nombre de couleurs importantes de la palette.

[palette de couleurs, sauf pour les images en 16 millions de couleurs et les  monochromes]
octet 1 : codage du bleu.
octet 2 : codage du vert.
octet 3 : codage du rouge.
octet 4 : réservé.

[Image 2 monochrome]
bit 1 : référence pour la couleur du premier pixel.
bit 2 : référence pour la couleur du deuxième pixel.
....

[Image 16 couleurs]
bits 1-4 : référence dans la palette pour la couleur du premier pixel.
bits 5-8 : référence dans la palette pour la couleur du deuxième pixel.
...

[Image 256 couleurs]
octet 1 : référence dans la palette pour la couleur du premier pixel.
octet 2 : référence dans la palette pour la couleur du deuxième pixel.
...

[Image 16 millions de couleurs]
octet 1 : codage du bleu.
octet 2 : codage du vert.
octet 3 : codage du rouge.
octet 4 : réservé .

I- L'intégration des méthodes d'apprentissage

Même avec un jeu particulièrement 'instinctif', comme peuvent l'être par exemple bon nombre de petits jeux Flashs que l'on trouve sur le net, il est toujours utile de guider le joueur dans ses premiers pas afin qu'il profite rapidement de la meilleure expérience possible du jeu : la gestion de l'apprentissage est donc un facteur clé pour un jeu, et cela à au moins deux niveaux :
- pour les jeux 'gratuits' : abandonner le jeu n'est pas coûteux pour le joueur, il faut donc prendre soin de soigner son apprentissage afin qu'il continue à y jouer.
- pour les jeux 'complexes' : ne pas donner accès à certaines informations sur le fonctionnement du jeu peut le rendre incompréhensible ou handicaper trop gravement le joueur qui ne les auraient pas découvertes ou apprises par l'expérience, avec au final un mauvais point pour l'équipe ayant produit le jeu et un a priori négatif pour ces prochaines productions.

Des livres ont été écrits sur le sujet, des débats sont encore ouverts... Il existe de nombreuses méthodes d'apprentissage différentes, toutes disposant de leurs avantages et de leurs inconvénients. Cela ne sera pas débattu dans cet article.

Il y a toutefois quelques points à mettre en avant. D'une part, l'apprentissage est une phase obligatoire pour le joueur, quelle que soit sa forme, afin qu'il maîtrise le jeu. D'autre part, l'efficacité d'une méthode d'apprentissage est à mettre en rapport avec le contexte dans lequel elle est appliquée : faire apprendre une table de multiplication "par l'expérience" ne parait pas très judicieux, tout comme faire apprendre des notions de relations sociales par du "par coeur".

Un point constituant un plus pour le jeu est donc la bonne intégration des méthodes d'apprentissage dans celui-ci, car bien gérée, elles vont aider le joueur à s'immerger progressivement dans le jeu.
Généralement les phases d'apprentissage se font dans les premiers 'niveaux' du jeu, alors que la difficulté est moindre. Les erreurs sont donc moins chèrement payées. Attention, cela n'est pas une raison pour négliger les conséquences de ces dernières.

Par exemple, dans un jeu de rôle, le joueur vient de passer une petite heure à se créer un personnage sur mesure, explorant les fonctionnalités du générateur de personnages. Le didacticiel se déroule sur un bateau et le joueur décide de monter à la vigie, il fait une fausse manipulation et son personnage tombe sur le pont et meurt. Il serait dommage de ne pas avoir prévu une sauvegarde automatique à la fin de la création du personnage... 

Autre exemple avec un jeu disposant d'un ladder, le joueur fait des essais, apportant peu d'importance à ses scores... Quelle déception quand il découvrira que ces 'essais' ont été comptabilisés et pénaliseront sont classement.

II- Les méthodes d'apprentissage

Les principales méthodes répertoriées sont donc les suivantes :

Apprentissage par imitation :
Il s'agit de montrer au joueur ce qu'il doit faire pour quel résultat : le jeu manipule les périphériques d'entrées (clavier, pad, souris) à la place du joueur pour lui montrer comment opérer. Idéalement, pour le clavier ou le pad, le jouer aura à l'écran une représentation de ces derniers et pourra visualiser les combinaisons de touches / boutons utilisées.

Apprentissage par essais et erreurs :
Le joueur se crée sa propre expérience. Généralement, cela se fait dans les premiers niveaux du jeu où le joueur est relativement 'Protégé' et peu donc tester à loisir les fonctionnalités du jeu sans grand risque. Il s'agira aussi d'orienter le joueur en restreignant ses possibilités au domaine de connaissances que l'on souhaite lui faire acquérir.

Apprentissage par explication :
Il s'agit ni plus ni moins que d'expliquer au joueur comment procéder. Cette méthode est généralement présente sous la forme d'une aide, mais on la retrouve aussi parfois disponible sous la forme de livres, parchemins ou autres supports de lecture, ou encore sous la forme de dialogues avec des PNJ. Les info-bulles font aussi parties de l'apprentissage par explication.

Apprentissage par répétition :
Le joueur est invité à répéter de multiples fois la même action jusqu'à la maîtriser suffisamment. Cette méthode apparaît souvent sous la forme d'un mode de jeu de type 'Entraînement' et est principalement utilisée dans les jeux de baston pour l'apprentissage de combinaisons de boutons.

Apprentissage combiné :
Il ne s'agit pas à proprement parler d'une méthode. L'idée est simplement de combiner les méthodes listées ci-dessus afin d'optimiser l'apprentissage.
Le schéma suivant montre les principales combinaisons rencontrées.

Bien souvent, il est nécessaire lorsque l'on réalise un jeu, de mettre en place un algorithme de pathfinding. Le plus connu d'entre eux est probablement le A* (prononcer ''A' star').

1- Principes

Les prérequis indispensables à l'utilisation de cet algorithme sont :
-  de formaliser la zone à parcourir sous la forme d'un réseau. Ce dernier peut se présenter sous la forme d'une grille, mais ce n'est pas une obligation. Il va de soit que chaque noeud de ce réseau doit permettre de trouver les noeuds avec lesquels il a un lien.
- connaître le noeud de départ et le noeud d'arrivée.

On utilisera aussi deux listes :
- une liste 'ouverte' : qui contiendra tous les noeuds accessibles depuis le noeud de départ.
- une liste 'fermée' : qui contiendra la liste des tous les noeuds qui ont déjà été étudiés.

Chaque liste contiendra : l'identifiant du noeud, l'identifiant du noeud précédent, un coût.

Le déroulement est très simple :
- En partant du noeud de départ, on identifie les noeuds voisins.
- Pour chaque noeud voisin, on calcule un coût constitué du coût pour atteindre le noeud précédent, plus le coût pour aller du noeud précédent à ce noeud.
- On passe le noeud de départ dans la liste des noeuds 'fermés', et ses noeuds voisins dans la liste des noeuds 'ouverts'.
- Ensuite, dans la liste ouverte, on étudiera le noeud ayant le coût le plus faible . Il faudra aller chercher ses noeuds voisins. Si le noeud voisin est dans la liste 'fermée', il a déjà été étudié et est donc ignoré : le nouveau coût calculé sera forcément au moins égal, voir supérieur.
Sinon, il faudra en calculer le coût associé :
Si le noeud voisin est dans la liste 'ouverte', et que le nouveau coût calculé est inférieur au dernier enregistré, on met à jour la liste avec le nouveau coût, et on change l'identifiant de son noeud précédent pour le noeud étudié.
Si le noeud voisin est dans la liste 'ouverte', mais que le nouveau coût calculé est supérieur au dernier enregistré, on ne change rien.
Si le noeud voisin n'est dans aucune des listes, on le passe dans la liste ouverte.

On arrête la recherche lorsque le noeud de destination est trouvé, il est alors à son tour passé dans la liste 'fermée', ou qu'il n'y a plus de noeud dans la liste ouverte. Dans ce dernier cas, cela signifie qu'il n'y a pas de chemin permettant d'aller du noeud de départ au noeud d'arrivée.

Au final, s'il existe un chemin, on obtient une liste chaînée des différents noeuds à parcourir.

L'A star permet de toujours trouver le chemin le plus court en terme de coûts.

2- Calcul des coûts

Le coût pour passer d'un noeud à un autre n'est pas forcément une constante unique à tous les noeuds : il pourra varier en fonction de différents critères.
Dans un RTS, s'agissant de parcourir une carte, on trouvera généralement une variation du coût en fonction du terrain à parcourir, de la météo, de la nature de l'unité,.... Par ailleurs, il peut aussi être pertinent de tenir compte de facteurs comme la dangerosité de certaines zones ou leur éloignement.

3- Optimisation de la recherche

3.1 Heuristique et A star

A la base, nous avons vu que la liste ouverte se parcourait dans l'ordre croissant des coûts. Le but va être de prendre en compte d'autres critères que le simple coût du chemin parcouru pour choisir la séquence des noeuds à étudier dans la liste 'ouverte', afin de privilégier un chemin 'probablement' plus court.

Il faudra toutefois être particulièrement attentif au fonctionnement de la liste fermée : ne doivent se trouver dans cette liste que les noeuds dont le coût est définitivement acquis. Dans le cas contraire, il faudrait non seulement mettre à jour ce noeud, mais aussi recalculer tous les coûts de tous les noeuds dont le chemin passerait par un noeud ayant fait l'objet d'une réévaluation de son coût suite à ce simple changement.

Outre ce point, il y a de fortes probabilités pour qu'une heuristique mise en place sur un algorithme comme le A star ne fournisse plus systématiquement le chemin le plus court, mais un chemin parmi d'autres.

3.2 Maillage

Un des inconvénients de A star est que sur des réseaux de grandes tailles, et plus particulièrement des cartes, son temps d'exécution va augmenter de façon disproportionnée.

Une autre méthode pour optimiser la recherche, s'appliquant plus particulièrement à la recherche de chemin sur une carte, consiste donc à calculer à l'avance les coût relatifs à des points particuliers de la carte.
L'algorithme sera alors utilisé trois fois successivement : une première fois pour estimer le trajet du point de départ vers un premier noeud particulier, une deuxième pour aller du point de destination vers un second point particulier, et une troisième fois pour rejoindre les deux points particuliers.

Ci dessous, en jaune, la zone approximativement étudiée avec le A star standard : on remarque que la recherche couvre une grande partie de la carte, et que le chemin trouvé est très optimisé.


A l'opposé, avec le maillage, la surface de recherche est beaucoup plus réduite. D'autre part, le maillage permet d'élargir un peu le chemin trouvé si le besoin s'en fait sentir.


Là encore, il faut savoir adapter en fonction de ses besoins.

3.3 Perfection et réalité

Comme indiqué, l'A star permet de toujours trouver le chemin le plus court en terme de coût. Or, dans la réalité, lorsque l'on cherche son chemin, on ne trouve que très rarement le parcourt optimal au premier essai : ainsi conçu, cet algorithme ne permet d'avoir cette sensation d'hésitation dans la recherche.

Il peut donc être intéressant, par exemple, de diviser la recherche en plusieurs étapes successives en fonction de l'éloignement du point d'arrivée ou de la vision du réseau qu'en a l'objet cherchant son chemin. Une illustration simple de cette problématique est la gestion d'un brouillard de guerre : il parait inconcevable de rester sur une solution où une unité irait directement au but dans une zone non découverte, en évitant des troupes ennemies qu'elle ne voit pas et en contournant des obstacles invisibles.