迷路を生成するときにコーナーを触れないようにするには

Question

私はPython 3で迷路ジェネレーターを開発しようとしていますが、近づいています。私は下の図のように迷路を作ることができるところまで持っていますが、あなたがよく見れば、私が心配している2つの問題を見ることができます。パスのコーナーが接触している場合もあります。これは、私が明示的に各潜在的なセル8エッジとコーナーをチェックすることによって回避しようとしているものです。私が見ることができるいくつかのスポットがありますが、それは空ですが、追加のセルのためのスペースを持つ "島"があります。どのように私がそれを修正できるかについてのあなたの考えがあるなら、それは素晴らしいでしょう。ありがとう！

import random 
import numpy as np 
from matplotlib import pyplot as plt 

# Width and height of the maze 
mx = 50 
my = 50 

# Maze Array 
maze = np.zeros((mx, my)) 

# Directions to move in the maze 
dx = [-1, 1, 0, 0, -1, 1, 1, -1] 
dy = [0, 0, -1, 1, -1, 1, -1, 1] 

# Visited Cells 
stack = [] 

# Find Which Neighbour Cells Are Valid 
def nextCell(cx, cy): 

    # Set Current Cell To '1' 
    maze[cy, cx] = 1 

    # List Of Available Neighbour Cell Locations 
    n = [] 

    # Check The 4 Available Neighbour Cells 
    for i in range(4): 

     nx = cx + dx[i] 
     ny = cy + dy[i] 

     # Check If Neighbours Cell Is Inbound 
     if nx >= 1 and nx < my - 1 and ny >= 1 and ny < mx - 1: 

      # Check If Neighbour Cell Is Occupied 
      if maze[ny, nx] == 0: 

       # Variable To Store Neighbour Cells Neighbours 
       cn = 0 

       # Loop Through Neighbour Cells Neighbours 
       for j in range(8): 

        ex = nx + dx[j] 
        ey = ny + dy[j] 

        # Check If Neighbour Cells Neighbour Is Inbound 
        if ex >= 0 and ex < my and ey >= 0 and ey < mx: 

         # Check If Neighbour Cells Neighbour Is Occupied 
         if maze[ey, ex] == 1: 
          cn += 1 

       # If Neighbour Cells Neighbour Has Less Than 2 Neighbours, Add Cell To List 
       if cn <= 2: 
        n.append((ny, nx)) 



    # Return The List Of Valid Neighbours 
    return n 

# Generate The Maze 
def GenerateMaze(sx, sy): 

    # Initialize 'x,y' With Starting Location 
    x = sx 
    y = sy 

    # Loop Until Maze Is Fully Generated 
    while True: 

     # Neighbour List 
     n = nextCell(x, y) 

     # Check If 'n' Contains A Neighbour 
     if len(n) > 0: 
      stack.append((y, x)) 

      ir = n[random.randint(0, len(n) - 1)] 

      x = ir[1] 
      y = ir[0] 

     # Go Back Through The Stack 
     elif len(stack) > 1: 
      stack.pop() 

      x = stack[-1][1] 
      y = stack[-1][0] 

     # Maze Is Complete 
     else:  
      break 



if __name__ == "__main__": 

    # Generate Maze 
    GenerateMaze(random.randint(1,8), random.randint(1,8)) 

    # Show Plot 
    plt.imshow(maze, interpolation='nearest') 
    plt.show() 

Answer 1

あなたはもう少し先に占有隣接セルをチェックするときに探すことで感動の角を取り除くことができます。ライン後

if maze[ny, nx] == 0: 

だけで次の行を追加します。

# Abort if there is an occupied cell diagonally adjacent to this one 
    if maze[ny+dy[i]+dx[i], nx+dx[i]+dy[i]] or maze[ny+dy[i]-dx[i], nx+dx[i]-dy[i]]: 
     continue 

はここでの結果です：島退治

は、私が思うに、少しトリッキーです。あなたが本当に避けたいものなら、より秩序ある方法で迷路を構築することをお勧めします。ウィキペディアにはmaze generation algorithmsに関するページがあります。無作為化されたKruskalのアルゴリズムはかなり良い結果をもたらし、Pythonで実装するのは非常に簡単なはずです。