​​Моё главное развлечение последней недели — генерация лабиринтов. Уже полгода у меня на ноуте лежит книга Mazes for Programmers, но добралась я до неё только сейчас.

Книга оказалась интересной, в ней объясняются алгоритмы построения и решения лабиринтов. Объясняются просто, в картинках и описаниях без лишних математических формул. Пока я освоила первую главу из четырёх. Там рассматриваются основные 6 алгоритмов для генерации идеальных (perfect) лабиринтов. Это в которых нет недоступных клеток, то есть из любой выбранной клетки можно попасть в любую другую.

Самые простые алгоритмы это Binary Tree и Sidewinder. Они создаются абсолютно случайно (фактически подбросом монетки в каждой клетке), поэтому имеют очень предсказуемую структуру. Противоположны им Aldous-Broder и Wilson's. С их помощью лабиринты получаются сложными и без угадываемой структуры, но создаются очень долго из-за большого числа случайных блужданий. Два последних алгоритма, Hunt and Kill и Recursive Backtracker, ограничивают блуждания, поэтому работают быстрее и эффективнее. А ещё у них меньше всего тупиков.

В следующих главах рассматриваются другие алгоритмы, лабиринты сложной или необычной формы, трёхмерные лабиринты и прочее. Буду ещё рассказывать. А это лабиринт, созданный методом Hunt and Kill

#алгоритмы #лабиринты