Quelle est la bonne stratégie pour construire un graphe dirigé pour une carte de jeu (en Python)?

Question

Je développe un monde de jeu généré de manière procédurale en Python. La structure du monde sera semblable au paradigme MUD / MUSH de salles et de sorties organisées sous forme de graphe dirigé (les chambres sont des nœuds, les sorties sont des arêtes). (Notez que ce n'est pas un graphe acyclique, bien que je sois prêt à envisager des solutions acycliques.)

Pour l'algorithme de génération de monde, les pièces de différentes sortes seront distinguées par les "tags" de chaque pièce. attribut (un ensemble de chaînes). Une fois qu'elles ont été instanciées, les salles peuvent être interrogées et sélectionnées par balises (balise simple, intersection de balise, union de balise, meilleur candidat).

Je vais créer des types spécifiques de pièces en utilisant un système glorifié d’objets modèles et de méthodes d’usine. Je ne pense pas que les détails soient importants ici, car la mise en œuvre actuelle changera probablement pour correspondre à la stratégie choisie. (Par exemple, il serait possible d’ajouter des balises et des requêtes de balises au système de modèle de salle.)

Par exemple, j'aurai des pièces de cette sorte:

side_street, main_street, plaza, bar, hotel, restaurant, shop, office

Enfin, la question: quelle est la bonne stratégie pour instancier et organiser ces salles afin de créer un graphique qui pourrait correspondre à des règles données?

Certaines règles peuvent inclure: une place pour 10 000 habitants; main_street se connecte à plaza ; side_street se connecte à main_street ou side_street ; hotel favorise les connexions main_street ou plaza et reçoit en conséquence d'autres balises; etc.

Bonus si une stratégie suggérée permettrait une implémentation pilotée par les données.

Answer 1

Tout d'abord, vous avez besoin d'une certaine idée de l'emplacement. Vos divers objets occupent une certaine quantité d’espace de coordonnées.

Vous devez décider de la régularité de ces différentes choses. Dans le cas trivial, vous pouvez les déposer dans votre espace de coordonnées sous forme de simples rectangles (ou de solides rectangulaires) pour simplifier la planification des emplacements.

Si les choses sont irrégulières - et densément remplies - la vie est un peu plus complexe.

Définissez une carte pour contenir des emplacements. Chaque emplacement a une étendue de coordonnées; si vous travaillez avec de simples rectangles, chaque emplacement peut avoir un tuple (gauche, haut, droite, bas).

Votre carte aura besoin de méthodes pour déterminer qui réside dans un espace donné, ce qui est adjacent à cet espace, etc.

Vous pouvez ensuite effectuer des tests unitaires avec un ensemble fixe d'emplacements que vous avez définis et qui peuvent tous être déposés dans la carte et passer des contrôles de validité élémentaires pour les zones non conflictuelles, adjacentes et similaires.

Deuxièmement, vous avez besoin d’une sorte de "générateur de labyrinthe". Un labyrinthe simplement connecté est facilement généré sous la forme d’une arborescence repliée dans l’espace donné.

Le labyrinthe / l’arbre a une "racine". noeud qui sera le centre du labyrinthe. Pas nécessairement le centre physique de votre espace, mais le nœud racine sera le milieu de la structure du labyrinthe.

Idéalement, une branche de ce noeud contient une "entrée". à l'espace entier.

L’autre branche de ce nœud contient un " exit " de tout l'espace.

Quelqu'un peut se promener de l'entrée à la sortie, en visitant de nombreuses "impasses". endroits le long du chemin.

Choisissez un type d’espace pour le nœud racine. Déposez-le dans votre espace Carte.

Cela aura 1 - n entrées, chacune étant un sous-arbre avec un nœud racine et 1 - n . C'est cette activité à entrées multiples qui fait d'un arbre un ajustement naturel pour cette structure. De plus, un arbre approprié est toujours bien connecté en ce sens que vous n’avez jamais de sections isolées inaccessibles.

Vous allez - de manière récursive - se déployer à partir du nœud racine, en choisissant des emplacements et en les déposant dans l'espace disponible.

Effectuez un test unitaire pour vous assurer qu'il occupe assez d'espace.

Le reste de vos besoins consiste à peaufiner la façon dont le générateur de labyrinthe choisit les emplacements.

Le plus simple est d’avoir un tableau des poids et des choix aléatoires. Choisissez un nombre aléatoire, comparez-le avec les poids pour voir quel type d'emplacement est identifié.

Votre définition de l’espace peut être 2D ou 3D - les deux sont plutôt rationnelles. Pour obtenir un bonus, réfléchissez à la manière dont vous implémenteriez un espace 2D en mosaïque avec des hexagones au lieu de carrés.

Cette " géométrie " peut être un plug-in Stratégie pour les différents algorithmes. Si vous pouvez remplacer la 2D carrée par la 2D hexagonale, vous avez fait du bon travail avec OO Design.

Answer 2

Découvrez les discussions sur le connecteur MUD . Il existe d'excellentes discussions sur la présentation et la génération du monde, et différents types de systèmes de coordonnées / navigation dans la section "Codage et conception avancés". (ou similaire) forum.