pathfinder

Введение

Лабиринты и карты используются в играх постоянно — аудио игры не исключение.
Если вам доводилось играть в сайдскроллер, там вы перемещались по полю в четырёх направлениях: вправо, влево, вверх, вниз.
Другое дело — шутер от первого лица.
Здесь курсорные клавиши верх и вниз позволяют двигаться вперёд и назад, а стрелки вправо-влево — поворачиваться в стороны.
В обоих случаях мы имеем дело с двумерной картой, где положение игрока и предметов задаются двумя координатами по осям x и y.
В сайдскроллере значение x увеличивается при движении вправо, а y – при движении вверх.
Принято говорить, что ось x указывает вправо, а y — вверх.
В шутере от первого лица ось x указывает на восток, ось y — на север.
Если игра строится на исследовании карты, одной из важных игровых задач становится перемещение.
Игрок слушает, где находится объект, поворачивается и идет в выбранном направлении, наталкивается на препятствие, пробует другой маршрут и так далее.
Но как при разработке игры заставить объекты, управляемые компьютером, двигаться самостоятельно по тому же принципу?
Допустим, вражеские роботы должны преследовать игрока, умело обходя бассейны с кислотой на пути.
Или мы хотим, чтобы крестьяне в игре занимались своими повседневными делами, не натыкаясь на стены.
И даже если что-то на карте меняется, мы хотим, чтобы её обитатели умели сами корректировать свой курс.

Как работает определитель пути?

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

Указываем размер карты

Прежде, чем определитель пути заработает, ему нужно знать размер игровой карты.
Задать размер можно методом create_map, как в следующем примере:
void main()
{
pathfinder holmes;
holmes.create_map(10, 5);
/ / Ещё какой-то код
}
Теперь определитель пути знает, что ширина вашей карты 10 клеток, а высота — 5.
Другими словами, при движении по карте координата x может меняться в диапазоне от 0 до 9, а координата Y — в диапазоне от 0 до 4.

Задаём функцию обратного вызова

Если вы новичок в BGT или мало знакомы с программированием, вы могли не встречаться раньше с термином функция обратного вызова.
Для вас — небольшое пояснение.
Представьте ситуацию:
вы в офисе и знаете, что по приходе домой у вас будет всего двадцать минут, чтобы успеть на поезд.
Вы звоните домой и просите кого-то из домашних собрать вам чемодан.
Через пять минут вам перезванивают из дома и спрашивают, хотите вы взять с собой черный или красный галстук.
Вы отвечаете: красный.
Еще через десять минут вам снова перезванивают с вопросом, будете ли вы есть перед дорогой.
Вы отвечаете, что, вероятно, на еду не хватит времени.
Еще двадцать минут спустя вам перезванивают, чтобы спросить, как долго вы будете отсутствовать.
Теперь переведём всё это в терминологию программирования.
Позвонить домой с просьбой собрать вам чемодан — значит вызвать метод под названием, например, pack_my_suitcase (собери_мне_чемодан) для объекта класса family_member (член_семьи).
Вот как это работает:
void main ()
{
family_member babushka;
babushka.pack_my_suitcase ();. / / Невежливо, но по существу
}
Далее, чтобы выполнить вашу просьбу, бабушке потребуется дополнительная информация.
Напишем функцию, которая ответит на все вопросы за нас:
string my_callback(string inquiry)
{
if(vopros == "Цвет галстука?")
{
return "Красный.";
}
else if(vopros == "Приготовить еду?")
{
return "Nope.";
}
else if(inquiry == "Надолго едешь?")
{
return "Три дня.";
}
else // Задан другой, неожиданный вопрос.
{
return "Не важно.";
}
}
Теперь давайте изменим главную функцию, чтобы рассказать бабушке о функции обратного вызова, к которой та сможет обращаться при необходимости.
void main()
{
family_member babushka;
babushka.set_callback_function(my_callback);
babushka.pack_my_suitcase(); // Невежливо, но по существу
}
Так же, как в реальной жизненной ситуации, бабушка будет обращаться к функции my_callback неоднократно, пока не соберёт всю необходимую информацию.
Обратите внимание:
мы никогда не вызываем my_callback непосредственно, мы лишь указываем, куда обращаться, если возникнут вопросы.
Оставляя функцию обратного вызова, мы словно оставляем номер телефона, по которому можно уточнить информацию.
Мы не звоним на свой номер сами, нам звонят другие, если считают нужным.
Пора применить новые знания к объекту pathfinder.
Пока мы передали ему только размер нашей карты.
Если теперь попросить его проложить маршрут между двумя точками, он не справится без уточняющих вопросов, поскольку не знает о нашей карте ничего, кроме её размера.
Например, он понятия не имеет, как расположены стены, преграждающие путь, где находятся двери, которые, возможно, необходимо открыть.
И есть ли вокруг бассейны с кислотой, которые делают перемещение в нужную точку опасным, а то и невозможным.
Короче говоря, нам нужна функция обратного вызова, которая сообщит определителю пути, трудно ли будет попасть с одной клетки на соседнюю.
Определитель пути всегда будет выбирать наиболее простой маршрут, собирая информацию о препятствиях по мере продвижения.
Давайте посмотрим, как может выглядеть наша функция обратного вызова:
int maze_callback(int x, int y, int parent_x, int parent_y, string user_data)
{
if(maze[x][y]==1)
{
return 10;
}
return 0;
}
Определитель пути вызывает эту функцию, чтобы уточнить, насколько трудно добраться до клетки с координатами x и y.
Кроме того, он уточняет координаты исходной клетки, с которой мы перемещаемся, обозначая их как parent_x и parent_y.
Это особенно удобно, когда попасть на некоторые клетки с одного направления проще, чем с другого.
Например, если у вас на карте есть односторонняя дверь, через которую можно пройти только слева-направо, но невозможно в обратном направлении.
Ещё пример:
кирпич легко летит вниз, но с трудом поднимается вверх.
Наконец, наша функция обратного вызова получает строковую переменную под названием user_data, и скоро мы увидим, зачем это нужно.
Какой результат возвращает наша функция обратного вызова?
Об этом мы уже намекали парой абзацев выше, когда сказали, что функция показывает, насколько трудно перебраться с одной клетки на соседнюю.
Эта трудность, которую ещё называют стоимостью или риском, — всего лишь числовая переменная со значением в диапазоне от 0 до 10.
Если значение 0, перемещение не несёт никакого риска и ничего не стоит, в то время как значение 10 указывает на невозможность перемещения в выбранном направлении.
Например, мы не сможем ходить через стены, если только наш персонаж не призрак и не Чак Норрис.
Итак, 0 означает, что путь свободен, а 10, — что «хода нет».
Конечно, не все участки маршрута будут одинаково легко проходимы:
у некоторых стоимость прохождения будет больше 0, но меньше 10.
Например, трудность прохождения клеток на мелководье можно установить равной двум.
На клетках глубокого водоёма значение может достигать шести.
Для клеток, где горит огонь, разумно установить трудность 9.
В нашем примере функция обратного вызова пока просто обращается к массиву с именем maze (в переводе — лабиринт), чтобы увидеть, есть ли стена на интересующей нас клетке.
Если да, функция возвращает число 10, указывая, что переход невозможен.
В противном случае она возвращает 0, указывая, что путь свободен.
Конечно, мы должны сообщить объекту pathfinder о нашей функции обратного вызова.
Сделать это можно следующим образом:
void main()
{
pathfinder holmes; //назвали наш объект Холмсом, ведь он выступит в роли следопыта.
holmes.create_map(10, 5);//сообщили Холмсу размеры карты
holmes.set_callback_function(maze_callback);//назначили функцию обратного вызова
// Здесь будет ещё какой-то код.
holmes.destroy_map();// Приказали Холмсу забыть данные о карте.
// Возможно, здесь будет ещё какой-то код, где не требуется определение пути.
}
Как видите, мы указываем определителю пути на функцию обратного вызова с помощью метода set_callback_function.
Этот метод имеет только один параметр — имя функции обратного вызова.
В нашем случае это maze_callback.
Если Вам интересно, как мы передали функцию другой функции, найдите в справочнике по языку BGT ключевое слово funcdef.
Отметим, что это совершенно не обязательно:
вы не обязаны знать, как это работает, чтобы этим пользоваться.
В этом преимущество удобных языков программирования.
В приведенном выше коде мы использовали еще один метод под названием destroy_map.
Он высвобождает память, которую объект pathfinder использует для вычисления пути.
Поэтому, если pathfinder временно не нужен, стоит вызвать метод destroy_map, а затем, когда поиск пути снова понадобится — вызвать create_map еще раз.
Для тех, кому интересны технические подробности:
память также высвобождается при уничтожении объекта pathfinder.
Если вы не уловили смысл предыдущего предложения — не обращайте внимания.
Создание и удаление объектов очень подробно освещаются в руководстве по языку BGT.

Собираем всё воедино

Теперь, когда мы знаем теорию, пора использовать определение пути для реальных задач.
Самое время вам просмотреть пример исходного кода из главы, посвящённой объекту pathfinder в справочнике по BGT.
Возможно, вы захотите скопировать и сохранить код в отдельный файл, чтобы экспериментировать с ним по ходу чтения.
Попробуйте внимательно прочесть код сверху вниз и найти компоненты, которые вам уже знакомы.
Видите ли вы, где в коде создается объект pathfinder и указывается размер карты?
Можете ли найти функцию обратного вызова: где она объявлена и где передана объекту pathfinder?
Код снабжён подробным комментарием, так что проблем с пониманием возникнуть не должно.
Систему, созданную в этом примере, можно назвать проводник по лабиринтам.
Сначала вы можете ходить по сетке с помощью курсорных клавиш, размещая и удаляя стены на пути.
Затем вы указываете своё текущее местонахождение, выбираете место назначения и позволяете проводнику показать, на что он способен.
Далее вы услышите перечень направлений от исходной клетки до места назначения.
Жаль, что ничего подобного не было предусмотрено в игре Zork.
Давайте посмотрим, где в коде определитель пути (наш pathfinder по имени Холмс) получает команду проложить для нас маршрут.
vector[] path=holmes.find(start_x, start_y, x, y, "");
Метод find принимает в качестве аргументов начальные координаты, координаты назначения, а также пустую текстовую строку — значение переменной user_data.
Пока строка в примере не используется, поэтому остается пустой.
А вообще её текст будет передаваться функции обратного вызова с параметром user_data.
Это бывает полезно, когда нужно, чтобы функция обратного вызова по-разному реагировала на полученные данные и, в частности, на причину, по которой нам нужно искать путь.
Метод find возвращает массив векторов.
Для определителя пути, вектор — это пара x и y координат, то есть точка на карте.
Таким образом, элементы массива составляют маршрут путешествия от начальной точки до места назначения.
Если путь проложить не удаётся, метод find выдаст на выходе пустой массив.

Упражнения

1. Отредактируйте код примера так, чтобы пользователь мог разместить на карте бассейны с кислотой.
Ходить по кислоте в принципе можно, но неприятно, поэтому проводник должен свести контакт с ней к минимуму.
2. Теперь давайте добавим еще один вид опасности.
Измените пример таким образом, что пользователь мог разместить лужи воды в произвольных местах на карте.
Такие лужи куда менее опасны, чем бассейны с кислотой, но проводник должен по возможности избегать их.
Конечно же, недопустимо для обхода лужи идти по кислоте.
3. Можете ли вы изменить функцию обратного вызова, так, чтобы идти на восток было сложнее, чем на запад, а двигаться на север было гораздо сложнее, чем на юг?
4. Можете ли вы сделать ограничения, созданные в упражнении 3, опциональными, по-прежнему используя только одну функцию обратного вызова?
5. Сделайте так, чтобы призрак мог проходить сквозь стены, но только при движении на восток.
6. Можете ли вы теперь создать врага, который преследовал бы игрока в шутере от первого лица?
Как обеспечить врага интеллектом, чтобы тот менял свой курс вслед за игроком?
7. Найдите в руководстве параметр desperation_factor объекта pathfinder.
Понимаете ли вы теперь принцип его работы?
Рассмотрите пример, где враги ведут себя все более отчаянно по мере того, как игрок приближается к концу уровня.
Какие ещё ситуации с нарастанием отчаянности врагов можно придумать?

Содержание

Оцените материал

0 0

Поделитесь с друзьями