Поиск пути в Java 2d-игре?

StackOverflow https://stackoverflow.com/questions/623095

Вопрос

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

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

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

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

Это было полезно?

Решение

Для хорошего алгоритма поиска пути, возможно, было бы неплохо использовать 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-х, вероятно, не будет использовать сложные алгоритмы поиска пути.

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

полное описание алгоритма есть на досье на Пакмана

с уважением

Гийом

Вы можете посмотреть на A * (звезда)

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

[править] Гах ... мозг слишком медленный ... забыл об этой книге, это C или C ++ (я забыл, какой), но вы все равно можете получить концепции для Java. Возможно, вам будет нелегко читать, но в целом неплохо. ИИ для разработчиков игр - Дэвид М. Бург, Гленн Симанн .

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top