Как создать алгоритм трассировки пути для pacman?

Question

Im ученик средней школы, который создает игру в сет-мир Pacman. Как вы знаете, у pacman есть призраки, которые следуют за pacman и пытаются его достать. Однако мне не удается создать algortihm, который ищет самый быстрый маршрут к объекту Pacman, а затем берет этот маршрут. Я читал несколько блогов в Интернете, но я не нашел ничего полезного. У вас, ребята, есть идеи по поводу того, что призрачный трек пакмана?

Answer 1

Вы можете попробовать алгоритм A *, as described here.

В конце концов вы заметите, что призраки будут использовать в основном одни и те же маршруты. Проверьте серию книг по программированию AI Game Programming Wisdom на множество полезной информации.

Answer 2

Ahh .... Gridworld, я помню, как это было вчера. Подумайте об этом, это было ...: |

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

Хотел бы я помочь больше, но это все, о чем я могу думать прямо сейчас.

Answer 3

Немного сложно предоставить полный ответ здесь ... но посмотрите на «Анти-объекты». Есть статья Александра Репеннинга (Университет Колорадо). Это не-ООП-моделирование рассматривает местоположение человека в том, что обычно описывается как аналогичное запаху.

Answer 4

Чтобы найти кратчайший путь стоимости я бы порекомендовал реализации что-то вроде алгоритмов Дейкстры или алгоритма Флойда (это выгоды будут нарастающие фронты затрат!)

http://en.wikipedia.org/wiki/Dijkstra «s_algorithm http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm