Estoy tratando de generar aleatoriamente un gráfico dirigido con el propósito de hacer un juego de rompecabezas similar a los rompecabezas deslizantes de hielo de Pokemon.
Esto es esencialmente lo que quiero poder generar aleatoriamente: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory .
Necesito poder limitar el tamaño del gráfico en una dimensión x e y. En el ejemplo dado en el enlace, estaría restringido a una cuadrícula de 8x4.
El problema con el que me encuentro no es generar el gráfico al azar, sino generar un gráfico al azar, que puedo trazar correctamente en un espacio 2d, ya que necesito algo (como una roca) en el lado opuesto de un nodo, para hacerlo visualmente tiene sentido cuando deja de deslizarse. El problema con esto es que a veces la roca termina en el camino entre otros dos nodos o posiblemente en otro nodo, lo que hace que se rompa todo el gráfico.
Después de discutir el problema con algunas personas que conozco, llegamos a un par de conclusiones que pueden llevar a una solución.
- Incluyendo los obstáculos en la cuadrícula como parte del gráfico al construirlo.
- Comience con una cuadrícula llena y simplemente dibuje una ruta aleatoria y elimine los bloques que harán que esa ruta funcione.
El problema se convierte en averiguar cuáles eliminar para evitar la introducción de una ruta adicional más corta. También estábamos pensando que un algoritmo de programación dinámica puede ser beneficioso, aunque ninguno de nosotros es demasiado hábil para crear algoritmos de programación dinámica de la nada. Cualquier idea o referencia sobre cómo se llama oficialmente este problema (si se trata de un problema gráfico oficial) sería de gran ayuda.
Aquí hay algunos ejemplos de lo que he logrado hasta ahora al colocar bloques al azar y generar el gráfico de navegación desde el inicio / finalización elegidos. La idea (como se describe en el enlace anterior) es que comiences en la S verde y quieras llegar a la F. Verde. Lo haces moviéndote hacia arriba / abajo / izquierda / derecha y continúas en la dirección elegida hasta que tocas un pared. En estas imágenes, el gris es una pared, el blanco es el piso, y la línea púrpura es la longitud mínima de principio a fin, y las líneas negras y los puntos grises representan posibles caminos.
Aquí hay algunos malos ejemplos de gráficos generados aleatoriamente:
Aquí hay algunos buenos ejemplos de gráficos generados aleatoriamente (o ajustados a mano):
También he notado que los más desafiantes cuando en realidad se juega como un rompecabezas son los que tienen muchos nodos de alto grado a lo largo del camino mínimo.
fuente
Respuestas:
propiedades más avanzadas:
ejemplo:
ejemplo de combinar fichas:
puede que te guste el juego Tsuro , usa fichas para generar un tablero aleatorio.
fuente
Tal vez la ingeniería inversa podría ayudarlo si está preparado para eso.
Si hay una única solución para cada problema, probablemente pueda generar un gráfico basado en la respuesta única. Esto no requerirá que realice una programación dinámica o incluso omita la fuerza bruta y opte por una generación metódica.
Puedes hacerlo al:
Aunque necesitará un dispositivo de acuerdo con la complejidad del problema y el tamaño del problema que generará esta pregunta para usted. No te limites a la fuerza bruta. Pruebe con un algoritmo aleatorio en su lugar. Esto te puede ayudar.
fuente
¿Qué tal otro enfoque? Comience con un laberinto vacío y agregue bloques como este:
Toque final: encuentre la ruta más corta con el algoritmo que proporcionó. Tome nota de todas las celdas que se usan y comience a llenar el resto al azar, asegurándose siempre de que la ruta más corta no se acorte.
Hay una advertencia en el paso dos, cuando no puede colocar el último bloque para que no cruce los caminos utilizados, pero veo dos soluciones a esto: mueva el bloque final antes o deshaga algunos pasos e intente nuevamente.
Y otro pensamiento para la longitud aleatoria de los pasos deslizantes: es posible que desee elegirlo para que un bloque colocado anteriormente se reutilice, siempre que las rutas no se superpongan.
fuente