Estoy diseñando un juego con mazmorras generadas al azar. Me gustaría ver esto como un gráfico conectado y no dirigido en el que los nodos son habitaciones y los bordes son puertas o corredores. Luego elijo un nodo "lateral" como entrada de la mazmorra, calculo la distancia entre esta entrada y todos los demás nodos, y decido que uno de los nodos más lejanos es el "objetivo" de la mazmorra (la ubicación del tesoro, jefe, princesa, etc.).
Vi 2 formas de generar la topografía final de la mazmorra:
- Primero genere un gráfico aleatorio, luego intente llenar el mundo 2d con habitaciones en ubicaciones aleatorias, respetando las conexiones de borde. Pensé que esto sería a veces difícil porque la generación de la sala podría "bloquearse" tratando de instalar habitaciones en lugares imposibles.
- Genere las primeras habitaciones, colocándolas al azar donde encajan, luego asigne el resultado a nodos y bordes. Decidí probar esto.
Mi idea consiste en:
- Primero genera una gran sala que contendría toda la mazmorra.
- Coloque una pared dentro de la habitación grande, en un lugar aleatorio, dividiendo la habitación grande en 2 habitaciones más pequeñas de diferentes áreas.
- Luego continúo dividiendo cada habitación en 2, hasta que sean demasiado pequeñas o el número total de habitaciones alcance un máximo (o cualquier otra condición). Cada nueva sala es un nodo.
- Una vez terminado, reviso cada habitación y encuentro todas las demás habitaciones adyacentes, marcando los 2 nodos como conectados por un borde.
De esa manera me aseguro de que todas las habitaciones tengan una posible ubicación en el mundo 2D y estén correctamente mapeadas por un gráfico conectado.
Mi problema es que hay demasiadas puertas y pasillos que conectan las habitaciones.
Entonces, me gustaría un algoritmo que reduzca el número de bordes de un gráfico conectado no dirigido , pero que lo mantenga conectado (todos los nodos permanecen accesibles) al final.
Respuestas:
Use el algoritmo de Prim para obtener el árbol de expansión mínimo para su gráfico (agregue pesos aleatorios, o agregue los pesos más altos cerca de la entrada, o haga un algoritmo de su elección) y vuelva a agregar algunas puertas / bordes al azar. De esta manera, tendrá todas las habitaciones conectadas y algunas rutas redundantes adicionales.
fuente
También puedes probar el algoritmo de Kruskal
fuente
Algunos de los generadores de mazmorras en esta lista de Inkwell Ideas son de código abierto o proporcionan documentación sobre sus algoritmos. Google también te dará mucho mediante la búsqueda de "generador de mazmorras [nombre del lenguaje de programación]". Desafortunadamente, mi favorito no se puede encontrar por ninguno de esos métodos, a pesar de ser el mejor documentado que he encontrado, y no puedo recordar su nombre ya que lo perdí recientemente debido a un bloqueo del disco duro. Actualizaré esta respuesta después de realizar la recuperación en esa unidad.
fuente