В данной статье я хочу показать как реализовать волновой алгоритм и мою модификацию его для работы с динамическими объектами в unity3d.
Данный метод подходит для 2д игр. А его модификация для нахождения пути к движущимся объектам. Область применения очень обширная и затрагивает множество игровых жанров и ситуаций, например:
В интернете достаточно много статьей по работе с алгоритмами нахождения кратчайшего пути, но при этом все равно постоянно создают темы на форумах, задают вопросы “как найти путь до объекта”. Я выделил несколько причин почему эта статья имеет право на существование:
Есть стартовая позиция S и точка F, до которой нужно добраться избегая препятствий кратчайшим путем. Волновой алгоритм один из самых быстрых и эффективных, но забегая вперед расскажу почему он не идеальный для нахождения пути к движущимся объектам. В случае, если объект стоит на месте, мы можем один раз найти путь к нему и начать двигаться. Но если же этот объект двигается, то нам нужно пересчитывать путь к нему каждый игровой такт, то есть каждый вызов метода Update().
А если у вас в игре участвуют сотни-тысячи юнитов? И каждый считает путь, да еще и каждый вызов метода Update()? Например сражение 500 на 500, при 30 кадров в секунду, придется вызывать метод FindPath() 1000 * 30 = 30 000 раз в секунду.
Для работы нам потребуется дискретное рабочее поле, или просто карта локации представленная в матричном виде.
Пример карты локации (или матрицы проходимости):
-1 — непроходимый участок, стена или бревно.
0 — проходимый участок.
Инициализация
Распространение волны
Восстановление пути
Демонстрация будет проводиться на примере прототипа моей стратегической игры. Есть сторона игрока и сторона противника, задача воинов найти ближайшего врага, дойти до него обходя других воинов и препятствия и начать сражение.
Как я раньше и писал, метод findPath() приходиться вызывать каждому юниту в методе Update(). Потому что враги так же перемещаются как и юниты игрока. И через 1 игровой такт, враг может поменять позицию, и старый путь будет не актуальный.
Получается следующая ситуация, мы нашли путь к врагу. переместились в клетку с минимальным весом. Враг поменял свое местоположение, мы снова просчитали путь до него, снова переместились в клетку с минимальным весов.
В данном случае мы используем только те клетки, которые соседние к нашему юниту, а весь остальной путь нам не нужен. Тогда нам не нужно высчитывать весь путь до врага. А нужно лишь узнать на какую соседнюю клетку переместить юнита, чтобы он был ближе всего к врагу.
Объект к которому нам нужно дойти назовем F. А объект который ищет путь к F назовем S. В unity3d очень просто посчитать расстояние от S до F.
Теперь нам всеголишь нужно пройтись по соседним клеткам. Посчитать расстояние с каждой соседней клетки до объекта F и переместиться в ячейку с минимальным расстоянием.
Находим в массиве neighbors минимальное значение и индекс ячейки. Далее по индексу ячейки определяем координаты ячейки, куда нужно переместить объект S. Повторять до тех пор, пока не дойдем до цели F.
Область применения
Данный метод подходит для 2д игр. А его модификация для нахождения пути к движущимся объектам. Область применения очень обширная и затрагивает множество игровых жанров и ситуаций, например:
- Игры жанра ТД. Где игровые локации удобно представлять в виде матрицы проходимости, к примеру 0 — участок по которому можно перемещаться, -1 — область недоступная для перемещения, -2 — ловушка и т.д.;
- Стратегические игры, особенно пошаговые. Например бои в серии игр “Герои Меча и Магии”;
- Платформеры;
- Шашки, шахматы, змейка и другие.
Обоснование написания статьи
В интернете достаточно много статьей по работе с алгоритмами нахождения кратчайшего пути, но при этом все равно постоянно создают темы на форумах, задают вопросы “как найти путь до объекта”. Я выделил несколько причин почему эта статья имеет право на существование:
- Для unity3d реализовано много алгоритмов нахождения кратчайших путей в виде ассетов, то есть готовых решений. Но иногда стоит не брать готовое решение, а написать свое, оптимальное конкретно к вашему случаю. Тем более если в игре много объектов, то плохая реализация алгоритма может сильно повлиять на производительность. И тем более производительность пострадает если этих объектов много и они меняют свое местоположение;
- Стандартный вариант волнового алгоритма — не самый оптимальный вариант для динамических объектов, поэтому я хочу показать его модификацию, которую разработал во время работы над своей стратегической игрой;
- В интернете нету хороших, простых, статей на тему реализации волнового алгоритма в unity3d.
Описание волнового алгоритма
Есть стартовая позиция S и точка F, до которой нужно добраться избегая препятствий кратчайшим путем. Волновой алгоритм один из самых быстрых и эффективных, но забегая вперед расскажу почему он не идеальный для нахождения пути к движущимся объектам. В случае, если объект стоит на месте, мы можем один раз найти путь к нему и начать двигаться. Но если же этот объект двигается, то нам нужно пересчитывать путь к нему каждый игровой такт, то есть каждый вызов метода Update().
А если у вас в игре участвуют сотни-тысячи юнитов? И каждый считает путь, да еще и каждый вызов метода Update()? Например сражение 500 на 500, при 30 кадров в секунду, придется вызывать метод FindPath() 1000 * 30 = 30 000 раз в секунду.
Для работы нам потребуется дискретное рабочее поле, или просто карта локации представленная в матричном виде.
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 -1 -1 -1 -1 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 0 0 0 0 0 0 0 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Пример карты локации (или матрицы проходимости):
-1 — непроходимый участок, стена или бревно.
0 — проходимый участок.
Алгоритм
Инициализация
Пометить стартовую ячейку 0
d := 0
Распространение волны
ЦИКЛ
ДЛЯ каждой ячейки loc, помеченной числом d
пометить все соседние свободные не помеченные ячейки числом d + 1
КЦ
d := d + 1
ПОКА (финишная ячейка не помечена) И (есть возможность распространения волны, шаг < количества ячеек)
Восстановление пути
ЕСЛИ финишная ячейка помечена
ТО
перейти в финишную ячейку
ЦИКЛ
выбрать среди соседних ячейку, помеченную числом на 1 меньше числа в текущей ячейке
перейти в выбранную ячейку и добавить её к пути
ПОКА текущая ячейка — не стартовая
ВОЗВРАТ путь найден
ИНАЧЕ
ВОЗВРАТ путь не найден
Реализация алгоритма в unity3d
Демонстрация будет проводиться на примере прототипа моей стратегической игры. Есть сторона игрока и сторона противника, задача воинов найти ближайшего врага, дойти до него обходя других воинов и препятствия и начать сражение.
- Для отладки будет удобно поделить игровое поле на клетки и отобразить их. Для удобства на этом шаге можно сделать координаты первой клетки равные (0,0), соседней справа (0,1) и тд.
- Теперь создадим класс Battlefield.cs и прикрепим его к объекту «поле» с помощью инспектора.
Battlefield.csusing UnityEngine; using System.Collections; public class Battlefield2 : MonoBehaviour { public static int[,] battlefield; // матрица местности public int enemyNumber = 6, playerNumber = 3; //public для возможности редактировать через инспектор public static int x, y; // ширина и высота поля public GameObject enemyMilitiaman; //префаб ополченца врага public GameObject swordsmanGO; //префаб мечника. public static bool ready = false; //мы не сможем начать искать путь, пока не разместим юнитов на поле. void Start () { battlefield = new int[,]{ // матрица нашей локации. 1 - стена. 0 - свободная клетка {1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,0,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; setEnemyPosition (enemyNumber); // размещаем врагов на поле setPlayerPosition (playerNumber); // размещаем воинов игрока ready = true; // можем начинать искать путь } // Update is called once per frame void Update () { } void setEnemyPosition(int numberEnemies){ ////// ////// РАЗМЕСТИТЕ ЮНИТОВ КАК ВАМ НЕОБХОДИМО, В ДАННОМ ПРИМЕРЕ ЭТО БУДЕТ 1 ЮНИТ НА (14,2) ///// // создаем объект противника GameObject go = Instantiate(enemyMilitiaman, new Vector3(14, 2, 10), Quaternion.identity) as GameObject; battlefield[14, 2] = 1; // обязательно запишите в карту локации, что клетка, на которой находится воин, занята. } void setPlayerPosition(int numberPlayerWarior){ ////// ////// РАЗМЕСТИТЕ ЮНИТОВ КАК ВАМ НЕОБХОДИМО, В ДАННОМ ПРИМЕРЕ ЭТО БУДЕТ 1 ЮНИТ НА (2,6) ///// GameObject go = Instantiate(swordsmanGO, new Vector3(2, 6, 10), Quaternion.identity) as GameObject; battlefield[2, 6] = 1; } public static void printMatrix(){ string arr = ""; for (int i = 0; i < x; i++) { for (int j = 0; j < y; j++) { arr += battlefield[i,j] + ","; } arr += "\n"; } print (arr); } }
Код закомментирован и не должен вызвать у вас затруднений.
В классе Battlefield мы создаем карту локации (матрицу), описывающую нашу локацию. Дале вызываем методы которые размещают юнитов игрока и врага на игровом полею В этих же методах записываем в ячейку матрицы на которой разместили юнита, что она уже занята и делаем ее непроходимой изменив значение с 0 на 1. Вот поэтому важно было сделать координаты клеток в игровом поле целыми числами и начинать отсчет с (0,0). Тогда при создании объекта, его координаты будут совпадать с координатами ячейки в матрице.
- Теперь создадим класс мечника Swordsman.cs и повесим его на префаб мечника
Swordsman.csusing UnityEngine; using System.Collections; using System; public class Swordsman2 : Warrior { private Vector3 currentPosition; private Vector3 lastPosition; private bool ready = true; private bool readyAttack = true; private bool endBattle = false; private GameObject closestEnemy; //ближайший враг GameObject[] gos; // массив всех врагов private float waitMove; // будем перемещать юнитов с задержкой void Start () { currentPosition = transform.localPosition; // сохраняем текущую позицию lastPosition = currentPosition; // сохраняем последную позицию юнита. // определяем с какой задержкой будет двигаться юнит waitMove = UnityEngine.Random.Range (0.4f, 0.65f); } void Update () { // если все юниты размещены на игровом поле if (Battlefield.ready) { if(ready){ //ищем всех врагов, заранее пометив их тегом Enemy gos = GameObject.FindGameObjectsWithTag("Enemy"); if(gos.Length == 0){ endBattle = true; // если врагов нету, то конец сражения print ("End Battle"); } //еслі есть врагі, то ходім if(!endBattle){ //находим ближайшего врага и его координаты GameObject goClosestEnemy = findClosestEnemy(); int targetX, targetY; targetX = (int)goClosestEnemy.transform.localPosition.x; targetY = (int)goClosestEnemy.transform.localPosition.y; int[,] cMap = findWave(targetX, targetY); // находим путь до ближайшего врага if(!stopMove(targetX, targetY)) // двигаемся, если цель не на соседней клетке // вызываем каротину для перемещения с задержкой StartCoroutine(move(cMap, targetX, targetY)); if(readyAttack){//атакуем, если дошли до цели if(stopMove(targetX, targetY)){ StartCoroutine(attack()); } } } // запоминаем новую позицию после перемещения и делаем ее текущей currentPosition = transform.localPosition; //помечаем, что клетка занята воином Battlefield.battlefield[(int)currentPosition.x, (int)currentPosition.y] = 1; //если мы переместились, то на старой клетки пишем, что она освободилась if (currentPosition != lastPosition) { Battlefield.battlefield[(int)lastPosition.x, (int)lastPosition.y] = 0; lastPosition = currentPosition; // запоминаем текущее рассположение как последнее } } } } private IEnumerator attack(){ readyAttack = false; // для того, чтобы юнит атакова 1 раз в 0.8 секунды yield return new WaitForSeconds(0.8f); //////// ////////РЕАЛИЗУЕМ МЕТОД АТАКИ ВРАГА //////// readyAttack = true; } /// <summary>РЕАЛИЗАЦИЯ ВОЛНОВОГО АЛГОРИТМА /// </summary> /// <param name="cMap">Копия карты локации</param> /// <param name="targetX">координата цели x</param> /// <param name="targetY">координата цели y</param> private IEnumerator move(int[,] cMap, int targetX, int targetY){ ready = false; int[] neighbors = new int[8]; //значение весов соседних клеток // будем хранить в векторе координаты клетки в которую нужно переместиться Vector3 moveTO = new Vector3(-1,0,10); // да да да, можно было сделать через цикл for neighbors[0] = cMap[(int)currentPosition.x+1, (int)currentPosition.y+1]; neighbors[1] = cMap[(int)currentPosition.x, (int)currentPosition.y+1]; neighbors[2] = cMap[(int)currentPosition.x-1, (int)currentPosition.y+1]; neighbors[3] = cMap[(int)currentPosition.x-1, (int)currentPosition.y]; neighbors[4] = cMap[(int)currentPosition.x-1,(int) currentPosition.y-1]; neighbors[5] = cMap[(int)currentPosition.x, (int)currentPosition.y-1]; neighbors[6] = cMap[(int)currentPosition.x+1,(int) currentPosition.y-1]; neighbors[7] = cMap[(int)currentPosition.x+1,(int) currentPosition.y]; for(int i = 0; i < 8; i++){ if(neighbors[i] == -2) // если клетка является непроходимой, делаем так, чтобы на нее юнит точно не попал // делаем этот костыль для того, чтобы потом было удобно брать первый элемент в // отсортированом по возрастанию массиве neighbors[i] = 99999; } Array.Sort(neighbors); //первый элемент массива будет вес клетки куда нужно двигаться //ищем координаты клетки с минимальным весом. for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) { for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) { if(cMap[x,y] == neighbors[0]){ // и указываем вектору координаты клетки, в которую переместим нашего юнита moveTO = new Vector3(x,y,10); } } } //если мы не нашли куда перемещать юнита, то оставляем его на старой позиции. // это случается, если вокруг юнита, во всех 8 клетках, уже размещены другие юниты if(moveTO == new Vector3(-1,0,10)) moveTO = new Vector3(currentPosition.x, currentPosition.y, 10); //и ура, наконец-то мы перемещаем нашего юнита // теперь он на 1 клетку ближе к врагу transform.localPosition = moveTO; //устанавливаем задержку. yield return new WaitForSeconds(waitMove); ready = true; } //Ищмем путь к врагу //TargetX, TargetY - координаты ближайшего врага public int[,] findWave(int targetX, int targetY){ bool add = true; // условие выхода из цикла // делаем копию карты локации, для дальнейшей ее разметки int[,] cMap = new int[Battlefield.X, Battlefield.Y]; int x, y, step = 0; // значение шага равно 0 for (x = 0; x < Battlefield.x; x++) { for (y = 0; y < Battlefield.y; y++) { if(Battlefield.battlefield[x,y] == 1) cMap[x,y] = -2; //если ячейка равна 1, то это стена (пишим -2) else cMap[x,y] = -1; //иначе еще не ступали сюда } } //начинаем отсчет с финиша, так будет удобней востанавливать путь cMap[targetX,targetY] = 0; while (add == true) { add = false; for (x = 0; x < Battlefield.x; x++) { for (y = 0; y < Battlefield.y; y++) { if(cMap[x,y] == step){ // если соседняя клетка не стена, и если она еще не помечена // то помечаем ее значением шага + 1 if(y - 1 >= 0 && cMap[x, y - 1] != -2 && cMap[x, y - 1] == -1) cMap[x, y - 1] = step + 1; if(x - 1 >= 0 && cMap[x - 1, y] != -2 && cMap[x - 1, y] == -1) cMap[x - 1, y] = step + 1; if(y + 1 >= 0 && cMap[x, y + 1] != -2 && cMap[x, y + 1] == -1) cMap[x, y + 1] = step + 1; if(x + 1 >= 0 && cMap[x + 1, y] != -2 && cMap[x + 1, y] == -1) cMap[x + 1, y] = step + 1; } } } step++; add = true; if(cMap[(int)transform.localPosition.x, (int)transform.localPosition.y] > 0) //решение найдено add = false; if(step > Battlefield.X * Battlefield.Y) //решение не найдено, если шагов больше чем клеток add = false; } return cMap; // возвращаем помеченную матрицу, для востановления пути в методе move() } // если в сосденей клетки есть враг, то останавливаемся public bool stopMove(int targetX, int targetY){ bool move = false; for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) { for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) { if(x == targetX && y == targetY){ move = true; } } } return move; } // ищмем ближайшего врага GameObject findClosestEnemy() { float distance = Mathf.Infinity; Vector3 position = transform.position; foreach (GameObject go in gos) { float curDistance = Vector3.Distance(go.transform.position,position); if (curDistance < distance) { closestEnemy = go; distance = curDistance; } } return closestEnemy; } }
Каждый шаг подробно описан в комментариях к коду.
В методе Update() проверяем, если есть враг, то ищем ближайшего. Далее вызываем метод findPath(), который ищет путь. За ним вызываем метод move(), который перемещает объект на 1 клетку в сторону врага, если объект еще не дошел до цели. Если объект уже дошел до цели, тогда вызываем метод attack().
Модификация волнового алгоритма для динамический объектов
Как я раньше и писал, метод findPath() приходиться вызывать каждому юниту в методе Update(). Потому что враги так же перемещаются как и юниты игрока. И через 1 игровой такт, враг может поменять позицию, и старый путь будет не актуальный.
Получается следующая ситуация, мы нашли путь к врагу. переместились в клетку с минимальным весом. Враг поменял свое местоположение, мы снова просчитали путь до него, снова переместились в клетку с минимальным весов.
В данном случае мы используем только те клетки, которые соседние к нашему юниту, а весь остальной путь нам не нужен. Тогда нам не нужно высчитывать весь путь до врага. А нужно лишь узнать на какую соседнюю клетку переместить юнита, чтобы он был ближе всего к врагу.
Объект к которому нам нужно дойти назовем F. А объект который ищет путь к F назовем S. В unity3d очень просто посчитать расстояние от S до F.
float curDistance = Vector3.Distance(F.transform.position, S.transform.position);
Теперь нам всеголишь нужно пройтись по соседним клеткам. Посчитать расстояние с каждой соседней клетки до объекта F и переместиться в ячейку с минимальным расстоянием.
float[] neighbors = new int[9];
int n = 0;
Vector3 goTo;
for (int x = (int)currentPosition.x-1; x <= (int)currentPosition.x+1; x++) {
for (int y = (int)currentPosition.y+1; y >= (int)currentPosition.y-1; y--) {
float curDistance = Vector3.Distance(new Vector3(x,y,0), S.transform.position);
neighbors[n] = curDistance;
}
}
Находим в массиве neighbors минимальное значение и индекс ячейки. Далее по индексу ячейки определяем координаты ячейки, куда нужно переместить объект S. Повторять до тех пор, пока не дойдем до цели F.