В настоящее время у меня есть некоторые проблемы с моей системой Pathfinding, которая "ненормально" медленна на моем большом графике:
Мой график
- Свойства графика: 16814 вершин / 61512 ребер
- Граф направлен.
- Каждая вершина имеет идентификатор подграфа (ID острова) → Нет решения между подграфами, НО ВСЕГДА внутри одного и того же подграфа.
Каждая вершина графаопределяется следующим образом:
- тип (камень, песок, ...).
- высота
Последнее правило: земля не связана с океаном (поэтомуу нас есть много подграфов).
Моя конфигурация Astar
Моя эвристика очень классическая: я вычисляю точку между текущей вершинойпозиция и позиция цели.
У меня нет предварительно рассчитанного веса для ребер.Я использую сложный алгоритм (зависит от скорости ходунка, типа земли, если мы пойдем вверх или вниз)
float PathWorld::updateWeight(const Agent& agent, const EdgeInfo& edgeInfo) const
{
const Agent::Navigation& navigation = agent.getNavigation();
const auto& fromTerrain = edgeInfo._from->_terrain;
const auto& toTerrain = edgeInfo._to->_terrain;
const float mean = (navigation._speed.at(fromTerrain._type) + navigation._speed.at(toTerrain._type)) * 0.5f;
const float diff = BT::Maths::clamp((1000.0f + toTerrain._height - fromTerrain._height) / 1000.0f, 0.5f, 2.0f);
return edgeInfo._distance / mean * diff;
}
Проблемы
В настоящее время время выполнения занимает менее 1 мс до1 секунда, когда я вычисляю один путь.Решение пути - это всего лишь 8 или 80 вершин, и у меня нет пропорционального времени.(Таким образом, путь 8 вершин может занимать 1 секунду, а путь 80 вершин - 1 мс.)
Я выполняю быстрое профилирование с помощью Visual Studio: повышение - мое узкое место.
Код и данные тестирования
Весь полный код и данные тестирования можно найти на моем GitHub.
https://github.com/Rominitch/myBlogSource/tree/master/DEMO/TestPathfinding
Простая / маленькая демонстрация не страдает от моей проблемы.Просто сложный случай.Все графические изображения были сгенерированы одной и той же программой (не опубликовано).
Вывод моей программы тестирования
Моя программа тестирования действительно пустая: - Я беру узел для начала в моем графике - Я беру XXX узловпосле этого (используя индекс) и вычислите путь.
Выходы:
Statistics:
Start node: Ocean H= 0 SubGraph= 2
nbValid: 2053/15000 (valid path / number of path computed)
min / max: 1/75 (number of vertex in path computed)
min time for one path: 0 ms
max time for one path: 7 ms
Statistics:
Start node: Forest H= 100 SubGraph= 1
nbValid: 1420/1500
min / max: 1/76
min time for one path: 0 ms
max time for one path: 558 ms
Statistics:
Start node: Swamp H= 50 SubGraph= 1
nbValid: 601/1000
min / max: 1/51
min time for one path: 0 ms
max time for one path: 1246 ms
Statistics:
Start node: Clay H= 300 SubGraph= 22
nbValid: 138/15000
min / max: 1/12
min time for one path: 0 ms
max time for one path: 0 ms
Вопросы
- Где моя проблема?(плохое повышение с использованием / плохой график / ограничение усиления)
- Повышение - хороший выбор для разрешения поиска пути (другая библиотека)?
- Можем ли мы оптимизировать данные моего графика (лучший алгоритм повышения, уменьшить дублирование данных, ...)?
Спасибо!