Algoritmo óptimo de generación de laberintos multijugador

Question

Estoy trabajando en un juego multijugador simple en el que se colocan de 2 a 4 jugadores en puntos de entrada separados en un laberinto y necesitan alcanzar un punto objetivo.Generar un laberinto en general es muy fácil, pero en este caso el objetivo del juego es llegar a la meta antes que los demás y no quiero que el algoritmo de generación favorezca drásticamente a un jugador sobre otros.

Así que estoy buscando un algoritmo de generación de laberintos donde el camino óptimo para cada jugador desde el punto de partida hasta la meta no sea más de un 10% más de pasos que el camino promedio.De esta manera los jugadores están más o menos en igualdad de condiciones.¿Alguien puede pensar en un algoritmo así?

(Tengo una idea tal como está, pero no está bien pensada y parece mucho menos que óptima; la publicaré como respuesta).

Answer 1

Una alternativa a la respuesta del espacio libre sería generar un laberinto aleatorio, luego asignar a cada celda un valor que represente el número de movimientos para llegar al final del laberinto (puedes hacer ambas cosas a la vez si decides que estás comenzando desde el final). ').Luego elige una distancia (¿quizás la más alta con n puntos a esa distancia?) y coloca a los jugadores en casillas con ese valor.

Answer 2

¿Qué tal si primero seleccionamos la posición de los jugadores y la portería y un camino de igual longitud y luego construimos un laberinto respetando los caminos definidos?Si los caminos no se cruzan, esto debería funcionar fácilmente, supongo.

Answer 3

Me acercaría a esto estableciendo la meta y el punto de entrada de cada jugador, luego generando caminos de longitud similar para cada uno de ellos hasta la meta.Luego comenzaría a agregar ramas falsas a lo largo de estos caminos, teniendo cuidado de evitar vincularse a los caminos de otros jugadores o que una rama se conecte nuevamente al camino.Básicamente, cada rama es un callejón sin salida.

De esta manera, garantiza que los caminos sean similares en longitud.Sin embargo, no permitirá que los jugadores interactúen entre sí.Sin embargo, puedes incluir esto creando vínculos entre las ramas de modo que los puntos de entrada de las ramas en cualquiera de los caminos estén a una distancia similar del objetivo.Y en esta rama puedes bifurcar más callejones sin salida para divertirte y obtener ganancias :-)

Answer 4

La solución más sencilla que se me ocurre es generar aleatoriamente un laberinto completo como de costumbre, luego elegir aleatoriamente el punto de destino y los puntos de inicio del jugador.Una vez hecho esto, calcule el camino más corto desde cada punto de inicio hasta la meta.Encuentre el promedio y comience a "suavizar" (eliminar/mover barreras; no sé cómo funcionará esto) los caminos que están significativamente por encima de él, hasta que todos los caminos estén dentro del margen adecuado.Además, podría ser posible tomar aquellas que están significativamente por debajo del promedio e insertar barreras adicionales.

Answer 5

Elija su punto de salida en algún lugar intermedio

Comience sus rutas N desde allí, agregando 1 a cada ruta por bucle, hasta que estén tanto tiempo como desee.

Están sus N puntos de inicio y todos tienen la misma longitud.

Agrega ramas adicionales fuera de las líneas, hasta que el laberinto esté lleno.