El algoritmo de ruta más largo para la generación de laberintos roguelike

10

Tengo un mapa simple basado en cuadrícula compuesto de habitaciones, como este (A = entrada, B = salida):

   0 1 2 3
  #########
0 # B # #####
  #########
1 # ### #
  #########
2 # # #
  # # #
3 # # #
  #########
4 # ### #
  #########
5 ### A #
  ### #
6 ### #
  #########

Y estoy atrapado tratando de hacer un algoritmo adecuado para crear un camino de puertas entre las habitaciones, de tal manera que el jugador tenga que explorar la mayor parte del mapa antes de encontrar la salida.

En otras palabras, estoy tratando de encontrar el camino más largo posible de A a B .

(Soy consciente de que este problema se puede resolver con gráficos acíclicos; sin embargo, en este caso puede haber ciclos).

EDITAR: Otro ejemplo en el que las habitaciones se conectan mediante un relleno y la salida se elige como la habitación más alejada de la entrada:

   0 1 2 3
  #########
0 # B # #
  # # - #####
1 # | # #
  ### # #
2 ### # #
  ### - # - ###
3 # | ###
  # - #######
4 #A | # #
  # # #
5 # # #
  # # #
6 # # #
  #########

Tenga en cuenta que la ruta a la salida no es la ruta más larga posible.

path-finding roguelikes Usuario no encontrado
fuente
Si obligas al jugador a tomar el camino más largo posible, en realidad estás construyendo un camino recto que pretende ser complejo. Esto es malo.
o0 '.
No está mal (es la base del género tirador de rieles, por ejemplo), pero debes ser consciente de que lo estás haciendo y diseñar el resto de tu juego para que funcione bien con él.
También es más fácil controlar el ritmo del juego cuando los niveles son mayormente lineales. Permite agregar, por ejemplo, una sala de recuperación después de una sala de monstruos particularmente difícil. Si no hubiera un camino principal, la distribución de desafíos y recompensas sería aleatoria.
Usuario no encontrado

Respuestas:

11

Creo que vas por esto de la manera incorrecta. La ruta máxima en un gráfico con ciclos está técnicamente indefinida porque es infinita si el ciclo se encuentra entre el inicio y el final. Probablemente hay formas inteligentes de extender / restringir la definición de ruta máxima, pero no creo que sea el mejor enfoque aquí.

No está intentando modelar un camino largo real (por ejemplo, un robot que intenta explorar la mayor cantidad de área posible en un mapa). Solo estás tratando de hacer que el jugador explore muchas habitaciones.

Entonces, aprovecha la posibilidad de que el jugador encuentre la salida proporcional al porcentaje del mapa explorado hasta ahora . Digamos que hay X habitaciones en un nivel, y el personaje jugador ha explorado Y. La próxima vez que el personaje ingrese a una habitación, coloque la salida allí con probabilidad f (Y, X). Un ejemplo trivial de f podría ser (Y * Y) / (X * X), ​​por ejemplo, para 10 habitaciones, hay un 100% de posibilidades de que salga en la última habitación, un 81% de posibilidades de que esté en la penúltima habitación, y solo un 1% de probabilidad de que esté en la primera habitación.

Puedes ajustar la ecuación como quieras para que el juego se sienta bien, y tal vez incluso darle al jugador algunas habilidades para que sea más probable que genere. La parte clave es, no generar la salida hasta que el personaje realmente entre en la habitación. Este método también es inmune al conocimiento del jugador sobre el algoritmo de generación de mazmorras; incluso si el jugador tiene patrones de movimiento extraños como el salto del caballero en NetHack o teletransportación, tendrá que explorar más habitaciones para encontrar la salida.

Si debe generar estáticamente la salida, puede usar la misma idea con un personaje virtual. Imagine un relleno de inundación a partir de la posición del personaje, moviéndose una vez la celda en cada iteración. La última habitación que se llena es la habitación a la que pertenece la salida (de hecho, la última celda que se llena es la celda donde está más alejado del jugador). Sin embargo, en este caso, el jugador tiene más información sobre la salida, si está a la izquierda, probablemente a la derecha, y si puede teletransportarse, en realidad puede llegar más rápido que una caminata aleatoria normal.

Finalmente, acabo de terminar un roguelike donde la salida se generó en el otro lado del mapa del personaje del jugador, y luego deambulé al azar. Algunos elementos en la mazmorra lo hicieron visible en el mapa, a expensas de tener hambre más rápido. No hice ningún análisis, pero definitivamente sentí que tenía que explorar más del mapa para encontrarlo, y le dio a los niveles una sensación única.


fuente
La generación dinámica parece una buena idea, siempre y cuando el jugador no se dé cuenta. De lo contrario, creo que se sentirían bastante engañados. Sin embargo, me encanta la idea del relleno.
Usuario no encontrado el
2
Bueno, toda tu propuesta es, en cierto sentido, engañar al jugador. No me culpes por refinar las matemáticas para no requerir un modelo mundial. ;) Pero puedes usar trucos de diseño para que sea más apetecible, por ejemplo, la salida se coloca a priori, pero una clave requerida para usarla se genera en el método que describí, o se coloca en un monstruo que solo se genera después de explorar X habitaciones / matar a X monstruos, o abrir la puerta requiere encender X interruptores, uno en cada habitación, etc ...
Intenté un enfoque de inundación. Hace un buen trabajo al conectar cada habitación y produce ramas cortas, pero en realidad no produce el camino más largo posible hacia la salida, incluso si la salida es el último nodo visitado (o, en mi implementación, el más lejano). (ejemplo agregado a mi pregunta)
usuario no encontrado el
Sin embargo, estoy a favor de laberintos basados ​​en llaves / interruptores. Simplemente parece más fácil implementar ese tipo de cosas con árboles, porque si tienes dos ramas, puedes detectar qué rama conduce a la salida, bloquearla y poner la llave en la otra rama.
Usuario no encontrado
Pero admito que me equivoqué al pensar que se trataba de un problema de búsqueda de caminos "A a B". Me doy cuenta de que tiene más sentido encontrar la salida como resultado del algoritmo que como un objetivo.
Usuario no encontrado el
6

Una alternativa posible sería crear un árbol de expansión (¿máximo?) Utilizando Prim / Kruskal (para eliminar ciclos) y aplicar un algoritmo tradicional de ruta más larga en el árbol de expansión.

Sin embargo, me preocupa que el algoritmo de árbol de expansión tenderá a crear ramas sin salida, lo que obligará al jugador a retroceder constantemente.

EDITAR: resultado de usar un algoritmo basado en Kruskal y colocar la salida al final de la rama más larga:

   0 1 2 3
  #########
0 #A | # #
  # ##### - #
1 # # #
  ### #
2 ### #
  ### #
3 ### #
  ### - #####
4 # | # #
  # - ##### - #
5 # ### #
  # - #######
6 # # B #
  # # - #
7 # | # #
  #########
Usuario no encontrado
fuente
1
Iba a sugerirle a Primm también :-), +1, creo que retroceder es una parte importante de muchos juegos también ... revisa diablo 2.
Mr.Gando
2

Aquí hay algo para jugar:

Connect each room with a door to another room.
N = 0.75*TotalNumberOfRooms
Until (pathSize > N) {
  Use A* pathing to get a path from A to B. (G being size of room, or # of monsters)
  if (pathSize < N) remove a connection/door
  if (noPath) choose a different door/connection
  if (room.doors < 1) choose a different door/connection
}

Quitaría puertas al azar a lo largo del camino, de lo contrario terminas con 1 puerta en la salida y toneladas de puertas al comienzo.

Creo que esto no es O(n^2)tan bueno para mapas grandes.

Stephen Furlani
fuente
Una solución muy elegante en principio. La próxima vez debería tratar de pensar en algo así antes de optar por técnicas complicadas.
Usuario no encontrado el
Bueno, elegante quizás, pero va a ser un procesador hog. O (n ^ 2) no escalará bien con mapas grandes.
Stephen Furlani
1

Creo que ya tiene excelentes respuestas, pero aquí está mi solución teórica de $ 0.02 al problema.

Lo que desea NO es el camino más largo, sino el camino más corto más largo. Desea la habitación más alejada, dado que está considerando el camino más corto hacia la habitación. Esto probablemente suene confuso, pero es muy fácil de calcular.

  1. Comience en su sala de partida. Marque cada uno de sus vecinos 1. Están a una distancia de 1 de la sala de inicio.
  2. Para cada habitación marcada con 1, visite a cada uno de sus vecinos NO MARCADOS y márquelos como 2. Están a 2 distancias del comienzo.
  3. Continúe hasta que haya cubierto todas las habitaciones. La habitación con el número máximo está más lejos desde el principio.

Calcular una ruta más larga real (no tomará demasiado tiempo para decir 10 habitaciones) no funcionará porque no puede hacer que el jugador tome esa ruta más larga. Por lo tanto, poner la entrada y la salida en las dos habitaciones más alejadas es la mejor opción. Para encontrar esto, calcule la habitación más alejada de una habitación aleatoria. Luego, desde esa habitación, encuentra la habitación más alejada. Esto se llama encontrar el diámetro de un gráfico, por favor Google.

Sid Datta
fuente