Еще довольно давно, примерно на первых курсах ВУЗа, я играл с другом по сети в игру SpellForce, и обратил внимание, что когда мой герой бежал по дороге вдоль забора, на повороте он оббежал забор по дуге.
Как раз незадолго до этого мы с друзьями работали над поиском пути для другого проекта, и в нашей реализации персонажи поворачивали резко. Я начал думать, смогу ли я адаптировать свою реализацию так, чтобы персонаж поворачивал по дуге. И я понял, что ничего из этого не выйдет.
Тогда я решил проверить как персонажи поворачивают в эталонной RTS игре, так как раньше внимания на это не обращал. Как и ожидалось, в StarCraft персонажи поворачивают резко.
С тех пор прошло много времени, и недавно, работая над уже совсем другим проектом, я опять задался этим вопросом.
Постановка задачи: имеется персонаж, представленный окружностью радиуса R, посланный из одной точки до другой на местности с препятствиями, представленными выпуклыми многоугольниками. Требуется найти кратчайший путь для персонажа. Очевидно, кратчайший путь будет всегда поворачивать вдоль дуги окружности радиуса R.
Демка почти рабочего решения -- в редких случаях найденный путь не является кратчайшим (левый клик в любой точке пошлет персонажа к этой точке):
Ну и это, в свою очередь, ничто иное, как задача D с чемпионата России по программированию 2006 года:
http://neerc.ifmo.ru/past/2006/problems/problems.pdf
За той лишь разницей, что там многоугольники могли быть не произвольными, а только прямоугольники со сторонами, параллельными осям координат. Что в сущности никак не влияет задачу - общее решение не сложнее частного.
Идея решения достаточно проста. Превращаем окружность в точку, расширив все прямоугольники на ее радиус во всех направлениях, превратив их тем самым в прямоугольники со скругленными углами, и дальше строим граф, где вешнины - это некоторые контрольные точки, а ребра между парой вершин есть тогда и только тогда, когда путь по прямой между этими вершинами не пересекает ни одного многоугольника. Даже при ограничениях, данных в задаче (30 прямоугольников) лучшее такое решение, которое я смог написать, работало 20 секунд на худшем тесте.
Но в нашей задаче есть несколько важных отличий, которые помогут сделать гораздо более быстрое решение:
1. На адекватной карте многоугольники распределены по поверхности карты, не создавая "крайних случаев". Проверяя для данного отрезка пути пересекает ли он какие-то ребра или скругленные углы многоугольников, мы можем использовать какие-то оптимизации, которые могут не улучшать худший случай, но улучшать средний, чтобы сразу отсечь кандидатов, которые даже близко не лежат на пути.
2. Нам не нужен идеальный маршрут. Игрок, скорее всего, не сможет отличить кратчайший маршрут от не самого короткого, а даже если и сможет, едва ли воспримет это как критичное упущение. Поэтому сделать ряд эвристик при проверке отрезка на пересечения.
3. Конечно, надо использовать A* а не Дийкстру.
Определим очертания алгоритма:
1. На вход подается набор многоугольников, координаты начала S, координаты конца E, радиус персонажа R.
2. Для каждого многоугольника отодвигаем каждое ребро от центра многоугольника на R. Для того, чтобы понять, в какую из двух сторон двигать ребро, надо понять, задан он по часовой стрелке или против часовой. Для этого можно, например, посчитать сумму всех векторных произведений соседних сторон. Абсолютная величина этого значения будет удвоенной площадью многоугольника, а знак будет говорить о том, направлены ребра по часовой стрелке или против часовой. В разорванные углы многоугольника добавляем дуги с радиусом R.
3. Забываем про многоугольники, оставляя только набор отрезков и дуг.
4. Строим граф. Для этого поймем, как будет выглядеть кратчайший путь. Если внимательно проанализировать тип карты, становится понятно, что каждый фрагмент пути будет либо пролегать вдоль одной из дуг, либо идти по общей касательной двух дуг (либо идти от стартовой/к конечной точке по касательной одной из дуг).
5. Строим путь. При поиске пути на каждой итерации мы будем находиться в какой-то точке какой-то дуги - вершине графа. Мы будем перебирать все остальные дуги, и идти к ним кратчайшим путем, который, очевидно, будет состоять из пути по дуге до точки касания общей касательной, а затем пути вдоль этой самой общей касательной.
Далее опишем сам алгоритм, и будем достаривать его до рабочего варианта.
1. Если конечная точка достижима из начальной, возвращаем один отрезок
Зависимости: Для проверки нам понадобится функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте. Это, в свою очередь, потребует написать функции пересечения отрезка и отрезка, и пересечения отрезка и дуги (можно заметить, что для данной конкретной задачи хватило бы пересечения отрезка и окружности).
2. Добавим в очередь вершины, достижимые из начальной точки.Вершину будем задавать как дугу, на которой она лежит, ее координаты относительно центра окружности, которой принадлежит эта дуга, и направление, по которому персонаж продолжит движение (по часовой стрелке или против).
{
Point center;
Vector relativePosition;
Bool isClockWise;
}
Для нахождения всех достижимых из начальной точки вершин, построим касательную из этой точке к каждой дуге, и проверим, что отрезок от начальной точки до точки касания не пересекает ничего на карте.
Зависимости: Функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте, у нас уже есть с прошлого шага. К этому добавляется функция поиска касательной к окружности из заданной точки, и проверка, принадлежит ли точка касания заданной дуге.
Нам также понадобится приоритетная очередь. Ключом для элемента приоритетной очереди будем считать уже известное нам расстояние от начальной точки до заданной вершины плюс эвклидово расстояние от заданной вершины до конечной точки (это эвклидово расстояние в нашем случае будет единственным отличием A* от Дийкстры).
3. Аналогично, найдем все вершины, из которых достижима конечная точка.
4. Пока приоритетная очередь не пуста, и пока не найден путь, достаем из приоритетной очереди вершину с минимальным ключом. Помним, что любая вершина -- это точка на дуге.
Обработаем два типа переходов:
а) Проверим, нет ли на текущей дуге вершины (пусть А), из которой достижима конечная точка. Если она есть -- проверим, можем ли мы дойти по дуге от текущей вершины до вершины А. Если можем, добавим в приоритетную очередь конечную точку.
б) Для каждой дуги на карте, отличной от текущей, построим все общие касательные для окружностей, содержащих текущую дугу и закрепленную дугу. Из не более чем четырех касательных оставим не более чем две: мы помним, в каком направлении (по часовой стрелке или против часовой стрелки) двигается персонаж -- оставим те две касательные, по которым можно начать движение двигаясь в том направлении, в котором двигается персонаж. Для каждой из не более чем двух оставшихся касательных проверим, пересекает ли путь по дуге от текущей вершины до точки касания на текущей дуге, а затем вдоль касательной до точки касания на закрепленной дуге, что-либо на карте. Если не пересекает, добавляем точку касания на закрепленной дуге в приоритетную очередь.
Если на очередной итерации с вершины приоритетной очереди достали конечную точку, восстанавливаем путь и возвращаем его.
Зависимости: нам понадобится функция, которая проверяет, пересекает ли заданная дуга что-либо на карте. Для этого надо написать две функции: пересечение дуги и дуги и пересечение дуги и отрезка. Вторая функция у нас осталась с первого шага.
Нам также понадобится функция, проверяющая пересекает ли заданный отрезок что-либо на карте. Она также осталась с первого шага.
Наконец, нам понадобится функция, находящая все общие касательные двух окружностей.
В принципе это весь алгоритм.
Код на ActionScript, и парный ему на JavaScript, доступен здесь:
http://skidanovalex.ru/files/astar.zip
Код на яваскрипте включает несколько тестов к геометрическим функциям (кроме пересечения отрезка и дуги).
Как раз незадолго до этого мы с друзьями работали над поиском пути для другого проекта, и в нашей реализации персонажи поворачивали резко. Я начал думать, смогу ли я адаптировать свою реализацию так, чтобы персонаж поворачивал по дуге. И я понял, что ничего из этого не выйдет.
Тогда я решил проверить как персонажи поворачивают в эталонной RTS игре, так как раньше внимания на это не обращал. Как и ожидалось, в StarCraft персонажи поворачивают резко.
С тех пор прошло много времени, и недавно, работая над уже совсем другим проектом, я опять задался этим вопросом.
Постановка задачи: имеется персонаж, представленный окружностью радиуса R, посланный из одной точки до другой на местности с препятствиями, представленными выпуклыми многоугольниками. Требуется найти кратчайший путь для персонажа. Очевидно, кратчайший путь будет всегда поворачивать вдоль дуги окружности радиуса R.
Демка почти рабочего решения -- в редких случаях найденный путь не является кратчайшим (левый клик в любой точке пошлет персонажа к этой точке):
Ну и это, в свою очередь, ничто иное, как задача D с чемпионата России по программированию 2006 года:
http://neerc.ifmo.ru/past/2006/problems/problems.pdf
За той лишь разницей, что там многоугольники могли быть не произвольными, а только прямоугольники со сторонами, параллельными осям координат. Что в сущности никак не влияет задачу - общее решение не сложнее частного.
Идея решения достаточно проста. Превращаем окружность в точку, расширив все прямоугольники на ее радиус во всех направлениях, превратив их тем самым в прямоугольники со скругленными углами, и дальше строим граф, где вешнины - это некоторые контрольные точки, а ребра между парой вершин есть тогда и только тогда, когда путь по прямой между этими вершинами не пересекает ни одного многоугольника. Даже при ограничениях, данных в задаче (30 прямоугольников) лучшее такое решение, которое я смог написать, работало 20 секунд на худшем тесте.
Но в нашей задаче есть несколько важных отличий, которые помогут сделать гораздо более быстрое решение:
1. На адекватной карте многоугольники распределены по поверхности карты, не создавая "крайних случаев". Проверяя для данного отрезка пути пересекает ли он какие-то ребра или скругленные углы многоугольников, мы можем использовать какие-то оптимизации, которые могут не улучшать худший случай, но улучшать средний, чтобы сразу отсечь кандидатов, которые даже близко не лежат на пути.
2. Нам не нужен идеальный маршрут. Игрок, скорее всего, не сможет отличить кратчайший маршрут от не самого короткого, а даже если и сможет, едва ли воспримет это как критичное упущение. Поэтому сделать ряд эвристик при проверке отрезка на пересечения.
3. Конечно, надо использовать A* а не Дийкстру.
Определим очертания алгоритма:
1. На вход подается набор многоугольников, координаты начала S, координаты конца E, радиус персонажа R.
2. Для каждого многоугольника отодвигаем каждое ребро от центра многоугольника на R. Для того, чтобы понять, в какую из двух сторон двигать ребро, надо понять, задан он по часовой стрелке или против часовой. Для этого можно, например, посчитать сумму всех векторных произведений соседних сторон. Абсолютная величина этого значения будет удвоенной площадью многоугольника, а знак будет говорить о том, направлены ребра по часовой стрелке или против часовой. В разорванные углы многоугольника добавляем дуги с радиусом R.
3. Забываем про многоугольники, оставляя только набор отрезков и дуг.
4. Строим граф. Для этого поймем, как будет выглядеть кратчайший путь. Если внимательно проанализировать тип карты, становится понятно, что каждый фрагмент пути будет либо пролегать вдоль одной из дуг, либо идти по общей касательной двух дуг (либо идти от стартовой/к конечной точке по касательной одной из дуг).
5. Строим путь. При поиске пути на каждой итерации мы будем находиться в какой-то точке какой-то дуги - вершине графа. Мы будем перебирать все остальные дуги, и идти к ним кратчайшим путем, который, очевидно, будет состоять из пути по дуге до точки касания общей касательной, а затем пути вдоль этой самой общей касательной.
Далее опишем сам алгоритм, и будем достаривать его до рабочего варианта.
1. Если конечная точка достижима из начальной, возвращаем один отрезок
Зависимости: Для проверки нам понадобится функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте. Это, в свою очередь, потребует написать функции пересечения отрезка и отрезка, и пересечения отрезка и дуги (можно заметить, что для данной конкретной задачи хватило бы пересечения отрезка и окружности).
2. Добавим в очередь вершины, достижимые из начальной точки.Вершину будем задавать как дугу, на которой она лежит, ее координаты относительно центра окружности, которой принадлежит эта дуга, и направление, по которому персонаж продолжит движение (по часовой стрелке или против).
{
Point center;
Vector relativePosition;
Bool isClockWise;
}
Для нахождения всех достижимых из начальной точки вершин, построим касательную из этой точке к каждой дуге, и проверим, что отрезок от начальной точки до точки касания не пересекает ничего на карте.
Зависимости: Функция, которая проверяет, пересекает ли заданный отрезок что-либо на карте, у нас уже есть с прошлого шага. К этому добавляется функция поиска касательной к окружности из заданной точки, и проверка, принадлежит ли точка касания заданной дуге.
Нам также понадобится приоритетная очередь. Ключом для элемента приоритетной очереди будем считать уже известное нам расстояние от начальной точки до заданной вершины плюс эвклидово расстояние от заданной вершины до конечной точки (это эвклидово расстояние в нашем случае будет единственным отличием A* от Дийкстры).
3. Аналогично, найдем все вершины, из которых достижима конечная точка.
4. Пока приоритетная очередь не пуста, и пока не найден путь, достаем из приоритетной очереди вершину с минимальным ключом. Помним, что любая вершина -- это точка на дуге.
Обработаем два типа переходов:
а) Проверим, нет ли на текущей дуге вершины (пусть А), из которой достижима конечная точка. Если она есть -- проверим, можем ли мы дойти по дуге от текущей вершины до вершины А. Если можем, добавим в приоритетную очередь конечную точку.
б) Для каждой дуги на карте, отличной от текущей, построим все общие касательные для окружностей, содержащих текущую дугу и закрепленную дугу. Из не более чем четырех касательных оставим не более чем две: мы помним, в каком направлении (по часовой стрелке или против часовой стрелки) двигается персонаж -- оставим те две касательные, по которым можно начать движение двигаясь в том направлении, в котором двигается персонаж. Для каждой из не более чем двух оставшихся касательных проверим, пересекает ли путь по дуге от текущей вершины до точки касания на текущей дуге, а затем вдоль касательной до точки касания на закрепленной дуге, что-либо на карте. Если не пересекает, добавляем точку касания на закрепленной дуге в приоритетную очередь.
Если на очередной итерации с вершины приоритетной очереди достали конечную точку, восстанавливаем путь и возвращаем его.
Зависимости: нам понадобится функция, которая проверяет, пересекает ли заданная дуга что-либо на карте. Для этого надо написать две функции: пересечение дуги и дуги и пересечение дуги и отрезка. Вторая функция у нас осталась с первого шага.
Нам также понадобится функция, проверяющая пересекает ли заданный отрезок что-либо на карте. Она также осталась с первого шага.
Наконец, нам понадобится функция, находящая все общие касательные двух окружностей.
В принципе это весь алгоритм.
Код на ActionScript, и парный ему на JavaScript, доступен здесь:
http://skidanovalex.ru/files/astar.zip
Код на яваскрипте включает несколько тестов к геометрическим функциям (кроме пересечения отрезка и дуги).
1. сперва определить ключевые точки - точки в которых угол между смежными сторонами многоугольника острый, <180 градусов. Ведь в противном случае никакой путь не будет лежать через точку, более того, ее не сможет "достичь" персонаж любого радиуса, так же как большой шар не может касаться плинтуса.
2. построить начальный граф видимости, состоящий из ребер, проведенных между каждой парой ключевых точек, для которых отрезок, их соединяющий, не пересекает ни одну из сторон какого-либо многоугольника.
3. для каждой из ключевых точек задать понятие "сектора касания", как бы на пальцах объяснить, лучше нарисую:
Очевидно, что такой сектор всегда будет существовать, по определению ключевых точек.
4. Теперь нужно для каждого ребра графа видимости определить вес - весом будет максимальный радиус Ri персонажа, который способен пройти по этому ребру, коснувшись точек, расположенных в концах этого ребра. Вот как сделать это, я пока еще не очень хорошо представляю. Есть такая идея (нежесказанное является функцией от ребра, все написано в контексте одного текущего ребра, эту операцию нужно проделывать для каждого ребра отдельно):
4.1. Определить "вектора роста" окружностей для концов ребра. Начала обоих векторов находятся в точках конца ребра, направление изначально выбирается на прямой, их соединяющей, навстречу друг другу, однако, если вектора не попадают в сектора касания, "подкрутить" их, чтобы попадали, я не умею выражаться строго математически, поэтому лучше вставлю еще одну картинку:
4.2. Теперь осталось определить, окружность какого максимального радиуса касающаяся первой ключевой точки и центр которой лежит на первом векторе роста, может по прямой передвинуться на позицию, когда она будет касаться второй ключевой точки, а центром лежать на втором векторе роста.
4.3. Я пока не придумал, как это сделать красиво, а тем более быстро, изящно, хотя эту операцию нужны выполнять лишь когда меняется топология, такая фича возможно будет добавлена мной позже, поэтому хотелось бы, чтобы считало быстро. Возможно, что начать стоит с того, чтобы определить, окружности какого максимального диаметра могут лежать в начальном и конечном положениях, выбрать минимум, построить прямогульник, боковые стороны которого будут диаметрами окружности в начальном и конечном положении, а стороны - касательными к ним. Далее, стоит просматривать по очереди все имеющиеся отрезки-стороны многоугольников, и в случае их пересечения с прямоугольником, уменьшать радиус. Не уверен.
5. Более того, остается момент с дугами вокруг ключевых точек во время движения. опять же хотелось бы быстроты, но я опишу решение, которое пока есть - заменять каждую вершины на полный связный граф (да, да, это ппц как много памяти и вычислений, но граф будет специфичный, есть место для оптимизации). Например, если из вершины выходят три ребра, то вершина заменятся на граф из трех точек, каждая из которых соединена с каждой, а вес ребра между ними все так же равен максимальному радиусу окружности, которая может по дуге обогнуть ключевую точку от вектора роста для ребра соответствующего первому ребру до вектора роста для ребра, соответствующего второму ребру. Я не буду рисовать картинок, если вы дочитали до этого места, думаю сами представляете, что я имею в виду, если уловили мою идею.
В итоге мы должны получить топологически правильный граф, который... блин, мне лень править все что я так аккуратно формулировал... В общем, я писал вес и говорил - максимальный радиус. Естественно, должно быть два веса, первый - максимальный радиус, а второй - геометрическая длина пути. Расстояние по прямой между точками для ребер, получившихся в пункте 4 и по дуге для ребер из пункта 5. Тогда мы можем юзать и дейкстру и А*, на полученном графе для поиска кратчайшего пути по "геометрическому весу" с учетом того, что ребра, "радиусный вес" которых меньше радиуса персонажа мы будем игнорировать.
Буду рад, если вы как-то прокомментируете, добавлю страницу в закладки.