Форум: "Потрепаться";
Текущий архив: 2002.01.24;
Скачать: [xml.tar.bz2];
ВнизЛинии Найти похожие ветки
← →
Merlin (2001-11-19 15:05) [19]> вместо того, чтобы клонировать шарики, проще сотворить рекурсивный вызов функции
В начале так и делал. Но при очень большом лабиринте (я это делал не для lines ;) получал переполнение. Потому сделал шарики и ограничил их максимальное число. Отсюда же появились возможные варианты, когда подходишь к клетке, а там уже был другой виртуальный шарик, но с большим кол-вом ходов. При правильном (последовательном) проходе такого вроде не должно получаться.
Кстати, еще один вариант. Для очень больших массивов.
Суть:
Движемся по направлению к конечной точке. Если нельзя двигаться напрямую к ней, то выбираем случайно любое доступное направление. Если зашли в тупик, то возвращаемся назад до первого свободного поворота.
Самое главное. Если мы своим движением образовали замкнутое пространство внутри которого нет конечной точки, то помечаем его целиком, как стену.
Как говорится, лучше один раз увидеть:
.B.....
######.
.......
####...
.1.....
.A.....
Буквально с первого шага получили замкнутуе пространство слева,
отрубаем его (совершенно верно то, что замкнутое пространство получилось и справа, но его отрубать нельзя, т.к. в нем конечная точка :)
.B.....
######.
...5...
####4..
#123...
#A.....
На 5-ом шаге, также есть замкнутый контур с пустыми полями, помечаем его и левее уже не двигаемся
.B.....
######8
###567.
####4..
#123...
#A.....
На 8-ом тоже есть контур, заполняем и его
.B.....
######8
###567#
####4##
#123###
#A#####
И т.д.
Надеюсь суть понятна :) Он не обеспечивает нахождения кратчайшего пути, но! дает фору первому методу на больших лабиринтах. Здесь только одна сложность, в поиске замкнутого контура и определения, есть ли конечная точка в нем или нет. Но на эту тему, есть в инете алгоритмы.
Страницы: 1 вся ветка
Форум: "Потрепаться";
Текущий архив: 2002.01.24;
Скачать: [xml.tar.bz2];
Память: 0.45 MB
Время: 0.004 c