Generador de laberinto acíclico aleatorio con punto de entrada y salida dado

Dados dos números enteros N y M , la tarea es generar cualquier laberinto de tamaño N * M que contenga solo 0 (que representa una pared) y 1 (que representa un espacio vacío donde uno puede moverse) con el punto de entrada como P0 y el punto de salida P1 y allí es sólo un camino entre dos posiciones móviles cualesquiera.

Nota: P0 y P1 estarán marcados como 2 y 3 respectivamente y uno puede moverse a través de las posiciones móviles en 4 direcciones (arriba, abajo, derecha e izquierda).

Ejemplos:

Entrada: N = 5, M = 5, P0 = (0, 0), P1 = (4, 4)
Salida: laberinto = [ [ 2 1 1 1 1 ],
                             [ 1 0 1 0 1 ],
                             [ 1 0 1 0 0 ],
                             [ 1 1 0 1 0 ],
                             [ 0 1 1 1 3 ] ]
Explicación: Es válido porque no hay ciclo,  
y no hay posición transitable inalcanzable.
Algunas otras opciones podrían ser 
[ [ 2 1 1 1 1 ],
  [ 1 0 1 0 1 ],
  [ 1 0 1 0 0 ],
  [ 1 1 1 1 0 ],
  [ 0 0 0 1 3 ] ] 
o
[ [ 2 1 1 0 1 ],
  [ 1 0 1 0 1 ],
  [ 1 0 1 0 0 ],
  [ 1 0 1 1 0 ],
  [ 1 0 0 1 3 ] ].
Pero estos no son válidos porque en el primero hay un ciclo en el laberinto
y en el segundo (0, 4) y (1, 4) no se puede llegar desde el punto de partida.

 

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Use un DFS que comience desde la posición P0 y se mueva a cualquiera de los vecinos pero no haga un ciclo y termine en P1. De esta manera, solo habrá 1 camino entre dos posiciones móviles cualesquiera.

Siga los siguientes pasos para implementar la idea:

  • Inicialice una pila (S) para el DFS iterativo , la array que se devolverá como el laberinto aleatorio. 
  • Inserte el punto de entrada P0 en la pila.
  • Mientras S no esté vacío, repita los siguientes pasos:
    • Elimine una posición (digamos P ) de S y márquela como se ve.
      • Si marca la posición transitable, forma un ciclo, entonces no la incluya como una posición móvil.
      • De lo contrario, establezca la posición como transitable.
    • Inserte los vecinos de P que no son visitados en orden aleatorio en la pila.
    • La inserción aleatoria en la pila garantiza que el laberinto que se genera es aleatorio.
    • Si alguno de los vecinos es el mismo que el P1 , insértelo en la parte superior para que no saltemos esta posición debido a la formación del ciclo.
  • Marque la posición inicial P0 (con 2) y la posición final P1 (con 3)
  • Devuelve el laberinto.

A continuación se muestra la implementación del enfoque anterior:

Python3

# Python3 code to implement the approach
  
from random import randint
  
# Class to define structure of a node
class Node:
    def __init__(self, value = None, 
               next_element = None):
        self.val = value
        self.next = next_element
  
# Class to implement a stack
class stack:
    
    # Constructor
    def __init__(self):
        self.head = None
        self.length = 0
  
    # Put an item on the top of the stack
    def insert(self, data):
        self.head = Node(data, self.head)
        self.length += 1
  
    # Return the top position of the stack
    def pop(self):
        if self.length == 0:
            return None
        else:
            returned = self.head.val
            self.head = self.head.next
            self.length -= 1
            return returned
  
    # Return False if the stack is empty 
    # and true otherwise
    def not_empty(self):
        return bool(self.length)
  
    # Return the top position of the stack
    def top(self):
        return self.head.val
  
# Function to generate the random maze
def random_maze_generator(r, c, P0, Pf):
    ROWS, COLS = r, c
      
    # Array with only walls (where paths will 
    # be created)
    maze = list(list(0 for _ in range(COLS)) 
                       for _ in range(ROWS))
      
    # Auxiliary matrices to avoid cycles
    seen = list(list(False for _ in range(COLS)) 
                           for _ in range(ROWS))
    previous = list(list((-1, -1) 
     for _ in range(COLS)) for _ in range(ROWS))
  
    S = stack()
      
    # Insert initial position
    S.insert(P0) 
  
    # Keep walking on the graph using dfs
    # until we have no more paths to traverse 
    # (create)
    while S.not_empty():
  
        # Remove the position of the Stack
        # and mark it as seen
        x, y = S.pop()
        seen[x][y] = True
  
        # Check if it will create a cycle
        # if the adjacent position is valid 
        # (is in the maze) and the position 
        # is not already marked as a path 
        # (was traversed during the dfs) and 
        # this position is not the one before it
        # in the dfs path it means that 
        # the current position must not be marked.
          
        # This is to avoid cycles with adj positions
        if (x + 1 < ROWS) and maze[x + 1][y] == 1 \
        and previous[x][y] != (x + 1,  y):
            continue
        if (0 < x) and maze[x-1][y] == 1 \
        and previous[x][y] != (x-1,  y):
            continue
        if (y + 1 < COLS) and maze[x][y + 1] == 1 \
        and previous[x][y] != (x, y + 1):
            continue
        if (y > 0) and maze[x][y-1] == 1 \
        and previous[x][y] != (x, y-1):
            continue
  
        # Mark as walkable position
        maze[x][y] = 1
  
        # Array to shuffle neighbours before 
        # insertion
        to_stack = []
  
        # Before inserting any position,
        # check if it is in the boundaries of 
        # the maze
        # and if it were seen (to avoid cycles)
  
        # If adj position is valid and was not seen yet
        if (x + 1 < ROWS) and seen[x + 1][y] == False:
              
            # Mark the adj position as seen
            seen[x + 1][y] = True
              
            # Memorize the position to insert the 
            # position in the stack
            to_stack.append((x + 1,  y))
              
            # Memorize the current position as its 
            # previous position on the path
            previous[x + 1][y] = (x, y)
          
        if (0 < x) and seen[x-1][y] == False:
              
            # Mark the adj position as seen
            seen[x-1][y] = True
              
            # Memorize the position to insert the 
            # position in the stack
            to_stack.append((x-1,  y))
              
            # Memorize the current position as its 
            # previous position on the path
            previous[x-1][y] = (x, y)
          
        if (y + 1 < COLS) and seen[x][y + 1] == False:
              
            # Mark the adj position as seen
            seen[x][y + 1] = True
              
            # Memorize the position to insert the 
            # position in the stack
            to_stack.append((x, y + 1))
              
            # Memorize the current position as its
            # previous position on the path
            previous[x][y + 1] = (x, y)
          
        if (y > 0) and seen[x][y-1] == False:
              
            # Mark the adj position as seen
            seen[x][y-1] = True
              
            # Memorize the position to insert the 
            # position in the stack
            to_stack.append((x, y-1))
              
            # Memorize the current position as its 
            # previous position on the path
            previous[x][y-1] = (x, y)
          
        # Indicates if Pf is a neighbour position
        pf_flag = False
        while len(to_stack):
              
            # Remove random position
            neighbour = to_stack.pop(randint(0, len(to_stack)-1))
              
            # Is the final position, 
            # remember that by marking the flag
            if neighbour == Pf:
                pf_flag = True
              
            # Put on the top of the stack
            else:
                S.insert(neighbour)
          
        # This way, Pf will be on the top 
        if pf_flag:
            S.insert(Pf)
                  
    # Mark the initial position
    x0, y0 = P0
    xf, yf = Pf
    maze[x0][y0] = 2
    maze[xf][yf] = 3
      
    # Return maze formed by the traversed path
    return maze
  
# Driver code
if __name__ == "__main__":
    N = 5
    M = 5
    P0 = (0, 0)
    P1 = (4, 4)
    maze = random_maze_generator(N, M, P0, P1)
    for line in maze:
        print(line)
Producción

[2, 0, 0, 1, 1]
[1, 1, 1, 0, 1]
[0, 0, 1, 1, 1]
[1, 1, 0, 0, 1]
[0, 1, 1, 1, 3]

Complejidad de tiempo: O(N * M)

  • Como el algoritmo es básicamente un DFS con más condiciones, la complejidad temporal es la complejidad temporal del DFS: O(V+E) (donde V es el número de vértices y E es el número de aristas). 
  • En este caso, el número de vértices es el número de cuadrados en la array: N * M. Cada «vértice» (cuadrado) tiene como máximo 4 «aristas» (4 cuadrados adyacentes), por lo que E < 4*N*M. Entonces O(V+E) será O(5*N*M), es decir, O(N*M).

Espacio Auxiliar: O(N * M)

  • Cada array auxiliar necesita O(N*M) de espacio. 
  • La pila no puede tener más de N*M cuadrados dentro, porque nunca contiene (en esta implementación) el mismo cuadrado más de una vez. 
  • La suma de todos los espacios mencionados será O(N*M). 

Publicación traducida automáticamente

Artículo escrito por raafm y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *