А никто не спрашивал

[size=-2]------ Добавлено в 15:53

Ну дык кратчайший путь ищет

tsdima, я не понял как твоим примером пользоваться. Задача конечно будет ресурсоёмкая, особенное если такие задачи раньше не решал. Но хочеться попробовать и посмотреть на что спаобен Комп и Я.

[size=-2]------ Добавлено в 15:56
tsdima, сообразил как им пользоваться. Алгоритмом не поделешься?

[size=-2]------ Добавлено в 15:57
tsdima, блин весь алгоритм уже готов.

[size=-2]------ Добавлено в 15:58
tsdima, блин весь алгоритм у тебя уже готов. А я собрался на пару месяцав подумать о геометрии и математике.

А чего, очень даже здоровао. Я сразу схемы вспомнил. Вот бы нам такое.

Dilma, а вот я тебе элемент MatrixWave (если название правильно вспомнил) показывал
Тогда, правда, у Bitmap-а еще точки Matrix не было (во как давно)
По теории - должно быть и быстрее....
У меня даже "целевая ф-ия" в переборе какая-никакая сляпана...

Это, если я правильно понимаю слово "рекурсивный". Неужто глубина рекурсии совпадает с длиной трассы

tsdima, нужно из этого сделать ф-цию, которая будет принимать координаты начальной и конечной точки, массив регионов и ломанных и выдавать в ответ массив точек между двумя заданными. Возвращает True, если путь найден и False в противном случае.

[size=-2]------ Добавлено в 16:10
Galkov, в те времена задача обхода не была такой острой. Хабов-то не было еще...

tsdima, блин хочеться даже к каой нибудь игре этот алгоритм прикрутить. А то у меня до этого ума не хватило.
P.S. Игра Машинки.

Так сейчас посмотри (типа - нашел) http://hiasm.com/xf//getfile/3684
Сам не смотрю, чтобы в ужас не прийти

tsdima, намекаю: я свой исходник выложил

Алгоритм прост до безобразия, и (я щас глянул исходники) даже без рекурсии. Используется FIFO очередь, на Хиасме можно для этого MemoryStream использовать. Поскольку, было написано на Бейсике, считаю что разберёшься. Несколько комментариев:
- максимальный размер матрицы 128x128 точек, в реале по размеру схемы
- максимальная длина очереди 1000 элементов, в реале должна быть динамической
- в очереди хранится 4 элемента: x,y,t,d - координаты точки, кратчайшее расстояние до начальной точки и направление, куда идти по кратчайшему расстоянию

по процедурам:
mClear - очистка матриц расстояний/объектов и направлений, отрицательное значение в матрице расстояний/объектов соответствует наличию объекта на поле
mFill - размещение объекта на поле
mPop, mPush - работа с очередью, mPush ещё и матрицы изменяет
mSearch - основная процедура
Form_Load - стартовая точка Бейсиковской формы
Form_MouseDown - обработка нажатия на кнопку мыши
Form_MouseMove - просто для информации в заголовке окна

code_1579.txt

Galkov, в твоем компоненте ограничений вроде нет же на размер матрицы? Я вроде не чего такого ограничивающего в Паснике не нашёл.

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

[size=-2]------ Добавлено в 17:36
У меня, кстати, подобная "целевая функция" используется на первом шаге, т.к. надо было определиться "куда же мы пойдём" Если направление задано заранее, то это можно выкинуть.

[size=-2]------ Добавлено в 17:41
Кстати, смысл точек, находящихся в очереди - это границы обработанной области - т.е. та самая "волна".

Попробуем вечерком привязать этот алгоритм к схеме. Полагаю, что он будет работать в качестве базового, а старый способ будет включаться только тогда, когда фактического пути найти не удалось.

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

[size=-2]------ Добавлено в 18:19
Вообще-то, если мы имеем хаб с трямя выходами, то соединяя сначала второй выход с элементом, находящимся выше или ниже хаба (но достаточно близко по горизонтали) мы блокируем первую или третью точки, так что, видимо, начальную точку в таком случае лучше тоже отодвигать от элемента, чтобы было пространство для неподключенных точек выше или ниже подключаемой.

Может задействовать цвета линий, чтобы при пересечении было ясно что это не поворот. Опционально конечно.

tsdima, теорию я читал крайне давно...
Кажется, еще в студенчестве.
Поэтому, по только памяти, без ссылок на первоисточники:

Так вот, во время перебора, чем лучше оценочная ф-я, тем меньший объем перебора требуется.
Это - ясный перец, вроде.
Но, самое главное, там ТЕОРЕМА есть (это тебе - не баб щупать ):
если твоя оценочная ф-ия НЕ БОЛЬШЕ реального значения полученного потом результата, то ПЕРВОЕ, найденное таким перебором (начиная с минимального значения оценочной в буфере) решение, ДЕЙСТВИТЕЛЬНО будет минимальным для целевой.

Поэтому, сомнения в минимальности достигаемого результата - с негодованием отвергаю

Ну и плюс к тому.... Фантазировать можно: типа количество разворотов поменьше бы...

Тут нужно сначала дойти до угла, а потом из него выбираться, так что-ли?