Pac-man - классическая игра. Кто не помнит в ней некий смайлик бегает по лабиринту и ест некие плюшки. При этом уворачивается от двух-четырек привидений, тупо его преследующих. Задача - слопать все плюшки. Простенько и со вкусом.

Смайликом управляет игрок. Приведения используют алгоритм A* (как правило) для того, чтобы направляться в сторону смайлика. Впрочем, могут быть и варианты проще.

Мне же нужен алгоритм не самой игры, а демо к ней. Т.е. вариант, в котором смайлик тоже управляется компьютером. Т.е. смайлик направляется по лабиринту в сторону не съеденных еще плюшек, но одновременно и убегает от привидений.

Не подскажет ли кто-нибудь алгоритм хорошо расписанный? Честно говоря не хочется велосипед городить. Если гуглю - все время вылезают описания алгоритма самой игры, т.е. движения привидений.

Спасибо.

а почему нельзя использовать алгоритм движения приведений применимо к смайлику? Пусть он случайно выбирает точку и движется к ней, съедая всё на своём пути (точка будет выступать в роли смайлика, на которого охотится приведение), а приведения пусть считает за стенки лабиринта.

Bitter, пожалуй приведения его сразу слопают. 

Здесь скорее надо выбирать некое среднее между привлекательностью плюшек и страхом привидений. При этом и страх и привлекательность, видимо, должны слабеть с расстоянием. Но это тоже туповато. И, главное, требует многих экспериментов с параметрами.

Вот я и думаю - надо ли самому изобретать то, что другие уже раз восемьсот изобрели?

Так а что мешает сделать тот же A*, только снабдить приведения очень большой стоимостью? Как вариант (чтобы смайлик не пытался пробегать под носом у приведений), места, находящиеся на некотором небольшом расстоянии от приведений (на графе лабиринта, конечно), также снабжаются большой стоимостью, растущей по мере приближения к приведению.

Фантом, хорошо. Пусть будет так. Хотя это опять ведет к экспериментам с параметрами. А как задать привлекательность множества плюшек?

Так ведь искать-то надо маршрут к чему-то. Вот и ищите маршруты ко всем плюшкам, потом выбирайте самый дешевый.

Наверное это будет иногда приводить к маятниковым движениям смайлика. Впрочем - с этого наверное можно начинать. А там видно будет 

Потом отпишу что получилось. Единственно, это "потом" может сильно затянуться. Проект этот у меня почти последний в списке срочности испольнения.

Спасибо!

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

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

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

_Y_, а почему бы не просчитывать "ходы" привидений на несколько ходов? Разбить все возможные варианты действий пакмена на элементарные предвижения - стоять-вверх-вниз-вбок на какой-то квант времени. Алгоритм движения привидений достаточно однообразен, так что особого разветвления дерева выбора не должно быть, глубина перебора должна быть достаточно приличной. 
В качестве функции оценки можно использовать количество заработанных очков. При достаточной глубине перебора будет в меру эффективно.

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

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

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

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

Это сообщение отредактировал(а) миг - 11.1.2011, 23:00