¿Cuál es una buena estrategia para construir un gráfico dirigido para un mapa del juego (en Python)?

Question

Estoy desarrollando un mundo de juego generado por procedimiento en Python. La estructura del mundo será similar al paradigma MUD/MUSH de habitaciones y salidas dispuestas como un gráfico dirigido (las habitaciones son nodos, las salidas son bordes). (Tenga en cuenta que esto es no necesariamente un gráfico acíclico, aunque estoy dispuesto a considerar soluciones acíclicos.)

Para el algoritmo de generación de mundo, habitaciones de diferentes tipos se distinguen por atributo "etiquetas" de cada habitación (una conjunto de cuerdas). Una vez que se han instanciado, las salas pueden consultarse y seleccionarse mediante etiquetas (etiqueta única, intersección de etiquetas, unión de etiquetas, mejor candidato).

Crearé tipos específicos de habitaciones utilizando un sistema glorificado de objetos de plantilla y métodos de fábrica. No creo que los detalles sean importantes aquí, ya que la implementación actual probablemente cambiará para coincidir con la estrategia elegida. (Por ejemplo, sería posible añadir etiquetas y etiquetas-consultas al sistema de plantilla de sala.)

Por ejemplo, voy a tener habitaciones de este tipo:

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

Por último, la pregunta: ¿cuál es ¿una buena estrategia para crear instancias y organizar estas salas para crear un gráfico que pueda corresponder a las reglas dadas?

Algunas reglas pueden incluir: una plaza por cada 10.000 habitantes; main_street se conecta a plaza; side_street se conecta a main_street o side_street; hotel favorece las conexiones main_street o plaza, y recibe etiquetas adicionales en consecuencia; etc.

Puntos de bonificación si una estrategia sugerida permite una implementación basada en datos.

Answer 1

Primero, necesitas algo de sentido de la ubicación. Sus diversos objetos ocupan una cierta cantidad de espacio de coordenadas.

Tienes que decidir qué tan regulares son estas cosas. En el caso trivial, puede colocarlos en su espacio de coordenadas como rectángulos simples (o sólidos rectangulares) para hacer que las ubicaciones sean más simples de planificar.

Si las cosas son irregulares, y densamente empaquetadas, la vida es algo más compleja.

Defina un Mapa para contener ubicaciones. Cada ubicación tiene un lapso de coordenadas; si trabajas con rectángulos simples, entonces cada ubicación puede tener una tupla (izquierda, superior, derecha, abajo).

Su Mapa necesitará métodos para determinar que está residiendo en un espacio dado, y lo que es adyacente al espacio, etc.

Puede entonces esta unidad de prueba con un conjunto fijo de lugares que ha funcionado de esa todos pueden soltarse en el mapa y pasar algunas verificaciones de cordura básicas para no conflictivo, adyacente y similares.

---

En segundo lugar, necesita un tipo de "generador de laberinto". Un laberinto simplemente conectado se genera fácilmente como una estructura de árbol plegada en el espacio dado.

El laberinto/árbol tiene un nodo "raíz" que será el centro del laberinto. No necesariamente el centro físico de su espacio, pero el nodo raíz será el centro de la estructura del laberinto.

Idealmente, una rama de este nodo contiene una "entrada" a todo el espacio.

La otra rama de este nodo contiene una "salida" de todo el espacio.

Alguien puede pasear de entrada a salida, visitando un montón de lugares "sin salida" en el camino.

Elija un tipo de espacio para el nodo raíz. Colócalo en tu espacio de Mapa.

Esto tendrá 1 - n entradas, cada uno de los cuales es un sub-árbol con un nodo raíz y 1 - n entradas. Es este negocio de entradas múltiples lo que hace que un árbol encaje de forma natural con esta estructura. También un árbol adecuado siempre está bien conectado, ya que nunca se tienen secciones aisladas que no se puedan alcanzar.

Te abrirás de forma recursiva desde el nodo raíz, seleccionando ubicaciones y colocándolas en el espacio disponible.

Unidad de prueba esto para asegurarse de que llena el espacio razonablemente bien.

---

El resto de sus requisitos están ajustando la forma en que el generador de laberinto selecciona las ubicaciones.

Lo más fácil es tener una tabla de pesos y opciones aleatorias. Elija un número al azar, compárelo con los pesos para ver qué tipo de ubicación se identifica.

---

Su definición de espacio puede ser 2D o 3D, ambas son bastante racionales. Para obtener un crédito adicional, considere cómo implementaría un espacio 2D con mosaicos hexagonales en lugar de cuadrados.

Esta "geometría" puede ser un Estrategia plug-in para los distintos algoritmos. Si puede reemplazar 2D cuadrado con 2D hexagonal, habrá hecho un buen trabajo con OO Design.

Answer 2

Consulte las discusiones en The MUD Connector - hay algunas grandes discusiones sobre el diseño y la generación mundial, y diferentes tipos de sistemas de coordenadas/navegación en el foro "Codificación y diseño avanzados" (o similar).