Прокладывание маршрута для персонажа из точки А в точку Б является одной из задач, которые приходится решать разработчику компьютерных игр. Разрабатываете ли вы тактическую пошаговую стратегию, RPG или просто игру-головоломку, перемещение по игровому миру требует от ваших подопечных ума и сообразительности чтобы не ломиться тупо по прямой к указанной цели и застревать в препятствиях.
Алгоритм поиска пути является основным кирпичиком, необходимым для создания A.I. (искусственный интеллект). и, с помощью различных заплаток, методом проб и ошибок, вы сможете сделать ваших персошажей чуточку умнее. Чтобы добраться до своей цели им, возможно, придется прогуляться через препятствия, найти свой путь в подземных лабиринтах или на улицах города. Но этого не достаточно и, в конечном итоге, они прибудут в пункт назначения каким-нибудь удручающе кружным путем, хотя маршрут должен быть максимально коротким.
Решение этой проблемы не является тривиальной задачей, но это стоит усилий. Пользователи, играющие в вашу игру, поймут, что юниты действуют разумно и смогут сосредоточиться на стратегии и тактике не няньчась с тупым AI.
Стандартный метод, который используется в большинстве игр называется A*, или "A-Star".
Происхождение алгоритма поиска пути
В пятидесятые годы математик Эдсгер Дейкстра разработал метод для расчета оптимальных маршрутов, которые могут быть применены к любой гипотетической ситуации, требующей автоматизированный выбор между многими возможными шагами.
Он часто используется в примере грузовиков, идущих из одного места до другого. Выбор наиболее короткого маршрута приведет к большей прибыли.
Приведенная выше анимация является типичным примером работы этого алгоритма. Обратите внимание, что каждый узел установлен на игровом поле хаотично. Это идеальный пример того, что мы хотим сделать: мы складываем «издержки» каждого маршрута чтобы найти самый невыгодный маршрут.
Если вы смотрите на приведенный выше анимированный рисунок, вы увидите, что каждый раз, когда мы приходим к новому узлу, мы складываем расходы и, таким образом, находим наиболее затратный.
Проблема с алгоритмом Дейкстра
Алгоритм Дейкстра прекрасно работает, но имеет недостаток - он не использует никаких эвристических методов для выбора наиболее вероятных кандидатов, поэтому решение известно только после того, как будет проверены все варианты.
В приведенном выше анимированном изображении вы можете увидеть, что каждая "клетка" или "узел" проходит проверку. В конечном итоге, мы получаем требуемый результат, но программист, живущий в вас, наверняка, думает, "нужна оптимизация!"
Алгоритм A-star спешит на помощь!
A-star является более быстрым и эффективным вариантом алгоритма Дейкстра. Он находит наилучший путь от одного узла к другому узлу.
Иными словами, A-star пересекает узел графа (набор точек в пространстве, соединенных между собой) и находит путь, который менее затратен (самый короткий) не исследуя при этом все узлы графа. В случае с видеоигрой узлом графа является игровой мир, та карта, по которой перемещаются наши юниты.
В приведенном выше анимированном изображении показан тот же игровой мир, что бы рассмотрен для алгоритма Дейкстра, но на этот раз мы видим, что проверяется меньшее количество узлов. В результате наша функция поиска оптимального маршрута работает быстрее, а это очень важно в играх!
Всегда есть место для оптимизации
Чем более оптимизирован этот алгоритм, тем чаще мы можем наверняка угадать с оптимальным направлением, не вдаваясь в подробные расчеты. Приписывая значение узлам, пройденным на нашем пути, мы можем предсказать, в каком направлении двигаться дальше.
Под этим я подразумеваю, что с помощью более тонкого анализа мы можем предсказать в каком направлении лучше всего двигаться и попробовать его в первую очередь.
В приведенном выше анимированном изображении мы видим очень эффективный пример звездочного алгоритма, который пытается угадать оптимальный маршрут вместо начинать с нуля каждый раз, когда движение заблокировано. Более сложная геометрия все только запутает, но в общей сложности вам должно быть понятно, что выгодно придерживаться этого способа.
Это именно то, что требуется враждебному AI в большинстве игр: найти кратчайший маршрут из точки А в точку Б и как можно быстрее!
Не пугайтесь всей этой математики!
Прежде чем с головой нырнуть в захватывающий мир алгоритмов или (что еще хуже) разбить компьютер в приступе бешенства, вызванном безграничностью его математических возможностей, успокойте себя мыслью о том, что совсем скоро вы узнаете о функциях, которые сделают всю работу за вас.
Они пересекут граф (список древовидной структуры данных, являющийся картой вашего игрового мира) и добавят затратности (в форме пройденного расстояния) многим возможным маршрутам. Наименее затратный маршрут будет кратчайшим путем из точки А в точку В.
Функция, о которой я собираюсь рассказать, просто поможет нам определить массив координат x и y, являющийся кратчайшим путем к месту назначения. Звучит просто, не так ли?
Наглядная демонстрация
Перед тем, как написать алгоритм поиска пути, мы должны получить наглядное представление о нашем игровом мире. Ваш мир может быть гораздо сложнее представленного здесь, но, если вы используете HTML5 Canvas для создания своей игры, вам будет легко его модифицировать.
Мы постараемся сделать все как можно проще и создадим самый примитивный случайный мир, применив список спрайтов к холсту HTML5.
Спрайты
По этой упрощенной демонстрации работы игрового алгоритма, нам нужно всего несколько изображений. Вместо нескольких крошечных файлов, все они объединены в один, для ускорения загрузки. Нам нужна плитка со свободными участками (трава), плитка с заблокированными областями (валуны) и плитки, обозначающие начало, конец пути и траекторию движения.
Вот пример спрайта, с помощью которого будет нарисован наш игровой мир:
HTML файл
Начнем с кодирования! Для начала мы создадим базовую страницу HTML5, которое не содержит ничего, кроме этикетки, холста, и кнопку, которая будет генерировать новый случайный мир. Проще некуда.
<!doctype html>
<html>
<title>A-STAR алгоритм поиска пути для HTML5 Canvas</title>
<style>
body { padding:0; margin:0; height:100%; width:100%; }
div { font-family:arial; font-size:16px; font-weight:bold; text-align:center; }
</style>
<script type='text/javascript' src='astar-pathfinding-canvas.js'></script>
</head>
<body onload='onload()'>
<section>
<header>
Генератор игрового мира
</header>
<input type='button' onClick='createWorld()' value='New World'>
<canvas id="gameCanvas"></canvas>
</section>
</body>
</html>
Файл Javascript
Вот и все, что нам нужно в HTML файле. Остальная часть этого урока проходит в написании JavaScript. В файле, который мы назовем astar-pathfinding-canvas.js
, напишем следующее:
// элемент игры - холст
var canvas = null;
// определяет тип контекста - 2d
var ctx = null;
// изображение со спрайтами
var spritesheet = null;
// true когда спрайт загрузится
var spritesheetLoaded = false;
// массив для игрового мира
var world = ;
// размер игрового мира (16 плиток)
var worldWidth = 16;
var worldHeight = 16;
// Размер плитки в пикселях
var tileWidth = 32;
var tileHeight = 32;
// начало и конец пути
var pathStart = [worldWidth,worldHeight];
var pathEnd = [0,0];
var currentPath = [];
// проверяем есть ли ошибки
if (typeof console == "undefined") var console = { log: function() {} };
В приведенном выше коде мы определяем переменные, необходимые для хранения данных для нашего игрового мира и ссылки на наш холст. Переменная world - двумерный массив (массив заполняется с массивами).
Таким образом, вы можете хранить данные в виде world[x][y]=значение;
, где значение - индекс плитки используемой в данном месте.
Мы также определяем размер нашего мира и данные маршрута, которые будут меняться в ходе демонстрации A-star.
Наконец, мы добавляем чуть-чуть кода для проверки поддерживает ли данный браузер консоль для отладки. В случае успешной проверки, мы сможем добавлять отладочные записи журнала, которые выводятся во время выполнения программы.
Следующий шаг состоит в обработке содержимого функции onload()
как только страница будет загружена.
Запуск
// Когда html страница загружена
function onload()
{
console.log('Страница загружена.');
canvas = document.getElementById('gameCanvas');
canvas.width = worldWidth * tileWidth;
canvas.height = worldHeight * tileHeight;
canvas.addEventListener("click", canvasClick, false);
ctx = canvas.getContext("2d");
spritesheet = new Image();
spritesheet.src = 'spritesheet.png';
spritesheet.onload = loaded;
}
Функция onload()
подхватает ссылку на холст в нашем HTML файле, делает его равным нашему игровому миру, и начинает отлавливать щелчки мыши на холсте. Мы также загрузили наш файл со спрайтами spritesheet.png
. Следующим шагом является создание навигации в нашем сказочном мире.
// файл с картинками загружен
function loaded()
{
console.log('Спрайты загружены.');
spritesheetLoaded = true;
createWorld();
}
// генерация ландшафта
function createWorld()
{
console.log('Создание мира...');
// создать пустоши
for (var x=0; x < worldWidth; x++)
{
world[x] = [];
for (var y=0; y < worldHeight; y++)
{
world[x][y] = 0;
}
}
// расставляем скалы случайным образом
for (var x=0; x < worldWidth; x++)
{
for (var y=0; y < worldHeight; y++)
{
if (Math.random() > 0.75)
world[x][y] = 1;
}
}
// рассчитать первоначальный возможный путь
// зы: маловероятно, но возможно, мы его не найдем))...
currentPath = [];
while (currentPath.length == 0)
{
pathStart = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];
pathEnd = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];
if (world[pathStart[0]][pathStart[1]] == 0)
currentPath = findPath(world,pathStart,pathEnd,'Manhattan');
}
redraw();
}
В приведенном выше коде запускалась функция обратного вызова в функции onload()
когда spritesheet.png
был загружен и готов к использованию. После этого мы сразу же приступали к созданию нашего игрового мира, запустив функцию createWorld
.
Первоначально для каждой системы координат х и у координат мы установили значение массива world
равным нулю (нулевому значению соответствует трава).
После того, как мы создаем бескрайние равнины, мы расставляем несколько валунов случайным образом, чтобы создать препятствия для нашего бесстрашного искателя приключений.
Наконец, выберем две случайные места на карте, соответствующие начальной и конечной точки маршрута, и рассчитаем алгоритм A-star, который очень скоро увидим в действии. Если маршрут недоступен, мы будем пробовать другие, пока не получим хорошую начальную конфигурацию.
Усовершенствованный генератор ландшафта
Естественно, вы можете разработать гораздо более интересный генератор ландшафта, чем этот. Вы можете использовать шум Перлина или Генератор псевдослучайных чисел для детерминировонного ландшафта с использованием случайных значений.
Вместо того, чтобы случайно расставлять предметы вокруг, вы могли бы использовать клеточные автоматы (cellular automata) для создания ячеек одинаковой местности, чтобы деревья складывались в лес, а скалы и просеки – в горы и долины.
Это невероятно увлекательно и, если вы хотите поупражняться в искусстве создания случайных ландшафтов, изучение таких аспектов, как генератор подземелий roguelike, процедурный ландшафт и создание случайных карт откроет перед вами поистине неограниченные возможности.
Отображение игрового мира
Следующим шагом, после того как мы заполнили массив world
, нужно вывести его содержание на экран.
function redraw()
{
if (!spritesheetLoaded) return;
console.log('redrawing...');
var spriteNum = 0;
// очистить экран
ctx.fillStyle = '#000000';
ctx.fillRect(0, 0, canvas.width, canvas.height);
for (var x=0; x < worldWidth; x++)
{
for (var y=0; y < worldHeight; y++)
{
// выбираем область спрайта для рисования
switch(world[x][y])
{
case 1:
spriteNum = 1;
break;
default:
spriteNum = 0;
break;
}
// рисуем с помощью:
// ctx.drawImage(img,sx,sy,swidth,sheight,x,y,width,height);
ctx.drawImage(spritesheet,
spriteNum*tileWidth, 0,
tileWidth, tileHeight,
x*tileWidth, y*tileHeight,
tileWidth, tileHeight);
}
}
// рисуем маршрут
console.log('Длима текущего маршрута: '+currentPath.length);
for (rp=0; rp<currentPath.length; rp++)
{
switch(rp)
{
case 0:
spriteNum = 2; // начало пути
break;
case currentPath.length-1:
spriteNum = 3; // конец пути
break;
default:
spriteNum = 4; // маршрут
break;
}
ctx.drawImage(spritesheet,
spriteNum*tileWidth, 0,
tileWidth, tileHeight,
currentPath[rp][0]*tileWidth,
currentPath[rp][1]*tileHeight,
tileWidth, tileHeight);
}
}
В приведенном выше коде мы просто перебираем массив world
и используем 2d функцию DrawImage для рисования на холсте путем копирования пикселей из нашего спрайта.
Следующий шаг – создать маршрут, нарисовав дополнительные спрайты для каждой координаты x и y, хранящихся в массиве currentPath, который мы вычислили перед этим.
Наш мир на данном этапе
Вот то, что мы с вами сделали - упрощенный генератор местности. Трава, по которой ваши персонажи могут ходить, и большие валуны, которые встретятся им на пути. Это хороший пример для демонстрации работы поиска оптимального пути.
Нажмите кнопку New World несколько раз, чтобы увидеть наш генератор местности в действии. Заметьте, что в примере выше прокомментирован код, использованный для A-star, поэтому здесь не может быть никаких ошибок, касающихся отсутствия нижеперечисленных функций.
Взаимодействие с пользователем
Теперь, когда у нас есть игровой мир, мы должны добавить некоторую интерактивность. Нам нужно отслеживать событие щелчка мыши по плитке на холсте. Для этого мы должы сначала определить, где в HTML-холст находится, а затем какая плитка на этом холсте находится под курсором мыши. Для простоты, каждый клик будет обозначать следующую точку нашего маршрута для нашего алгоритма поиска пути. Предыдущая конечная точка, следовательно, будет новой точкой отсчета.
// обработка события щелчка мыши на холсте
function canvasClick(e)
{
var x;
var y;
// определяем координаты курсора относительно
//левого верхнего угла браузера
if (e.pageX != undefined && e.pageY != undefined)
{
x = e.pageX;
y = e.pageY;
}
else
{
x = e.clientX + document.body.scrollLeft +
document.documentElement.scrollLeft;
y = e.clientY + document.body.scrollTop +
document.documentElement.scrollTop;
}
// определяем координаты курсора относительно холста
x -= canvas.offsetLeft;
y -= canvas.offsetTop;
// return tile x,y that we clicked
var cell =
[
Math.floor(x/tileWidth),
Math.floor(y/tileHeight)
];
// теперь мы знаем на какую плитку мы нажали
console.log('we clicked tile '+cell[0]+','+cell[1]);
pathStart = pathEnd;
pathEnd = cell;
// рассчитать путь
currentPath = findPath(world,pathStart,pathEnd);
redraw();
}
Процедура выше определяет координаты курсора мыши относительно верхнего левого угла браузера и переводит их в координаты относительно холста, так как холст может располагаться где угодно на странице. Как только мы получим координаты точки, на которую нажали кнопкой мыши, мы разделим ее на размер плитки и таким образом узнаем на какую плитку в массиве world мы нажали.
Теперь, когда конечное положение предыдущего хода стало начальным положением следующего, запустим алгоритм A-star еще раз. Таким образом, в результате каждого клика маршрут пролегает из одной точки в другую – это похоже на передвижение юнитов в стратегиях, которое происходит не поступательно, а последовательно.
Теперь, когда у нас есть генератор игрового мира, функции рендеринга и взаимодействия с пользователем, пришел черед сделать последний шаг и написать функцию поиска пути.
A-star алгоритм
Мы собираемся создать одну большую функцию под названием FindPath ()
. Чтобы не захламлять код игры и позволить вам легко редактировать алгоритм из этого учебника и использовать его в своей игре, все функции, которые потребует этот алгоритм будут вложены в него. Просто, но эффективно.
В альтернативных методах функции могут находиться в разных областях, а также могут использоваться фабрика класса или одинарный объект, но нет ничего проще, чем копипаст.
Если вам нужен алгоритм поиска пути A-star, который не зависит от другого кода и существует в виде единого блока кода, не затрагивающего глобальное пространство имен какими-либо временными переменными, вам понравится этот метод. Просто копируйте и вставляйте
Поскольку мы используем этот способ, все фрагменты кода действуют внутри одной функции. Мы просто разобьем весь код на логические части – весь алгоритм состоит из 250 строк. Начнем с того, определим функцию и параметры, которые должны ей передаваться, а именно:
// world - 2d массив целых чисел (eg world[10][15] = 0)
// pathStart и pathEnd массивы, например [5,10]
function findPath(world, pathStart, pathEnd)
{
// упростим запись
var abs = Math.abs;
var max = Math.max;
var pow = Math.pow;
var sqrt = Math.sqrt;
// Данные мира представляют собой целочисленные переменные:
// Все значения, превышающие эту цифру, блокируются.
// Это удобно, если вы используете пронумерованные спрайты.
// Ходить можно по дороге, траве, грязи и т.д.
var maxWalkableTileNum = 0;
// Отслеживаем размер массива world
// Обратите внимание, что A* предполагает, что наш мир квадратный,
// то есть имеет равную высоту и ширину. Если ваш игровой мир
// прямоугольный, просто заполните массив world фиктивными значениями,
// чтобы дополнить пустое пространство.
var worldWidth = world[0].length;
var worldHeight = world.length;
var worldSize = worldWidth * worldHeight;
// Какой эвристический анализ мы используем?
// по умолчанию: не ходим по диагонали (Манхэттен)
var distanceFunction = ManhattanDistance;
var findNeighbours = function(){}; // пока пусто
/*
// альтернативные эвристические методы в зависимости от вашей игры:
// можно ходить по диагонали, но не через трещины в скалах:
var distanceFunction = DiagonalDistance;
var findNeighbours = DiagonalNeighbours;
// ходьба по диагонали и через трещины в скалах допускаются:
var distanceFunction = DiagonalDistance;
var findNeighbours = DiagonalNeighboursFree;
// Евклидово расстояние, проход через трещины не возможен:
var distanceFunction = EuclideanDistance;
var findNeighbours = DiagonalNeighbours;
// Евклидово расстояние, проход через трещины возможен:
var distanceFunction = EuclideanDistance;
var findNeighbours = DiagonalNeighboursFree;
*/
В приведенном выше коде, вы можете увидеть, что мы опрашиваем двумерный массив чисел, которые является ссылкой на вашу карту в игре. Он использует тот же формат, что и массив карты мира в генераторе местности (см. код выше), поэтому мы можем просто обратиться к нему без изменений. Остальные два параметра, - начальный и конечный пункт назначения в нашем мире, формируются в виде массива из координат х
и у
.
Первые несколько строк ускорят наши вычисления, сохраняя ссылки на часто используемые Math - функции. Это достаточно простая оптимизация, которая делает код немного меньше.
Теперь мы определим номер плитки самого большого массива игрового мира, по которому смогут перемещаться ваши персонажи. В нашем примере - это только трава (плитка номер ноль), но в реальной игре можно разнообразить число плиток, например: земля или улица, стена или мост...
Наконец, мы добавим пару ссылок на функции, о которых поговорим ниже, когда будем рассчитывать расстояния. Какие из них мы будем использовать, зависит от того, как алгоритм поиска пути будет вести себя по отношению к диагоналям и углам заблокированных плиток. Просто поменяйте функции distanceFunction и findNeighbours на те, которые вам нужны, как показано в прокомментированных примерах.
Расчет расстояния - Какой эвристический алгоритм использовать?
Прежде чем начать сравнивать плитки карты, необходимо решить, какую эвристику использовать. В нашем уроке, мы особо не заморачивались и позволили персонажу двигаться только вдоль четырех сторон света (север, юг, восток и запад).
Вычисление расстояний этим способом называется манхэттеновское расстояние - в честь решетчатой структуры некоторых районов Нью-Йорка. Есть несколько способов вычислить расстояния на основе диагоналей.
Первый – просто назвать перемещение по диагонали 1 space, с той же затратностью, что и движение NSEW, которое в коде фигурирует как DiagonalDistance. Еще один, более правильный способ измерения диагональных расстояний между плитками называется EuclideanDistance. Он основан на использовании теоремы Пифагора для измерения настоящего расстояния, которое примерно в 1,4 раза больше, чем между соседями NSEW.
Однако, если вашы юниты не могут двигаться по диагонали, вы определенно должны измерять расстояние с помощью метода Манхэттен. В любом случае, выбор за вами.
Изображение выше показывает разницу между этими двумя метожами. Зеленая линия - Евклидово расстояние (примерно 8,5 единиц), а все остальные - расстояния, полученные с помощью метода Манхэттен (всего 12 единиц).
Функция расстояния
Продолжая разговор о коде findPath, давайте рассмотрим все возможные функции расстояния, которые могут вам понадобиться. Для вашей игры вам нужна только одна.
// функции distanceFunction
// возвращают расстояние между точками
function ManhattanDistance(Point, Goal) {
// линейное перемещение – никаких диагоналей,
// просто ориентация по сторонам света (NSEW)
return abs(Point.x - Goal.x) + abs(Point.y - Goal.y);
}
function DiagonalDistance(Point, Goal) {
// движение по диагонали – диагональное расстояние
// приравнивается к 1, как и стороны света
return max(abs(Point.x - Goal.x), abs(Point.y - Goal.y));
}
function EuclideanDistance(Point, Goal) {
// диагональное расстояние немного увеличивается по сравнению со сторонами света
// движение по диагонали вычисляя Евклидово расстояние (AC = sqrt(AB^2 + BC^2))
// когда AB = x2 - x1 и BC = y2 - y1 и AC будет [x3, y3]
return sqrt(pow(Point.x - Goal.x, 2) + pow(Point.y - Goal.y, 2));
}
Свободно перемещение по диагонали или нет?
Дополнительные функции также включены в код для перемещения по диагонали независимо от того, считаете ли вы приемлемым перемещение сквозь щели между двумя прилегающими плитками, расположенными по диагонали друг к другу
Для каждого типа эвристики перемещений существует два варианта кода: FREE и стандартный (без суффикса).
Как правило, если два блока прилегают друг к другу по диагонали, точка, в которой соприкасаются два угла, недостаточно широка, чтобы через нее можно было пройти. Использование FREE вариации кода позволит вашим юнитам протиснуться через крошечные щели между двумя стенами.
На этой картинке зеленые стрелочки показывают, что мы имеем в виду под FREE диагоналями. Если вы МОЖЕТЕ пройти в щель между двумя красными блоками, эвристика, используемая вами для перемещения по диагонали, должна соответствовать одной из FREE вариаций. Если нет, используйте один из стандартных способов
Что в соседней плитке?
Теперь создадим функции, определяющие, какие соседи у каждого узла.
Это зависит от того, как настроены перемещения по диагонали: если вы не собираетесь использовать FREE передвижение, вам не надо включать в код приставку FREE.
Продолжим код внутри функции FindPath
. Добавьте следующие строки:
// Функции поиска соседних клеток, используются функцией
// findNeighbours для определения прилегающих незаблокированных клеток.
// Возвращает все доступные на севере, юге, востоке или западе ячейки.
// Диагонали отсутствуют, если функция distanceFunction
// не является манхэттоновским расстоянием
function Neighbours(x, y)
{
var N = y - 1,
S = y + 1,
E = x + 1,
W = x - 1,
myN = N > -1 && canWalkHere(x, N),
myS = S < worldHeight && canWalkHere(x, S),
myE = E < worldWidth && canWalkHere(E, y),
myW = W > -1 && canWalkHere(W, y),
result = [];
if(myN)
result.push({x:x, y:N});
if(myE)
result.push({x:E, y:y});
if(myS)
result.push({x:x, y:S});
if(myW)
result.push({x:W, y:y});
findNeighbours(myN, myS, myE, myW, N, S, E, W, result);
return result;
}
// Возвращает все доступные на северо-востоке, юго-востоке
// северо-западе и юго-западе ячейки – отсутствие свободного
// перемещения по диагонали
function DiagonalNeighbours(myN, myS, myE, myW, N, S, E, W, result)
{
if(myN)
{
if(myE && canWalkHere(E, N))
result.push({x:E, y:N});
if(myW && canWalkHere(W, N))
result.push({x:W, y:N});
}
if(myS)
{
if(myE && canWalkHere(E, S))
result.push({x:E, y:S});
if(myW && canWalkHere(W, S))
result.push({x:W, y:S});
}
}
// Возвращает все доступные на северо-востоке, юго-востоке
// северо-западе и юго-западе ячейки – включая перемещение по диагонали
// между углами прилегающих квадратов
function DiagonalNeighboursFree(myN, myS, myE, myW, N, S, E, W, result)
{
myN = N > -1;
myS = S < worldHeight;
myE = E < worldWidth;
myW = W > -1;
if(myE)
{
if(myN && canWalkHere(E, N))
result.push({x:E, y:N});
if(myS && canWalkHere(E, S))
result.push({x:E, y:S});
}
if(myW)
{
if(myN && canWalkHere(W, N))
result.push({x:W, y:N});
if(myS && canWalkHere(W, S))
result.push({x:W, y:S});
}
}
Можно ли ходить по данной плитке?
Теперь мы готовы создать вспомогательные функцию для окончательного алгоритма A-star. Для начала – простая функция, определяющая проходимость того или иного узла.
// возвращает логическое значение
// (клетка мира открыта для перемещения)
function canWalkHere(x, y)
{
return ((world[x] != null) &&
(world[x][y] != null) &&
(world[x][y] <= maxWalkableTileNum));
};
В приведенном выше коде, мы создали простое условие, проверяющее существование индекса массива world
. Если индекс существует, мы проверяем, чтобы число, которое хранится там, было меньше или равно максимальному индексу плитки, по которой можно ходить (мы определили его в самом начале).
Сохранение расходов на движение во время поиска пути
Далее, нам необходимо создать временные объекты, которые используются для хранения затрат на передвижение и сокращают индексы массива во время обработки.
Описанный ниже алгоритм A-star создаст списки этих узлов, которые составляются путем пересечения всех маршрутов, проверенных нами по пути.
// Функция узла, возвращает новый объект
// со свойствами узла. Используется функцией calculatePath
// для хранения затрат на маршруты и т.д.
function Node(Parent, Point) {
var newNode = {
// указывает на другой объект узла
Parent:Parent,
// индекс массива узла в линейном массиве мира
value:Point.x + (Point.y * worldWidth),
// координаты расположения узла
x:Point.x,
y:Point.y,
// затратность distanceFunction при перемещении
// к этому узлу от НАЧАЛА
f:0,
// затратность distanceFunction при перемещении
// от этого узла к МЕСТУ НАЗНАЧЕНИЯ
g:0
};
return newNode;
}
Объекты узлов формируют список с указателями , поскольку каждый ссылается на родительский узел. Здесь также содержатся координаты x и y, расстояния между начальной и конечной точками и индексы массивов, которые используются для ускорения вычислений.
Рождение A-Star
И наконец, сам алгоритм A-star. Это последний блок в нашей функции findPath().
// функция маршрута, выполняет операции AStar
function calculatePath() {
// создает узлы на основе начальных и конечных координат x и y
var mypathStart = Node(null, {x:pathStart[0], y:pathStart[1]});
var mypathEnd = Node(null, {x:pathEnd[0], y:pathEnd[1]});
// создать массив, который будет содержать все клетки игрового мира
var AStar = new Array(worldSize);
// список открытых узлов
var Open = [mypathStart];
// список закрытых узлов
var Closed = [];
// список конечного массива для вывода
var result = [];
// ссылка на узел (находящийся поблизости)
var myNeighbours;
// ссылка на узел (который мы рассматриваем в данное время)
var myNode;
// ссылка на узел (лежащий в начале текущего маршрута)
var myPath;
// изменяем целочисленные переменные, используемые при расчете
var length, max, min, i, j;
// прокладываем маршруты через открытый список, пока не задействуем все узлы
while(length = Open.length) {
max = worldSize;
min = -1;
for(i = 0; i < length; i++) {
if(Open[i].f < max) {
max = Open[i].f;
min = i;
}
}
// берем следующий узел и удаляем его из открытого массива
myNode = Open.splice(min, 1)[0];
// это узел назначения?
if(myNode.value === mypathEnd.value) {
myPath = Closed[Closed.push(myNode) - 1];
do {
result.push([myPath.x, myPath.y]);
}
while (myPath = myPath.Parent);
// очистить рабочие массивы
AStar = Closed = Open = [];
// мы хотим сделать конечную точку началом маршрута
result.reverse();
}
else // не пункт назначения
{
// определите, какие узлы, находящиеся поблизости, являются проходимыми
myNeighbours = Neighbours(myNode.x, myNode.y);
// протестируйте каждый узел, который вы еще не пробовали
for(i = 0, j = myNeighbours.length; i < j; i++) {
myPath = Node(myNode, myNeighbours[i]);
if (!AStar[myPath.value]) {
// приблизительная затратность маршрута на данном этапе
myPath.g = myNode.g + distanceFunction(myNeighbours[i], myNode);
// приблизительная затратность всего
// предполагаемого маршрута до точки назначения
myPath.f = myPath.g + distanceFunction(myNeighbours[i], mypathEnd);
// запомним этот новый маршрут, чтобы протестировать его, как описано выше
Open.push(myPath);
// отметим этот узел в графе мира как посещенный
AStar[myPath.value] = true;
}
}
// запомним этот маршрут как полностью протестированный
Closed.push(myNode);
}
} // продолжаем прокладывать маршруты, пока не исчерпаем весь открытый список
return result;
}
Вы можете следовать этому алгоритму вместе со всеми комментариями. По сути, мы наполняем несколько списков с указателями объектами узлов, содержащих данные карты мира и место для хранения расстояний по ходу маршрута.
Заметьте, что в данном примере A-star используется квадратный мир с одинаковой шириной и длиной. Если вы хотите создать прямоугольный мир, просто заполните массив фиктивными значениями, чтобы заполнить пустое пространство.
Как написано в главе, посвященной оптимизации, сначала мы ищем маршруты, которые кажутся кратчайшими путями к цели. Мы продолжаем помещать узлы в каждый из массивов в зависимости от длины маршрута, по которому мы можем туда попасть. Исчерпав открытый список, мы получаем наименее затратный путь, который сохраняется в конечном массиве и готов к конечному выводу.
Начиная с первого узла, который является начальной точкой, предписанной функцией findPath, мы используем список узлов, которые нужно проверить.
Это открытый массив. Закрытый список (содержащий проверенные узлы) используется для повышения эффективности поиска.
Мы также учитываем пройденное расстояние; свойство узла g соответствует затратности пути от начальной точки, а свойство f - это значение g плюс эвристические затраты от данной точки до точки назначения.
Чем ниже свойство f, тем выше приоритет узла. На каждом этапе узел с наименьшим значением f удаляется из списка, значения f и g соседних узлов обновляются, и эти соседи добавляются в список и могут быть включены в маршрут.
Так продолжается, пока узел назначения не станет узлом с наименьшим значением f в очереди (или пока очередь не опустеет).
Этот алгоритм мог бы украсить любую магистерскую работу по программированию. Не расстраивайтесь, если это кажется немного запутанным и сложным. Зато теперь вы можете использовать эту функцию в вашей собственной игре и пожинать плоды высшей математики. Стоя на плечах гиганта, так сказать.
Теперь, когда мы создали несколько встроенных функций в алгоритме findPath(), we мы можем запустить A-star и применить результаты к нашей игре.
// рассчитывает маршрут a-star
// возвращает массив координат
// остается пустым, если нет возможного маршрута
return calculatePath();
} // конец функции findPath()
Теперь, когда мы хотим, чтобы персонаж в нашей в игре перемещался по местности, мы просто вызываем FindPath ()
и передаем в массив world
координаты начальной и конечной точки маршрута.
Пример того, как эта функция должна быть вызвана находится в функции canvasClick выше. В принципе, вы просто сделать так currentPath = findPath(world,pathStart,pathEnd)
и получите массив c координатами ([х, у]
).
В реальном сценарии игры, вы можете ограничить расстояние, пройденное каждый ход. Например, в тактической игре вы можете позволить игроку переместиться только на шесть клеток за ход. Это можно сделать просто останавливая движение на полпути, используя только первые несколько значений массива.
Окончательный результат
Посмотрим на наш код в действии. Нажмите по карте и обратите внимание как рассчитывается кратчайший путь (если его возможно рассчитать). Представьте себе возможности для вашей будующей стратегической, тактической игры, или головоломки!
Вот и все! Вы можете не тратить время на копипастинг всего кода от каждого отдельного раздела этого учебника, а скачать полный код.
Практический пример
В качестве примера, вы можете увидеть как работает наш код в реальных играх. Уверен, это будет интересно тем, кто захочет применить A-star алгоритм в своих играх, поэтому хочу вам представить логическую игру, в которой как раз используется код из этого учебника. Она называется "Пафос" и я приглашаю вас поиграть в нее.
Наш урок закончен. Простые AI движения добавят в вашу игру элемент стратегического мышления, юниты, способные найти путь к цели, и другие интересные возможности для стратегий, тактических игр и головоломок.
Удачи вам в ваших будущих игровых проектах. Вам все по-плечу!