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

Question

Estoy desarrollando un mundo de juego generado por procedimientos 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íclicas).

Para el algoritmo de generación mundial, las salas de diferentes tipos se distinguirán por las "etiquetas" de cada sala. atributo (un conjunto de cadenas). Una vez que se han instanciado, las salas se pueden consultar y seleccionar mediante etiquetas (etiqueta única, intersección de etiqueta, unión de etiqueta, mejor candidato).

Crearé tipos específicos de salas 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 que coincida con la estrategia elegida. (Por ejemplo, sería posible agregar etiquetas y consultas de etiquetas al sistema de plantillas de sala).

Por ejemplo, tendré habitaciones de este tipo:

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

Finalmente, 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 más etiquetas en consecuencia; etc.

Puntos de bonificación si una estrategia sugerida permitiría una implementación basada en datos.

Answer 1

Primero, necesitas un poco de sentido de 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 sencillas de planificar.

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

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

Tu mapa necesitará métodos para determinar quién está residiendo en un espacio determinado, y qué hay adyacente al espacio, etc.

A continuación, puede probar esto con un conjunto fijo de ubicaciones que haya resuelto y que se puedan soltar en el mapa y pasar algunas comprobaciones básicas de no conflicto, adyacentes y similares.

---

Segundo, necesitas una especie de "generador de laberinto". Un laberinto conectado simplemente se genera fácilmente como una estructura de árbol que se pliega en el espacio dado.

El laberinto / árbol tiene una "raíz" Nodo que será el centro del laberinto. No necesariamente es 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 deambular desde la entrada hasta la salida, visitando muchos "callejones sin salida" lugares a lo largo del camino.

Elija un tipo de espacio para el nodo raíz. Colóquelo en su espacio de mapa.

Esto tendrá 1 - n entradas, cada una de las 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 sea un ajuste natural para esta estructura. Además, un árbol adecuado siempre está bien conectado, ya que nunca tiene secciones aisladas a las que no se puede acceder.

Se desplegará, recursivamente, desde el nodo raíz, seleccionando ubicaciones y soltándolas en el espacio disponible.

Pruebe esto para asegurarse de que llena el espacio razonablemente bien.

---

El resto de sus requisitos son ajustes en la forma en que el generador de laberintos selecciona las ubicaciones.

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

---

Su definición de espacio puede ser 2D o 3D; ambos son bastante racionales. Para obtener crédito adicional, considere cómo implementaría un espacio 2D en mosaico con hexágonos en lugar de cuadrados.

Esta " geometría " puede ser un complemento de Estrategia para los diversos algoritmos. Si puede reemplazar el cuadrado 2D con el hexagonal 2D, ha hecho un buen trabajo de diseño OO.

Answer 2

Echa un vistazo a las discusiones en El conector MUD : hay algunas grandes discusiones sobre el diseño y la generación del mundo, y diferentes tipos de sistemas de coordenadas / navegación en la sección " Codificación y diseño avanzados " (o similar) foro.