¿Cómo evitar que el algoritmo de aleatoriedad se "atasque"?

Question

Estoy haciendo un juego deshonesto y estoy usando una caminata aleatoria dentro de una cuadrícula para formar un sistema de 'cueva'. Sin embargo, la caminata aleatoria que he encontrado se atasca, en particular cuando el andador está cerca del borde de la cuadrícula y está rodeado de 'agujeros'.

Este no es el código exacto que estoy usando en mi proyecto, no puedo acceder a mi código desde el trabajo. Sin embargo, reescribí una muestra del mismo algoritmo que estoy usando en casa.

Básicamente, tomé una cuadrícula de 20x20 de enteros y la llené con 1. Mientras camino pongo un 0 en cada paso que doy.

void walk(int grid[][20]){ 
    int x = rand() % 10 + 9; 
    int y = rand() % 10 + 9; 

    int walk_count; 

    for(walk_count = rand() % 1000 + 500; walk_count >= 0; walk_count--){ 
    switch(rand() % 4){ 
     case 0: if(grid[x][y - 1] == 1 && y - 1 >= 1){ y--; grid[x][y] = 0;} break; 
     case 1: if(grid[x][y + 1] == 1 && y + 1 < 20){ y++; grid[x][y] = 0;} break; 
     case 2: if(grid[x - 1][y] == 1 && x - 1 >= 1){ x--; grid[x][y] = 0;} break; 
     case 3: if(grid[x + 1][y] == 1 && x + 1 < 20){ x++; grid[x][y] = 0;} break; 
     default: break; 
    } 
    } 
} 

Answer 1

Primero, explique la asimetría en su código. En el caso 1, tiene && y + 1 < 20. En el caso 3, tiene && x + 1 >= 1, que yo esperaría que fuera && x + 1 < 20.

Voy a señalar que como un error de transcripción/error tipográfico y no es la fuente de su problema. Según tengo entendido, tu problema es que tienes un caminante al azar que pinta el suelo y se está arrinconando. Se espera este comportamiento, ¿no es así?

El problema es que simplemente está haciendo una caminata aleatoria y espera un comportamiento que es más inteligente que aleatorio. Si quieres evitar arrinconarte, ponlo en tu algoritmo. Suponiendo que estos caminantes aleatorios quieren llegar al jugador, simplemente verifique que cada dirección, si está llena, todavía tendría un camino hacia el jugador. Luego, elija aleatoriamente entre las direcciones donde eso es cierto.

Answer 2

tengo una solución para usted:

primeros gráficos de uso: cada célula es vértice y si dos células son adyacentes y ambos 1, entonces hay una ventaja en el gráfico entre sus vértices.

Ahora, al caminar a una nueva celda y poner 0 en ella, se rompen todos los bordes que estaban conectados a su vértice.

Lo que tenemos aquí es que ahora puede ver los componentes conectados en el gráfico y decir si hay una ruta entre dos celdas (si están en el mismo componente conectado entonces hay una ruta), ya que probablemente tenga algún tipo de salida de la cueva, así que será la celda especial, y ahora puede construir una regla cuando la celda es "buena" solo si está en el mismo componente conectado que la celda especial.

Por último: su condición de caminar será solo si la celda adyacente es "buena" (desde antes) con esta condición nunca terminará en un callejón sin salida :) ya que siempre tendrá un camino hacia su salida (puede ser más de una :) no hay problema)

espero que les guste esta solución consulte más sobre gráficos aquí:

http://en.wikipedia.org/wiki/Graph_theory

http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29