Du procédural en jam: l'algorithme Tetedanslecube

Bon bon bon, tarte au quetsche est sorti, faut vraiment que je lui trouve un autre nom, et j'pense à l'améliorer en un jeu "mieux". Mais avant ça j'ai envie de revenir sur un petit élément qui donne son sel à mon jeu, qui fait qu'on à envie d'y retourner deux ou trois fois...

La génération procédurale.

Parce que oui, la génération procédurale d'une map, pendant une game jam, c'est possible. Et même, c'est facile.

Alors d'abord:

-----------LA GENERATION PROCEDURALE, POURQUOI?-----------

Certes quand le temps vient à manquer et que le désespoir règne lorsqu'on s'aperçois de la quantité de la tache que nous nous convions soit même face à l'ampleur de la petitesse du temps alloué, il sembler l'ultime évidence que de se dire "Ouais nique ça, j'vais faire une map classique". Et ça aurais ses avantages, mais aura l'inconvénient que le jeu n'aurais que peu d'intérêt à être joué plus d'une fois.

Aussi, se lancer dans la génération procédural peut-être une solution pour que les joueurs aient autant de votre jeu qu'ils peuvent le souhaiter.

En plus, comme nous le verrons si dessous, une bonne génération procédurale permet pas mal de souplesse, et est assez simple à programmer. Il suffit donc de savoir précisément ce qu'on veux pour notre jeu, et en l'occurence...

-----------QUELLE GENERATION POUR TARTE AU QUETSCHE?-----------

Pour savoir quelle faire une bonne génération procédurale, le secret, c'est de tout prévoir en avance. Savoir exactement ou on va permet de savoir exactement comment y aller.

Pour mon jeu, le concept est assez simple:

Il y as 4 zones de couleur differente, avec chacune 9 salles présente, choisi parmi un pool de 20 salles possibles (réduites à 10 ensuite pour des questions de temps), et un boss par zone (qui sera remplacé par un autel avec une clef, pareil, question de temps).

Et je souhaite que le jeu donne une sensation de labyrinthe, sans en être vraiment un.

La carte sera donc un carré de 6*6, avec deux murs ajouté dans chaque zone afin de rendre le tout clair mais sans être entièrement ouvert, et pour éviter les situations impossibles, chaque salle doit permettre une sortie dans chacune des direction, et un maximum d'un mur par salles (hors bords) est placé.

C'est fort joli, on à notre concept, c'est un bon début.

-----------ON NE PLANTE PAS UN CLOU AVEC UNE SCIE-----------

Pour se simplifier le travail, le mieux à faire, d'abord, c'est de bien choisir ses outils.

Et pour faire une carte, en général, rien de mieux que de faire un tableau à deux dimension. Sur game maker, on à le choix entre DS list et Array, la premiere est idéal quand on ne sait pas la taille de la liste, donc on va utiliser la seconde. Il nous faudra aussi noter si une salle à déjà était finie ou non.

Ensuite, qu'est-ce qu'on va mettre dedans? C'est simple: un niveau, c'est une salle choisie entre 0 et 9, et un certain nombre de portes.

Pour la salle, un entier aléatoire pour chaque salle suffira pour l'instant. Le problème est qu'il est probable d'avoir deux fois la même salle, ce qui peut être réglé facilement en retirant tout les nombres déjà tiré dans une zone donnée.

Pour les portes, deux solutions s'offrent à nous:

Le premier cas consiste à donner un nombre entre 1 et 10 qui correspond à lâ présence ou non d'un mur. 0 représente une salle sans mur, 1 à 4 un seul mur, 5 et 6 un couloir, et 7 à 10 une salle avec une seule porte. Cela pose trois problèmes:  

1) de manière générale, on ne peux pas avoir de diagonales. Une autre solution serait donc de généré à la place une valeur entre 0 et 3 pour les entier et une entre 1 et 4 pour les décimales, avec 1 = pas de mur, 2 = mur en haut/gauche, 3 = mur en bas/droit et 4, deux murs, et ensuite les parties entieres représentes les horizontales et les décimales les verticales. Un 4.4 et un 0 sont des salles inexistantes. Mais c'est long à faire, rend la génération bien plus complexe, et ne serait pas très utile ici.

2) beaucoup de cas ne nous servirais à rien, car les bords peuvent être géré via la proximité d'une bordure de la map, et les murs placé procéduralement ne peuvent être qu'un seul.

3) cela demanderais de faire un troisième tableau juste pour savoir si la salle à était, ou non, finie.

Une autre possibilité c'est de simplifier se format, et de se contenter de retenir un nombre entre 0 et 4, 0 n'ayant pas de mur, et les autres indiquant la place du mur, et si la salle à était complété, ajouter 5 au chiffre de la porte.  C'est quand même plus clair, moins de cas impossibles sont pris en comptes d'office, et on à un tableau de moins à gérer. C'est donc le cas que je vais prendre.

-----------PASSONS A LA PRODUCTION-----------

La production se fait en 6 étapes assez simples.

La première, c'est de créer 10 salles dans game maker par environnement, et de les nommer selon une nomenclature fixe. J'ai opté pour "couleurChiffre", avec la couleur remplacé par "minus" pour les salles spéciales. Ca nous donnes des noms comme "Red1", "Minus5" ou "Green9". Chacune des salles doit contenir 4 portes, une de chaque coté. 

Ensuite, on crée un objet qui servira à stocker les array, qui n'est créer qu'une et une seule fois au lancement du jeu, et qui est persistant. Je l'ai appelle "o_mapMaker" parce que l'originalité c'est pour les fan d'ori and the blind ginale.

La seconde, c'est de générer le tableau des salles, quand on lance la partie. Ca donne quelque chose du style:

/*on met à 0 carte contenu*/
cartecontenu[0, 0] = 0;
/*on va passer dans chaque zone une fois*/
for (k = 0; k < 4; k = k + 3;)
{
for (l = 0; l < 4; l = l + 3;)
{
/*On creer une liste des chiffres déjà placé*/
list = ds_list_create();
/*On passe une fois dans chaque salle, dans le sens de la lecture*/
for (i = 0; i < 3; i++;)
{
for (j = 0; j < 3; j++;)
{
/*On génère une valeur, et tant qu'elle est déjà placée on en regénère une autre*/
mavaleur = irandom_range(0,9);
while (ds_list_find_index(list, mavaleur) != -1)
{
mavaleur = irandom_range(0,9);
}
/*Une fois qu'on à une valeur non placée, on la met dans la salle à laquelle on est arrivée, puis on stocke la valeur placer dans la liste des valeurs placées*/
ds_list_add(list, mavaleur);
cartecontenu[i+k, j+l] = mavaleur;
}
}
/*On détruit la liste des valeurs déjà placées*/
ds_list_destroy(list)
}

Notez que pour la liste des valeurs déjà placée, j'ai utiliser une dslist pour pouvoir facilement grandir le nombre de salles sans changer trop de code, et que le nombre de salle plaçable *doit* être au moins égale au nombre de salles à placer.

La troisième: on va placer les salles spéciales. On ne les places que maintenant afin qu'elles ne soient pas remplacées par un autre salle. Cela se fait manuellement, ainsi, la prochaine ligne de mon code, par exemple, est:

cartecontenu[0, 0] = -1;

Car ma salle de début, fixe, est la salle "-1", qui est toujours en haut à gauche. Il est possible de mettre un peu d'aléatoire la dedans aussi, mais comme dit juste au dessus, c'est du cas par cas.

La quatrième consiste à construire la table des portes, en la mettant à 0. La c'est assez simple:

cartemursetfin[0, 0] = 0;
for (i = 0; i < 6; i++;)
{
for (j = 0; j < 6; j++;)
{
cartemursetfin[i, j] = 0;
}}

Un remplissage basique de tableau à deux dimension.

La cinquième est de loin la plus complexe, mais reste relativement simple quand on y vas étape par étape: pour chaque zone, deux fois, on va tirer aléatoirement une salle et un nombre entre 1 et 4. Si la salle peux se voir attribuer le mur qu'indique le nombre, c'est a dire si la salle adjacente dans la direction indiqué existe, est dans la même zone, et à la valeur 0, alors on place le mur indiqué dans cette salle et le mur inverse dans la salle adjacente dans la direction indiqué, sinon on recommence le tirage de nombre aléatoires.

Dit comme ça, sa parrait complexe, mais dans les faits, c'est surtout un peu long. Voici le code final:

/*pour chaque zone*/
for (i = 0; i < 4; i = i+3;)
{
for (j = 0; j < 4; j = j+3;)
{
k = 0 // k contiendra le nombre de mur déjà placé. Ici, on s'arrete une fois deux murs posé. 3 risquerais de créer des situations inextriquables.

while (k < 2) 
{
/*on génère une position x et y aléatoires dans la zone indiquée*/
choosedX = irandom_range(i+0,i+2); choosedY = irandom_range(j+0,j+2);
if cartemursetfin[choosedX, choosedY] == 0 //si la zone choisie est vide
{
cartemursetfin[choosedX, choosedY] = irandom_range(1,4) //on décide du mur qu'on va placer
if (cartemursetfin[choosedX, choosedY] = 1 and choosedY-j = 0) //si le mur choisit contient déjà un bord de la carte
or (cartemursetfin[choosedX, choosedY] = 2 and choosedY-j = 2)
or (cartemursetfin[choosedX, choosedY] = 3 and choosedX-i = 0)
or (cartemursetfin[choosedX, choosedY] = 4 and choosedX-i = 2)
{
cartemursetfin[choosedX, choosedY] = 0 //On remet la salle à 0, pas de mur ne sera placé à se passage
}

/* ensuite, la partie complexe: pour chaque mur, on verifie si la salle adjacente est disponible, et si oui, on va*/
/* placer le mur inverse dans la salle adjacente, et augmenter k de 1. Sinon, on remet à 0 la salle actuelle*/

if (cartemursetfin[choosedX, choosedY] == 1) //Pour le cas ou le mur est en haut
{
if cartemursetfin[choosedX, choosedY-1] == 0 //Si la salle d'au dessus n'as pas de mur
{
cartemursetfin[choosedX, choosedY-1] = 2; k = k + 1 //Alors la salle au dessus à un mur vers le bas
}
else
{
cartemursetfin[choosedX, choosedY] = 0 //sinon la salle actuelle ne prends pas de mur
}

//Comme après ça, se code est répété pour chaque mur possible avec juste une petite variation sur la salle ciblée et la valeur qu'elle prend, je les laisse mais ne les met pas en valeur ni ne les commentes.

}
if (cartemursetfin[choosedX, choosedY] == 2)
{
if cartemursetfin[choosedX, choosedY+1] == 0 {cartemursetfin[choosedX, choosedY+1] = 1; k = k + 1}
else{cartemursetfin[choosedX, choosedY] = 0}
}
if (cartemursetfin[choosedX, choosedY] == 3)
{
if cartemursetfin[choosedX-1, choosedY] == 0 {cartemursetfin[choosedX-1, choosedY] = 4; k = k + 1}
else{cartemursetfin[choosedX, choosedY] = 0}
}
if (cartemursetfin[choosedX, choosedY] == 4)
{
if cartemursetfin[choosedX+1, choosedY] == 0 {cartemursetfin[choosedX+1, choosedY] = 3; k = k + 1}
else{cartemursetfin[choosedX, choosedY] = 0}
}}}}}

Comme vous pouvez le voir, ça donne un code assez long, très répétitif et pas vraiment réductible, mais dans les fait assez simple.

La sixième et dernière étape consiste juste a coder les portes pour les remplacer par un mur à chaque fois que la salle actuelle ne peux pas avoir de porte à cette endroit. Soit par exemple, pour la porte du haut quand on est en Y=0, soit parce qu'il y à un mur. N'oubliez pas de prendre en compte que le mur du bas, par exemple, apparait pour les salles pour laquelle la table cartemursetfin indique 2 ET 7!

-----------C'EST BIEN BEAU, MAIS ON EN FAIT QUOI?-----------

Bha après ça, c'est tout simple: quand on lance le jeu, on lance la salle minus1, on demande au code d'aller chercher la position de la salle "-1" pour récupérer les coordonées du début de jeu, et à chaque fois que le personnage joueur fini une salle, celle si vois son numéro de porte augmenté de 5. Et quand le personnage joueur passe une porte, selon la porte passée, on augmente ou diminue la coordonée Y ou X de la position selon ce qu'il convient, et on va chercher dans la table cartecontenu quelle salle est à la nouvelle position indiquée. Et selon le chiffre indiqué, on va vers la salle correspondante.

Certains pourraient être tenté de créer un gros case pour aller chercher toutes les salles, mais notre nomenclature nous permettra sous game maker d'utiliser "asset_get_index", ce qui donne ceci (pour le cas d'une salle qui n'est pas une salle spéciale, et qui est dans la zone grise. Les autres sont des variation sur le même code.):

if cartecontenu[actualroomx, actualroomy] >= 0{  //c'est pas une salle spéciale, qui sont toujours négatives. Notez que 0 est une salle normale
if actualroomx <= 2{ //C'est une des zones de gauche, donc la zone grise ou la rouge
if actualroomy <= 2{ //C'est une des zones du haut, donc la zone grise
room_goto(asset_get_index("grey"+string(cartecontenu[actualroomx, actualroomy])))}

Room_goto permet d'aller dans une salle en indiquant son nom.

Asset_get_index permet d'aller chercher un objet room dont le nom correspond à un string donné

String sert à transformer un chiffre en string.

On à donc ici "ramène moi dans la salle dont le nom est "grey" et le nombre qu'il y à dans le tableau, dans la ou je doit être".

J'ai peut être donné l'impression de vous prendre pour des idiots avec ce dernier point mais comme ici j'utilise un outil propre à game maker, je préfère m'assurez que vous compreniez précisément tout ce qu'il se passe afin de pouvoir le réutiliser avec les outils d'unity ou godot ou que sais-je.

-----------ET MAINTENANT?-----------

Bha maintenant, vous avez la base, a vous de mettre un coup de polish. Vous voulez que certaines portes nécéssitent des clefs? Rajouter des salles spéciales et des conditions aux portes! Vous voulez que le jeu se passe sur 6 zones? Grandissez le tableau! Vous voulez créer une carte? Faites un objet qui dessine un sprite pour chaque valeur dans le tableau des portes! Vous voulez une tarte? Demandez à votre grand mère! 

Tout ça est possible, mais ne touche plus à la génération procédurale en elle même.

Cependant, comme vous l'aurez remarqué, l'algorithme "tetedanslecube" ne peux faire que des trucs globalement en forme de rectangle. Il n'est pas impensable de le complexifier, mais ça restera une carte assez simple. C'est pas un mal, mais ça peux ne pas être ce que votre jeu recommande. Aussi, je vais peut-être vous proposer d'autres algos de mon cru, éventuellement, tel que le isaac basiic ou le fakelabyrinthe.

Ce qui m'importait ici était de vous montrer qu'en réalité, créer de la génération procédurale de carte, c'est pas *dur*, c'est juste que sa demande un peu de préparation en avance.

Du coup, bon courage les loulous!