Поиск пути [Delphi 6] [Win98]
Hello all!
Нужен алгоритм поиска пути.
Допустим дан двухмерный массив map[0..100,0..200]: boolean;
Если map[x,y]=false тогда точка пуста
Если map[x,y]=true тогда в точке стена, которую следует обойти.
нужно определить кратчайший путь из точки map[x_nachalo,y_nachalo] в точку
map[x_konec,y_konec]
при этом нельзя ходить по диагонали(!) можно только вправо, влево, вверх и
вниз.
Также нужно, чтобы была функция "расстояние в шагах между
map[x_nachalo,y_nachalo] и [x_konec,y_konec]".
Помогите пожалуйста!
Ответ присылать желательно с кодом, т.к. я уже перерыл очень много
информации алгоритмах поиска пути, но так и не нашёл нужного.
Заранее спасибо!
Пока!
С уважением Lakmus
http://www.nvkz.kuzbass.net/lakmus
Номер выпуска : 3433
Возраст листа : 305 (дней)
Количество подписчиков : 446
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/196570
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru
-*Информационный канал Subscribe.Ru
Адрес подписки:
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписать: mailto:comp.soft.prog.prog--unsub@subscribe.ru
http://subscribe.ru/ mailto:ask@subscribe.ru
[23.07.2004 13:32] Обнаружено письмо от Lakmus
[23.07.2004 13:32] Тема "Поиск пути [Delphi 6] [Win98]"
Вообще все зависит от свойств стен :)
Вообще если задачу нужно выполнить точно, то можно воспользоваться
волновым алгоритмом:
Строим двумерный массив в каждом элементе - направление, и расстояние
по этому направлению до конечного пункта.
Затем пробегаем массив. Можно оптимизировать добавив еще один член
в элемент массива - булевую переменную (нужно мерить или нет). Для
каждого элемента смотрим вокруг элемент с минимальным расстоянием, и
на него указываем направление. После прохода когда не изменился ни
один элемент - карта готова. Берем стартовую точку и по направлениям
рисуем путь. Значение расстояния если нужно, оно есть :)
Способ требует много времени, поэтому если конечная точка неподвижна,
карту можно не перестраивать.
С пожеланием доброго времени суток,
Олень Элмо
JabberID: da.el***@j*****.ru
gpg --keyserver pgp.mit.edu --search-keys da.el***@m*****.ru
Key fingerprint = 273C 4245 7209 240B E880 81E0 B22E 4291 77DB FB8C
Номер выпуска : 3434
Возраст листа : 305 (дней)
Количество подписчиков : 446
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/196748
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru
-*Информационный канал Subscribe.Ru
Адрес подписки:
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписать: mailto:comp.soft.prog.prog--unsub@subscribe.ru
http://subscribe.ru/ mailto:ask@subscribe.ru