Добрый вечер!
Начал я тут недавно создавать (опять) игру свою (2D, с видом сверху, стрелялка). Работает всё отлично. Присутствует редактор карт, ГГ уже и анимирован, и стрелять умеет, и ходить… НО! Столкнулся с большой проблемой! Забыл про AI… когда начал программировать, столкнулся с большой проблемой… противники не могут найти и дойти до ГГ! Была ошибка в алгоритме нахождения пути. Противники, то тупо останавливались, то упирались в стены. Мучился долго. Потом со злости, что ничего не получилось, снёс ИИ к чёрту, а в мести и с ИИ пол кода программы (не заметил…немного…). Теперь восстанавливаю.
Помогите, кто может! Я, конечно, понимаю, что это сложнейший алгоритм, но хотя бы подтолкните меня на это, пожалуйста!

SWF- ролик. Описание:
Белый квадрат – пусто (Значение 0)
Коричневый квадрат – стена (Значение 1)
Зелёный – враг (Значение 4)
Жёлтый – ГГ (значение 10)
Зелёная линия – правильный путь противника
Коричневый – неправильный

Заранее благодарю!

C++, Perl

Посмотрел? Есть идеи, как это реализовать? Я даже не знаю с чего отталкиваться...
Хотя нет, я думаю, можно реализовать с помощью ОЧЕНЬ большого количества If.

Ну вот я о том же...
Хотя можно с помошью For...

С помощь IF у меня ни чё не получилось!

Вообще алгоритм нахождения кратчайшего пути базируется на том, что нужен двумерный массив и в первую клетку заносится 1, затем а каждую точку рядом с начальной заносится 2, кроме той, что содержит 1, затем в следующие рядом с теми что содеражат 2, заносится 3, но при условии что там 0, но не 1 или 2 и .т.д. И так до тех пор пока не дойдешь до конечной точки. А тогда остается лишь пройтись по точкам со значениями 1,2,3,4,N и вот тебе кратчайший путь...

Имеется ввиду ставить числа в клетки связанные с текущей. Сначала ставишь единицу (она всего одна в начальной клетке), потом просматриваешь 8 клеток вокруг и ставишь 2 в те с которымы есть связь (может и 4 а не 8, смотря какой у тебя лабиринт), там где стены - там не надо ставить ничего (должен 0 остаться)... потом просматриваешь двойки и ставишь 3 в те клетки с которыми связь есть, но там не туда где 1 или 2 и т.д.
Этот алгоритм придумали в 198х затертом году он называется "волновой алгоритм поиска пути", и дает 100% результат, если конечно вообще путь есть...

а может кто-нибудь на словах объяснить как вообще работает такой алгоритм? и лично ничего придумать не могу =\

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

спасиб .. почитаю

Дай ссылку на статью

А в чем проблема? Я же в принципе описал как делать.

Единствено забыл указать ньанс:

• когда все клетки заполнены, нужно начинать просмотр с КОНЕЧНОЙ точки в порядке уменьшения цифр: N,N-1,N-2, ..., 1 В принципе не важно какую выбирать клетку если цифры в них одинаковы, все равно путь будет длины N клеток.