Ну, здесь и правда ничего сложного нет, если имеются базовые знания о графах. Иначе некоторые моменты могут быть неочевидны. Что-то по-настоящему сложное… Ну, может быть, при пересекающихся коридорах или полярных лабиринтах сложность будет повыше. На примитивном двухмерном пространстве всё тривиально при наличии опыта в программировании и немного в математике.
Перевод просто ужасен. Обычно симпатизирую Вашем переводам, а тут какой-то тихий ужас. Не знаю, может быть и в других статьях так же и я просто был невнимателен.
Взял первую попавшуюся на глаза строчку:
Это довольно противоречивый вопрос, но скорее надо реализовать эту функцию, чем нет.
This is a rather controversial issue, but much more likely than not you will need to implement it.
Просто бездумное калькирование логики построения и структуры фразы из английского языка на русский. Извините, но так статьи не переводят. Не для таких ресурсов. Постоянные повторы одних и тех же слов и словосочетаний: «довольно», «другими словами», вечные «это»/«эти»/«этим».
Если вы и правда зовете себя «переводчиком-фрилансером», то, пожалуйста, прочитайте ту же Нору Галь с её «Слово живое и Мертвое». Да, книжка старая и некоторые моменты устарели, но в вашем случае качество статей может увеличиться на порядок. ИМХО.
Да, всё верно. Надо отучить себя от привычки отвечать второпях, чтобы таких казусов не происходило.
Эллер работает с ограниченным количеством множеств, вплоть до размерности строки.
То есть, если у Вас строка состоит из десяти клеток, то, теоретически, Эллер может работать с 10 отдельными множествами и не объединить ни одного. Sidewinder же всегда работает исключительно с одним.
Нет, Сайдвиндер и Эллер хоть и похожи по работе, всё-таки, это разные алгоритмы. У Эллера совсем иная работа с сетами и логика их использования. Если в Сайдвиндере мы всегда работает исключительно с одним множеством в единицу времени, то Эллер манипулирует неограниченным количнством одновременно, в том числе и объединяя некоторые из них.
А так в вашем списке не хватает еще 2-3 алгоритмов:
Алгоритм Уилсона,
Алгоритм HuntandKill,
Алгоритм растущего дерева (по сути, рекурсивный поиск с возвратом при одном из вариантов реализации)
Сейчас уже готовлю материалы про алгоритм Алдоса-Бродера и Уилсона. Надеюсь уложиться в неделю. Единственое, что может задержать – необходимость переписать реализацию Уилсона на Луа, потому что в нынешнем виде мне немного стыдно её выкладывать.
Лабиринты без тупиков зовутся Braid-mazes и, как Вы верно подметили, они гораздо сложнее для решения человеком. Обязательно посвящу им отдельный цикл статей, если наберется материала. Но, лично по-моему, идеальные лабиринты красивее, хотя по своей сути и являются остовным деревом.
Очень странная расстановка стен, непонятно от чего зависящая. Лабиринт явно не идеальный, так как имеет циклы, судя по всему, с более вертикальным смещением.
Приятно слышать :)
Алгоритмы генерации помещений, боюсь, немного выходят за рамки цикла, но, при возможности, я с радостью о них напишу. Единственное, что подойдет для таких целей, я думаю, алгоритм рекурсивного деления, который при должной настройке способен создавать планы помещений.
Насчет карт с произвольными дорогами… Тут сложнее. Прежде, чем увлечься лабиринтами, я замышлял написать свой генератор процедурных городов, со всеми правилами строительства: выбором роста города и дорог (прямые дороги, радиальные, хаотичные...), выбором различных городских занятий (туристический город/промышленный), от которых бы зависели типы и размеры районов, и всё в таком духе. К сожалению, пока до реализации такого не дошло, но, может быть, ради Хабра что-нибудь да напишу.
Ну, хороший программист не станет ждать, пока его научат. Более того, у хорошего программиста уже есть лучший учитель – интернет. Так что, гугл в зубы и вперед, новые знания ждут! :)
Взял первую попавшуюся на глаза строчку:
Просто бездумное калькирование логики построения и структуры фразы из английского языка на русский. Извините, но так статьи не переводят. Не для таких ресурсов. Постоянные повторы одних и тех же слов и словосочетаний: «довольно», «другими словами», вечные «это»/«эти»/«этим».
Если вы и правда зовете себя «переводчиком-фрилансером», то, пожалуйста, прочитайте ту же Нору Галь с её «Слово живое и Мертвое». Да, книжка старая и некоторые моменты устарели, но в вашем случае качество статей может увеличиться на порядок. ИМХО.
А, да, верстка режет глаз.
Не вижу никаких проблем.
У самого лет с 16 есть эта книжка, и ничего, вроде живой пока ;)
Эллер работает с ограниченным количеством множеств, вплоть до размерности строки.
То есть, если у Вас строка состоит из десяти клеток, то, теоретически, Эллер может работать с 10 отдельными множествами и не объединить ни одного. Sidewinder же всегда работает исключительно с одним.
А так в вашем списке не хватает еще 2-3 алгоритмов:
Алгоритм Уилсона,
Алгоритм HuntandKill,
Алгоритм растущего дерева (по сути, рекурсивный поиск с возвратом при одном из вариантов реализации)
О лабиринтах Вашего типа, возможно, поговорим попозже.
UPD: А еще у вас там изолированные области встречаются, что точно нехорошо.
Очень странная расстановка стен, непонятно от чего зависящая. Лабиринт явно не идеальный, так как имеет циклы, судя по всему, с более вертикальным смещением.
Алгоритмы генерации помещений, боюсь, немного выходят за рамки цикла, но, при возможности, я с радостью о них напишу. Единственное, что подойдет для таких целей, я думаю, алгоритм рекурсивного деления, который при должной настройке способен создавать планы помещений.
Насчет карт с произвольными дорогами… Тут сложнее. Прежде, чем увлечься лабиринтами, я замышлял написать свой генератор процедурных городов, со всеми правилами строительства: выбором роста города и дорог (прямые дороги, радиальные, хаотичные...), выбором различных городских занятий (туристический город/промышленный), от которых бы зависели типы и размеры районов, и всё в таком духе. К сожалению, пока до реализации такого не дошло, но, может быть, ради Хабра что-нибудь да напишу.
То, что алгоритм можно переписать на циклы не отменяет того, что он работает так же, и, по сути, является тем же самым, что и Recursive Division =)