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

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.