Comment puis-je générer un chemin de donjon (relativement) linéaire?

8

Nous développons un concept de défilement latéral d'action. Nous avons besoin d'un moyen de générer une carte (relativement) droite. J'entends par là quelque chose comme ...

entrez la description de l'image ici

Il est clair que cette carte suit un itinéraire simple, même si elle s'écarte un peu. Avec cela, nous allons également implémenter des voies errantes - raccourcis ou passages secrets. Pour que, peut-être, pour passer de la troisième zone encerclée à la quatrième, vous ayez le chemin principal et un passage secret rempli d'ennemis plus forts, mais plus rapide et avec des récompenses plus élevées.

Ici, nous sommes dans une impasse. Nous explorons quelques options mais n'avons pas vraiment fait de progrès. Quelle approche pourrions-nous utiliser pour générer ce type de chemin Nous ne sommes pas liés par les langages de programmation, car jusqu'à présent nous avons expérimenté Java, C # et C ++. De même, nous n'avons aucune dépendance actuelle sur des moteurs de jeu spécifiques.

user2444503
la source
11
J'ajouterais qu'il n'est pas clair quel est le résultat final que vous recherchez. La «carte» que vous montrez est une vue descendante d'une région. Vous développez une roulette latérale 2D. Comment sont les 2 liés?
Vaillancourt
J'ai supprimé la "meilleure" formulation de votre question, car elle n'est pas vraiment utile. J'ai également supprimé vos trois approches suggérées, qui sont toutes des réponses potentiellement valables. Il est généralement préférable de ne pas inclure de solutions potentielles dans votre question, car la comparaison des solutions fournies n'est généralement pas une requête que nous examinons ici (mais la question de savoir comment résoudre le problème en l'absence de biais de solution existants l'est généralement). J'ai également nettoyé une partie des bavardages de commentaires qui, selon moi, sont atténués par les modifications.
1
Cette ligne ressemble presque exactement à ce que j'ai eu quand j'ai commencé avec une ligne droite et y ai ajouté du bruit perlin (ou simplex) (plusieurs octaves). Peut-être un domaine à explorer (je créais un éclaircissement variable dans le temps)
Richard Tingle

Réponses:

15

Exigences

  1. Vous voulez plusieurs chemins de A à B.
  2. Vous voulez travailler dans l'espace de la grille, c'est probablement de l'espace pour vos carreaux.
  3. Vous ne voulez pas que les chemins se croisent, sinon cela gâchera la progression du jeu.
  4. Vous voulez que les chemins semblent raisonnablement organiques.

Diagrammes de Voronoi

Les diagrammes de Voronoi sont des graphiques planaires remplissant l'espace:

entrez la description de l'image ici

Une bonne chose à leur sujet est de savoir comment vous pouvez les utiliser pour créer des chemins organiques. Si vous tracez une ligne droite de centre à centre, vous obtiendrez un chemin assez imprévisible (lire: non ortholinéaire).

Comment créer un diagramme de Voronoi pour une utilisation avec un système basé sur des tuiles

Créez une carte d'une taille raisonnable, disons 128x128. Générez ndes coordonnées de grille aléatoires (x, y) dans la carte et remplissez chacune avec un identifiant / une couleur unique. Créez une liste pour cette couleur et ajoutez-y cette cellule de départ; faites cela pour chaque couleur.

Vous avez maintenant ces points de couleur uniques flottant dans un vide, mais vous devez créer des îlots de couleurs entiers autour d'eux, avec un résultat final qui ressemble à ceci:

entrez la description de l'image ici

Pour ce faire, nous devons voir quelle couleur appartient à chaque cellule de la carte (cellule = pixel dans l'image ci-dessus). Nous parcourons chaque cellule de la carte, vérifiant lequel de nos npoints de couleur de départ est le plus proche (via pythagore). Cette cellule entre dans la liste associée à cet identifiant / couleur unique ... ci-après dénommé cellules d' îles AKA Voronoi (dans le diagramme ci-dessus, groupes de pixels de même couleur).

Vous devriez maintenant avoir un diagramme de Voronoi quantifié. L'étape suivante consiste à analyser l'adjacence de chaque île aux autres îles. Configurez un nœud simple et une structure de bord afin de pouvoir stocker un graphique (le nœud n'est que l'ID, la liste de cet ID et une liste vide de bords; le bord n'est que le nœud de début et de fin). Pour chaque île identifiée de manière unique, créez un nœud et ajoutez des arêtes pour la relier à chaque île à laquelle elle est adjacente.

Une fois que vous avez le diagramme complet (graphique), vous arrivez à la partie amusante - utilisez le graphique pour trouver des chaînes d'îles et en faisant en sorte que toutes les cellules de chaque île de la chaîne aient le même ID, vous découpez l'une des vos chemins. Supposons qu'un îlot avec toutes les cellules ayant l'ID 503 se trouve à côté d'un îlot avec l'ID 657. Vous pouvez remplacer toutes les 503 cellules par un ID 657, créant ainsi un plus grand îlot de 657 adjacents.

Par exemple - le rouge est le chemin 1, le bleu est le chemin 2, le magenta est à la fois:

entrez la description de l'image ici

Vous pouvez utiliser n'importe quel algorithme de graphe existant (A * inclus) pour générer les chemins du début à la fin. Obtenir un chemin sinueux est un cas de ne pas toujours utiliser le pas optimal vers l'île de but.

Enfin, il est trivial de rétrécir les îles si vous voulez des chemins plus étroits, ou d'utiliser une carte plus grande avec beaucoup plus d'îles afin d'obtenir une résolution plus fine.

Une étape finale facultative pour la recherche de chemin

Soit vous pouvez utiliser le graphique de haut niveau que vous avez construit en conjonction avec les cellules / tuiles sous-jacentes pour effectuer l'exécution A *, OU vous pouvez faire de l' escalade sur les cellules / tuiles sous-jacentes pour un meilleur mouvement:

Au centre (ou n'importe quelle coordonnée) de votre île de but, vous pouvez placer une cellule d'influence. Cette influence peut pomper le "parfum" comme dans la diffusion collaborative . Ce parfum se propagera tout le long du chemin de retour à ce qui était l'île de départ, devenant de plus en plus faible au fur et à mesure. Maintenant, pour une entité au début, nous passons simplement d'une cellule à parfum inférieur à une cellule à parfum supérieur, chaque fois vous rapprochant de l'objectif - de la même manière qu'un chien fonctionne. Chaque chemin étant à peu près linéaire, cela vous permet d'éviter d'utiliser A * au moment de l'exécution. Ou vous pouvez faire la même chose avec le graphique des îles, mais cette façon est un peu plus complexe car vous voudrez probablement naviguer dans vos entités au niveau des tuiles. Donc, la première façon est peut-être meilleure. Dans les deux cas, vous pourrez accéder à l'objectif à faible coût de traitement.

Ingénieur
la source
J'ai créé un générateur de cartes en utilisant Voronoi et Perlin Noise en Java, peut-être qu'il peut vous être utile comme point de départ: github.com/dragondgold/Map-Generator
Andres