Цитата

Выбираешь один путь, например все время идешь в сторону, которая ближе всего к конечному пункту. Если заходишь в тупик, то возвращаешься по шагам назад до тех пор, пока не найдешь другой путь и т.д. Если путь от А до В существует, то алгоритм конечен. А если не существует, то можно ограничить кол-вом шагов, т.е. длиной пути, которая всегда конечна. Можно пользоваться рекурсией, проверяя длину пути. Если матрица очень большая, то можно разбить матрицу над подматрицы, и выполнять каждую подматрицу рекурсией отдельно, определяя в каждой подматрицы начальный и конечный пункты...

Это BackTracking? Напоминает задачу "обход конем шахматной доски". Вообше, по-моему, это пока единственный способ, оптимальный для заqдачи.

Цитата

например можно делить "волну" на 2 (то есть инициировать новый "центр", рекурсию, то бишь) тогда и только тогда, когда на препятствие натыкаемся... ну и не обязательно - прям каждую точку инициировать. жирно будет, как ты правильно подметил. достаточно будет и одной точки на "отрезок" (участок волны, стиснутый между двумя препятствиями).

А как волну строить? Спираль вокруг точки обводить, пока не наткнусь на что-нибудь? Хотя это будет ближайшее препятствие. Направить волну в сторону точки назначания? А если там тупик, она загасится (из правила выведенного в предыдушем сообшении).

Цитата

Мне кажется, что решение возможно подобно алгоритму процедуры FloodFill (закраска области, окруженной замкнутой ломаной указанного цвета - Паскаль). Ей передается точка внутри области (любая, но обязательно внутри), цвет закрашивания, цвет границы. Закрашивает всю внутренность.

Ты знаешь, я всегда думал: как эта процедура работает так быстро? Может это и подойдет.

Цитата

Забей на "непрямоугольный" путь, ведь любой путь в матрице 2x2 - прямоугольный.

Да. Ты прав, но мне все таки надо, чтоб шло как "программист в магазин".

Цитата

а для чего тебе вообще? чувствую тут попахивает стратегией, а "юниты" ну никак не хотят идти куда пошлют, не проходя сквозь стены?

Да нет. Программированием игр не увлекаюсь. Мне это нужно для того, чтобы соединить два блока в блок-схеме, обойдя остальные блоки. Вот так.

Всем огромное спасибо за ответы! Рассмотрю все ваши идеи. И не знал, что так много будет. Результаты опубликую здесь.

А такая идея (безусловно, не оптимальная, но простая в реализации):
Если войти в лабиринт и идти, всё время держась правой (левой, кому больше нравится) рукой за стенку, то в конце концов выйдешь наружу. Copyright Lewis Carrol, если не изменяет память. Предлагаю найти такой путь, а потом его оптимизировать - проверять на пересечения с самим собой, возможности срезать путь и т. д. По-моему, быстро будет.

Neutrino
А ты литературой по данному вопросу интересовался? А то у меня книжка есть, там описаны два алгоритма поиска пути в лабиринте. Думаю, на земле обетованной ее (книжку) не найдешь. Если надо - кинь на е-мейл, куда тебе слить отсканированные страницы. Только ящик укажи пообъемнее. А я уж поработаю со сканером.
А потом всем расскажешь.

Цитата

А такая идея (безусловно, не оптимальная, но простая в реализации): Если войти в лабиринт и идти, всё время держась правой (левой, кому больше нравится) рукой за стенку, то в конце концов выйдешь наружу. Copyright Lewis Carrol, если не изменяет память. Предлагаю найти такой путь, а потом его оптимизировать - проверять на пересечения с самим собой, возможности срезать путь и т. д. По-моему, быстро будет.

Я такую программу писал. Если ты с ней знаком, то должен знать, что если ты идешь вокруг "островка лабиринта", то "вытягиваешь" другую руку и идешь "шюпая" стену по другой стороне. Тут она не подойдет, т.к. эти блоки - сплошные островки.

Цитата

Neutrino А ты литературой по данному вопросу интересовался? А то у меня книжка есть, там описаны два алгоритма поиска пути в лабиринте. Думаю, на земле обетованной ее (книжку) не найдешь. Если надо - кинь на е-мейл, куда тебе слить отсканированные страницы. Только ящик укажи пообъемнее. А я уж поработаю со сканером. А потом всем расскажешь.

Да, про поиски этой книжки тут, ты прав. Здесь ничего не найдешь. А вообше если ты думаешь, что там есть что-нибудь полезное для этой задачи, и если тебе не впадлу, то давай. Не очень мне хочется тебя принуждать к черной работе. А мыло мое есть в профиле. Хотя: [email protected].
Thnx

Цитата(podval @ 22.10.2002, )

Neutrino А ты литературой по данному вопросу интересовался? А то у меня книжка есть, там описаны два алгоритма поиска пути в лабиринте. Думаю, на земле обетованной ее (книжку) не найдешь. Если надо - кинь на е-мейл, куда тебе слить отсканированные страницы. Только ящик укажи пообъемнее. А я уж поработаю со сканером. А потом всем расскажешь.

Буду очень благодарен, если мне тоже вышлешь. [email protected]

Уточнение: рисуется кратчайший путь (т.е. без учёта препятствий, прямой отрезок), потом по нарисованному пути последовательно перебираются шаги до встречи препятствия. Препятствие обходится с вытянутой рукой, далее процедура повторяется. По достижении пункта назначения весь путь проверяется на наличие петель и прочих несуразностей. Лично я уже не вижу недостатков в таком варианте. Хотя они, наверно, есть.

Ребята, я помогу, но вам придется чуть-чуть подождать: на работе грохнули систему, ищем дрова для сканера. Немножко терпения!

Выяснилось , что задача эта- упрощённый вариант алгоритма Дейкстры. Решается свё просто. Пусть на матрице пустые клетки - нули, прямоугольники- минус единицы(для удобства). Так в точке А мы начинаем- ставим там 1,
в четырёх соседних точках, не равных -1, ставим 2, и так рекурсивно заполняем все точки, увеличивая значение на каждом шаге. Если значение точке Б ни разу не поменялось, то туда дороги нет, если поменялось, то идём обратно 10, 9, 8, т.д- семейство таких путей и будет найкратчайшими траекториями. Вот. Всё доказано.

А вот что я нашел:
http://www.shpaga.ru/rus/shareware03_01.html

ну, блин, в этом мире просто невозможно придумать что-то новое

интересно, что это за "блок-схема" такая с пересекающимися блоками?

neutrino, обрати plz внимание на мою мессагу на две позиции выше, а то она потеряется напрочь из виду, а ведь это на самом деле точное решение

Цитата(piero @ 25.10.2002, 17:23)

neutrino, обрати plz внимание на мою мессагу на две позиции выше, а то она потеряется напрочь из виду, а ведь это на самом деле точное решение

Не, бойся . Я обязательно ее прочитаю (вернее уже прочитал). Просто у меня берет много времени досконально просмотреть все алгоритмы и выбрать наилучший. Уже их столько, что глаза разбегаются. Спасибо тебе за твой вариант.
Пока я скажу, что алгоритм "с волнами", наверное не подойдет. Алгоритм с рекурсией (и бэктрэкингом) Dayanы, тоже.

Цитата

ну, блин, в этом мире просто невозможно придумать что-то новое интересно, что это за "блок-схема" такая с пересекающимися блоками?

Просто и такое бывает.

И так, постараюсь подвести итоги. В обшем можно классифицировать алгоритмы на две группы:
1) алгоритм Dayanы, December'а и мой (с бинарным деревом);
2) алгоритм Chingachguka, "волновой" алгоритм (SetQ), алгоритм Piero. В принципе они все похожи.

Вопрос в том, что как в алгоритме Piero (Дейксры) все таки найти путь по полученной "сетке" из точек "1"? А ведь это и впрямь похоже на FloodFill. Мне нужно, чтобы путь был с наименьшим количеством поворотов (менее изломлен).
А в алгоритме Dayanы, можно прийти к ситуации, когда путь мы найти не сможем: если мы идем пока не наткнемся на тупик, то когда мы на него натыкаемся, возвращяемся обратно, а возможно в аналогичной ситуации нужно обойти препятствие. Пока мы все пути не опробуем, этого сделать нельзя.

Хочу еще привести такую идею: допустим мы построили бинарное дерево обхода препятствий по всем возможным путям. Далее, чтобы выбрать нужный путь, надо взять самую короткую ветвь дерева. В узле можно писать сколько пикселей прошли до него. Только я не совсем понимаю, как это дерево строить. Опыта с деревьями у меня нет.

P.S. Хочу выразить благодарность всем участникам темы. Эх, жили бы вы здесь, я бы вас на пиво позвал, А Dayan'у на коктейль, что Vit посоветовал (да муж, наверняка не пустит, он ведь не программист) .

P.P.S. Я ... это... тему не закрываю, просто расчувствовался ...  

Цитата

Вопрос в том, что как в алгоритме Piero (Дейксры) все таки найти путь по полученной "сетке" из точек "1"?

Да как два байта переслать
Сначала по-подробнее опишу алгоритм...
0)заводим счётчик=1 и значение клетки начала=1 остальные 0 если свободно -1 если препятствие

1)Цикл по всем клеткам
Для любой клетки  а)if значение>0 или <0 то следующая клетка
                             б)if значение==0 то если все клетки вокруг <=0 то                                                          следующая клетка иначе если есть соседняя клетка==счётчик то значение равно счётчик+1.
конец цикла

2)счётчик++
3)Проверка конца пути если там не 0 то переходим непосредственно к поиску пути. Если не изменилось значение ни одной клетки, то путь не существует
4)Поиск пути: осматриваем все соседние с концом пути клетки и исчем клетку значение в которой меньше на единицу. Такая всегда есть (если такая не одна то берём отбалдовую). Затем выполняем эту же процедуру с вновь найденой клеткой и.т.д. в итоге получаем клетку с номером 1-начло пути. Координаты клеток найденых таким образом дадут путь.
Вот...

Алгоритм является упрощённой версией Алгоритма Дейкстры, который является оптимальным для нахождения кратчайшего пути в графах.

Никаких рекурсий одни циклы...

Совет: при реализации лучше использовать матрицу увеличенную на строку сверху и снизу и стиолбец слева и справа, забитый минус единицами. Т.е. мы как бы окаймляем матрицу -1.  Цикл проводиь по внутренней матрице. Если делать так то при проверке соседних клеток не придётся проверять выход за границы матрицы.

Для того чтобы уменьшить количество изломов можно придумать коофицент поворота т.е. при присвоении значения клетке приповороте увеличивать значение на 3 или больше а при прямом пути на 1. Но в любом случае сожет оказаться что ломаный путь меньше прямого и при таком коофиценте становится немного труднее найти обратный путь.
Вобщем если тебя интересует такой алгоритм с коофицентом  то я могу выслать ихсодничек в паскале...

p.s.

Цитата

А такая идея (безусловно, не оптимальная, но простая в реализации): Если войти в лабиринт и идти, всё время держась правой (левой, кому больше нравится) рукой за стенку, то в конце концов выйдешь наружу. Copyright Lewis Carrol, если не изменяет память. Предлагаю найти такой путь, а потом его оптимизировать - проверять на пересечения с самим собой, возможности срезать путь и т. д. По-моему, быстро будет.

Ну так ничего не выдет по такому принципу можно не заблудится в лабиринте т.е. выйти откуда пришёл. Принцип валится на нулевом примере: гордый блок посреди поля дойти нужно в угол  этого поля а стартовая точка возле блока. Тогда держась правой/левой рукой можно ходить вокург блока до бесконечности.

p.p.s.
Господа, изучайте фундаментальную торию алгоритмов, в ней есть ответы на вопросы над которыми мы все мучаемся придумывая велосипед в очередной раз...

Вот это результат работы алгоритма, если я правильно понял.


Здесь самая темная полоса - путь. Препятствия - "-1", Слабый серый цвет обозначает множество возможных (наикротчайших) ходов. Вопрос в том как выбрать именно этот. Это как прямоугольники, а у них правая и нижняя стороны только.

Как говорила одна моя знакомая красоту не заалгоритмируешь , но попробывать можно.

Вариант 1)При повороте прибавлять не 1 а 3 или больше.
           Плюсы: а)Быстро и изящно
           Минусы: Работает не всегда, замучаешься находить обратный путь
Вариант 2)Создать дерево наикратчайших путей, т.е. в корень помесить координаты конца пути,  детями сделать все клетки у которых значение на один меньше и.т.д. Потом обходя дерево сверху оставлять только ребёнка у которого количество попоротов минимальное.
          Плюсы: 100% результат и нет  проблем с поиском пути
          Минусы: долговато и требует доп памяти.
Короче всё вот так...