Optimal algoritmo de generación de laberinto multijugador

Question

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

Así que estoy buscando un algoritmo de generación de laberinto donde la ruta óptima para cada jugador desde el punto de inicio hasta la meta no sea más de un 10% más de pasos que la ruta promedio. De esta forma, los jugadores están más o menos en igualdad de condiciones. ¿Alguien puede pensar en semejante algoritmo?

(Tengo una idea tal y como está, pero no está bien pensado y parece mucho menos que óptima -. Voy a publicar como una 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 en el 'final'). Luego escoge una distancia (tal vez la más alta con n puntos a esa distancia?) Y coloca a los jugadores en casillas con ese valor.

Answer 2

La solución más fácil que se me ocurre con es generar aleatoriamente un laberinto completo como normal, luego seleccionar aleatoriamente el punto de gol y los puntos de inicio del jugador. Una vez hecho esto, calcule el camino más corto desde cada punto de inicio hasta el objetivo. Encuentre el promedio y comience a 'suavizar' (eliminar/mover barreras - no sé cómo funcionará esto) las rutas que están significativamente por encima de él, hasta que todas las rutas estén dentro del margen apropiado. Además, podría ser posible tomar aquellos que están significativamente por debajo del promedio e insertar barreras adicionales.

Answer 3

¿Qué hay de la primera selección de la posición de los jugadores y el objetivo y un camino de igual longitud y luego construir un laberinto respetando las rutas definidas? Si las rutas no se cruzan esto debería funcionar fácilmente, supongo que

Answer 4

Me acercaría a esto al establecer el objetivo y el punto de entrada de cada jugador, y luego generar caminos de similar longitud para cada uno de ellos a la meta. Entonces comenzaría a agregar ramas falsas a lo largo de estos caminos, teniendo cuidado de evitar enlazar con las rutas de otros jugadores, o tener una rama conectada de nuevo a la ruta. Entonces, esencialmente, cada rama es un callejón sin salida.

De esta manera, usted garantiza que las rutas son similares en longitud. Sin embargo, no permitirá que los jugadores interactúen entre ellos. Sin embargo, puede poner esto en práctica, creando enlaces entre sucursales, de modo que los puntos de entrada de la sucursal en cualquiera de las rutas se encuentren a una distancia similar de la meta. Y en esta rama puede ramificar más callejones sin salida para divertirse y obtener ganancias :-)

Answer 5

Escoja su punto de salida en algún punto intermedio

Inicio sus caminos N desde allí, añadiendo 1 a cada ruta por lazo, hasta que estén todo el tiempo que quisiera que fueran.

Hay sus N puntos de inicio, y todos son de la misma longitud.

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