Еще довольно давно, примерно на первых курсах ВУЗа, я играл с другом по сети в игру 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
Код на яваскрипте включает несколько тестов к геометрическим функциям (кроме пересечения отрезка и дуги).
Comments (0)
