Как определить диапазон возможного движения в пошаговой стратегической игре на расстоянии?

11

Я создаю двухмерную пошаговую стратегическую игру с использованием c ++ и SFML-2.0. Движение основано на расстоянии, а не на сетке, с несколькими различными фигурами в форме треугольника, каждый из которых в данный ход может либо вращаться на месте, либо двигаться вперед.

Движение будет работать таким образом, что игрок выбирает место для перемещения фигуры, что создает потенциальный путь для фигуры. Как только игрок подтвердит свое решение, фигура будет перемещаться по этому пути в нужное место. Траектории ограничены двумя факторами: расстоянием, расстоянием, на которое способна фигура, принимая во внимание любые повороты (поэтому, если есть кривая, это будет длина вдоль кривой, а не непосредственно от точки к точке); и угол поворота рулевого колеса, насколько далеко деталь может вращаться в любой (и до каждой) точке при движении (например, от -30 до 30 градусов).

Мой вопрос заключается в том, как мне определить диапазон потенциальных мест, которые игрок может выбрать для перемещения фигуры?

Я не совсем уверен, какие уравнения и / или алгоритм использовать здесь. Мой первоначальный план был чрезвычайно сложным, до такой степени, что его было практически невозможно реализовать, не говоря уже о том, чтобы объяснить, и в этот момент я полностью растерялся, когда проект застопорился.

Как я могу определить диапазон, в котором может двигаться юнит, учитывая его радиус поворота?

Например, на изображении ниже. Красные, синие и зеленые линии будут одинаковой длины. Фиолетовый кружок обозначает диапазон движения, который может перемещать юнит. (Форма, вероятно, неточная, и линии, вероятно, на самом деле не имеют одинаковую длину, но вы поняли идею)

введите описание изображения здесь

sfphilli
источник
Он все еще сможет двигаться на то же (общее) расстояние. Таким образом, вопрос на самом деле о выяснить , «насколько же это получается?» / « Сколько нужно повернуть?» / « Где делает это нужно повернуть?». Вам, вероятно, нужно начать с определения обычного пути, а затем повернуть начало поворота назад для углов выше определенной величины; обратите внимание, что конечное расстояние будет длиннее на прямой линии (поворот в последнюю очередь), чем на кривых.
Заводная муза
Да, пройденное расстояние является основным ограничивающим фактором. Мое самое большое препятствие здесь заключается в том, что мне нужно учитывать, что фигура может поворачиваться и продолжать вращаться в любой точке, в которой она может достичь, пока у нее остается доступное расстояние.
сффилли
Что вы имеете в виду, дальность, на которую может двигаться юнит? Ты имеешь в виду точки, в которые он может двигаться? Насколько вы знакомы с линейной алгеброй (векторами)?
BlueRaja - Дэнни Пфлугхофт
1
Какой реальный сценарий вы пытаетесь смоделировать? Ваша проблема слишком расплывчата в требованиях, в результате чего предлагается слишком много подходов к решению. Существуют хорошо известные подходы (практически) к каждой конкретной проблеме в этой области, но каждый угадывает, какую из этих многочисленных проблем вы действительно решаете.
Питер Гиркенс
1
@PieterGeerkens Я полагаю, потому что OP не запрашивает код, они запрашивают алгоритм. И предоставили достаточно подробную информацию о сценарии, чтобы алгоритм мог быть разумно задуман. Это распространено и приемлемо.
MichaelHouse

Ответы:

4

Создайте поле потока или расстояния, используя Dijsktra's.

По сути, заполните сетку, используя алгоритм Дейкстры без указания пункта назначения (возможно, другое имя для этого; не знаю). Просто возьмите каждый открытый узел, вычислите доступных соседей, вставьте их в открытый список, установите в закрытом списке, обновите «следующий» путь родительского узла и т. Д. При определении стоимости достижения нового узла учитывайте ограничения поворота.

Результатом будет то, что у вас есть сеть всех ваших узлов о том, как вернуться к началу. Узлы, которые не могут быть достигнуты, не будут затронуты первым шагом. Для узлов, которые могут быть достигнуты, будет вычислен элемент «следующий узел по наилучшему возможному пути к родительскому», так что вы можете как выделить все узлы, так и затем использовать эту информацию, чтобы показать или выполнить путь перемещения, когда пользователь наводит указатель мыши или нажимает на выделенные области.

Шон Миддледич
источник
Не совсем то, как я бы объяснил концепцию, или как я бы это реализовал, но, безусловно, правильный подход.
Питер Гиркенс
Мое понимание алгоритма, как есть, заключается в том, что обход узла должен быть независимым от пути. Таким образом, для достижения этой цели вам необходимо добавить еще одну степень свободы (еще одну ось, на которой создаются ваши узлы), предназначенную для облицовки. Другими словами, у вас будет узел для каждой комбинации разных X, Y, потенциально Z и Facing. В противном случае, поиск кратчайшего пути для входа в узел не различает разные стороны при выходе из него. Это правильно? Если это так, является ли этот метод слишком интенсивным?
ТАСагент
@TASagent: хорошая мысль, я не думал, что до конца. Алгоритм тогда, возможно, немного не в порядке, но подход должен работать.
Шон Миддледич
@PieterGeerkens: я согласен, это плохое объяснение. Вы должны сделать свой собственный ответ, который объясняет все это лучше.
Шон Миддледич
Кажется, что это довольно близко к тому, что мне нужно, но я должен признать, что никогда не слышал об этом алгоритме, и поэтому не знаю, как обобщить его до того, что мне нужно. У вас есть ссылка на любую полезную информацию или учебники?
сффилли
4

Решение грубой силы было бы:

  1. Создайте круг вершин вокруг единицы, с единицей в центре. Радиус круга - это максимальное расстояние перемещения. Плотность вершин может меняться в зависимости от того, насколько детальным вы хотите получить конечный результат.
  2. Для каждой позиции вершины симулируйте движение рулевого управления агрегата в направлении этой позиции. Это делается в тесном цикле без рендеринга.
  3. Когда в симуляции рулевого управления будет достигнуто максимальное расстояние, переместите вершину в точку симулируемой единицы. Эта точка является ближайшей единицей, которая может добраться до этой вершины до того, как закончится текущий поворот. Это приводит к уменьшению круга до размера фактического движения.
  4. Используйте эти вершины вместе с вершиной, центрированной на единице, чтобы создать визуализированный круг, чтобы нарисовать возможные расстояния перемещения.

введите описание изображения здесь

Итак, начиная с синего круга, вы обрабатываете свои пути, заканчивая фиолетовым кругом. Затем вы можете использовать эти точки с центральной точкой на устройстве, чтобы сделать красные треугольники, необходимые для отображения формы. (Просто создание этого изображения заставляет меня понять, что эта форма не является правильной, но будет интересно посмотреть, что на самом деле правильно)

MichaelHouse
источник
3

Я собираюсь расширить решение Шона в отдельном ответе, поскольку он представляет собой подход, отличный от того, что я предлагал изначально.

Это решение, вероятно, представляет собой наиболее доступный метод. Это требует разделения вашей среды на узлы. Да, это повторное внедрение подхода, основанного на сетке, но его можно сделать относительно хорошо или использовать для широкого поиска пути с более точным позиционированием, обрабатываемым в узле. Чем более грубая структура узла, тем быстрее поиск пути.

Большая проблема здесь заключается в том, что вы на самом деле имеете дело с облицовкой корабля, поэтому многие традиционные решения поиска пути не могут быть использованы без изменений. Обычно они не зависят от пути, потому что им все равно, как вы попали на узел, в котором находитесь. Это прекрасно работает, когда ускорение, замедление и поворот происходят мгновенно и свободно. К сожалению для вас обращение не бесплатно. Тем не менее, поскольку в этом упрощении действительно есть одна дополнительная информация, мы можем закодировать ее как другую переменную. В физике это будет известно как фазовое пространство.

Предполагая пока 2-мерное измерение, вы можете экстраполировать на 3:

Обычно вам потребуется один узел для каждой допустимой дискретной координатной позиции. Например:

(0,0) - (1,0) - (2,0)
  | \  /  |  \  / |
(0,1) - (1,1) - (2,1)

И т. Д. Вы должны построить нодграф соседних точек и соединить их пространственной смежностью. Затем вы будете использовать алгоритм Дейкстры, убивая узлы, которые превышают допустимое для хода значение перемещения, пока не останется неизведанных живых узлов, оставшихся подключенными к исследованным узлам. Каждый узел отслеживает наименьшее расстояние, необходимое для его достижения.

Чтобы расширить этот метод для использования с вращением, представьте этот же нодграф в 3-х измерениях. Направление Z соответствует повороту / направлению и является циклическим, то есть, если вы продолжаете двигаться в направлении + Z, вы возвращаетесь к тому, с чего начали. Теперь узлы, соответствующие соседним позициям, соединены только через то направление, которое соответствует этому направлению. Вы перебираете узлы, связанные с уже исследованными узлами, как обычно. Я бы порекомендовал ограничиться N, NE, E, SE, S, SW, W, NW в этой схеме.

Это решение может рассказать вам обо всех доступных областях пространства, а также о том, как лучше всего туда добраться, сколько у вас вращения, когда вы туда доберетесь, и обо всех направлениях, которые вы могли бы иметь, когда вы туда доберетесь.

Затем, когда вы на самом деле выполняете путь, вы можете интерполировать / кубический сплайн, чтобы он выглядел более аутентично.

TASagent
источник
1
Это отлично. Мне нужно будет немного изучить алгоритм и поэкспериментировать с ним в моей игре, но это действительно показалось мне идеальным решением, тем более что я могу обобщить его для некоторых других важных частей игры.
сффилли
1

Звучит так, как будто вам, возможно, придется сначала решить, как именно вы хотели бы включить работу на ходу. Варианты как:

  • Если они движутся внутри конуса, сначала вращайте, затем начинайте двигаться. Это простое решение для реализации и путь для. Это также менее интересно, поэтому я бы не хотел его использовать.

  • Непрерывный поворот при движении, до 45 градусов. Этот намного хитрее, и, надеюсь, тот, который вам нужен. Численная интеграция по пути с использованием фиксированного временного шага, вероятно, является самым простым способом приблизиться к этому. Ваш конус будет ограничен максимальным (+ X градусов на каждый шаг) и минимальным (-X градусов на каждый шаг) поворотом.

Как лучше всего пройти через пространство со вторым из этих требований, во многом зависит от среды, в которой они будут перемещаться. Если есть много препятствий, которые вам нужно преодолеть, то все может стать действительно сложным и действительно дорогим. Однако, если его нет, вы можете загрузить (и даже уменьшить) вращение, чтобы в конечном итоге оказаться в нужном месте.

У меня есть ощущение, что я, возможно, только частично затронул темы, по которым у вас возник вопрос, поэтому не стесняйтесь добавлять больше комментариев, и я могу расширить обсуждение.

TASagent
источник
Я совершенно определенно хочу использовать второй вариант, например, повернуть до (например) 45 градусов в любой и, возможно, в каждой точке вдоль пути. Также будут препятствия, каждое больше, чем кусочки (подумайте о гигантских камнях). Первоначально я думал об этом, чтобы сгенерировать конус возможных конечных точек, а затем для каждой из этих конечных точек сгенерировать новый конус и так далее для каждого возможного местоположения, пока оно не достигнет максимального пройденного расстояния. Тем не менее, я не совсем уверен, как реализовать это без сумасшедшего чрезмерного усложнения.
сффилли
Хммм, кажется, я был немного неясен относительно некоторых деталей. Оглядываясь назад на вопрос, я вижу, что вы указали «пошаговый» и что юниты могут «вращаться или двигаться» в свой ход. Значит ли это, что игрок готовит свои действия за много ходов заранее, и вы хотите найти путь, пока он движется? Некоторое дальнейшее разъяснение о том, как движение должно работать, было бы полезно.
ТАСагент
Нет, я имел в виду, что в данный ход игрок может либо вращать свою фигуру на месте, сколь угодно далеко, либо он может двигаться в направлении, которое он уже смотрит. Если они двигаются, они могут пройти определенное расстояние вдоль пути, и они могут повернуться или повернуть на определенный угол (например, в диапазоне от -45 до 45 градусов) во время движения. Итак, представьте, что выбранный путь будет включать в себя кривую, чтобы двигаться влево или вправо. Путь будет определяться игроком, выбирающим точку, в которую он хочет переместиться, в пределах диапазона возможных точек, которые у меня возникают проблемы при определении.
сффилли
Итак, на самом деле звучит так, что, к сожалению, ваши желаемые характеристики могут быть слишком ограничивающими для алгоритма Дейкстры, о котором мы говорили выше: - \. Возможно. Я обрисую некоторые вещи для этого позже, когда вернусь домой.
TASagent
Возможно, вы захотите отредактировать часть этой информации, которую вы собрали, чтобы прояснить проблему в исходном вопросе, чтобы люди, пришедшие позже, могли начать с получения дополнительной информации.
ТАСагент