Comments 54
Где же код?
Всё очень хорошо, но тут скорее — «где же текст?», за картинки — спасибо, тема про крота — не раскрыта.
document.body.style.tabSize = 4
Насчёт двойных 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;
Зачем вы это сделали? Теперь я не засну, пока не пойму, как оно работает…
В ASCII таблице Commodore64 на позициях 205 и 206 находились диагональные линии (вроде /и \ только под углом 45 градусов).
Эта программа просто выводит в случайном порядке либо одну линию, либо другую.
Потому что линии стыкуются друг с другом. Просто попробуйте внимательно изучить скриншот или возьмите тетрадь в клеточку и нарисуйте несколько строк диагональных линий. Можно бросать монетку для истиной случайности :-)
Кстати, не могу не вспомнить другой, ещё более простой алгоритм генерации лабиринтов:
- Окружаем лабиринт стеной, внутри пока пусто.
- Случайно выбираем "кирпич" с чётной координатой на одной из сторон.
- Начинаем строить от него стену — причём сразу после кирпича пропускаем одну позицию (оставляем проход)
- Повторяем 1-2 в случайном порядке для остальных "чётных" кирпичей на всех 4 стенах.
(Получается, что в первой стене будет проход у края, в перпендикулярной ей — у края и у первой стены и так далее)
Не помню, в какой книжке я его вычитал в детстве, но работал на бейсике на тогдашних машинках (8-битный проц 8080, 2 мегагерца тактовая, от 4 тактов на инструкцию — т.е. эдак на 4 порядка медленней нынешних) довольно шустро.
Хотя алгоритм несколько примитивный.
Не совсем: стена всегда строится от края до края лабиринта (что исключает рекурсию, там просто два цикла for).
Но действительно создаёт лишь подмножество множества лабиринтов, создаваемых методом рекурсивного деления.
То, что алгоритм можно переписать на циклы не отменяет того, что он работает так же, и, по сути, является тем же самым, что и Recursive Division =)
Посему, вопрос к коммьюнити: стоит ли делать цикл статей по 11 «классическим» алгоритмам процедурной генерации лабиринтов? Есть ли люди, которым это интересно? (с картинками, объяснениями, гифками, кодом и печеньками)
размерностью 150х150, что подразумевало использование типа ineger, а не byte.
Честно говоря, не понял, почему у Вас размер поля с типом данных связан.
А так, на английском языке отличные: ThinkLabyrinth, Buckblog, книжка Mazes for Programmers.
Собственно куча алгоритмов на английском если кому интересно.
Различные термины, объяснения, техники. Но это чисто справочник. Но сайт полезный, да.
Очень интересно выглядят например cracks или sparseness. Правда для этого раздела описаний нет. :(
#!/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()
#!/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()
Неприлично простая реализация неприлично простого алгоритма генерации лабиринта