|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alex Astafiev 2:5000/228.16 16 Jul 2001 01:31:28
To : All
Subject : Поиск пути (хитрый ;)
--------------------------------------------------------------------------------
AV>> Hо необходимо сделать поиск пути в геометрическом 2D пространстве
AV>> с наличием карты высот. В самом пространстве существуют
AV>> прямоугольники (произвольно ориентированные), а также окружности.
AV>> Поиск пути нужно осуществлять для объектов обоих видов.
AV>> Проблем-то, вроде бы, и нет - лучевой алгоритм использовать
AV>> можно. Hо хочется ввести в этот алгоритм стоимость пути. Вот как
AV>> тут быть? Что нужно добавить в лучевой алгоритм, чтобы стоимость
AV>> пути отражалась, чтобы алгоритм не тащил объект в гору, когда это
AV>> дорого, а пускал его в обход?
PG> Вариант такой:
PG> Имеем "горную поверхность"
PG> Hаходим "вершины гор" (максимумы функций)
PG> Строим сетку соединияющие "вешины"
PG> В каждой ячейке находим "низину" (точку минимуа, должна быть одна
PG> (??вроде), и не обязательно точку - линию, плоскость). Hаходим все
PG> пути соединяющие "низины" и их цену, заносим в табличку По таблице,
PG> расматривая все суммы, находим путь с минимальной стоимостью.
PG>
PG> Или можно рассмотреть пути внутри ячейки соединяющие минимумы на линии
PG> соединяющие две вершины, ограничивающие ячейку.
PG>
PG> вабще весь алгоритм "высосан из пальца" за 30 минут, так что можешь н
PG> не обращать внимания :) Да и в мелочах проработать надо.
Я предлагаю свой (придуманый) алгоритм, модификацию волнового. Суть в том что
существует карта твоей местности, где в ячейках карты - высота данной точки.
Когда пускаешь волны или "разливаешь воду" - то реализуй то, что в гору вода
"плохо, медленнее течет". Соответственно, алгоритм будет моделировать течение
воды по местности. Следует использовать и эквивалент "уровня воды" в данной
ячейке.
Возможно, более удачной будет аналогия если вместо воды взять маленькие
металлические шарики - в том месте где ты их будешь высыпать, их уровень будет
повышаться, и они будут стремиться "течь" по зонам наименьшей высоты, пока не
достигнут точки назначения.
Этот алгоритм можно многими способами оптимизировать по затратам выч
мощности/памяти, один из которых субразбиение карты. Сначала используй крупную
детализацию, а затем все мельче, мельче, мельче..
Также можно оптимизировать представление сложных обьектов - используй оболочки
(прямоугольники).
P.S.
Просьба связаться со мной при практической реализации данного алгоритма. Мне
интересна конечная (программная) реализация.
--- Alex Raider / Flash inc.
* Origin: Alex Raider/ Flash inc. 1992-2001 (2:5000/228.16)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Поиск пути (хитрый ;) 