Бесконечно перемещать объекты вокруг случайно без столкновения

Ответ 1

A* - это алгоритм для нахождения кратчайшего пути между конфигурацией начала и цели (с точки зрения того, что вы определяете как короткое: общее - это, например, эвклидовое расстояние, стоимость или время, расстояние angular). У ваших насекомых, похоже, нет конкретной цели, им даже не нужен кратчайший путь. Я бы, конечно, не пошел за A*. (Кстати, поскольку у вас есть динамическая среда, D* была бы идеей - все же это означало найти путь от A до B).

Я бы решил проблему следующим образом:

Случайные пути и последующие за ними

Для случайных путей я вижу два метода. Первым было бы простое случайное блуждание (нажмите здесь, чтобы увидеть приятную 2D-анимацию с пояснениями), которая может страдать от дрожания и не выглядите слишком красиво. Второе требует немного более подробных объяснений.

Для каждого насекомого генерируются четыре случайные точки вокруг них, возможно, начиная с синусоиды. С сплайновая интерполяция генерирует плавную кривую между этими точками. Позаботьтесь о наличии C1 (в 2D) или C2 (в 3D) continuity. (Предложение: Hermite splines) С сплайны Catmull-Rom вы можете найти свои конфигурации при движении по кривой.

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

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

If third point is reached
    Remove first
    Append new point
    Recalculate spline
End if

Для более плавной кривой добавьте больше очков и двигайтесь где-то посередине, принцип остается прежним. (Лично я использовал это только в фиксированных средах, но должен работать и в динамических.)

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

Избегать других насекомых

Чтобы избежать других насекомых, мне приходят три разных метода.

• Алгоритмы ошибок
• Автомобили Брайтенберга
• Применение потенциальных полей

Для потенциальных полей я рекомендую прочитать эту статью о динамическом планировании движения (pdf). Это от робототехники, но довольно легко применить к вашей проблеме. Вы можете просто использовать роботы следующей точки сплайна в качестве цели и установить ее скорость на 0, чтобы применить этот подход. Однако, это может быть слишком много для вашей простой игры.

Обсуждение транспортных средств Брайтенберга можно найти здесь (pdf). Первоначальная идея была скорее техническим методом (двигателем в направлении или от источника света в зависимости от того, как ваш двигатель соединен с фоторецептором), и часто используется, чтобы показать, как мы применяем эмоциональные концепции, такие как страх и притяжение к другим объектам. Поведение "страха" - это подход, используемый для предотвращения препятствий в робототехнике.

Третий и, вероятно, самый простой способ: алгоритмы ошибок (pdf). У меня всегда есть проблемы с границей, которая немного сложна. Но чтобы избежать другого насекомого, эти алгоритмы - независимо от того, какой из них вы используете (я предлагаю Bug 1 или Tangent Bug), должны делать трюк. Они очень просты: двигайтесь в направлении своей цели (в этом приложении с помощью сплайнов с камуфляжем), пока у вас не будет препятствия впереди. Если препятствие близко, измените состояние насекомых на "предотвращение препятствий" и выполните свой алгоритм ошибок. Если вы дадите обе "сталкивающимся" насекомым одинаковое направление поворота, они автоматически перейдут друг к другу и будут следовать своему первоначальному пути.
В качестве варианта вы можете просто позволить им повернуть и пересчитать новый сплайн с этой точки.

Заключение

Поиск путей и генерация случайного пути - это разные вещи. Вы должны экспериментировать вокруг того, что лучше всего подходит для ваших насекомых. A * определенно предназначен для поиска кратчайших путей, а не для создания случайных путей и следования им.

Ответ 2

Посмотрите этот и this, который описывает AI программа для автоматического воспроизведения игры Mario.

Итак, в этой ссылке, что сделал автор, был использован алгоритм A * star для руководства Mario Get to the right border of the screen as fast as possible. Avoid being hurt.

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

Источник: http://www.quora.com/What-are-the-coolest-algorithms

Ответ 3

Вы не можете заранее планировать траектории на неопределенный срок!

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

Обязательно повторите проверку коллизий в случае, если вы создали еще более раннее столкновение!

Реальная задача в вашем случае - эффективно прогнозировать столкновения между многочисленными объектами, априорно задание O (N²). Вы ускорите это, наложив грубую сетку на поле воспроизведения и просмотрите объекты только в соседних ячейках.

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

Ответ 4

Для A * вам понадобится 2D-сетка, даже если она не видна. Если я правильно понял, вы могли бы сделать следующее.

Внедрить путь (например, A *), а затем просто создать случайные точки назначения на экране и рассчитать путь. Как только ваше насекомое достигнет места назначения, сгенерируйте другую точку назначения/ячейку сетки и продолжайте движение до тех пор, пока насекомое не умрет.

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

Примечание. Я однажды внедрил A *, позже узнал, что Ли Алгоритмв значительной степени делает то же самое, но проще реализовать.

Ответ 5

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

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

Вы всегда можете использовать узлы сетки как узловые точки для сплайна, чтобы сгладить движение, или даже случайным образом смещать все точки от своих строгих позиций 2d-сетки, пока не получите желаемое движение.

Пример цикла Гамильтона из Викимедиа:

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