Red de conocimiento informático - Computadora portátil - registro experimental cs61b (3) proyecto 2 algoritmo de generación aleatoria prim maze

registro experimental cs61b (3) proyecto 2 algoritmo de generación aleatoria prim maze

nada especial

Para más detalles, consulte mi GitHub: /BoL0150/Berkeley-cs61b/tree/main/hw1

El objeto aleatorio es un "pseudo -número aleatorio" "Generador, que puede generar una secuencia infinita de números aparentemente aleatorios y llamar al método nextInt para obtener cada número de la secuencia.

La razón por la que se le llama "número pseudoaleatorio" es porque la secuencia que genera no es verdaderamente aleatoria. La forma en que obtenemos diferentes secuencias es pasar un número al constructor de Random. Este número se llama "semilla". Si construimos Random con la misma semilla, definitivamente obtendremos exactamente la misma secuencia.

También hay un método estático llamado random() en java.lang.Math que puede generar números aleatorios

El método Math.random() genera dobles en el rango de [0 , 1) Escriba un número aleatorio; los métodos de la serie nextXxxx(n) en la clase Random generan números aleatorios entre 0 (inclusive) y n (exclusivo).

Dibujar un mapa:

; Desde una perspectiva macro Desde el punto de vista anterior, se divide principalmente en los siguientes pasos:

Crear una clase de Habitación, tratar cada habitación como un objeto, generar aleatoriamente las coordenadas, el largo y el ancho de la habitación. y luego determine si las habitaciones se superponen.

También establezca un parámetro para controlar el límite superior del número de regeneraciones de habitaciones. Coloque todos los objetos de habitación generados en una Lista, porque después de construir el laberinto, debe conectar cada habitación con el laberinto al lado para obtener la ubicación y los parámetros de la habitación.

Las razones para llenar GRASS en la habitación y usar dos matrices en este momento se explicarán más adelante.

Desglosemos este paso primero: ¿cómo generar un laberinto en un gráfico vacío?

Utilizamos el algoritmo de generación aleatoria Prim maze. El principio y la implementación específica de este algoritmo son los siguientes:

Principio:

Implementación específica:

Al generar un laberinto, tenga cuidado de seleccionar puntos aleatoriamente de la lista de candidatos; de lo contrario, el laberinto generado estará en la misma dirección.

Sabemos cómo generar un laberinto en un gráfico vacío y También podemos inferir cómo generar un laberinto en un gráfico vacío. Generar un laberinto alrededor de la habitación

No hay nada que decir sobre este paso Seleccione aleatoriamente un punto en un borde de cada habitación para abrirlo. Si no se cumplen las condiciones (como NADA, etc.), seleccione un nuevo punto.

Sin embargo, todavía hay muchos callejones sin salida en la imagen en este momento (es decir, PISO con tres paredes), y la habitación todavía es HIERBA, por lo que debemos completar todos los callejones sin salida y reemplazarlos. CÉSPED con SUELO.

Para eliminar callejones sin salida, debemos verificar para cada punto si los cuatro puntos circundantes son MUROS y luego cambiar este punto antes de ingresar al siguiente. Esto le recuerda a la gente a DFS, pero el DFS original camina de un extremo a otro a lo largo de una ruta. Para cada punto de la carretera, simplemente verifica los puntos circundantes por turno. Una vez que encuentra un punto por el que se puede pasar, ingresa inmediatamente. Es imposible determinar si hay 3 MUROS alrededor de este punto.

Sólo cuando llegues al final y escanees los cuatro puntos circundantes y descubras que ninguno de ellos puede pasar, te retirarás. En otras palabras, solo cuando retrocedemos podemos conocer la situación de todos los puntos alrededor de un determinado punto. Para llenar todos los callejones sin salida, debemos comenzar desde los puntos finales de todos los callejones sin salida, converger hacia el medio y llenarlos a medida que avanzamos.

Por lo tanto, necesitamos transformar DFS para verificar la situación de todos los puntos circundantes cuando avanzamos y retrocedemos antes de continuar con el siguiente paso.

También necesitamos eliminar todas las paredes redundantes, es decir, la PARED sin SUELO en las cuatro esquinas.

Finalmente, agregamos Player y Lock_Door y listo

> Adjunto está la calificación del autograder