У меня есть сетка с препятствиями, и мне нужно найти наиболее привлекательный многоугольник между двумя узлами.Операция, скорее всего, будет узким местом, поэтому я надеюсь, что на ранних этапах будет реализована достаточно эффективная реализация, и у меня все еще есть портативное решение (т.е. пока нет C).Я бы хотел сделать решение OpenCL как позднюю игру, но сначала нужно это сделать.
Я уже использую struct::graph для решения ряда проблем и подумал, что смогу использовать его еще раз для этой.Читая документацию о graph и op , кажется, что проблема уже решена, но она не дает мне понять, как на самом деле использовать API.
Проблема в упрощенном дизайне,Существует конечная прямоугольная сетка (30x30 вершин), где каждая ячейка является узлом на графике.Каждый узел имеет выровненные по оси ребра с другими узлами в сетке, если на пути нет препятствий, обычно это концы уже существующих многоугольников.Стоимость краев ниже для более длинных краев, что делает многие повороты (лестницы) менее привлекательными для алгоритма поиска пути.(Существуют также другие эвристики, влияющие на стоимость фронта.)
Если я заполнил struct::graph выше, как мне найти кратчайший путь от узла A к любому из набораузлы B (много, если подключиться к гиперграфу)?
Достигнутый прогресс: Многие из операционных API, похоже, возвращают кратчайший путь к всем узлам на графике, что не то, что мне нужно, хотя я мог быиспользуйте его, пока я не найду лучший способ.Предполагая, что я могу изменить граф в walk cmd, я мог бы сделать более простое сокращение на лету, но документы не указывают на это как на возможность.
И если выясняется, что struct :: graphпо своей природе (слишком) медленный, я был бы рад исправить это в форме.Просто нужно сначала знать, что я собираюсь использовать ...