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

Область применения

Данный метод подходит для 2д игр. А его модификация для нахождения пути к движущимся объектам. Область применения очень обширная и затрагивает множество игровых жанров и ситуаций, например:

1. Игры жанра ТД. Где игровые локации удобно представлять в виде матрицы проходимости, к примеру 0 — участок по которому можно перемещаться, -1 — область недоступная для перемещения, -2 — ловушка и т.д.;
2. Стратегические игры, особенно пошаговые. Например бои в серии игр “Герои Меча и Магии”;
3. Платформеры;
4. Шашки, шахматы, змейка и другие.

Обоснование написания статьи

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

1. Для unity3d реализовано много алгоритмов нахождения кратчайших путей в виде ассетов, то есть готовых решений. Но иногда стоит не брать готовое решение, а написать свое, оптимальное конкретно к вашему случаю. Тем более если в игре много объектов, то плохая реализация алгоритма может сильно повлиять на производительность. И тем более производительность пострадает если этих объектов много и они меняют свое местоположение;
2. Стандартный вариант волнового алгоритма — не самый оптимальный вариант для динамических объектов, поэтому я хочу показать его модификацию, которую разработал во время работы над своей стратегической игрой;
3. В интернете нету хороших, простых, статей на тему реализации волнового алгоритма в 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

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

1. Для отладки будет удобно поделить игровое поле на клетки и отобразить их. Для удобства на этом шаге можно сделать координаты первой клетки равные (0,0), соседней справа (0,1) и тд.
   
2. Теперь создадим класс Battlefield.cs и прикрепим его к объекту «поле» с помощью инспектора.
   
   Battlefield.cs

   using 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). Тогда при создании объекта, его координаты будут совпадать с координатами ячейки в матрице.
   
3. Теперь создадим класс мечника Swordsman.cs и повесим его на префаб мечника
   
   Swordsman.cs

   using 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.

Демонстрация