Поиск пути в Java 2d Game?

Question

По сути, это игра-клон pacman, над которой я работаю. У меня есть класс Enemy и создано 4 экземпляра этого класса, каждый из которых представляет 4 призрака игры.

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

Нет лабиринта / препятствий (пока), поэтому вся карта (400x400 пикселей) открыта для них.

Для игрока и каждого Призрака я могу получить атрибуты X, Y, ширины и высоты изображения. Кроме того, у меня уже есть алгоритм обнаружения столкновений, так что не беспокойтесь об этом, просто о призраках, попадающих в pacman.

Answer 1

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

Например, решение заставить персонажа двигаться, в псевдокоде:

if (target is to the left of me):
    move(left);
else
    move(right);

if (target is above me):
    move(up);
else
    move(down);

Да, персонаж не собирается делать наиболее эффективное движение, но он будет становиться все ближе и ближе к цели на каждой итерации игрового цикла.

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

Answer 2

Если у вас просто сетка пикселей - «большое поле», по которому pacman и призрак могут свободно перемещаться - тогда самый короткий путь прост - прямая линия между призраком и pacman.

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

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

Итак, у вас есть это: ("*" = узел, "-, /, \, |" = край)

*-*-*
|\|/|
*-*-*  ... (etc)
|/|\|
*-*-* 

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

Что-то более близкое к реальности может быть следующим:

*-*-*
| | |
*-*-*  ... (etc)
| | |
*-*-* 

Теперь Пакман не может двигаться по диагонали. Для перехода из центра в правый нижний угол требуется 2 «прыжка», а не один.

Чтобы продолжить прогресс:

*-*-*-*
| | | |
| | | |
| | | |
*-*-*-*
| | | |
*-*-*-*

Теперь, чтобы перейти от узла посередине к узлу сверху, вам нужно 3 прыжка. Тем не менее, чтобы двигаться к дну, требуется всего 1 прыжок.

Было бы легко перевести любую настройку игрового поля в график. Каждое «пересечение» является узлом. Путь между двумя пересечениями является ребром, а длина этого пути - весом этого ребра.

Введите A *. Построив график (используйте матрицу смежности или список узлов), вы можете использовать алгоритм A *, чтобы найти кратчайший путь. Другие алгоритмы включают Дейкстры. И много других! Но сначала вам нужно сформулировать свою проблему в виде графика, а затем поиграть с тем, как бы вы перешли от узла A (pacman) к узлу B (ghost).

Надеюсь, это поможет!

Answer 3

Прошло очень много времени, но по памяти призраки в Pac-Man мало что сделали для поиска пути. Они делали довольно стандартный рандомизированный обход лабиринта, пока не «заметили» вас, что включало нахождение беспрепятственного пути вдоль оси коридора к вам, а затем они двигались бы прямо к вам, пока вы не исчезли с их поля зрения, после чего они возобновил бы случайный образец. На более высоких уровнях Pac-Man оставлял на некоторое время невидимые следы, чтобы призраки «пахли», а иногда и следовали.

Когда Pac-Man получил питание, единственное отличие в алгоритме состоит в том, что, когда они заметят вас, призраки будут бежать от вас, а не двигаться к вам.

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

Answer 4

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

Следующий урок - отличное руководство для начала работы с A * с загружаемыми примерами.

Поиск пути на картах на основе плиток

Answer 5

у Пакмана у всех призраков был другой алгоритм погони

• Blinky -> Погони. Обычно выбирают кратчайший маршрут и стремятся следовать.
• Пинки -> Засады. Имеет тенденцию идти более окольным путем к pac-man. Смертельный. (мизинец и блинки имеют тенденцию выбирать по-разному при выборе направления, часто загоняя игрока в угол)
• Inky -> Freak. Этот чувак ведет себя странно. Он передвигается по доске довольно случайно, но иногда гоняется, когда подходит близко.
• Клайд -> Идиот. Перемещается случайным образом. Не большая угроза.

У призраков есть запрограммированный в их движениях интересный паттерн: иногда они одновременно прекращают преследование Pac-Man и отказываются от него и возвращаются в свои соответствующие уголки лабиринта, переходя в «режим разброса».

есть полное описание алгоритма в досье pacman

привет

Гийом

Answer 6

Я думаю использовать алгоритм кратчайшего пути на каждом шаге, сделанном pacman. Очень хорошая реализация - алгоритм Дейкстры .

Просто подведу итог: визуализируйте лабиринт в виде графа с вершинами и ребрами. Каждое ребро имеет ожидание (в вашем случае все ребра имеют одинаковый вес). Алгоритм находит кратчайший путь от исходной до целевой вершины, перемещая один шаг вниз по каждому непосредственно достижимому ребру. Затем на следующей вершине вы делаете то же самое и продолжаете делать, пока не доберетесь до цели. Первый достигнутый путь - самый короткий путь. Для этого алгоритма может быть сделано много оптимизаций, чтобы ускорить такие вещи, как принятие во внимание, где pacman находился в своей предыдущей позиции и в каком направлении он двигался, чтобы вы могли получить некоторую наследственность в алгоритме. Я бы предложил находить кратчайший путь от каждого призрака до пакмана в каждом движении и перемещать призрака в этом направлении. Со временем расстояние уменьшится, и вы сможете поймать пакмана.

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

Answer 7

Вы могли бы начать глядя на A * (Звезда)

И вот страница , на которой есть ссылки на другие алгоритмы поиска пути.

[править] Гах ... мозг слишком медленный ... забыл об этой книге, это C или C ++ (я забыл, какой), но вы все равно можете получить концепции для Java. Возможно, вам будет нелегко читать, но в целом неплохо. AI для разработчиков игр. Автор: David M. Bourg, Glenn Seemann .