Day.png);">
Apprendre


Vous êtes
nouveau sur
Oniromancie?

Visite guidée
du site


Découvrir
RPG Maker

RM 95
RM 2000/2003
RM XP
RM VX/VX Ace
RM MV/MZ

Apprendre
RPG Maker

Tutoriels
Guides
Making-of

Dans le
Forum

Section Entraide

Sorties: Star Trek: Glorious Wolf - (...) / Sorties: Dread Mac Farlane - episode 3 / News: Plein d'images cools créées par (...) / Sorties: Star Trek: Glorious Wolf - (...) / Jeux: Final Fantasy 2.0 / Chat

Bienvenue
visiteur !




publicité RPG Maker!

Statistiques

Liste des
membres


Contact

Mentions légales

341 connectés actuellement

29189556 visiteurs
depuis l'ouverture

4607 visiteurs
aujourd'hui



Barre de séparation

Partenaires

Indiexpo

Akademiya RPG Maker

Blog Alioune Fall

Fairy Tail Constellations

Lunae - le bazar d'Emz0

Zarok

RPG Maker VX

Le Comptoir Du clickeur

Guelnika & E-magination

Tous nos partenaires

Devenir
partenaire



Génération procédurale d'un donjon à la Zelda

Un algorithme simple est présenté afin de générer des donjons aléatoires à la Zelda. L'algorithme doit être implémenté dans un langage qui supporte la r&

Ecrit par Roi of the Suisse le 19/11/2014


❤ 1

Génération procédurale d'un donjon à la Zelda




Cet article explique comment générer à partir d'un algorithme simple des donjons comme ceux que l'on peut trouver dans Zelda Link's Awakening :

image


Rappels terminologiques
Je rappelle le sens de quelques termes que j'emploie, au cas où tout le monde ne serait pas familier avec :

Un graphe est un ensemble de points (appelés noeuds) reliés entre eux par des segments (appelés arêtes).
Pour qu'un graphe soit un "arbre", il ne faut pas qu'il comporte un cycle (une boucle).
Une extrémité de l'arbre est parfois appelée feuille. C'est un point qui n'a qu'une arête.
Affine signifie en ligne droite, c'est-à-dire selon une fonction du type y=a*x+b.
On appelle "arbre binaire" un arbre dont chaque noeud a un père (noeud contigu) et deux fils (noeuds contigus aussi), sauf un noeud qui n'a pas de père (appelé racine) et quelques noeuds qui n'ont pas de fils (appelés feuilles).


Présentation de l'algorithme

Le donjon est un ensemble de salles, reliées entre elles par des portes. Il s'agit donc d'un graphe : les salles sont les noeuds et les portes sont les arêtes.
Afin de pouvoir placer les clés et les serrures, nous avons besoin dans un premier temps que le donjon n'ait pas de cycles. Les cycles seront rajoutés en dernier. Nous partons donc d'un arbre :

image

Notre donjon possède deux pôles : S (start) et E (end). On choisira la position de S de préférence à une extrémité de branche, et puis on choisira E de préférence à une extrémité et le plus loin possible de E.

Commençons à présent l'algorithme qui permet de placer les clés et les serrures.
On coupe le graphe en deux, de sorte que S soit d'un côté et E de l'autre :

image

Nous allons placer à la limite un blocage : cela peut être une serrure, une porte fermée reliée à un interrupteur, une énigme qui nécessite l'arme du donjon...
Puis, dans la moitié du graphe qui contient S, il faudra placer l'objet résolvant : la clé, l'interrupteur qui ouvre la porte, l'arme du donjon...

image

Il faudra aller chercher l'objet résolvant dans la première partie du donjon* pour pouvoir accéder à la deuxième partie.
L'idée est ensuite de recommencer cette division sur les deux moitiés obtenues !
La salle de l'objet résolvant devient E', et la salle juste après le blocage devient S' :

image

On re-divise récursivement :

image

Et on ajoute les objets résolvants et les blocages correspondants.
Je conseille de mettre les objets résolvants aux extrémités si possible, afin d'éviter les branches entières de donjon inutiles.

image

On a à présent un donjon valide (= forcément faisable).

Cet algorithme est récursif, je propose d'arrêter la division selon une fonction "probabilité de continuer". Si le bout de donjon dont on considère l'éventuelle division est petit (moins de 2 salles) on s'arrête forcément (probabilité 0). Si le bout de donjon est grand (plus de 6 salles) on le divise forcément (probabilité 1). Entre les deux on peut faire une probabilité affine ou bien juste mettre un nombre aléatoire qui vaut 0 ou 1.


Quelques remarques

La première division à effectuer doit être la serrure du boss (et son objet résolvant la clé du boss). Cette première division ne se fait pas n'importe où : elle doit se faire juste avant la dernière salle (E).
Les autres divisions peuvent se faire n'importe où sur le chemin allant de S à E.
Je conseille cependant après la division du boss de procéder à la division de l'arme du donjon, et de placer cette division à peu près au milieu du chemin allant de S à E.

Quand je dis "placer les objets résolvants en priorité à une extrémité", on peut se demander : comment savoir si une salle du donjon est une extrémité ?
C'est tout simplement une salle qui n'a qu'une seule porte.

Les objets facultatifs présents dans les donjons à la Zelda, comme par exemple la carte, la boussole ou des trésors bonus (argent, objet collectionnable...) peuvent être placés en priorité dans les extrémités inutilisées (par un objet résolvant) afin que ces salles soient utiles. Ensuite le reste de ces objets facultatifs peut être disséminé un peu partout.


Pour aller plus loin 1 : généralisation du placement des objets résolvants

Le lecteur attentif remarquera que la clé tout à gauche (dans la zone bleu clair) qui permet d'accéder à la zone bleu foncé aurait très bien pu être placée dans les zones vertes.
Qu'est-ce que cela signifie ?
Cela signifie que l'objet résolvant n'est pas forcément dans la moité inférieure de son bout de donjon, la seule chose qui importe c'est que l'objet résolvant soit avant son blocage.
Vu que la zone bleu clair est après la ligne verte, elle est après les zones vertes.

On doit placer l'objet résolvant dans une zone antérieure au blocage. Certes. La question qui se pose alors est : comment savoir si une zone du donjon est avant une autre ?
Modélisons notre découpage du donjon par un arbre binaire : la première division, celle qui coupe le donjon en deux, est la racine et les deux moitiés de donjon obtenues sont ses fils. Ensuite, vu qu'on divise chaque moitié, ces moitiés auront aussi deux fils, et cetera. Cet arbre contient donc toutes les zones du donjon à toutes les échelles possibles. Le fils gauche sera la partie avant le blocage et le fils droit la partie après le blocage.
Je propose alors une numérotation des zones :
- La racine possède pour valeur "2 puissance son altitude". Ici l'altitude est 2 donc sa valeur est 4.
- Quand un noeud obtient une valeur, il transmet sa valeur à son fils droit. On a maintenant trois noeuds avec la valeur 4.
- Pour un noeud sans valeur (le noeud n'est pas la racine et n'est pas le fils droit de son père) la valeur est la valeur du père (dont il est le fils gauche) moins 2 puissance l'altitude. On obtient donc 4-2^1=2 au milieu à gauche ; 2-2^0=1 en bas à gauche ; 4-2^0=3 en bas au milieu.

image
sur ce schéma les noeuds représentent les zones et non plus les salles

Pour bien lire cet arbre binaire : les noeuds sont des zones ; les feuilles (en bas) sont les zones minimales ; une zone comporte un ensemble de salles ; un noeud non-feuille a pour salles les salles de ses deux fils.

Vu qu'on a besoin de l'altitude pour donner une valeur à chaque zone, cela doit se faire une fois que l'algorithme de division du donjon est terminé.

On peut maintenant dire si une zone se trouve avant un blocage, et donc y mettre l'objet résolvant.
L'objet résolvant doit donc être placé dans une zone minimale :
- à la valeur inférieure strictement à celle de son blocage
- qui est un fils gauche.


Pour aller plus loin 2 : les cycles et les passages à sens unique

L'arbre est le squelette du donjon. Il est maintenant possible, pour rendre le donjon plus naturel, d'y ajouter des cycles.

Ajout d'un cycle

La présence de cycles rend le donjon plus facile. J'aurais donc tendance à déconseiller le cycle, qui provoque l'inutilité de certaines salles du donjon. Donnez à ce phénomène une faible probabilité.

Si deux salles sont :
- géographiquement côte-à-côte (une coordonnée en commun, et l'autre coordonnée diffère de 1)
- séparées par un mur
- dans la même zone minimale (considérer les feuilles)
Alors on a le droit d'ouvrir le mur.

Respecter ces règles est très important pour ne pas quitter la structure du donjon décidée pendant l'algorithme.

image

Ajout d'un passage à sens unique :

Peut être utilisé pour :
- rendre le donjon plus labyrinthique
- permettre au joueur de revenir facilement dans les premières zones du donjon

Si deux salles sont :
- géographiquement côte-à-côte (une coordonnée en commun, et l'autre coordonnée diffère de 1)
- séparées par un mur
- la zone minimale (considérer les feuilles) de la salle A est avant (ou égale à) la zone minimale de la salle B
Alors on peut faire un chemin à sens unique allant de B vers A.

Respecter ces règles est très important pour ne pas quitter la structure du donjon décidée pendant l'algorithme. Le non-respect de ces règles peut déboucher sur un donjon infaisable !

image

Le passage à sens unique peut être modélisé par une porte qui se referme juste derrière le héros, ou encore par la possibilité de sauter d'une petite falaise qui empêche de remonter.
J'aurais tendance à davantage préconiser le passage à sens unique par rapport au cycle.


Pour aller plus loin 3 : pouvoir forcément accéder à tout le donjon

Certains l'auront remarqué, le donjon exemple qui sert à expliquer l'algorithme peut être résolu de plusieurs façons différentes. Il est notamment possible d'utiliser la première clé pour accéder directement à la deuxième moitié du donjon (bleue), sans avoir à faire le deuxième quart du donjon (vert clair). Il est alors possible de finir le donjon sans pouvoir jamais visiter le deuxième quart du donjon.

Ce phénomène sera d'autant plus fréquent qu'on n'utilisera pas le "Pour aller plus loin 1".
Ce phénomène sera d'autant plus fréquent qu'on n'alternera pas la nature des blocages (serrure, porte qui s'ouvre grâce à un interrupteur, énigme impossible à résoudre sans l'arme du donjon...).

Pour corriger ce problème, il suffit d'ajouter les clés manquantes dans la toute dernière zone du donjon. Ainsi, quand le joueur aura fini le donjon, il pourra toujours revenir en arrière pour explorer les salles qu'il a évitées.
C'est la solution utilisée par le donjon-designer de Zelda Link's Awakening dans le cadre du donjon 3. Ce donjon, la "cave aux clés", peut être terminé sans avoir exploré plusieurs zones situées derrière des serrures. A la fin du donjon, le donjon-designer offre au joueur des clés pour lui permettre d'aller explorer ces zones facultatives du donjon. Le joueur se retrouve alors forcément avec des clés en trop une fois le donjon totalement exploré.
Si le fait d'avoir des clés en trop à la fin du donjon vous dérange, vous pouvez faire en sorte que les coffres ne donnent plus de clés une fois que toutes les portes du donjon ont été ouvertes. Remplacez par exemple les clés par un objet bonus inutile.


Pour aller plus loin 4 : salles subdivisées

La grande force des donjons de Zelda Link's Awakening est la subdivision des salles de ses donjons. J'entends par là que très souvent la salle est découpée en deux (ou plus !) zones hermétiques.

image

En quoi est-ce important ?
Cette simple caractéristique augmente considérablement le plaisir de résolution du donjon à partir d'un phénomène psychologique bien connu en game-design. Le joueur, en arrivant dans une salle subdivisée, aperçoit la zone de la salle à laquelle il ne peut pas accéder. Dans cette zone pour le moment inatteignable se trouve peut-être même un coffre ou d'autres bonus. Cela va créer un micro-but chez le joueur. La frustration de ne pas pouvoir accéder immédiatement à cette zone qu'on lui montre va faire qu'il va chercher à y aller.
Ce bête phénomène est le moteur principal de l'exploration ; le joueur n'a pas de raison d'agir à la base, c'est donc au game-designer de lui donner des buts, et ceci est la façon la moins artificielle de mouvoir le joueur. Une façon artificielle étant par exemple de dire au joueur "il faut que tu ailles là-bas pour des raisons scénaristiques".
Les donjons du jeu Binding of Izaac ne possèdent pas cette caractéristique et en font à mon sens de bien piètres donjons par rapport à ceux de Link's Awakening.

Pour faire un donjon à salles subdivisées comme dans Link's Awakening, il suffit de générer un donjon 4 fois plus grand pour ensuite coller les salles 4 par 4 :

image

Comment obtenir l'arbre des salles du début ?

Pour obtenir l'arbre des salles reliées, je propose le mini-algorithme suivant.

On part d'une case qui sera une salle centrale du donjon.
Il y a alors 4 possibilités pour étendre notre donjon : en haut, en bas, à gauche, à droite. Donnons une probabilité de 1/4 à l'ouverture de ces murs :

image

Une fois le choix fait, notre donjon s'agrandit d'une salle.
Il y a maintenant 6 possibilités pour étendre notre donjon :

image

Faisons un choix avec une probabilité de 1/6 pour chaque mur externe :

image

Je choisis de m'arrêter à un donjon de 12 salles :

image

On peut choisir la forme globale du donjon à l'avance en fixant un contour que le donjon n'a pas le droit de dépasser durant son expansion. On demande alors à ce mini-algorithme exactement le nombre de salles de l'intérieur du contour limite.

Finalement, en appliquant le grand algorithme présenté au début de cet article, notre donjon devient :

image



Nemau - posté le 19/11/2014 à 20:10:34 (52129 messages postés) - honor -

❤ 0

The Inconstant Gardener

T'as viré le passage où tu dis que je vais hurler donc c'est nul. =>[]



Quel RPG Maker choisir ?Ocarina of Time PCPolaris 03 • Le matérialisme c'est quand tu as du matériel.


Joke - posté le 19/11/2014 à 22:52:57 (5089 messages postés)

❤ 0

Bilouteux fou

Excellent et intéressant ! :sourire3

biloumaster.fr, mon joli site ouèb tout bô tout frai !


verehn - posté le 20/11/2014 à 21:43:15 (9054 messages postés) - honor

❤ 0

Vhehrhehn

Sympa que tu aies pensé à passer tout ça en article. :plusun

Eldrao ~ PakuPaku ~ Winged Light ~ Ruin ~ Ma galerie ~ LTDAD ~ Don de graphismes plateforme 2D

Suite à de nombreux abus, le post en invités a été désactivé. Veuillez vous inscrire si vous souhaitez participer à la conversation.

Haut de page

Merci de ne pas reproduire le contenu de ce site sans autorisation.
Contacter l'équipe - Mentions légales

Plan du site

Communauté: Accueil | Forum | Chat | Commentaires | News | Flash-news | Screen de la semaine | Sorties | Tests | Gaming-Live | Interviews | Galerie | OST | Blogs | Recherche
Apprendre: Visite guidée | RPG Maker 95 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker MV | Tutoriels | Guides | Making-of
Télécharger: Programmes | Scripts/Plugins | Ressources graphiques / sonores | Packs de ressources | Midis | Eléments séparés | Sprites
Jeux: Au hasard | Notre sélection | Sélection des membres | Tous les jeux | Jeux complets | Le cimetière | RPG Maker 95 | RPG Maker 2000 | RPG Maker 2003 | RPG Maker XP | RPG Maker VX | RPG Maker VX Ace | RPG Maker MV | Autres | Proposer
Ressources RPG Maker 2000/2003: Chipsets | Charsets | Panoramas | Backdrops | Facesets | Battle anims | Battle charsets | Monstres | Systems | Templates
Ressources RPG Maker XP: Tilesets | Autotiles | Characters | Battlers | Window skins | Icônes | Transitions | Fogs | Templates
Ressources RPG Maker VX: Tilesets | Charsets | Facesets | Systèmes
Ressources RPG Maker MV: Tilesets | Characters | Faces | Systèmes | Title | Battlebacks | Animations | SV/Ennemis
Archives: Palmarès | L'Annuaire | Livre d'or | Le Wiki | Divers