Алгоритм прохождения лабиринта

[PAVEL315]

Можете подсказать алгоритм прохождения лабиринта из точки А в точку В при учёте того, что точка Б постоянно перемещается?
Достаточно лишь "увидеть" вторую точку - это будет конец.
Пример лабиринта в приложении.
"Спаун" происходит в углах - верхнем левом и правом нижнем.

Два варианта:
1) Точка В перемещается рандомно
2) Точка В пытается убежать от точки А

Точки видят друг друга.

Подскажите пожалуйста

[Миша]

Не знаю смогу ли тебе помочь но думаю что это делается так:
Сначала сохраняешь линии своего лабиринта в массиве:

var
a:array of array of Integer;
begin
// задаем размерность
SetLength(a,200,2);//где 200 количество линей
//Наполняем массив
a[1,1]:=1;//координата по Х
a[1,2]:=2;//координата по У
      Form1.Canvas.Pixels[X,Y]=clBlack then
{ ... }
end;

Рисуешь на Form1.Canvas свой лабиринт. Лучше это делать в событие главной формы OnPaint

Image1.Canvas.MoveTo(a[1,1],a[1,2]);
Image1.Canvas.LineTo(a[2,1],a[2,2]);

Потом с помощью математических формул перемещаешь свою точку. И при столкновении её с линией не допускаешь перехода её то есть if Form1.Canvas.Pixels[X,Y]=clBlack then …

[PAVEL315]

Видимо не понял меня)

Лабиринт уже есть в виде картинки, просто идёт проверка на линию - её переступить невозможно.

Мне нужен именно алгоритм ПОИСКА, а не графика.

Ну хотя через массив тоже можно.
Но интересует именно поиск.

[Arigato]

Необходимо найти оптимальный путь от т. А в т. В. Как только т. В переместиться, ищем путь заново.
Как найти оптимальный путь в лабиринте - обсуждалось на форуме.

[PAVEL315]

Можно ткнуть пальцем в тему?
http://www.programmersforum.ru/showthread.php?t=10952
Тут аваст ловит троянчик

[Пепел Феникса]

а вам exe нужен?
мне кажется что вам сорцы оттуда нужны.
exe просто не трогайте(сотрите)
а Индюк описан в тут по соседству.

[Arigato]

Сообщение от PAVEL315

Можно ткнуть пальцем в тему?

А Вам лень промотать страничку вниз и посмотреть раздел "Похожие темы"?

[k1r1ch]

Оптимальный маршрут можно найти волновым алгоритмом к примеру.

[PAVEL315]

Волновой алгоритм наполовину реализован - но уже тут понятно, что дико всё тормозит, ибо поле 450х450 - а будут раз в 10 больше - простите, уже заполнение массива значением о каждой клетке занимает около 7 секунд - так ещё этот массив надо будет пролистать!

[Arigato]

Странно, от куда 7 секунд? 450*450 = 202500, такое должно быстро отработать.
Но, во-первых, не надо рассматривать лабиринт попиксельно. Можно взять более крупные куски, например, по 4*4 пикселя, если там есть стена - кусок не проходим, если нет - проходим.
Во-вторых, используйте не волновой алгоритм, а , к примеру, тот, что я приводил в этом посту: http://www.programmersforum.ru/showp...29&postcount=6
В данном случае при поиске пути просматриваются только те клетки, что находятся близко от оптимального пути. А если препятствий не много (судя по Вашему рисунку), так оптимальный путь будет найден практически сразу без рассмотрения других клеток (которые не находятся на оптимальном пути).