Le travail sur la programmation, les graphismes et les sons dans certains nouveaux jeux est terminé - seuls les niveaux restent. Travail facile et agréable, mais pour une raison quelconque, il est très difficile. Peut-être l'effet de la fatigue générale.
Pensant à simplifier sa vie, l'idée de génération procédurale lui est venue à l'esprit. Bien sûr, il faudra aussi l'écrire, mais comme il a été dit dans un ouvrage bien connu, "il vaut mieux perdre une journée, puis voler en cinq minutes".
Attention! Sous la coupe, beaucoup de texte et de gifs "gras".
Introduction
Les niveaux seront toujours polis manuellement, il n'y a donc pas d'exigences particulières pour la mémoire, la vitesse ou même la qualité des niveaux résultants.
Initialement, je prévoyais que le générateur ne lance que des pièces et des portes, et tout autre raffinement (intrigue, paysage et ennemis) sera effectué en mode manuel. Mais pour l'instant, je pense que le générateur peut faire beaucoup plus. Néanmoins, le réglage manuel restera - il est nécessaire que les joueurs sentent qu'au moins un peu d'amour est investi dans les niveaux.
J'ai regardé ma base de connaissances sur le développement de jeux et j'ai rédigé des liens vers des articles sur la génération de procédures dans un document séparé. La plupart, bien sûr, concernent la génération de labyrinthes classiques ou la génération de terrain (au fait, les résultats sont très impressionnants), ce qui ne convient pas à un tireur 3D. Mais certains étaient proches de ce dont j'avais besoin (avec un astérisque j'ai noté ceux qui me semblaient les plus adaptés):
J'ai décidé de commencer par les deux derniers - ils viennent d'être mis en œuvre et donnent de bons résultats.
Structure du générateur
En fait, je ne suis pas venu tout de suite dans cette structure, mais dans le processus de nombreuses refactoring et réécriture, mais j'écris tout de suite pour que ce soit clair:
- Génération de la géométrie initiale (au choix - "BSP" ou disposition de la pièce).
- Effacement des sections d'ordures (ces sections qui ne peuvent pas exister dans le jeu).
- Établir des connexions.
- Effacement des sous-graphiques d'ordures (ces groupes de sections qui sont interconnectés, mais il n'y a pas de connexion avec les sections restantes).
- Suppression des connexions inutiles (construction d'un arbre couvrant , un lien est donné à l'arbre couvrant minimum , car il y a une image là, mais pour le générateur il n'y a pas besoin du minimum).
- La randomisation des connexions est la restauration de certaines connexions distantes (pour un type de niveau plus «humain»), ainsi que la transformation de certaines autres en passages entre sections (qui fusionne plusieurs sections en une seule forme plus complexe).
- Génération de chambre secrète.
- Génération d'un «scénario» (où seront les sections initiales et finales, et quel chemin devra être franchi pour passer de l'initiale à la finale).
- Optimisation de la connexion.
- Création de portes et fenêtres.
- Le choix de l'action à effectuer dans cette section (appuyez sur l'interrupteur, relevez la clé ou trouvez le mur secret).
Il y a encore quelque part environ 12 points, mais ils ne sont pas encore terminés (quand j'aurai fini, j'écrirai un article séparé à leur sujet).
Génération initiale de la géométrie: "BSP"
Cette traduction a été prise comme base. Je ne sais pas combien ce qui se passe dans cet algorithme est proche du vrai BSP, donc j'écris "BSP" entre guillemets.
L'algorithme est assez simple. Initialement, créez un rectangle de la taille de l'ensemble du terrain de jeu:
Ensuite, nous le divisons au hasard en deux parties - horizontalement ou verticalement. Où la ligne de séparation aura lieu, nous choisissons également au hasard:
Nous faisons récursivement la même chose pour les nouveaux rectangles:
Et encore et encore, dans une certaine mesure:
Ensuite, dans chaque rectangle, nous sélectionnons une «pièce» - un rectangle de la même taille que l'original ou plus petit (mais pas moins de 3x3 - plus sur celui ci-dessous).
Ensuite, les chambres sont reliées par des couloirs. Mais pas chacun, mais un peu délicat, car ils sont stockés dans une structure de type "BSP" (voir l'algorithme d'origine pour plus de détails).
Le couloir reliant les sections violettes et blanches.
Dans l'algorithme d'origine, les pièces et les couloirs sont de la même couleur (c'est-à-dire qu'ils sont équivalents), donc les couloirs sont simplement dessinés au-dessus des pièces. Dans mon cas, les pièces d'origine doivent être conservées, de sorte que les couloirs soient dessinés comme «derrière» les pièces.
De plus, si la pièce (turquoise sur la figure) traverse le couloir, elle doit la diviser en deux sections différentes (par conséquent, le même couloir peut être dessiné de différentes couleurs):
Et voici le résultat:
Commence alors la phase de marquage des poubelles:
Comme je l'ai déjà écrit, aucun secteur ne peut être inférieur à 3x3 cellules. Cela est dû au fait que le secteur doit être entouré de murs (au moins 1 cellule de chaque côté) et qu'il doit avoir au moins une cellule d'espace libre:
Par conséquent, toutes les cellules qui ne correspondent pas à cette règle sont étiquetées. Mais prenez-le et vous ne pouvez pas les supprimer - tant de connexions disparaissent et le niveau est très limité.
Au lieu de cela, pour chaque cellule étiquetée, le secteur auquel elle peut se joindre est recherché (en respectant la règle 3x3):
Si la cellule ne peut toujours pas être attribuée à un secteur, elle sera supprimée (mais pas dans ce cas - tout va bien ici).
À la dernière étape, cette belle image est vectorisée, et les secteurs dessinés se transforment en poly-boîtes - de tels polygones dans lesquels chaque bord est soit strictement vertical soit strictement horizontal (il y a probablement un nom plus scientifique):
Génération initiale de la géométrie: disposition de la pièce
Un autre article a été pris comme base. Cet algorithme est un peu plus compliqué que le précédent, mais pas non plus la science des fusées.
Tout d'abord, le terrain de jeu est rempli d'une certaine valeur d'arrêt, puis une zone rectangulaire est effacée au hasard dessus:
L'étape de nettoyage d'un rectangle aléatoire est effectuée un certain nombre de fois (également aléatoire), et en conséquence, les contours externes du niveau sont obtenus:
Dans l'espace libre, les points de croissance des pièces sont dispersés de façon aléatoire (la taille minimale de la pièce est de 3x3):
La première étape de la croissance de la pièce commence - pour chaque pièce, le plus grand côté est sélectionné, qui peut encore grandir, et il croît de 1 cellule (s'il y a plusieurs côtés de la même longueur - un au hasard). Les pièces sont déplacées à tour de rôle afin qu'il n'y ait pas d'intersections.
Les pièces sont ensuite converties en polyboxes:
Et la deuxième étape de la croissance commence - à ce stade, le côté peut être divisé en plusieurs parties. Contrairement à la première étape, il ne fait pas pousser une cellule à la fois, mais immédiatement à l'arrêt maximum - cela évite l '"échelle" au niveau des joints des pièces. Si après le passage dans toutes les pièces il y a encore des cellules vides, le cycle se répète.
Le résultat est un espace entièrement rempli:
Ensuite, les polyboxes sont dessinées sous la forme d'un raster, et (comme dans le cas du générateur «BSP»), l'étape de marquage des cellules «ordures» commence:
Et en les associant aux secteurs existants:
Ici, il n'a pas été possible de fixer toutes les cellules - les cellules supplémentaires ont été supprimées.
Le résultat est reconverti en polybox:
Nettoyage des sections de déchets
Parfois, des sections apparaissent à l'intérieur desquelles la règle 3x3 n'est pas respectée:
Vous pouvez essayer de "restaurer" de telles sections, mais je suis allé de la manière la plus simple et je les ai simplement supprimées:
Établir des connexions
Pour chaque section, ses voisins sont recherchés et dans les lieux de contact de ces sections, des connexions sont créées. Des connexions sont créées des deux côtés - si la section A est en contact avec la section B, alors il y aura une connexion de A à B et de B à A. Le résultat est un graphique bidirectionnel.
Effacement des sous-graphiques d'ordures
Parfois, à la suite du nettoyage des sections d'ordures, nous obtenons non pas un graphique, mais plusieurs graphiques indépendants, comme dans cet exemple:
Dans ce cas, le sous-graphique est sélectionné comme principal, la "zone" des sections est maximale et le reste est supprimé (la "zone" est entre guillemets, car bien qu'il soit possible de calculer la zone réelle de la zone poly, j'ai simplifié la tâche et je considère la zone de la zone de délimitation - c'est faux, mais adapté à un générateur).
Éliminer les composés en excès
S'il y a un passage de chaque secteur à chacun avec lequel il est connecté, alors il y aura trop de portes au niveau, et on sentira plus fortement qu'il est généré. Par conséquent, à ce stade, les connexions en excès sont supprimées:
Pour plus de randomisation, je ne génère pas d'arbre couvrant dans le nombre minimum de passes, mais plutôt, je supprime un bord aléatoire à la fois (en le choisissant au hasard parmi tous les possibles à l'étape en cours).
Bien que, lorsque j'écris ceci, l'idée est apparue qu'il serait assez aléatoire de sélectionner le secteur initial et de supprimer les bords déjà plus efficaces.
Randomisation de connexion
Ci-après, les illustrations proviendront d'une autre génération, car dans le précédent, il y avait une erreur dans le générateur, à cause de laquelle les autres images étaient incorrectes.
Mais un niveau dans lequel il n'y a pas une seule connexion superflue ne semble pas non plus très humain, donc un peu de chaos est introduit:
- Certains bords supprimés sont restaurés.
- Et certains se transforment en allées.
De plus, les sections entre lesquelles les passages ont été formés fusionnent en une seule:
S'il vous a semblé que dans cette illustration, les connexions supprimées à l'étape précédente sont réapparues - il vous semble :). Quand j'ai lu le texte, cela m'a semblé aussi, mais après avoir soigneusement regardé l'illustration précédente, il devient clair que tout va bien.
Génération de chambre secrète
Les secteurs qui n'ont qu'une seule connexion sont sélectionnés sur le graphique:
S'il existe plusieurs secteurs de ce type, ils se regroupent tous dans un tableau et sont triés par "zone". Ensuite, ce tableau est tronqué de manière aléatoire (mais de sorte qu'au moins un élément y reste). Ces secteurs deviendront des salles secrètes:
Génération de script
Tout d'abord, les secteurs avec le nombre minimum de connexions libres (c'est-à-dire ceux les plus proches du "bord" du graphique) sont sélectionnés:
Dans cette illustration, un secteur est sélectionné, mais s'il y en avait plus, de toute façon, un serait sélectionné (au hasard).
NB. Au cours de la relecture de l'article, j'ai pu trouver une situation où un secteur avec un nombre minimum de connexions libres ne sera pas seulement à la limite, mais lui assigner un script conduira à un niveau infranchissable. En fait, vous pouvez choisir n'importe quel secteur, mais un seul, après quoi le graphique ne tomberait pas dans plusieurs sous-graphiques.
Ensuite, sélectionnez les secteurs qui sont connectés au secteur actuel et qui n'ont qu'une seule connexion gratuite. Ils, avec une certaine probabilité, seront utilisés pour continuer le script. Par exemple, si le graphique était le même que dans l'illustration ci-dessous, alors le secteur indiqué par la question pourrait être inclus dans la liste.
La salle secrète est marquée en gris, les croix sont les connexions qui auraient dû être supprimées dans le graphique d'origine et le secteur source est un plus.
NB. Lors de la relecture de l'article, il m'a semblé que la condition de présence d'une seule connexion était trop stricte, la même que dans l'étape précédente suffirait - pour qu'après suppression de ce secteur, le graphique ne se décompose pas.
Ensuite, le numéro de script est attribué à cette liste de secteurs (juste un numéro, à ce stade, cela ne signifie rien de spécifique), et les connexions aux frontières de cette liste de secteurs sont marquées comme fermées par ce script.
Dans ces illustrations, différents scénarios auront des couleurs de remplissage de secteur différentes. Ils n'ont rien à voir avec la couleur de la frontière du secteur (dans les prochaines étapes cela sera corrigé, mais dans cette étape c'est plus pratique pour moi).
Ensuite, le secteur suivant est sélectionné, une liste est compilée et cette liste est marquée avec un nouveau scénario:
Faites attention aux petits points bleus à l'intérieur des carrés rouges - c'est ainsi que l'ouvreur de scénario est dessiné - c'est-à-dire quelque part dans la section avec le script rouge, il y aura une clé ou un interrupteur qui ouvrira le passage aux secteurs avec un script bleu.
Cela continue jusqu'à ce qu'il ne reste plus de secteurs libres:
Le secteur le plus récent ne se voit pas attribuer de script, mais uniquement un ouvre-scénario. Ce secteur sera le secteur dans lequel le joueur commence la partie.
Pour ce niveau:
- Le joueur commence dans le secteur de départ, quelque part là où il trouve un «décapsuleur» pour le secteur jaune, y va.
- Dans le secteur jaune, ouvre le secteur bleu, y va.
- Dans le secteur bleu s'ouvre vert, va là-bas.
- Dans le secteur vert s'ouvre le violet, y va.
- En violet s'ouvre le rouge.
- En rouge - bleu.
- Où il trouve l'interrupteur de niveau final.
Schématiquement, cela peut être montré comme suit:
Un «ouvre-porte» peut être soit une clé, soit un interrupteur, ou autre chose, par exemple, une tâche pour détruire tous les ennemis dans n'importe quel secteur (mais je ne prévois pas que dans un avenir proche le générateur ou le moteur le supportera).
Optimisation de la connexion
À cette étape, pour chaque connexion, un côté est sélectionné (comme vous vous en souvenez, les connexions sont initialement générées dans les deux sens). Cela est nécessaire pour rendre le niveau plus «manuel» et pour simplifier les étapes suivantes (mais pour un type de niveau encore plus intéressant, je prévois dans un avenir proche de «désoptimiser» certaines connexions) .
Création de portes et fenêtres
Pour chaque secteur, toutes ses connexions sont visualisées (qui après l'étape précédente ne regardent que dans une seule direction), et des portes et fenêtres sont placées sur chaque connexion visualisée.
- Tout d'abord, un point est sélectionné à la jonction, de préférence plus près du centre.
- Ensuite, à ce stade, une porte ou une fenêtre est placée (et s'il s'agit d'une connexion à une pièce secrète, alors un mur secret).
- Si une porte est placée, elle peut avoir de 1 à 3 cellules (une est une porte ordinaire, deux ou trois sont une porte hermétique épaisse, qui s'ouvre après avoir appuyé sur un interrupteur).
- De plus, la connexion est divisée en deux parties: la partie avant le point sélectionné et la partie après. Et, s'il reste de l'espace avant ou après, la fonction est appelée récursivement.
Pour rendre le niveau plus intéressant, à différentes étapes, il existe une probabilité différente de placer une porte ou une fenêtre:
- À la première étape, la porte est toujours placée, car à quoi sert de se connecter s'il n'y a que des fenêtres.
- À la deuxième étape, avec une probabilité plus élevée (75%), une fenêtre est placée qu'une porte.
- S'il y a une troisième étape (par exemple, la connexion est longue), une fenêtre doit être placée dessus.
- Dans le cas de la 4ème étape, la porte ou la fenêtre est placée de manière similaire.
- Si la connexion est extra longue, le générateur revient à la deuxième étape.
Sélection d'actions
Bien que cela ne soit pas lié à la génération, la visualisation change à cette étape - maintenant la bordure du secteur est peinte dans la couleur du script:
Le secteur de départ est gris clair, le secteur final est bleu. Notez également qu'au lieu de la porte de la salle secrète (gris foncé à gauche) un mur est dessiné - tout est correct, c'est un mur secret.
Sélectionnez ensuite les secteurs dans lesquels vous pouvez placer les clés:
Ils sont sélectionnés tout simplement:
- S'il s'agit d'une pièce secrète, il ne peut y avoir aucun "ouvre-porte" et la clé ne peut pas y être placée.
- Vous ne pouvez pas non plus placer la clé dans le secteur final, car elle est définitive.
- De plus, la clé ne peut pas ouvrir les portes doubles et triples - en raison des caractéristiques du moteur, elles ne peuvent être ouvertes qu'à l'aide de l'interrupteur (il n'y a pas de tels secteurs dans l'illustration ci-dessus) .
Après cela, le nombre de clés à un niveau (de zéro à trois) est sélectionné au hasard, puis, au hasard, dans la liste des secteurs disponibles, ceux dans lesquels il y aura des clés sont sélectionnés.
Dans les autres secteurs, il y aura des commutateurs.