Добавлено: Сб Dec 05, 2009 22:55
Заголовок сообщения:
Да, это горячо мною любимый поиск пути. Из-за него и ИИ тормозит на больших картах. Не хватает силы воли заставить себя переписать этот алгоритм - ещё свежи воспоминания, как я с ним намучился в своё время
осколок имел примерно 100 провинций.
имеем граф со 100 узлами и с длинами дуг длиной от 1 до 4(сложность местности).
т.е. длины - целые числа.
алгоритм нахождения кратчайшего пути в графе - классический простой алгоритм, тем более с целыми дугами.
но тут сложность с тем что за один ход герой с моб. = 1 может пройти болото (длина дуги = 3 или 4, не помню).
Если бы не было бы рельефа, то все решалось бы просто:
Классический алгоритм типа «водопровод»:
Есть граф-водопровод с длинами труб только 1 метр.
Есть начальный источник воды *, который заливает воду в трубы во все стороны со скоростью 1 метр в день. (да, такая вот у меня вода
)
И дальше все просто: эмулируем как вода ползет в первый день, как во второй, как в третий и т.д.
А как учесть горы-болота?
Просто так сделать длины труб = 1, 2, 3, 4 мало.
Тут я попробовал придумать простой алгоритм заливки графа с рельефом.
Похоже, получилось:
================================
допустим, у героя есть какая-то мобильность = N, т.е. заливается N метров трубы в день.
Создаем граф с длинами дуг-труб = 1, 2, 3, 4
День первый: из точки * идет заливка во все стороны обычным способом с одним исключением.
Если * находится рядом с болотом (длина трубы = дуги =3), а N = 1, то принудительно вода загоняется в смежные узлы.
Т.е. имеем классическую заливку + принудительное наводнение смежных узлов.
Наступает ночь. Приходит уборщица со шваброй и осушает все неполностью залитые трубы (в которых воды не 100%).
Наступает день второй: все граничные узлы (рядом с сухими трубами) становятся источниками воды *.
вода опять весело льется во все стороны из * со скоростью N метров в день.
Алгоритм линейный.
--------
P/S Можно еще упростить:
трубу длиной = 4 из точки А в Б можно понимать как 4 подтрубы длиной 1.
Т.е. заменить дугу А-Б на подграф А-X-Y-Z-Б.
Но, конечно, для уборщицы 4 трубы А-X-Y-Z-Б должны восприниматься как одна труба
----
P/S да, сразу не заметил, что граф ориентированный а не (одно)направленный.
т.е. дуга из болота в равнину имеет длину = 1, обратно = 4.
В общем, обычный алгоритм заливки ориентированности не предполагает.
Но представить, что две точки могут быть соединены двумя трубами, по которым вода может течь только в определенных направлениях, тоже можно.
И, главное, написать эмуляцию движения "воды" по таким "трубам"
тоже можно.
Последний раз редактировалось: Jeka (Пн Dec 07, 2009 0:05), всего редактировалось 1 раз
Великая Кузня
