algorithm - metadatos - ¿Qué usar para la creación de niveles aleatorios de juegos de flujo libre?

generador de metadatos (5)

Necesito un consejo. Estoy desarrollando un juego similar a Flow Free en el que el tablero de juego se compone de una cuadrícula y puntos de colores, y el usuario tiene que conectar los mismos puntos de colores juntos sin superponer otras líneas, y usar TODOS los espacios libres en el tablero.

Mi pregunta es sobre la creación de niveles. Deseo hacer los niveles generados aleatoriamente (y al menos debería poder resolverse por sí solo para que pueda dar pistas a los jugadores) y estoy en un nudo sobre qué algoritmo usar. ¿Alguna sugerencia?

Nota: la imagen muestra el objetivo de Flow Free, y es el mismo objetivo de lo que estoy desarrollando.

Gracias por tu ayuda. :)

Considere la posibilidad de resolver su problema con un par de algoritmos más simples y manejables: un algoritmo que crea de manera confiable tableros sencillos y pre-resueltos y otro que reorganiza los flujos para hacer que los tableros simples sean más complejos.

La primera parte, la construcción de una simple placa pre-solucionada, es trivial (si quieres que sea) si estás usando n flujos en una cuadrícula n x n :

Para cada flujo ...
- Coloque el punto de cabeza en la parte superior de la primera columna abierta.
- Coloque el punto de la cola en la parte inferior de esa columna.

Alternativamente, puede proporcionar sus propios tableros de inicio hechos a mano para pasar a la segunda parte. El único objetivo de esta etapa es construir una placa válida, incluso si es trivial o predeterminada, por lo que vale la pena mantenerlo simple.

La segunda parte, reorganizar los flujos, implica hacer un bucle sobre cada flujo, ver cuál se puede trabajar con su flujo vecino para crecer y reducirse:

Para un cierto número de iteraciones ...
- Elige un flujo aleatorio f .
- Si f está en la longitud mínima (digamos 3 cuadrados de longitud), salte a la siguiente iteración porque no podemos reducir f este momento.
- Si el punto de cabeza de f está al lado de un punto de otro flujo g (si hay más de una g para elegir, elija una al azar) ...
  - Mueva el punto de la cabeza de f una casilla a lo largo de su flujo (es decir, camine una casilla hacia la cola). f ahora es un cuadrado más corto y hay un cuadrado vacío. (El rompecabezas está ahora sin resolver.)
  - Mueva el punto vecino de g al cuadrado vacío desocupado por f . Ahora hay un cuadrado vacío desde donde se movió el punto de g .
  - Rellene ese lugar vacío con el flujo de g . Ahora g es un cuadrado más largo de lo que era al comienzo de esta iteración. (El rompecabezas está de vuelta para ser resuelto también.)
- Repita el paso anterior para el punto de la cola de f .

El enfoque actual es limitado (los puntos siempre serán vecinos) pero es fácil de ampliar:

Agrega un paso para recorrer el cuerpo del flujo f , buscando formas más complicadas de intercambiar espacio con otros flujos ...
Agrega un paso que evite que un punto se mueva a una ubicación antigua ...
Añade cualquier otra idea que se te ocurra.

La solución general aquí es probablemente menor que la ideal que está buscando, pero ahora tiene dos algoritmos simples que puede desarrollar para cumplir el papel de un gran algoritmo que lo abarca todo. Al final, creo que este enfoque es manejable, no críptico, fácil de modificar y, en todo caso, un buen lugar para comenzar.

Actualización: codifiqué una prueba de concepto basada en los pasos anteriores. Comenzando con la primera cuadrícula de 5x5 a continuación, el proceso produjo las siguientes 5 tablas diferentes. Algunos son interesantes, otros no, pero siempre son válidos con una solución conocida.

Punto de partida

5 resultados aleatorios (perdón por las capturas de pantalla desalineadas)

Y un 8x8 al azar para una buena medida. El punto de partida fue el mismo enfoque de columnas simples que el anterior.

Creo que querrás hacer esto en dos pasos. Paso 1) encuentra un conjunto de caminos que no se intersecan que conecten todos tus puntos, luego 2) Crece / cambia esos caminos para llenar todo el tablero

Mis pensamientos sobre el Paso 1 son esencialmente realizar el algoritmo Dijkstra en todos los puntos simultáneamente, creciendo juntos los caminos. Al igual que Dijkstra, creo que querrá rellenar cada uno de sus puntos, seleccionando qué nodo buscar a continuación usando algo de heurística (Mi corazonada dice que elegir puntos con el menor grado de libertad primero, luego por distancia, puede ser una buena). De manera muy diferente a Dijkstra, aunque creo que podemos quedarnos estancados por tener que retroceder cuando tenemos varias rutas que intentan crecer en el mismo nodo. (Por supuesto, esto podría ser bastante problemático en mapas más grandes, pero podría no ser un gran problema en mapas pequeños como el que tienes arriba).

También puede resolver algunas de las rutas más fáciles antes de iniciar el algoritmo anterior, principalmente para reducir el número de pistas de retroceso necesarias. Específicamente, si puede hacer un rastreo entre los puntos a lo largo del borde del tablero, puede garantizar que conectar esos dos puntos de esa manera nunca interferirá con otros caminos, así que simplemente puede rellenarlos y sacarlos de la ecuación. A continuación, puede repetir esto hasta que todas estas rutas "rápidas y fáciles" se encuentren trazando a lo largo de los bordes de la placa o las fronteras de las rutas existentes. Ese algoritmo resolvería completamente el tablero de ejemplo anterior, pero sin duda fallaría en otra parte ... aún así, sería muy barato de realizar y reduciría el tiempo de búsqueda del algoritmo anterior.

Alternativamente

Simplemente puede hacer un algoritmo de Dijkstra real entre cada conjunto de puntos, eliminando primero los puntos más cercanos (o probándolos en algunos órdenes aleatorios varias veces). Esto probablemente funcionaría en un buen número de casos, y cuando falla, simplemente tire el mapa y genere uno nuevo.

Una vez que haya resuelto el Paso 1, el Paso 2 debería ser más fácil, aunque no necesariamente trivial. Para hacer crecer tus caminos, creo que querrás hacerlos crecer hacia afuera (así que primero los caminos más cercanos a las paredes, que crecen hacia las paredes, luego otros caminos internos hacia el exterior, etc.). Para crecer, creo que tendrás dos operaciones básicas, voltear esquinas y expandirte en pares adyacentes de cuadrados vacíos ... es decir, si tienes una línea como

.v<<. v<... v.... v....

Primero querrás voltear las esquinas para rellenar tus espacios de borde

v<<<. v.... v.... v....

Entonces querrás expandirte en pares vecinos de espacio abierto

v<<v. v.^<. v.... v.... v<<v. >v^<. v<... v....

etc.

Tenga en cuenta que lo que he descrito no garantizará una solución si existe, pero creo que debería poder encontrar una la mayor parte del tiempo si existe, y luego, en los casos en que el mapa no tiene solución, o el algoritmo falla encuentra uno, simplemente tira el mapa y prueba uno diferente :)

He implementado el siguiente algoritmo en mi solucionador de números y generador . Aplica la regla, que una ruta nunca puede tocarse, lo cual es normal en la mayoría de las aplicaciones y rompecabezas de enlaces numéricos "hardcore"

Primero, el tablero está embaldosado con dominós 2x1 de una manera simple y determinista. Si esto no es posible (en un papel de área impar), la esquina inferior derecha queda como un singleton.
Luego, los dominós se barajan aleatoriamente girando pares aleatorios de vecinos. Esto no se hace en el caso de anchura o altura igual a 1.
Ahora, en el caso de un papel de área impar, la esquina inferior derecha se adjunta a uno de sus dominós vecinos. Esto siempre será posible.
Finalmente, podemos comenzar a encontrar caminos aleatorios a través de los dominós, combinándolos a medida que pasamos. Se tiene especial cuidado de no conectar "flujos de vecinos" que crearían rompecabezas que se "doblan sobre sí mismos".
Antes de que se imprima el rompecabezas, ''compactamos'' la gama de colores utilizados, tanto como sea posible.
El rompecabezas se imprime reemplazando todas las posiciones que no son cabezas de flujo con a.

Mi formato de enlace numérico usa caracteres ascii en lugar de números. Aquí hay un ejemplo:

$ bin/numberlink --generate=35x20 Warning: Including non-standard characters in puzzle 35 20 ....bcd.......efg...i......i......j .kka........l....hm.n....n.o....... .b...q..q...l..r.....h.....t..uvvu. ....w.....d.e..xx....m.yy..t....... ..z.w.A....A....r.s....BB.....p.... .D.........E.F..F.G...H.........IC. .z.D...JKL.......g....G..N.j....... P...a....L.QQ.RR...N....s.....S.T.. U........K......V...............T.. WW...X.......Z0..M................. 1....X...23..Z0..........M....44... 5.......Y..Y....6.........C.......p 5...P...2..3..6..VH.......O.S..99.I ........E.!!......o...."....O..$$.% .U..&&..J.//.(.)......8...*.......+ ..1.......,..-...(/:.."...;;.%+.... ..c<<.==........)./..8>>.*.?......@ .[..[....]........:..........?..^.. ..._.._.f...,......-.`..`.7.^...... {{......].....|....|....7.......@..

Y aquí lo ejecuto a través de mi solver (la misma semilla):

$ bin/numberlink --generate=35x20 | bin/numberlink --tubes Found a solution! ┌──┐bcd───┐┌──efg┌─┐i──────i┌─────j │kka│└───┐││l┌─┘│hm│n────n┌o│┌────┐ │b──┘q──q│││l│┌r└┐│└─h┌──┐│t││uvvu│ └──┐w┌───┘d└e││xx│└──m│yy││t││└──┘│ ┌─z│w│A────A┌┘└─r│s───┘BB││┌┘└p┌─┐│ │D┐└┐│┌────E│F──F│G──┐H┐┌┘││┌──┘IC│ └z└D│││JKL┌─┘┌──┐g┌─┐└G││N│j│┌─┐└┐│ P──┐a││││L│QQ│RR└┐│N└──┘s││┌┘│S│T││ U─┐│┌┘││└K└─┐└─┐V││└─────┘││┌┘││T││ WW│││X││┌──┐│Z0││M│┌──────┘││┌┘└┐││ 1┐│││X│││23││Z0│└┐││┌────M┌┘││44│││ 5│││└┐││Y││Y│┌─┘6││││┌───┐C┌┘│┌─┘│p 5││└P│││2┘└3││6─┘VH│││┌─┐│O┘S┘│99└I ┌┘│┌─┘││E┐!!│└───┐o┘│││"│└─┐O─┘$$┌% │U┘│&&│└J│//│(┐)┐└──┘│8││┌*└┐┌───┘+ └─1└─┐└──┘,┐│-└┐│(/:┌┘"┘││;;│%+───┘ ┌─c<<│==┌─┐││└┐│)│/││8>>│*┌?│┌───┐@ │[──[└─┐│]││└┐│└─┘:┘│└──┘┌┘┌┘?┌─^││ └─┐_──_│f││└,│└────-│`──`│7┘^─┘┌─┘│ {{└────┘]┘└──┘|────|└───7└─────┘@─┘

He probado la sustitución del paso (4) con una función que, iterativamente, fusiona aleatoriamente dos rutas adyacentes. Sin embargo, es un juego de rompecabezas mucho más denso, y ya creo que lo anterior es demasiado denso para ser difícil.

Aquí hay una lista de problemas que he generado de diferentes tamaños: https://github.com/thomasahle/numberlink/blob/master/puzzles/inputs3

La forma más sencilla de crear un nivel así es encontrar una manera de resolverlo. De esta manera, básicamente puede generar cualquier configuración de inicio aleatoria y determinar si es un nivel válido al intentar resolverlo. Esto generará los más diversos niveles.

E incluso si encuentra una manera de generar los niveles de alguna otra manera, igual querrá aplicar este algoritmo de resolución para probar que el nivel generado es bueno;)

Enumeración de fuerza bruta

Si la placa tiene un tamaño de celdas NxN, y también hay N colores disponibles, la fuerza bruta enumera todas las configuraciones posibles (independientemente de si forman rutas reales entre los nodos de inicio y final):

N ^ 2 células totales
Células 2N ya ocupadas con nodos de inicio y fin
Células N ^ 2 - 2N para las que aún no se ha determinado el color
N colores disponibles.
N ^ (N ^ 2 - 2N) posibles combinaciones.

Asi que,

Para N = 5, esto significa 5 ^ 15 = 30517578125 combinaciones.
Para N = 6, esto significa 6 ^ 24 = 4738381338321616896 combinaciones.

En otras palabras, la cantidad de combinaciones posibles es bastante alta para comenzar, pero también crece de manera ridículamente rápida una vez que comienzas a agrandar el tablero.

Restricción del número de celdas por color.

Obviamente, deberíamos intentar reducir la cantidad de configuraciones lo más posible. Una forma de hacerlo es considerar la distancia mínima ("dMin") entre las celdas de inicio y final de cada color: sabemos que al menos debería haber tantas celdas con ese color. El cálculo de la distancia mínima se puede hacer con un relleno de inundación simple o el algoritmo de Dijkstra. (NB: tenga en cuenta que esta siguiente sección completa solo trata el número de celdas, pero no dice nada acerca de sus ubicaciones )

En su ejemplo, esto significa (sin contar las celdas de inicio y final)

dMin(orange) = 1 dMin(red) = 1 dMin(green) = 5 dMin(yellow) = 3 dMin(blue) = 5

Esto significa que, de las 15 celdas para las que aún no se ha determinado el color, debe haber al menos 1 naranja, 1 roja, 5 verde, 3 amarilla y 5 azules, lo que hace un total de 15 celdas. Para este ejemplo particular, esto significa que la conexión de las celdas de inicio y final de cada color mediante (una de) las rutas más cortas llena todo el tablero, es decir, después de llenar la tabla con las rutas más cortas, no quedan celdas sin color. (Esto debe considerarse "suerte", no todas las configuraciones iniciales de la placa harán que esto suceda).

Por lo general, después de este paso, tenemos un número de celdas que pueden colorearse libremente, llamemos a este número U. Para N = 5,

U = 15 - (dMin(orange) + dMin(red) + dMin(green) + dMin(yellow) + dMin(blue))

Debido a que estas celdas pueden tomar cualquier color, también podemos determinar el número máximo de celdas que pueden tener un color en particular:

dMax(orange) = dMin(orange) + U dMax(red) = dMin(red) + U dMax(green) = dMin(green) + U dMax(yellow) = dMin(yellow) + U dMax(blue) = dMin(blue) + U

(En este ejemplo en particular, U = 0, el número mínimo de celdas por color también es el máximo).

Búsqueda de caminos usando las restricciones de distancia

Si tuviéramos que utilizar la fuerza bruta para enumerar todas las combinaciones posibles utilizando estas restricciones de color, tendríamos muchas menos combinaciones de las que preocuparnos. Más específicamente, en este ejemplo particular tendríamos:

15! / (1! * 1! * 5! * 3! * 5!) = 1307674368000 / 86400 = 15135120 combinations left, about a factor 2000 less.

Sin embargo, esto todavía no nos da los caminos reales. por lo tanto, una mejor idea sería una búsqueda de seguimiento, donde procesamos cada color por turno e intentamos encontrar todas las rutas que:

no cruza una celda ya coloreada
No es más corto que dMin (color) y no más largo que dMax (color).

El segundo criterio reducirá la cantidad de rutas reportadas por color, lo que hace que la cantidad total de rutas a tratar se reduzca considerablemente (debido al efecto combinatorio).

En pseudocódigo:

function SolveLevel(initialBoard of size NxN) { foreach(colour on initialBoard) { Find startCell(colour) and endCell(colour) minDistance(colour) = Length(ShortestPath(initialBoard, startCell(colour), endCell(colour))) } //Determine the number of uncoloured cells remaining after all shortest paths have been applied. U = N^(N^2 - 2N) - (Sum of all minDistances) firstColour = GetFirstColour(initialBoard) ExplorePathsForColour( initialBoard, firstColour, startCell(firstColour), endCell(firstColour), minDistance(firstColour), U) } } function ExplorePathsForColour(board, colour, startCell, endCell, minDistance, nrOfUncolouredCells) { maxDistance = minDistance + nrOfUncolouredCells paths = FindAllPaths(board, colour, startCell, endCell, minDistance, maxDistance) foreach(path in paths) { //Render all cells in ''path'' on a copy of the board boardCopy = Copy(board) boardCopy = ApplyPath(boardCopy, path) uRemaining = nrOfUncolouredCells - (Length(path) - minDistance) //Recursively explore all paths for the next colour. nextColour = NextColour(board, colour) if(nextColour exists) { ExplorePathsForColour( boardCopy, nextColour, startCell(nextColour), endCell(nextColour), minDistance(nextColour), uRemaining) } else { //No more colours remaining to draw if(uRemaining == 0) { //No more uncoloured cells remaining Report boardCopy as a result } } } }

FindAllPaths

Esto solo deja a FindAllPaths (placa, color, startCell, endCell, minDistance, maxDistance) para ser implementado. Lo complicado aquí es que no estamos buscando las rutas más cortas, sino las rutas que caen en el rango determinado por minDistance y maxDistance. Por lo tanto, no podemos simplemente usar Dijkstra''s o A *, porque solo registrarán el camino más corto a cada celda, no cualquier desvío posible.

Una forma de encontrar estas rutas sería usar una matriz multidimensional para la placa, donde cada celda sea capaz de almacenar múltiples waypoints, y un waypoint se define como el par (waypoint anterior, distancia al origen). El punto de ruta anterior es necesario para poder reconstruir la ruta completa una vez que hayamos llegado al destino, y la distancia al origen nos impide superar la distancia máxima.

Luego se puede encontrar todos los caminos utilizando un relleno de inundación como la exploración desde el inicio de Celda hacia afuera, donde se explora recursivamente para cada celda determinada, sin color o con el mismo color que el color actual (excepto los que se forman) nuestro camino actual hacia el origen) hasta que alcancemos el endCell o excedamos el maxDistance.

Una mejora en esta estrategia es que no exploramos desde el inicio hasta el final hasta el final, sino que exploramos tanto desde el inicio como hacia el final, utilizando Floor (maxDistance / 2) y Ceil (maxDistance / 2) como Distancias máximas respectivas. Para valores grandes de maxDistance, esto debería reducir el número de celdas exploradas de 2 * maxDistance ^ 2 a maxDistance ^ 2.

Tienes dos opciones:

Escribe un solucionador personalizado
Bruta lo fuerza.

Utilicé la opción (2) para generar tableros tipo Boggle y es MUY exitoso. Si vas con la Opción (2), así es como lo haces:

Herramientas necesarias:

Escribe un solver A *.
Escribe un creador de tableros al azar

Resolver:

Generar un tablero aleatorio que consiste en solo puntos finales
mientras que el tablero no se resuelve:
- obtener dos puntos finales más cercanos entre sí que aún no están resueltos
- ejecutar A * para generar la ruta
- actualizar la placa para que la próxima A * conozca el nuevo diseño de la placa con la nueva ruta marcada como no transitable.
En la salida del bucle, verifique el éxito / falla (si se usa toda la placa / etc) y ejecute nuevamente si es necesario

El A * en un 10x10 debe ejecutarse en centésimas de segundo. Probablemente puedas resolver 1k + tablas / segundo. Por lo tanto, una carrera de 10 segundos debería darte varias tablas ''utilizables''.

Puntos extra:

Cuando genere niveles para un paquete de nivel IAP (en la compra de la aplicación), recuerde verificar si hay espejos / rotaciones / reflejos / etc para que no tenga una placa de una copia de otra (que es simplemente cojo).
Cree una métrica que determine si dos tableros son ''similares'' y, de ser así, abandone uno de ellos.