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. Продолжение следует...

 


Индикаторы: Уроки, Action Script 3
Постоянная ссылка

 

 

Спасибо за уроки! Крут! :)

Арсен
21 Января 2011
— 00:21
#

Ох как раз нужен. Спасибо

zarkua
21 Января 2011
— 00:24
#

Пара дополнений к алгортму поиска пути:

1) Чтобы не "пробегать" по всей карте (иногда множество раз) можно в класс PathFinder добавить еще один массив для хранения "активных" клеток с "водой". В методе findWay добавляем в этот массив добавить стартовую точку (или конечную) и организовать цикл с условием на пустоту этого массива (цикл выполняется пока в массиве есть хоть одна клетка), в методе goWater сначала извлекаем из этого массива текущую клетку (с которой "льем воду"), и по условиям (не выходит за границы, свободна от препятствий и "воды") добавляем соседнии клетки. Таким образом и "вода" будет "течь" "правильнее", и не будут "просматриваться" не свободные клетки.

2) В начало метода findWay хорошо бы добавить проверки стартовой и финишной клеток на выход за границы и принадлежность к непроходимым зонам - чтобы не искать заведомо не существующий путь.

Sturm LS
21 Января 2011
— 07:16
#

Спасибо Антон!!! Я уж и не надеялся :)

Иван
21 Января 2011
— 07:27
#

Для изучения вопроса статья очень хороша, но алгоритм поиска не справляется

http://img9.tempfile.ru/10020/10881d8939/9727e1930f4c3b15de72f763.png

если сделать как на картинке то он путь не найдет а если убрать один квадратик который красным обведен тогда найдет я так понимаю это как раз все из-за максимального числа итераций.

Иван
21 Января 2011
— 10:14
#

Спасибо, Антон.
Возник вопрос: сможет ли враг при реализации такого метода находить путь и двигаться по диагонали. В "недостатках" метода говориться, что это будет происходить реже, чем движение по прямых углах. Но все же будет?

jarofed
21 Января 2011
— 11:05
#

Да, волновои самыи простой и выгодныи в данном случае (сам писал месяц назад).
Но у него свои минусы.
Советую браться за астар.

Даниил
21 Января 2011
— 11:24
#

Не работает алгоритм. Находит путь только в лабиринте из двух-трех стенок, а чуть больше - не находит.

Max
21 Января 2011
— 13:34
#

@Sturm LS оба дополнения отличные! Первое делать не стал чтобы реализация выглядела наглядно и понятно. Думаю, что желающие могут попробовать реализовать хранение волны самостоятельно.

Про проверку вхождения клеток в карту и на наличие припятствий - я забыл совсем :)

Ant.Karlov
21 Января 2011
— 17:33
#

@Иван на вашем скриншоте как раз нарисован такой лабиринт где мы по высоте поднимаемся два раза с половиной, что равняется как раз примерно 50 проходам учитывая высоту нашей карты. Для такого волнообразного лабиринта понадобится больше итераций. Попробуйте поставить 500 ;)

Ant.Karlov
21 Января 2011
— 17:38
#

@jarofed если имеется в виду именно поиск пути по диоганали, то в метод goWater() нужно добавить еще четыре условия для проверки соседних клеток по диоганали и все будет работать. Но чтобы получать более оптимальный путь нужно реализовать полноценое движение волны во все стороны, сделать это можно так как описал Sturm LS в своем комментарии выше.

Ant.Karlov
21 Января 2011
— 17:43
#

@Max чтобы находить путь в сложных лабиринтах - увеличте максимальное количество итераций. С количеством итераций по умолчанию я немножко ошибся :)

Ant.Karlov
21 Января 2011
— 17:47
#

Кстати можно сэкономить и вместо функции inMap просто обвести весь уровень бордюром непроходимых клеток :)

Ещё я так понял описан алгоритм Декстры. Лучше имхо его модификация - алгоритм А*. На разреженных картах он даёт большой выигрыш в производительности.

Oleg Antipov
22 Января 2011
— 10:50
#

Молодец! Идею донёс отлично (+код - это вдвойне молодец). И не смотри на тех кто пишет что "фи, не работает в моём ах%%тельном лабиринте" - идея описана, есть даже код, разберутся, допишут и хождение по диагоналям, и разные скорости по траве, болотам и дорогам...

Robot Bobot
23 Января 2011
— 01:09
#

Возникла небольшая проблема:
Из Библиотеки я добавляют МувиКлип. В этом МувиКлипе есть кнопка.
Мне нужно, что бы при нажатии на нее переходил на след. кадр не в этом МувиКлипе, а на главной сцене.
Т.е., псевдокод:
partent::gotoAndStop(n);

Как такое реализовать?

f-duck
23 Января 2011
— 13:40
#

@f-duck:
Нужно получить доступ к образцу класса Stage.
Например, вот так:
var p:DisplayObjectContainer = parent;

while ( ! (p is Stage) )
{
p = p.parent;
}
//Цикл закончится, так как все пути ведут к Stage, так или иначе.

//Далее остается просто вызвать:
Stage(p).gotoAndStop(n);

Но, это слишком грубый способ, лучше в какой-нибудь статичной переменной запомнить указатель на Stage и не искать его постоянно.

BuxomBerry
23 Января 2011
— 18:27
#

@Ant.Karlov
Интересный подход к описанию волнового алгоритма. Возник один вопрос: почему все волны нумеруются одним числом-флагом WATER_KEY? Может я что-то упустил? Обратный ход и критерий остановки алгоритма упростится, если нумеровать каждый шаг волны уникальным числом - номером итерации. Если мне память не изменяет, в оригинале этого алгоритма делается именно так.

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

BuxomBerry
23 Января 2011
— 18:50
#

А как же А*?

Michael Tkachuk
23 Января 2011
— 23:28
#

Антон, посоветуйте туториалы, уроки по графике.
Как рисовать, на чем заострить внимание.
Реально хочется научиться рисовать, пусть не в живую, а на компьютере...

f-duck
23 Января 2011
— 23:37
#

@BuxomBerry я в самом начале записи я написал, что это упрощенный алгоритм поиска пути без каких-либо оптимизаций и тонкостей, в первую очередь рассчитанный на легкое понимание работы принципа алгоритма. Более того в том виде в котором он сейчас есть, его вполне будет достаточно для данной игры.

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

Ant.Karlov
23 Января 2011
— 23:45
#

@Michael Tkachuk, а алгоритм A* мы разберем в следующий раз ;)

Ant.Karlov
23 Января 2011
— 23:48
#

@f-duck, следующая запись будет про графику, там я приведу пару ссылок. В любом случае, чтобы уметь рисовать на компьютере, умение рисовать на бумажке не будет лишним! ;)

Ant.Karlov
23 Января 2011
— 23:53
#

@Ant.Karlov, жду с превеликим нетерпением.

f-duck
24 Января 2011
— 00:00
#

Антон, на МочиГеймс наткнулся случайно на обзор MT2. Скорее всего вы уже видели но всё-же =) : http://blog.mochigames.com/2011/01/25/mining-truck-2-trolley-transport-review/ .

Кирилл
30 Января 2011
— 16:07
#

check

bob
31 Января 2011
— 18:13
#

Эх жаль тебя не было на IndieSnow!

Посмотрел бы мой тавер дефенс, редактор и мой простой метод задания путей. Может бы подсказал чего по оформлению, стилизации и игре в целом!

Кстати волновой метод намного перспективнее (ну и а* конечно тоже) так как позволяет оч.много что позволяет)) Если следующая игра будет тоже топ-даун скорее всего буду писать эти методы. А пока что других головняков в тавер дефенсе хватает. Скажем так, поиск путей/написание базовой логики монстров и каркас приложения это процентов 10 всей работы...

RaymondGames
3 Февраля 2011
— 23:15
#

@RaymondGames разболелись мы тут немножко, поэтому сорвалась поездка к моему большому сожалению.

Посмотреть и подсказать чего я могу и из дома. Если есть желание пиши на почту ;)

Мне волновой тоже больше чем A* нравится. Движки поиска пути можно не только в top-down играх использовать но и в любых других. Даже в платформерах если очень надо :) Конечно наличие технической части для игры — это лишь малая часть. Вся прелесть игр в контенте и его балансе, а это в свою очередь занимает больше всего времени при разработке.

Ant.Karlov
4 Февраля 2011
— 01:41
#

А как скоро ожидать след. урок?)

Робокоп
4 Февраля 2011
— 20:02
#

@Ant.Karlov есть вариант что скоро запустим тестирование, если это действительно так - приглашаю участвовать! Как только узнаю точно - напишу письмо.

RaymondGames
5 Февраля 2011
— 12:50
#

Антон, спасибо огромное за уроки! Ждем следующего с нетерпением.

Ваше имя
7 Февраля 2011
— 12:01
#

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

У меня в целом одна большая проблема с написанием игры. Я не вижу целостную структуру игры от и до. В основном из-за того, что не могу представить как отдельные функциональные элементы (ИИ, вывод графики, поиск пути, классы персонажей, меню) будут взаимодейстовать друг с другом и как их лучше реализовывать. Сказывается отсутствие опыта.

Примеры простых игр не помогают, там это все слишком упрощено. А уроки из этого блога просто чудо. Я пишу игру, но не могу уверенно продвинутся без помощи ваших уроков.

Скажите, пожалуйста, примерно когда ждать следующего урока. А то я в RSS ридер чуть ли не каждый час заглядываю уже 2 недели))

Алексей
19 Февраля 2011
— 01:42
#

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

Извиняюсь за задержку, немного выбился из рабочего графика последнюю неделю :) Спасибо за терпение!

Ant.Karlov
19 Февраля 2011
— 08:35
#

Антон, к вам такой вопрос, возможно тупой и нубский, но все же меня интересует, почему большинство классов разных экранных обьетктов наследуються именно от Sprite? Почему не от MovieClip допустим?

zag
19 Февраля 2011
— 23:56
#

@zag, MovieClip является потомком класса Sprite и имеет дополнительные свойства и методы (например для работы с анимацией и кадрами) которые как правило нам не нужны для простых объектов. Поэтому намного рациональнее унаследоваться от более упрощенных классов визуального типа если нам нужны простые визуальные свойства. Если же класс вовсе не нуждается в визуальном его представлении то еще лучше наследоваться от Object.

Ant.Karlov
20 Февраля 2011
— 12:37
#

Спасибо, Антон, теперь немного прояснилось)

zag
20 Февраля 2011
— 13:22
#

Антон, Ваша функция EnemyBase.init не задает начальные координаты врагу. Из-за этого все работает только при нулевых начальных координатах. Думаю стоит написать вот так:
[code]
public function init(posX:int, posY:int, targetX:int, targetY:int):void
{
...
// Запоминаем положение и цель врага
_position = new Point(posX, posY);
_target = new Point(targetX, targetY);

x = _position.x * Universe.MAP_CELL_SIZE + Universe.MAP_CELL_HALF;
y = _position.y * Universe.MAP_CELL_SIZE + Universe.MAP_CELL_HALF;
...
}
[/code]

Nikius
2 Марта 2011
— 14:38
#

if (ax >= 0 && ay < _mapWidth && ay >= 0 && ay < _mapHeight)
Тут очепятка, во втором условии вместо ay должно быть ax.
Что интересно и в исходнике так же. :)

Уроки отличные, узнаю для себя много интересного!

Dan4ez
23 Марта 2011
— 18:37
#

еще в функции goWater() перепутано право и лево. :)

Dan4ez
24 Марта 2011
— 12:56
#

@Dan4ez, спасибо за первое замечание. А вот по поводу goWater() — не нужно пугать читателей в самом коде все врено, а комментарии про лево и право перепутаны, да :)

Ant.Karlov
24 Марта 2011
— 21:55
#

Урок отличный, понравился)) Может я невнимательно прочитал или что-то упустил из предыдущих уроков, но в коде EnemyBase.as

// Ищим маршрут
var pathFinder:PathFinder = new PathFinder(_universe.mapMask);

у Universe.as есть приватный массив _mapMask, в общем нжно было указать, чтобы еще геттер повесили

public function get mapMask():Array { return _mapMask}

J0x
10 Апреля 2011
— 08:19
#

хорошая статья, правда немного длинная :) зачет

Scripter
24 Мая 2011
— 19:16
#

А если каждый проход проводить из разных углов?
Получится всего 4 прохода, по количеству углов.

Должно работать.

Денис
26 Июля 2011
— 01:17
#

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

Ant.Karlov
26 Июля 2011
— 09:30
#

Точно, путь может изменяться. Вот еще пара оптимизаций:

1) Сначала перед поиском пути находим направление к цели (например сначала угол от старта до финиша, а потом знаки его sin и cos, но проще будет написать четыре условия), и начинаем пробегать массив уже в этом направлении - в большинстве случаев понадобиться один проход.

2) Если с первого прохода не нашлось (т.е. в обход нужно идти), то дальше пробегаем не весь массив, а только одну строку и один столбец.
Т.е. 1ую итерацию проще вынести за цикл, а в цикле оставить проход по одной строке и одному столбцу.
Количество обращений к массиву в несколько раз снизиться.

Денис@eGanz
26 Июля 2011
— 11:45
#

Так, 2ая оптимизация мимо - путь не будет находится.

Денис@eGanz
26 Июля 2011
— 13:05
#

Привет Антон=)Читаю уроки получаю удовольствие, только вот беда, тестируя и свой и ваш проект обнаружил такую штуку - даже имея маршрут, юнит все равно не двигается, выдается сообщение об отсутствии пути, в чем может быть проблема?

Костик
11 Сентября 2011
— 22:02
#

Супер, очень интересно и легко читается, а главное познавательно !

kadlk
22 Октября 2011
— 17:09
#

Излазил весь исходник, не вижу ошибки и все тут! в окне вывода выдает:
ReferenceError: Error #1056: Не удается создать свойство 19 в Number.
at com.framework::PathFinder/findWay()
at com.towerdefence.enemies::EnemyBase/init()
at com.towerdefence.enemies::EnemySolder/init()
at com.towerdefence::Universe/newEnemy()
at com.towerdefence::Game/keyDownHandler()
и монстр в нулевых координатах топчется. цифры не из головы, все как в уроке. что за?..

zergus
16 Января 2012
— 19:00
#

Реализация поиска пути какая-то мутная и не понятная. Всё гораздо проще на самом деле.

Fear_Factory
2 Апреля 2013
— 15:13
#

В исходниках ошибка в inMap;


ay < _mapWidth вместо ax < _mapWidth

Женя
5 Мая 2014
— 20:38
#

@Nikius
Да, не задается нечальное положение. Причем в тексте говорится, что сейчас мы будем использовтаь метод из прошлого ДЗ, который устанавливает Врага не клетку, а потом этот метод нигде не вызывается и в исходниках его нет

А еще позицию клетки в прошлом задании просили назвать _cellPosX, _cellPosY, а в этом она называется _position

Ну, - you know the dril - "Тщательно обработать напильником" Ю)

Антон, спасибо огромное за уроки!

Дан
2 Июля 2015
— 09:03
#

А еще в EnemyBase/init() было бы логично либо убрать проверку

if (_sprite != null)

либо (лучше) поставить весь код под это условие.

Потому что так у нас если когда-нибудь окажется sprite==null, то враг появится в игре и будет действовать, а на экране ничего не появится.

Дан
2 Июля 2015
— 09:13
#