__________________________________________ Теория AI (c)SpoozE/oHg/XXL Здрасте всем! Сразу о главном. В этой статье я расскажу Вам о реализации искуственного интеллекта (далее - AI), в масштабах нашего с вами SPECCY. Для начала в общих чертах, что же такое AI и к чему надо стремиться при его написании. К разработке AI надо подходить весьма внимательно, так как каждая задача требует узко специализированного и "подогнанного" алгоритма ее решения. В связи с этим, я буду поэтапно описывать создание AI для широко известной игры "BATTLE CITY". Итак, самым первым нашим шагом будет оценка тре- буемых действий от AI-объектов ( далее - боты). В нашем случае требуется, чтобы та- нки: ездили просто так,охраняли базу,напа- дали на базу противника, ошибались. Хм, возможно некоторых смутил последний пункт, но ошибки в действиях ботов очень важны, мы ведь хотим создать реалистичную модель поведения. Если в игровой ситуации все танки устремятся к вражеской базе, то это будет выглядеть мягко говоря не очень реалистично, да и геймплей от этого изме- нится далеко не в лучшую сторону, так что пока оставим полный поиск пути и поговорим о хаотическом движении. Самое простое - конечно же просто случай- ным образом выбирать направление через какие-то промежутки времени, но смотрется это будет не совсем так, как нам нужно. Мне на момент разработки показалось целе- сообразным ввести для каждого танка счет- чик смены направления и типа движения. Про смену типа движения расскажу немного позже, а сейчас про смену направления. Как это работает? В счетчик ложим случайное число - количество ходов до смены направ- ления (диапозон зависит от масштабов кар- ты, но можно ввести зависимость от модели поведения ). Затем каждый тик (интервал времени, за который обрабатывается игровая ситуация),мы уменьшаем счетчик на единицу, и если он равен нулю, то опять обновляем направление и счетчик. Также счетчик сле- дует обнулять при неудачной попытке сделать ход (например танк столкнулся с другим танком или со стеной).Таким образом мы достигли достаточно реалистичного дви- жения "наугад". Но, увы, в данном случае вероятность достижения танком определенных позиций зависит от пространственной конфи- гурации блоков и может быть очень мала. Как видно на рисунке -вероятность того, что танк пройдет в дыру в стене близка к нулю. В таких случаях для экономии аппаратных ресурсов, вместо тру- доемких рассчетов выгоднее использовать так называемые чекпойнты ( от англ. Checkpoint - точка проверки). В моей реа- лизации чекпойнты представляют собой мас- сив таких же блоков, как и уровень, только блоки имеют значения смены направления и еще несколько свойств. Таким образом каж- дый тик идет проверка танков,на чекпойнты, если танк находится на позиции с чекпойн- том, то идет несколько дополнительных про- верок ( чекпойнты могут быть например только для красных танков ), и в случае успеха танк принимает направление, которое соответствует чекпойнту. Немного забегая вперед, хочу отметить тот факт, что в со- ответствии с поставленной целью у нас должно быть несколько моделей поведения танков. Я обозначил две - атакующие и обо- роняющиеся. Атакующие стремятся к базе противника, используя волновой алгоритм поиска пути (о котором ниже), а обороняю- щиеся просто разъезжают по карте. В связи с этим чекпойнты различаются по модели поведения танков, которые будут по этим чекпойнтам ездить. Например чекпойнт может быть только для команды красных и только для атакующих танков (можно придумать свои критерии дифференцирования ). Итак нам нужно реализовать полный алгоритм поиска пути. Самый простой способ - волновой алгоритм. Реализуется он элементарно, по следующему алгоритму: 1. Начальная точка - пункт назначения бота, в нашем случае - база противника. 2. Разбиваем поле на условные квадраты, целесообразно будет разбить на те же раз- меры, что и блоки и чекпойнты. 3. Забиваем клетки с "непроезжими" бло- ками например #FF 4. Присваиваем клетке с координатами цели значение ноль. 5. Всем пустым и "проезжим" клеткам вокруг нее присваиваем значение на единицу больше. 6. Обрабатываем каждую из помеченных клеток аналогично. В случае с танками мы сформировали два поля AI - для красной и для синей базы. Теперь чтоб пройти по кратчайшему пути к объекту, надо всего лишь двигаться в ту клетку, где значение меньше. Легче всего идентифицировать движение по этому алгоритму, как пятое направление и выбирать его так же как и вверх, вниз, влево и вправо, но только для нападающих танков. То есть при нулевом счетчике, у нападающего танка есть возможность выбора движения по кратчайшему пути к вражеской базе. Но как только счетчик становится равен нулю,танк может поехать и по обычно- му направлению,что ведет к реалистичности. Также стоит учесть, что движение по волно- вому алгоритму приоритетней, чем движение по чекпойнту и при "наступлении" на чекпойнт проверять, не движется ли танк по пятому направлению. Фух. На сегодня я, пожалуй, закончу, но даже и не надейтесь отвязаться ;) 2 b cont...