|
•Готов демо-пример алгоритма поиска кратчайшнго пути - Geo, 18.05.2003 11:39:03 |
|
|
Выложен в буфер файл PathFind.zip, который содержит exe-шник, чтобы могли попробовать и те, у кого нет Дельфи. Так что желающих милости просим на тестирование.
Предупреждаю сразу, программа создавалась для тестирования алгоритма. Ни богатства графики, ни продуманности пользовательского интерфейса вы в ней не найдете. Да и ошибки вполне возможны: очень спешил. Все управляется мышой и ее левой кнопкой. Описание писать ломает. Авось так разберетесь. Там вроде бы все названия говорящие.
Описание идеи алгоритма. Есть две точки: начальная и конечная. В одну из них помещаем юнит и пытаемся ехать во всех направлениях, то есть если из клетки можно поехать в несколько направлений, то делается несколько копий юнита, чтобы по каждому направлению поехал один из них. Если юнит доезжает до клетки, из которой некуда ехать (или все соседние клетки не допускают движения юнита такого типа, или по ним уже кто-то раньше проехал), то этот юнит убирается. Путь того юнита, который доехал до другой точки первым мы принимаем за кратчайший путь. Если все юниты убраны, значит путь не существует.
Небольшое примечание: в M.A.X. затраты на движение могут выражаться дробными числами по отношению к единице скорости (speed). К тому же есть ходы, которые стоят менее одной единицы скорости (по дорогам например). Чтобы не возиться с дробными числами надо взять за единицу стоимости перемещения четверть единицы скорости.
Таблица затрат на движение в приведенных единицах (по прямой/по диагонали):
По дороге: 2/3
Без дороги: 4/6
Амфибии по воде: 12/18
Для получения этих же значений в единицах скорости нужно поделить эти числа на 4. Округление производится в бОльшую сторону.
Barloggg: Я могу прислать исходники программы, но там черт ногу сломит (как обычно). Вылизывать демку некогда. Поэтому либо придумай сам по приведенному описантю идеологии, либо я создам чисто под твой вариант. На крайняк могу попытаться написать универсальный модуль, но это сложнее.
Немного о стандартных алгоритмах. Стнадартные алгоритмы поиска кратчайшего пути на графе (алгоритм Дейкстры, например) тут не катят: у нас очень частный случай задачи (в любую точку можно попасть не более чем из восьми прилегающих к ней точек, плюс цена перемещения определяется только типом конечной точки и диагональностью направления перемещения). Поэтому не имеет смысла искать какие-то из стандартных алгоритмов, чтобы применить их здесь. Любой (даже переборный) алгоритм будет работать много быстрее.
В оригинальном M.A.X. кстати путь ищется очень долго: либо они использовали классический алгоритм, либо анимация съедает кучу ресурсов. |
|
| |