Генерация случайных лабиринт с помощью непересекающихся множества


Я как-то писала, что генерирует случайный лабиринт с помощью непересекающихся множества, используя группировку класс я нашла здесь.

Я генерации лабиринта путем создания всех клеток, с каждой ячейкой, имеющей стене справа от него и под ним. Каждая стена может быть активным или нет.

Я выбираю стену случайным образом и выглядят на пару клеток по обе стороны от него, чтобы увидеть, если они находятся в одной группе (подключен), если они есть, я оставляю стену, если это не так, я разрушить стену, и вступайте в группы соседних клеток принадлежал.

Это будет продолжаться, пока все клетки связаны. Я тогда пытаюсь печатать лабиринт, наверное, действительно ужасным способом.

Я действительно хотел бы получить некоторую обратную связь на все, что я мог бы сделать лучше. Можно ли сделать код более эффективным? Если я делаю 1000*1000 лабиринте, это занимает очень много времени, чтобы вычислить.

import random
from grouper import Grouper
import sys

X = 20
Y = 20

class Cell():
    """Represents a cell in the maze, with an x and y coordinate and its
    right hand wall and downwards wall.

    """
    def __init__(self, x, y):
        self.x, self.y = x, y
        self.right_wall = self.down_wall = None

class Wall():
    """Represents a wall in the maze with its two neighbouring cells.
    """
    def __init__(self):
        self.neighbours = None
        self.active = True

def popchoice(seq):
    """Takes an iterable and pops a random item from it.
    """
    return seq.pop(random.randrange(len(seq)))

# A mapping of coord tuple to Cell object    
cells = {}
# A list of all the non-edge walls
walls = []

# Generate cells
for y in range(Y):
    for x in range(X):
        cells[(x, y)] = Cell(x, y)

# Generate walls and add to the neighbouring cells
for y in range(Y):
    for x in range(X):
        current_cell = cells[(x,y)]
        down_wall = Wall()
        current_cell.down_wall = down_wall
        right_wall = Wall()
        current_cell.right_wall = right_wall
        if y != Y-1:
            down_wall.neighbours = (current_cell, cells[(x,y+1)])
            walls.append(down_wall)

        if x != X-1:
            right_wall.neighbours = (current_cell, cells[(x+1,y)])
            walls.append(right_wall)


# Get a list of all the cell objects to give to the Grouper            
cell_list = [cells[key] for key in cells]

maze = Grouper(cell_list)

for _ in range(len(walls)):
    # Pop a random wall from the list and get its neighbours
    wall = popchoice(walls)
    cell_1, cell_2 = wall.neighbours
    # If the cells on either side of the wall aren't already connected,
    # destroy the wall
    if not maze.joined(cell_1, cell_2):
        wall.active = False
        maze.join(cell_1, cell_2)

# Draw the maze

maze_map = []

x_max = (X*2)+1
y_max = (Y*2)+1

# Make an empty maze map with True for wall and False for space
# Make top wall
maze_map.append([True for _ in range(x_max)])
for y in range(1, y_max):
    # Make rows with left side wall
    maze_map.append([True]+[False for _ in range(1, x_max)])

# Add the down and right walls from each cell to the map
for coords, cell in cells.items():
    x, y = coords
    # Add the intersection wall for each cell (down 1 right 1)
    maze_map[(y*2)+2][(x*2)+2] = True
    if cell.right_wall.active:
        maze_map[(y*2)+1][(x*2)+2] = True
    if cell.down_wall.active:
        maze_map[(y*2)+2][(x*2)+1] = True

def output(string):
    sys.stdout.write(string)

# Print the map
for row in maze_map:
    for tick in row:
        if tick: output('X'),
        else: output('.'),
    output('\n')

Это дает лабиринт такой:

XXXXXXXXXXXXXXXXXXXXX
X.......X...X.X.X...X
XXX.XXXXXXX.X.X.X.XXX
X.X...............X.X
X.XXXXXXXXX.XXXXX.X.X
X...X...X.X.X.......X
X.XXXXX.X.X.XXXXXXXXX
X.X.X.....X...X...X.X
X.X.XXX.XXX.XXXXX.X.X
X.X...X.........X...X
X.XXX.XXX.X.XXX.X.XXX
X...X.X.X.X.X.X.X.X.X
XXX.X.X.XXX.X.XXX.X.X
X.................X.X
XXXXX.XXX.XXXXX.X.X.X
X...X.X.X.X...X.X.X.X
XXX.XXX.X.XXX.X.XXX.X
X.X...X...X.....X...X
X.X.X.XXX.X.X.XXX.X.X
X...X.....X.X.....X.X
XXXXXXXXXXXXXXXXXXXXX


2221
7
задан 2 апреля 2011 в 11:04 Источник Поделиться
Комментарии
1 ответ

import random
from grouper import Grouper
import sys

X = 20
Y = 20

class Cell():

Либо объектов в качестве базового класса, или не включают (). Это действительно не имеет значения, но я думаю, что это некрасиво.

    """Represents a cell in the maze, with an x and y coordinate and its
right hand wall and downwards wall.

"""
def __init__(self, x, y):
self.x, self.y = x, y
self.right_wall = self.down_wall = None

class Wall():
"""Represents a wall in the maze with its two neighbouring cells.
"""
def __init__(self):
self.neighbours = None
self.active = True

def popchoice(seq):
"""Takes an iterable and pops a random item from it.
"""
return seq.pop(random.randrange(len(seq)))

Назвать это pop_choice так что вам не придется гадать, где одно слово начинается, а другой существует. Также он принимает последовательность не повторяемое

# A mapping of coord tuple to Cell object    
cells = {}

Рекомендую смотреть и NumPy. Он имеет тип массива. В принципе, вы можете создать массив как: клетки = и NumPy.массив( (Г,Х), объекта), который обеспечит эффективную 2D структуры массива. Что будет лучше работать и быстрее, чем используемый словарь.

# A list of all the non-edge walls
walls = []

# Generate cells
for y in range(Y):
for x in range(X):
cells[(x, y)] = Cell(x, y)

Вы не должны делать логику и петли в области модуля. Они медленнее есть то в функции.

# Generate walls and add to the neighbouring cells
for y in range(Y):
for x in range(X):
current_cell = cells[(x,y)]
down_wall = Wall()
current_cell.down_wall = down_wall
right_wall = Wall()
current_cell.right_wall = right_wall
if y != Y-1:
down_wall.neighbours = (current_cell, cells[(x,y+1)])
walls.append(down_wall)

if x != X-1:
right_wall.neighbours = (current_cell, cells[(x+1,y)])
walls.append(right_wall)

Вы создаете стены в любом случае, но только иногда добавлять их к стенам. Это предполагает либо ошибка или так называемой стены переменной.

# Get a list of all the cell objects to give to the Grouper            
cell_list = [cells[key] for key in cells]

Если через дикт, это так же, как cell_list = клетки.значения() если вы используете библиотеки numpy массивы, как я предлагаю его cell_list = клетки.расплющить()

maze = Grouper(cell_list)

Эта переменная действительно не держала лабиринт. Назвав его Лабиринт вводит в заблуждение

for _ in range(len(walls)):
# Pop a random wall from the list and get its neighbours
wall = popchoice(walls)
cell_1, cell_2 = wall.neighbours
# If the cells on either side of the wall aren't already connected,
# destroy the wall
if not maze.joined(cell_1, cell_2):
wall.active = False
maze.join(cell_1, cell_2)

Это делать не так:

random.shuffle(walls)
for wall in walls:
cell_1, cell_2 = wall.neighbours
...

Это будет эффективнее и понятнее.

# Draw the maze

maze_map = []

x_max = (X*2)+1
y_max = (Y*2)+1

Не понятно, зачем нужно x_max, комментарий будет полезен пояснив, что

# Make an empty maze map with True for wall and False for space
# Make top wall
maze_map.append([True for _ in range(x_max)])
for y in range(1, y_max):
# Make rows with left side wall
maze_map.append([True]+[False for _ in range(1, x_max)])

Вот еще один случай, который можно реально использовать ndarrays и NumPy это:

maze_map = numpy.zeros( (x_max, y_max), bool)
maze_map[0,:] = True
maze_map[:,0] = True

Что делает то же, что весь код maze_map до сих пор. Также, называя maze_map, перекрыли что бы было понятнее, почему вы ставите истинного/ложного в ней.

# Add the down and right walls from each cell to the map
for coords, cell in cells.items():
x, y = coords
# Add the intersection wall for each cell (down 1 right 1)
maze_map[(y*2)+2][(x*2)+2] = True
if cell.right_wall.active:
maze_map[(y*2)+1][(x*2)+2] = True
if cell.down_wall.active:
maze_map[(y*2)+2][(x*2)+1] = True

Формула используется, чтобы выяснить, какие клетки находятся под ссылкой, Это трудно выяснить.

def output(string):
sys.stdout.write(string)

# Print the map
for row in maze_map:
for tick in row:
if tick: output('X'),
else: output('.'),
output('\n')

Следующий может быть более четкой версией для рисования:

def output(blocked):
sys.stdout.write(".*"[blocked])

for x in range(2*X+1):
output(True)
sys.stdout.write('\n')

for y in range(Y):
output(True)
for x in range(X):
cell = cells[(x,y)]
output(False)
output(cell.right_wall.active)
sys.stdout.write('\n')
output(True)
for x in range(X):
cell = cells[(x,y)]
output(cell.down_wall.active)
output(True)
sys.stdout.write('\n')

Я думаю, что его немного яснее, потому что нет формулы, как 2*х+1. Он должен больше комментировать, но я верю, ты справишься с этим.

Редактировать

Для библиотеки numpy, использовать его как это:

cells = numpy.empty( (X,Y), object)
# object is the python object type, not the object you want to put into it
# python's default is to use a number types which are more efficient
# but we aren't storing numbers
for x, y in numpy.ndindex(X, Y):
cell[index] = Cell(x,y)

Скорость:

Самый большой срок-потребитель в коде-это код окунь. Этот код предпочла реализуется проще, а затем более эффективный алгоритм для этой задачи. Вы должны действительно implememt Союза-найти алгоритм. Этот алгоритм является сумасшедшим эффективны, работает в за то, что всех намерений и целей постоянное время.

Память:

Если память не является проблемой, добавить слоты к классам. Посмотрите в документации, как это сделать. Однако, я не беспокойтесь, если вам действительно не хватает памяти.

5
ответ дан 3 апреля 2011 в 12:04 Источник Поделиться