Comments 54
Где же код?
Всё очень хорошо, но тут скорее — «где же текст?», за картинки — спасибо, тема про крота — не раскрыта.
А ссылка на страницу в самом начале? Там весь алгоритм, вроде доступно расписан.
Не хотелось отвлекаться от сути, а после статьи желания вернуться в начало не было. Хотя заголовок у вас правильно передаёт мысль, но первый абзац читается в довольно чётком ключе: «продолжение алгоритма с упором на реализацию». Манипулировать читателем предупреждениями — бессмысленно, это просто ушло в игнор на автомате. Ну а поскольку никакого алгоритма не было, а была только реализация то закономерно: просмотреть наискосок и читать следующие вкладки браузера. Наверное, формально, вы — правы. За гифку в первой части, спасибо.
Почему бы не использовать отступы в 16 символов или давайте сразу в 64. Никогда не понимал это странное желание растягивать код, что по горизонтали что по вертикали.
По мне так 4 вполне хороший компромисс: 2 позиции для меня недостаточно выразительны, а 8 разрывают канву повествования. Но я-то и открывающую фигурную сношу, чтобы визуальное сопоставление с закрывающей было «автоматическим».
Это нативные табы. По-умолчанию они шириной в 8 символов (что актуально для текста), на хабре просто в стилях не хватает указания корректного размера. Попробуйте сами в консоли запустить:
document.body.style.tabSize = 4
Код, конечно, ужасен — это медицинский факт, но отступы-то там же по 1 символу всего?
Насчёт двойных if — почитайте про операцию &&, будете приятно удивлены (она не вычисляет второй аргумент, если достаточно первого)
Также, обратите внимание на фигурные скобки после первичного if — else относится именно к нему, а другой способ записать это мне неизвестен.
Это у вас из питона такой ужасный стиль расстановки скобок? Со скобками пишется так:
if (x != 1) {
if (maze[y][x-2] == pass) {
a += 1;
}
} else {
a += 1;
}или так
if (x != 1)
{
if (maze[y][x-2] == pass)
{
a += 1;
}
}
else
{
a += 1;
}Иначе вы когда-нибудь запутаетесь и сделаете ошибку. В питоне компилятор отступы проверяет, а тут он вам ничего не подскажет.
Это можно записать еще проще:
if (x == 1 || maze[y][x-2] == pass)
a += 1;
Нет, алгоритм будет убиваться возле стен.
Я ничего не знаю про алгоритм, это просто логика. Если вы посмотрите на изначальное условие, то увидите, что выражение а += 1 выполнится в 2-х случаях: (x == 1) или (maze[y][x-2] == pass && х != 1). Во вторую часть условия можно попасть только тогда, когда х != 1, в противном случае мы попадаем в первую часть, поэтому проверять на x != 1 не имеет смысла.
Просто привык не ставить скобки для одной операции. Да, питон портит людей.
Ни фига себе неприлично простой. Я думал тут что-то в духе 10 PRINT CHR$(205.5+RND(1));: GOTO 10, а тут такие простыни кода…
О_о
Зачем вы это сделали? Теперь я не засну, пока не пойму, как оно работает…
Зачем вы это сделали? Теперь я не засну, пока не пойму, как оно работает…
В ASCII таблице Commodore64 на позициях 205 и 206 находились диагональные линии (вроде /и \ только под углом 45 градусов).
Эта программа просто выводит в случайном порядке либо одну линию, либо другую.
Была такая мысль, но тогда мне неочевидно, что должен получиться такой крависый связный рисунок.
Поблагодарим JTG за это
Потому что линии стыкуются друг с другом. Просто попробуйте внимательно изучить скриншот или возьмите тетрадь в клеточку и нарисуйте несколько строк диагональных линий. Можно бросать монетку для истиной случайности :-)
Сам алгоритм простой :). Просто студентов не учат как писать простые алгоритмы, что функция должна влезать на экран, декомпозиция и тому подобное. Или учат, но на последних курсах, которые студенты уже не посещают, так как на фултайме на php пишут :). Соответственно выглядит это как спагетти, черти какой уровень вложенности кода, почти вся логика в одном методе и т.д. Тоже самое можно написать гораздо проще и понятнее, но для этого нужно чтоб автору показали как это делать.
Кстати, не могу не вспомнить другой, ещё более простой алгоритм генерации лабиринтов:
- Окружаем лабиринт стеной, внутри пока пусто.
- Случайно выбираем "кирпич" с чётной координатой на одной из сторон.
- Начинаем строить от него стену — причём сразу после кирпича пропускаем одну позицию (оставляем проход)
- Повторяем 1-2 в случайном порядке для остальных "чётных" кирпичей на всех 4 стенах.
(Получается, что в первой стене будет проход у края, в перпендикулярной ей — у края и у первой стены и так далее)
Не помню, в какой книжке я его вычитал в детстве, но работал на бейсике на тогдашних машинках (8-битный проц 8080, 2 мегагерца тактовая, от 4 тактов на инструкцию — т.е. эдак на 4 порядка медленней нынешних) довольно шустро.
Хотя алгоритм несколько примитивный.
Метод рекурсивного деления (Recursive division method).
Не совсем: стена всегда строится от края до края лабиринта (что исключает рекурсию, там просто два цикла for).
Но действительно создаёт лишь подмножество множества лабиринтов, создаваемых методом рекурсивного деления.
Генерация лабиринтов – прекрасная тема для изучения, для которой, в общем-то, код наименее важен. В этой статье кода значительно больше, чем самого алгоритма и его разбора.
Посему, вопрос к коммьюнити: стоит ли делать цикл статей по 11 «классическим» алгоритмам процедурной генерации лабиринтов? Есть ли люди, которым это интересно? (с картинками, объяснениями, гифками, кодом и печеньками)
Посему, вопрос к коммьюнити: стоит ли делать цикл статей по 11 «классическим» алгоритмам процедурной генерации лабиринтов? Есть ли люди, которым это интересно? (с картинками, объяснениями, гифками, кодом и печеньками)
Простите, прочитал вашу предыдущую статью. И очень опечалился. Назвать алгоритм Эллера – неэффективным по памяти, это, конечно, сильно. Он способен генерировать бесконечно-большие гриды, так как смотрит только один ряд за проход. Ему вообще до лампочки, что там сверху и снизу. Единственное ограничение по памяти – хранения грида. Но и его можно оптимизировать, например, матрицой смежности.
Да, мне уже говорили, что я его не очень правильно реализовал раз выходят такие накладки. Просто опять-таки, я связывался с лабиринтами, размерностью 150х150, что подразумевало использование типа ineger, а не byte. На тот момент это было серьезной проблемой, а использование массива 2х150 для работы и какой-нибудь булевый массив для сохранения я не додумался, пардон.
размерностью 150х150, что подразумевало использование типа ineger, а не byte.
Честно говоря, не понял, почему у Вас размер поля с типом данных связан.
Как я понял, в алгоритме Эллера нужно было нумеровать ячейки, а после этого объединять их в группы случайным образом. Длинна 150 — 150 номеров, а byte в Pascal ограничен в размерах до 128. Опять-таки, поправьте если я где-то ошибаюсь.
UFO just landed and posted this here
Обязательно напишите! Я с удовольствием прочитаю, для меня эта тема весьма интересна.
Есть-есть. Тема очень интересная. Натыкался на сайт с огромной коллекцией разных описаний способов генерации (к сожалению потерял ссылку). Залип уже на одних картинках. Правда там были очень хитрые варианты.
Картинки могу покидать в ЛС :)
А так, на английском языке отличные: ThinkLabyrinth, Buckblog, книжка Mazes for Programmers.
А так, на английском языке отличные: ThinkLabyrinth, Buckblog, книжка Mazes for Programmers.
О, как раз первый, спасибо :)
Собственно куча алгоритмов на английском если кому интересно.
Собственно куча алгоритмов на английском если кому интересно.
По факту, алгоритмов там не куча. Там в целом очень много информации по теме :)
Различные термины, объяснения, техники. Но это чисто справочник. Но сайт полезный, да.
Различные термины, объяснения, техники. Но это чисто справочник. Но сайт полезный, да.
На самом деле там интересен уже один только список алгоритмов. В котором есть и не прямоугольные, и вообще не имеющие явной сетки.
Если мы про те, что «Perfect Maze Creation Algorithms», то именно о них я и собираюсь писать. (разве что, опущу на первое время их вариации). Основная проблема в переводе термина bias – никак не могу подобрать аналог на русском языке :(
Вот реализация похожая на ваш исходный алгоритм, но в ней случайный поиск свободной точки заменен на обычный перебор. Не требует искусственного ограничения итераций и работает, я полагаю, быстрее.
#!/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()
Для вышеприведенного кода из-за метода перебора в лабиринте преобладают вертикальные линии. Должен отметить, что есть множество возможностей по «тонкой» настройке качества генерации. Например, можно перебирать координаты точек «роста» псевдослучайно (с помощью прибавления большого простого числа и взятия остатка от деления на число столбцов таблицы). Тогда общее число итераций останется прежним (~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()
Sign up to leave a comment.
Неприлично простая реализация неприлично простого алгоритма генерации лабиринта