• Игролог
• Игры
• Об авторе

TowerDefence #5. Поиск пути

Представим, что у нас есть некий абстрактный мир с видом сверху и нам нужно найти путь из точки А в точку Б — как мы это можем сделать? В реальном мире мы ищем себе дорогу исключительно за счет нашего зрения. �? мы знаем свой путь настолько,насколько видим вперед. Таким образом, первое, что нам приходит в голову — это оснастить наших юнитов «зрением», которое бы позволяло оглядывать/прощупывать окресность вокруг себя в некотором радиусе. A далее, исходя из текущей обстановки, выбирать направление движения и двигаться какое-то время, а потом вновь оглядываться, и так делать до тех пор, пока юнит не доберется до цели. Этот способ достаточно логичный, так как неплохо работает в реальном мире, но у него есть недостатки.

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

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

С какой стороны подойти?

Много лет назад, когда мне впервые нужно было реализовать поиск пути — в �?нтернет еще не было так много доступной и подробной информации как сейчас о готовых алгоритмах поиска пути. А та информация, что была — не всегда поддавалась пониманию в виду ее слишком специализированной подачи. Таким образом, я вообще не мог сообразить с какой стороны к этому вопросу подобраться, пока случайно не наткнулся на подсказку.

Все мы знаем одну хорошую поговорку «вода под лежачий камень — не течет» — казалось бы какое отношение это имеет к поиску пути вообще? Но все до безобразия просто! Если мы возьмем некую плоскость, положим на нее камни и начнем куда-нибудь в одно место лить аккуратно воду, то вода равномерно будет заполнять свободное пространство вокруг камней. Более того, когда например вода достигнет определенного места на этой плоскости, то мы с уверенностью сможем определить то, откуда она пришла. Бинго!

Я надеюсь вы улавливаете суть? Та точка, куда мы льем воду — эта та точка, в которой находится юнит, и из которой ему нужно найти путь. А любая другая точка на плоскости — это куда, например, юниту нужно найти путь. �? когда вода достигает финальной точки нам нужно лишь проследить откуда она пришла и у нас будет готовый путь. Таким образом, надо лишь придумать простой алгоритм заполнения свободного пространства «водой».

Позже я выяснил, что подобный алгоритм поиска пути называется «Волновой» — это потому, что от стартовой точки как круги по воде волна расходится в разные стороны, заполняя все свободное пространство до тех пор, пока не захлыстнет финальную точку. Но сегодня я расскажу о более примитивном алгоритме, базирующимуся на основе волны.

Движок для поиска пути

Для удобства использования алгоритма поиска пути в текущем проекте и при последующем переносе в любые другие проекты, я предлагаю вынести его в отдельный класс, который мы назовем PathFinder.as. Давайте создадим его в нашем проекте. Файл класса поместим в папку com.framework и сразу откроем его для редактирования.

В прошлых уроках мы уже подготовили карту проходимости для поиска пути и для определения в каких ячейках можно что-то строить, а в каких нельзя. Чтобы сделать некое подобие заполнение карты проходимости водой с последующим определением направления движения этой самой воды —нам нужно будет два двухмерных массива. В первый массив _mapMask мы будем копировать карту проходимости и во время поиска заполнять его «водой», а во второй массив _mapDirs мы будем сохранять направление движения «воды».

�?так, первым делом объявим все основные переменные, которые нам понадобятся:

// Уникальный номер воды, которым заполняется маска по мере заполнения
private static const WATER_KEY:int = 999;
        
private var _mapMask:Array = []; // Копия маски карты
private var _mapDirs:Array = []; // Направления
private var _mapWidth:int = 0; // Ширина карты
private var _mapHeight:int = 0; // Высота карты
        
private var _freeCell:int = -1; // Вид свободной ячейки
private var _maxIterations:int = 50; // Счетчик повторов

С первыми четырьмя локальными переменными я думаю все понятно и они не требуют дополнительных пояснений. А вот последние две я хотел бы прокомментировать. Переменная _freeCell хранит в себе вид свободной ячейки — это нужно, чтобы наш класс поиска пути был максимально универсальным и мы могли бы его использовать в любых других проектах. Таким образом при инициализации класса поиска пути нам нужно будет указать через эту переменную, какой тип ячейки считается пустой в маске проходимости. А перемененная _maxIterations отвечает за количество проходов по карте проходимости во время поиска пути, позже я еще дополнительно объясню зачем это нужно.

Теперь напишем конструктор класса, он будет выглядеть следующим образом:

public function PathFinder(mapArr:Array)
{
  var rowMask:Array; // Строка для карты
  var rowDirs:Array; // Строка для направлений
  _mapWidth = mapArr[0].length; // Ширина карты
  _mapHeight = mapArr.length; // Высота карты
            
  for (var y:int = 0; y < _mapHeight; y++)
  {
    // Новые строки
    rowMask = []; 
    rowDirs = [];
    for (var x:int = 0; x < _mapWidth; x++)
    {
      rowMask.push(mapArr[y][x]); // Копируем состояние клетки
      rowDirs.push(new Point()); // Создаем нулевую коордианту направления
    }
    _mapMask.push(rowMask);
    _mapDirs.push(rowDirs);
  }
}

При создании класса поиска пути в качестве основного параметра мы передаем двумерный массив карты проходимости из основной игры. Ширину и высоту карты вычисляем исходя из размера полученного двумерного массива карты проходимости. Далее мы копируем полученную карту проходимости в локальную переменную _mapMask, где в последующем и будем с ней работать, а так же создаем пустой двумерный массив направлений — он будет заполняться во время поиска пути.

Далее начнем с создания более простых методов, чтобы было все максимально понятно и напишем простенький приватный метод, который будет выполнять проверку на выход за пределы карты:

private function inMap(ax:int, ay:int):Boolean
{
  if (ax >= 0 && ax < _mapWidth && ay >= 0 && ay < _mapHeight)
  {
    return true;
  }
  else
  {
    return false;
  }
}

В качестве атрибутов передаются координаты ячейки и выполняется проверка на предмет попадания этих координат в размер карты проходимости — эта проверка нужна, чтобы избежать выхода за пределы карты проходимости/двумерного массива, когда мы будем «разливать воду».

Теперь нам нужно написать метод, который будет «разливать воду» из указанной ячейки в соседние:

private function goWater(ax:int, ay:int):void
{
  // Если клеточка сверху свободна
  if (inMap(ax, ay - 1) && _mapMask[ay - 1][ax] == _freeCell)
  {
    _mapMask[ay - 1][ax] = WATER_KEY; // Заполняем её водой
    // Запоминаем из какой клетки вода пришла
    (_mapDirs[ay - 1][ax] as Point).x = ax;
    (_mapDirs[ay - 1][ax] as Point).y = ay;
  }
            
  // Если клеточка слева свободна
  if (inMap(ax + 1, ay) && _mapMask[ay][ax + 1] == _freeCell)
  {
    _mapMask[ay][ax + 1] = WATER_KEY; // Заполняем её водой
    // Запоминаем из какой клетки вода пришла
    (_mapDirs[ay][ax + 1] as Point).x = ax;
    (_mapDirs[ay][ax + 1] as Point).y = ay;
  }
            
  // Если клеточка снизу свободна
  if (inMap(ax, ay + 1) && _mapMask[ay + 1][ax] == _freeCell)
  {
    _mapMask[ay + 1][ax] = WATER_KEY; // Заполняем её водой
    // Запоминаем из какой клетки вода пришла
    (_mapDirs[ay + 1][ax] as Point).x = ax;
    (_mapDirs[ay + 1][ax] as Point).y = ay;
  }
                
  // Есле клеточка справа свободна
  if (inMap(ax - 1, ay) && _mapMask[ay][ax - 1] == _freeCell)
  {
    _mapMask[ay][ax - 1] = WATER_KEY; // Заполняем её водой
    // Запоминаем из какой клетки вода пришла
    (_mapDirs[ay][ax - 1] as Point).x = ax;
    (_mapDirs[ay][ax - 1] as Point).y = ay;
  }
}

Метод goWater() в качестве атрибутов получает координаты ячейки, в которой уже якобы имеется «вода» и выполняет её разливание в соседние ячейки при условии, если мы не выходим за пределы карты и соседние ячейки пусты. Обратите внимание на условия — вначале мы добавляем к текущим координатам ячейки значение и проверяем не вышли ли мы за пределы карты. �? только в случае, если мы не вышли за пределы карты, уже проверяем состояние соседней ячейки. Если соседние ячейки равны статусу свободной ячейки, то в свободную мы помещаем нашу «воду». В качестве воды используется уникальный номер 999, который мы храним в константе WATER_KEY. Будьте внимательны: номер воды не должен совпадать с любыми другими номерами, находящимися в карте проходимости. Так же когда мы поместили в соседнюю ячейку воду, записываем в массив направлений в ячейку с такими же координатами откуда вода в нее попала — это ключевой момент в алгоритме поиска пути. Только благодаря массиву направлений мы потом сможем вычислить, как вода разливалась по карте и получить маршрут.

Теперь самое интересное, фактически ядро нашего класса поиска пути, пишем метод findWay():

public function findWay(start:Point, end:Point):Array /* of Point */
{
  // Устанавливаем точку куда льем "воду"
  _mapMask[end.y][end.x] = WATER_KEY;
  var counter:int = 0; // Счетчик проходов по карте
            
  // Выполняем проходы по карте
  while (counter < _maxIterations)
  {
    // �?щем путь / размазываем воду по маске проходимости
    for (var y:int = 0; y < _mapHeight; y++)
    {
      for (var x:int = 0; x < _mapWidth; x++)
      {
        // Если в текущей ячейке вода 
        if (_mapMask[y][x] == WATER_KEY) 
        {
          goWater(x, y); // то распространяем её в соседние ячейки
        }
      }
    }
                
    // Проверяем не попала ли вода в точку финиша
    if (_mapMask[start.y][start.x] == WATER_KEY)
    {
      // Ура! Путь найден!
      // Возвращаем путь
      return getWay(start, end);
    }           
    counter++;
  }
            
  // Количество проходов исчерпано, путь не найден
  // Возвращаем пустой массив
  return [];
}

В качестве атрибутов мы передаем две точки — это стартовая позиция, откуда будем искать путь, и финальная позиция, куда нужно найти дорогу. Если путь будет найден, то вернется массив координат ячеек, шагая по которым можно будет добраться из точки start в точку end. Ну, а если путь не будет найден, то вернется пустой массив.

Теперь немного об алгоритме поиска пути. Как вы уже заметили, в точку, откуда мы начинаем искать путь, мы присваиваем значение «воды», а далее нам нужно несколько раз пройтись по карте проходимости и каждый раз, натыкаясь на клетку с водой, распространить её в соседние пустые ячейки. Поскольку один проход по карте проходимости выполняется с левого верхнего угла слева на право и построчно сверху в низ — нам прийдется выполнить несколько проходов по всей карте проходимости, чтобы наверняка заполнить все доступные пустые ячейки водой. Например: чтобы найти дорогу из верхнего левого угла в правый нижний — нам хватит одного прохода, потому что направление пути соответствует направлению прохода по карте проходимости, и карта проходимости будет заполнена водой за один проход. Но вот если нам понадобится найти путь из правого нижнего угла в левый верхний, то тут нам понадобится много проходов, так как каждое смещение «воды» снизу вверх будет равняться одной клеточке за один проход.

�?так, выполнение проходов во время поиска пути может быть прервано по двум причинам: в ячейку, куда мы искали путь, попала вода и это значит, что вода успешно дотекла оттуда, куда мы её лили туда куда нам нужно было найти дорогу, и тут остается только получить список ячеек, по которым она протекла — это набор координат ячеек, по которым она перемещалась прямо, как русло ручья :) Получаем эти координаты методом getWay() (нам его еще предстоит написать). �? вторая причина, по которой поиск пути останавливается — это превышение максимального числа доступных проходов, то есть «вода» так и не добралась до нужной нам клетки, то есть путь не может быть найден.

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

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

Вопрос на засыпку: Какие преимущества дает поиск пути не со стартовой точки, а с финишной?

Ну что, путь мы можно сказать нашли, осталось только его построить и вернуть в качестве списка координат ячеек, то есть создать маршрут. Для этого мы напишем отдельный метод getWay():

private function getWay(start:Point, end:Point):Array /* of Point */
{
  var way:Array = []; // Маршрут
  var p1:Point = new Point(start.x, start.y);
  var p2:Point = new Point();
            
  // Добавляем в маршрут все точки
  // пока не дойдем до конца
  while (true)
  {
    // Получаем новую точку из направления предыдущей
    p2.x = (_mapDirs[p1.y][p1.x] as Point).x;
    p2.y = (_mapDirs[p1.y][p1.x] as Point).y;
                
    way.push(new Point(p2.x, p2.y)); // Добавляем новую точку в маршрут
    p1.x = p2.x;
    p1.y = p2.y;
                
    // Проверяем, не добрались ли до конца
    if (p1.x == end.x && p1.y == end.y)
    {
      break;
    }
  }
  return way;
}

Метод getWay() работает уже только с массивом направлений и извлекает из него маршрут. Чтобы извлечь маршрут корректно, мы передаем так же точки откуда и куда мы должны построить маршрут, используя карту проходимости. Здесь нам понадобятся две дополнительные переменные типа Point, которые будут поочередно сменять друг друга. Для первой точки мы сразу указываем стартовую позицию и далее выполняем цикл до тех пор, пока не доберемся до финальной точки, используя направления.

Принцип работы достаточно прост, во вторую переменную мы сохраняем координаты соседней ячейки, из которой пришла вода, потом копируем эти координаты в маршрут и передаем их в первую переменную. Таким образом, на следующую итерацию цикла мы сместимся на одну ячейку согласно направлению и так будет выполняться до тех пор, пока мы не дойдем до финальной точки. А когда добрались до финальной точки, прерываем работу бесконечного цикла и возвращаем маршрут. Вот и все! :)

Прежде чем внедрять наш движок поиска пути в игру, давайте допишем еще пару сеттеров, которые нам позволят задавать тип свободной ячейки и максимальное количество итераций:

public function set freeCell(value:int):void
{
  _freeCell = value;
}
        
public function set maxIterations(value:int):void
{
  _maxIterations = value;
}

�? еще не забудьте импортировать класс Point в заголовке нашего класса PathFinder.as так:

import flash.geom.Point;

�?спользование алгоритма в проекте

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

Чтобы у нас один и тот же код не повторялся для классов всех врагов, мы реализуем использование класса PathFinder.as в базовом классе врага EnemyBase.as — открываем его для редактирования и первым делом добавляем новые внутренние переменные:

protected var _position:Point; // Текущее положение врага
protected var _target:Point; // Цель, куда должен прийти враг
        
protected var _way:Array; // Маршрут врага
protected var _isWay:Boolean = false; // Определяет существование маршрута
protected var _wayIndex:int = 0; // Текущий индекс маршрута
protected var _wayTarget:Point; // Текущая цель

Следующим шагом модифицируем метод init():

public function init(posX:int, posY:int, targetX:int, targetY:int):void
{
  if (_sprite != null)
    addChild(_sprite);
            
  // Запоминаем положение и цель врага
  _position = new Point(posX, posY);
  _target = new Point(targetX, targetY);
            
  // Устанавливаем врага на карте
  _universe.addEnemy(this);
            
  // �?щем маршрут
  var pathFinder:PathFinder = new PathFinder(_universe.mapMask);
  pathFinder.freeCell = Universe.STATE_CELL_FREE;
  _way = pathFinder.findWay(_position, _target);
            
  if (_way.length == 0)
  {
    trace("EnemyBase::init() - Путь не найден!");
  }
  else
  {
    // Путь найден!
    _isWay = true;
    _wayIndex = 0; // Текущий шаг
    _wayTarget = _way[_wayIndex]; // Текущая цель
  }
}

Помните домашнее задание из предыдущего урока, где вам нужно было добавить возможность устанавливать врага в определенную клетку? Если вы его не выполнили, то сейчас все равно это прийдется сделать. В методе init() в качестве аттрибутов у нас теперь указывается текущее положение в клетках posX и posY, а так же мы сразу добавляем атрибутами targetX и targetY клетку цель, куда враг должен двигаться.

В самом методе первым делом мы эти все атрибуты запоминаем и сразу выполняем поиск пути. Создаем наш движок поиска пути. Показываем ему, как выглядят наши свободные ячейки в игре, и получаем маршрут в переменную _way. Если длинна массива _way == 0, значит путь не найден, а иначе мы устанавливаем флаг, что маршрут существует, устанавливаем нулевой индекс маршрута и указываем первую точку в маршруте, как текущую цель. Само же движение юнита мы уже реализуем непосредственно в его классе.

Открываем EnemySolder.as для редактирования и первым делом исправляем метод init() согласно тому, как мы это сделали в базовом классе врагов, а так же не забываем вызывать родительский метод, передав ему все указанные атрибуты, чтобы наш код в базовом классе выполнился:

public override function init(posX:int, posY:int, targetX:int, targetY:int):void
{
  // Уникальные параметры врага
  _kind = EnemyBase.KIND_SOLDER;
  _health = 100;
  _speedX = 100;
  _speedY = 100;
            
  // Создание графического образа
  _sprite = new Solder_mc();
        
  // Вызов родительского метода
  super.init(posX, posY, targetX, targetY); 
}

Далее переходим к методу update(), где нам нужно реализовать перемещение юнита по клеточкам, изменяем его следующим образом:

public override function update(delta:Number):void
{
  // Если маршрут существует
  if (_isWay)
  {
    x = _wayTarget.x * Universe.MAP_CELL_SIZE + Universe.MAP_CELL_HALF;
    y = _wayTarget.y * Universe.MAP_CELL_SIZE + Universe.MAP_CELL_HALF;
                                
    // Обновляем текущие координаты в клеточках
    _position.x = int(x / Universe.MAP_CELL_SIZE);
    _position.y = int(y / Universe.MAP_CELL_SIZE);
                
    // Переходим к новому шагу
    _wayIndex++;
    if (_wayIndex == _way.length)
    {
      // Весь маршрут пройден
      _isWay = false;
    }
    else
    {
      _wayTarget = _way[_wayIndex];
    }       
  }
}

Поскольку пока перемещение юнита осуществляется строго по клеточкам, то мы просто присваиваем юниту текущее положение согласно координатам в маршруте. Далее мы обновляем текущее положение юнита и переходим к следующей точке в нашем маршруте — вот и все вроде бы! :)

Но не спешите компилировать игру. Нужно еще немного доработать классы Universe.as и Game.as, чтобы полноценно насладиться результатом.

Первым делом открываем класс Universe.as и находим в конструкторе мира строчки с созданием тестового врага — выделяем и вырезаем их оттуда. Теперь создадим временный публичный метод, который будет создавать каждый раз нового врага, выглядеть он будет так:

public function newEnemy():void
{
  // Создание тестового врага
  var solder:EnemySolder = new EnemySolder();
  solder.init(0, 0, 19, 14);
}

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

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

В классе Game.as содержимое конструктора перенесите в новый метод init(), который должен выглядеть так:

private function init(event:Event = null):void
{
  // �?гровой мир
  _universe = new Universe();
  addChild(_universe);

  // Обработчики мыши и клавиш
  addEventListener(MouseEvent.MOUSE_MOVE, mouseEventHandler);
  stage.addEventListener(KeyboardEvent.KEY_DOWN, keyDownHandler);

  removeEventListener(Event.ADDED_TO_STAGE, init);
}

Здесь мы создаем игровой мир и привязываем обработку нажатий клавиш и мышки. А конструктор класса Game.as теперь сделаем таким:

public function Game()
{
  if (stage)
  {
    init();
  }
  else
  {
    addEventListener(Event.ADDED_TO_STAGE, init);
  }
}

Это не хитрая манипуляция нужна лишь только для того, чтобы инициализация игры происходила только тогда, когда класс игры добавлен на сцену в список отображаемых объектов, и все это ради ссылки на stage. А теперь добавим обработчик нажатия клавиш:

private function keyDownHandler(event:KeyboardEvent):void
{
  _universe.newEnemy(); // Добавляем врага
}

Теперь точно все! Можем компилировать наш проект, рисовать любую карту проходимости и нажимать любую клавишу. �? мы увидим, как враг, сломя голову, проносится через всю карту, показывая найденный маршрут. Выглядит не очень эстетично, но этого вполне достаточно, чтобы завершить сегодняшний урок :)

Если у вас что-то не получается или по ходу компиляции возникают какие-либо ошибки, пожалуйста, следуйте следующим шагам:

1. Перечитайте еще раз внимательно урок;
2. Скачайте исходники и свертесь с ними;
3. Пишите свой вопрос мне на почту или в комментарии.

 

Домашнее задание

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

Заключение

Сегодня мы разобрались с основами поиска пути и как оказалось на практике не все так сложно, правда!? Это, пожалуй, самый простой и надежный способ поиска пути, который я использовал, и вообще когда-либо встречал. Но не спешите радоваться, не смотря на свою надежность у данного алгоритма есть существенный недостаток. Слабое место данного алгоритма заключается в том, что он может найти не всегда оптимальный путь, поскольку поле заполняется «водой» не равномерно во все стороны, а согласно тому как осуществляется проход по игровой маске. Таким образом, путь под прямым углом будет найден с большей вероятностью, чем по диагонали. Это, конечно, мелочь, но для таких игр, где правильный поиск пути важен для геймплея, это может оказаться существенным недостатком. Между тем данный алгоритм хорошо себя зарекомендовал в играх типа паззл, и я его успешно использовал в своих играх Lines3D, Joe's Farm и в Santa Is Coming.

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

Ссылка на исходники — CS4, *.zip, 105 кб.

P.S.: Ответ на засыпку из прошлого урока: обработчик мышки добавляется в основной класс игры только для того, чтобы мы получали координаты мыши не зависимо от того, какие дополнительные игровые окна или панели инструментов у нас будут появляться по мере создания игры. То есть, если мы сейчас добавим игровое меню или любой другой визуальный объек в класс Game.as перекрывающий игровой мир, то мир все равно будет получать координаты мышки.

Содержание

1. Вступление
2. Структура игры
3. Карта проходимости
4. Первый враг
5. Готовимся к поиску пути
6. Поиск пути
7. Редактор уровней
8. Движение врагов
9. Первая башня
10. Кэширование объектов
11. Полоса жизни
12. Вражеские волны
13. Загрузка вражеских волн
14. Продолжение следует...