Здравствуйте.
Мне нужно разработать алгоритм для обхода препятствий, причем припятствия бывают только прямоугольной формы и могут "пересекаться", а путь может состоять только из горизонтальных и вертикальных линий.
Я конечно пытался придумать что-то, но никакого обьективного алгоритма не получилось.

P.S. Путь, конечно, должен быть наиболее краток.

В смысле, препятствия - это параллепипеды что-ли ? Ими утыкана плоскость ?
И они могут пересекаться ?:

_
|                 |
|                 |_|

?

Это прямоугольники на плоскости.
           _|

Из А в Б.

Извиняюсь, рисунок не вышел. Вот здесь красная линия - это путь.

И у меня не вышел ;(((
Это глюк !!!
Вообще, я все меньше страниц в инете с помощью IE<=5.x вижу нормально !
Постоянно какие-то ошибки...
Ну это я так, нашло что-то ;)

Так прямоугольники на плоскости, но непересекаются ?
А что ты имел в виду под вертикальными линиями (вверх ?)
Или имеется в виду движение по плоскости ?

Вообще это вроде бы "Транспортная задача". Меня как-то один фанат Пролога?
(извиняюсь, не помню точно названия) убеждал, что этот язык - the best для этого...

Цитата

И у меня не вышел ;((( Это глюк !!! Вообще, я все меньше страниц в инете с помощью IE<=5.x вижу нормально ! Постоянно какие-то ошибки...

Да этот експлорер меня принудит на Оперу перейти...

Прямоугольники пересекаются, как видно на рисунке (те два, что справа внизу). Задача не транспортная. В транспортной задаче нет траектории перевозок, только длина. Под линииями я подразумевал просто возможные направления (вверх, вниз, влево, вправо только не под углом <> 90, 180, 270, 360).

Чтобы обойти одно припятствие можно пойти направо или налево. Может это рекурсивный алгоритм? В смысле за один шаг рекурсии можно взять ситуацию, когда сталкиваемся с препятствием. Получится бинарное дерево, и если, геометрически можно увидеть один узел с другого, то соединить эти узлы.
У кого какие мысли? Поделитесь.

neutrino, опиши plz точно, что есть на входе и что надо получить на выходе, вместе подумаем...

э... скажи пожалуйста, а надо ли учитывать ситуацию в которой такую траекторию невозможно построить? (точка А в замкнутом пространстве из прямоугольников).

потому что мне кажется, что рекурсия тут может сыграть злую шутку.

Цитата

neutrino, опиши plz точно, что есть на входе и что надо получить на выходе, вместе подумаем...

На входе рисунок (точнее матрица с координатами прямоугольников) и координаты двух точек (откуда и куда идти). На выход: массив с линиями траектории. Давай подумаем, буду очень рад.

Цитата

потому что мне кажется, что рекурсия тут может сыграть злую шутку.

Я даже о таком случае и не думал. Хммм... В таком случае нельзя попасть в точку B. Я дома подумаю над действиями в такой ситуации. Спасибо.

если ты ещё не ушёл домой:

ты прав - рекурсия. но не схемой "напрямик - препятствие - обойти", а по другому - идти сразу во все стороны.

то есть пусть точка А - эпицентр, от которого расходится круглая (или лучше квадратная?) волна, ну чисто как в физике - каждая точка фронта есть источник ещё одной волны. (только пусть волна "гаснет", когда натыкается на препятствие, а не "отражается" от него :)

вот чего мне приглючилось... как дальше пока не знаю

2SetQ: Мысль твоя мне ясна. Но если из каждой точки фронта строить все время новые "волны", то это для стэка будет хуже чем бесконечная рекурсия . И как потом, все таки, найти траекторию? Ведь мне можно строить только горизонтальные и вертикальные линии.
Ух, чуется мне, плохи мои дела ...

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

Цитата(neutrino @ 20.10.2002, 14:21)

2SetQ: Мысль твоя мне ясна. Но если из каждой точки фронта строить все время новые "волны", то это для стэка будет хуже чем бесконечная рекурсия :). И как потом, все таки, найти траекторию? Ведь мне можно строить только горизонтальные и вертикальные линии. Ух, чуется мне, плохи мои дела ... :(

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

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

2Dayana: это как? та же рекурсия но от точки В?

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

В принципе, это - что-то из серии рекурсии, как уже грили.

В твоем случае возможно представить область между "прямоугольниками" как область закраса и тд... в процессе закраса следить, не наткнулись ли на конечную точку ?...

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

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

Цитата

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

Это 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% результат и нет  проблем с поиском пути
          Минусы: долговато и требует доп памяти.
Короче всё вот так...

P.S. только что заметил: как в примере единичек многовато она должна быть только одна либо я что-то перепутал при описании алгоритма либо...

отмена

Цитата(man2002ua @ 18.11.2002, 14:49)

отмена

? ? ?

а как удалить свой пост?

Цитата(man2002ua @ 20.11.2002, 12:40)

а как удалить свой пост?

Это только модератор может сделать. Я могу только всю тему удалить

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

Всем кто это читает, привет и наилучшие пожелания!
Для тех кто хочет улучшить крутизну своей любимой машинки.

Универсальный механизм - позволяющий открывать двери автомобиля вертикально. Механизм работает в широком диапазоне температур, от -30 до +80 градусов по Цельсию. Механизм достаточно компактен и может инсталлироваться без особого труда практически для всех автомобилей мира. 

Сделайте Ваш автомобиль похожим на «Lamborghini»! Ведь после установки комплекта «lambo Door Kit», не важно какой у Вас автомобиль: «Honda», «Mazda», «Восьмерка» или «Ока». Наш механизм подходит для любого автомобиля. Комплект без труда встанет на легковушку, джип, и на грузовик!

Более подробная информация на сайте http://lambodoor.ru/ldk.php или http://lambodoorkit.ru/