Для вышеприведенного кода из-за метода перебора в лабиринте преобладают вертикальные линии. Должен отметить, что есть множество возможностей по «тонкой» настройке качества генерации. Например, можно перебирать координаты точек «роста» псевдослучайно (с помощью прибавления большого простого числа и взятия остатка от деления на число столбцов таблицы). Тогда общее число итераций останется прежним (~m*n/4), но избытка верикальных линий не будет. Можно еще до начала полного перебора выбрать небольшое число точек роста случайно, это совсем чуть-чуть замедлит алгоритм, но увеличит количество тройных ветвлений. Можно вначале выбрать несколько точек роста от границ лабиринта. В итоге получаются такие же запутанные лабиринты, как и у автора статьи, полностью заполненные и с фиксированным временем генерации.
Вторая версия
#!/usr/bin/env python3
"""
Рандомизированный вариант построения лабиринта
"""
import random
import turtle
import time
ALL_DIRECTIONS = ((1, 0), (-1, 0), (0, 1), (0, -1))
def create_maze(m, n): # д.б. нечетные числа
def grow_branch(maze, i, j):
while True:
directions = []
if i < m - 2 and maze[i + 2][j] == 0: directions.append((1, 0))
if i > 0 and maze[i - 2][j] == 0: directions.append((-1, 0))
if j < n - 2 and maze[i][j + 2] == 0: directions.append((0, 1))
if j > 0 and maze[i][j - 2] == 0: directions.append((0, -1))
if not directions:
break
delta_i, delta_j = directions[random.randrange(len(directions))]
for _ in range(2):
maze[i][j] = 1
i += delta_i
j += delta_j
maze[i][j] = 1
maze = [[0] * n for _ in range(m)]
for i in range(m):
maze[i][0] = 1
maze[i][-1] = 1
for j in range(n):
maze[0][j] = 1
maze[-1][j] = 1
m1 = (m + 1) // 2
n1 = (n + 1) // 2
# random branches at the border
grow_branch(maze, 0, random.randrange(2, n - 1, 2))
grow_branch(maze, m - 1, random.randrange(2, n - 1, 2))
grow_branch(maze, random.randrange(2, m - 1, 2), 0)
grow_branch(maze, random.randrange(2, m - 1, 2), n - 1)
# more random branches
for _ in range(max(m1, n1)):
i, j = random.randrange(0, m, 2), random.randrange(0, n, 2)
grow_branch(maze, i, j)
# "randomized" iteration over all cells
k = 0
for _ in range(m1 * n1):
k = (k + 15485863) % (m1 * n1) # prime number
i1, j1 = divmod(k, n1)
i, j = 2 * i1, 2 * j1
if maze[i][j] == 1:
# ветки растут лишь от уже существующих (удлинение)
grow_branch(maze, i, j)
return maze
def draw_maze(maze, m, n):
turtle.tracer(0, 0)
t = turtle.Turtle()
t.setundobuffer(None)
t.hideturtle()
t.color("blue")
t.up()
dy = 600 / m
dx = 800 / n
t.width(min(dx, dy))
for i in range(0, m, 2):
for j in range(0, n, 2):
if maze[i][j]:
if i < m - 1 and maze[i + 1][j]:
t.goto(dx * j - 400, 300 - dy * i)
t.down()
t.goto(dx * j - 400, 300 - dy * (i + 2))
t.up()
if j < n - 1 and maze[i][j + 1]:
t.goto(dx * j - 400, 300 - dy * i)
t.down()
t.goto(dx * (j + 2) - 400, 300 - dy * i)
t.up()
t.screen.update()
turtle.done()
def main():
# размеры лабиринта - нечетные числа
m = 151
n = 201
t1 = time.time()
maze = create_maze(m, n)
t2 = time.time()
print(t2 - t1, "sec")
draw_maze(maze, m, n)
main()
Вот реализация похожая на ваш исходный алгоритм, но в ней случайный поиск свободной точки заменен на обычный перебор. Не требует искусственного ограничения итераций и работает, я полагаю, быстрее.
#!/usr/bin/env python3
import random
import turtle
import time
m = 151
n = 201
all_directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
t1 = time.time()
maze = [[0] * n for i in range(m)]
for i in range(m):
maze[i][0] = 1
maze[i][-1] = 1
for j in range(n):
maze[0][j] = 1
maze[-1][j] = 1
for i1 in range(2, m - 1, 2):
for j1 in range(2, n - 1, 2):
i, j = i1, j1
while True:
directions = [d for d in all_directions
if maze[i + 2 * d[0]][j + 2 * d[1]] == 0]
if not directions:
break
delta_i, delta_j = directions[random.randrange(len(directions))]
for _ in range(2):
maze[i][j] = 1
i += delta_i
j += delta_j
maze[i][j] = 1
t2 = time.time()
print(t2 - t1, "sec")
turtle.tracer(0, 0)
t = turtle.Turtle()
t.setundobuffer(None)
t.hideturtle()
t.color("blue")
t.width(5)
t.up()
for i in range(2, m - 1):
for j in range(2, n - 1):
if maze[i][j]:
t.goto(-400 + 4 * j, 300 - 4 * i)
t.down()
t.forward(0)
t.up()
t.screen.update()
turtle.done()
В период 2008—2010 годов в китайском Северо-западном политехническом университете под руководством профессора Яна Цзюаня был создан прототип, развивающий усилие 0,72 Н. В 2016 году статья была отозвана, так как была обнаружена большая ошибка в измерениях, после исправления которой измеренная тяга оказалась в пределах шума измерений.
Предлагаю неточное выражение «Работоспособность EmDrive подтверждена NASA» везде заменять на «Проверка работоспособности Emdrive независимыми исследователями привела к отрицательным результату.»
Вы правы, работы на самом деле много. Настоящей работы, связанной с анализом экспериментальных данных, с созданием новых, проверяемых моделей, итп. Один конфайнмент чего стоит. Сейчас это не котируется — много работать над старой проблемой, которая часто вообще не проблема, а научное направление. То ли дело громкий треск модных слов, возможность попиариться, премия Миллера, непроверяемые утверждения, и конечно же «Эту теорию понимают 1 — 5 человек во всем мире!».
Обе «теории» — не подтвержденные НИЧЕМ гипотезы, в настоящее время просто математика (математику не обижаю, упор на то, что это не физика). Что поделать, в физике высоких энергий кризис, известные элементарные частицы превращаются при столкновениях в самих себя, конец (шучу). Но ведь нужно как-то выдавать публикации пачками, устраивать конференции и становиться профессорами? Вот, есть такая деятельность, можно в ней участвовать. Небольшое усложнение, переход от точечных базовых объектов к одномерным, позволяет десятилетиями кормиться немалой части научного сообщества. Измышление гипотез стало вполне респектабельным занятием. Представьте, что ваш ноутбук это лишь четырехмерная проекция некоего юбердивайса, существующего в 30-мерном пространстве с двумя временными осями, при этом упомянутую проекцию можно осуществить 10^500 способами. Когда наша цивилизация перейдет в стадию IV или V по (расширенной) классификации Кардашева, это утверждение можно будет проверить. Наверное. Если не придумают новую «теорию», с 10^100^100 измерениями.
Основная проблема с путешествиями по галактике — ограниченность предельной скорости распространения взаимодействий. Давайте подумаем, как ее превысить.
В период 2008—2010 годов в китайском Северо-западном политехническом университете под руководством профессора Яна Цзюаня был создан прототип, развивающий усилие 0,72 Н. В 2016 году статья была отозвана, так как была обнаружена большая ошибка в измерениях, после исправления которой измеренная тяга оказалась в пределах шума измерений.
Предлагаю неточное выражение «Работоспособность EmDrive подтверждена NASA» везде заменять на «Проверка работоспособности Emdrive независимыми исследователями привела к отрицательным результату.»