Пишу алгоритм для построения лабиринта на основе бэктрекинга. Хотелось бы узнать, как наиболее эффективно реализовать бэктрекинг, чтобы алгоритм выполнялся быстрее для очень больших по размеру лабиринтов. Идея такова:
Массив клеток лабиринта, где каждый элемент либо 0, либо 1 - стена или проход. Изначально все пространство - стены, в которых по ходу алгоритма пробивается проход. Попали в тупик? Отмечаем текущую клетку как тупик. Далее рандомно выбираем клетку с уже прорытым проходом, которая пока не является тупиком. Начинаем рыть проход из этой клетки. Когда все клетки с проходами станут тупиками - лабиринт построен. Но я не знаю, какой метод выбора нетупикового прохода лучше в плане скорости поиска. У меня есть 2 идеи:
1) Каждый элемент массива помимо состояния стена / проход должен хранить состояние тупик / не тупик. Тогда при поиске нетупиковой клетки придется выбирать все нетупиковые из всех существующих клеток пространства, а уже потом среди них выбрать одну рандомную. Такой метод мне не нравится тем, что общее количество клеток пространства может быть огромное количество. И каждый раз придется снова пробегать по всему массиву в поисках нетупиковых элементов и выбора из них одного случайного.
2) Второй подход - это хранить все клетки с проходами в отдельном массиве. А массив с состояниями клеток оставить одномерным. При попадании в тупик нужно будет удалять из массива с проходами текущую клетку, чтобы не обращаться к ней в следующий раз. В итоге выбирать рандомно нетупиковую клетку придется с каждым разом среди всё меньшего количества клеток. Но такой подход мне не нравится большим количеством операций с массивом. Прорыли новый проход - добавить в массив. Попали в тупик - удалить из массива (почти всегда откуда-то из середины массива).
Что бы вы посоветовали? Может, какой-нибудь другой вариант?
Средний
