ПрограммированиеФорумИгровая логика и ИИ

Сложный поиск пути в стратегиях (2 стр)

Страницы: 1 2
#15
16:20, 31 июля 2012

Алгоритм дейкстры, А* и прочие в первую очередь строят дерево кратчайших путей из некоторой начальной точки во все остальные, до которых дерево дотянется.  Несложная модификация А* позволяет искать одним заходом кратчайшие маршруты из точки А в набор точек {B1, B2, B3...}. Совсем классический пример - задача "до какой точки мне топать ближе". В случае с большим зданием можно продолжать строить дерево, пока оно не охватит всё здание, а потом выбрать точку здания ( или периметра ) с минимальной стоимостью маршрута.

Кстати вполне реальны ситуации применения А* практически "наизнанку", когда начальных точек несколько, а финиш совсем отсутствует ( покрытие всей карты ).

Страницы: 1 2
ПрограммированиеФорумИгровая логика и ИИ

Тема в архиве.