Реализация волнового алгоритма нахождения кратчайшего пути к динамически движущимся объектам в unity3d на C# в 2d игре

В данной статье я хочу показать как реализовать волновой алгоритм и мою модификацию его для работы с динамическими объектами в 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.

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

Метки:
Поделиться публикацией
Похожие публикации
Комментарии 12
  • +1
    Мне статья нравится. Особенно нравится подход, когда пробуют все своими руками. Но есть пара замечаний.
    1) Вы используете термины, которе тут абсолютно лишние: «окрестности Мура», «окрестности фон Неймана». Статья написана для неискушенного пользователя, а вот такие термины, как бы намекают на очень сильную связь с научным трактатом. А ведь можно было смело без терминов обойтись.
    2) Либо у конкретно вашей реализации, либо у волнового алгоритма в целом нету возможности задать «проходимость клетки», то есть поиск пути в ситуации, где клетки могут быть пройдены с разной скоростью и «кратчайший» != «оптимальный». Например может будет быстрее пробежать по мосту, чем плыть через реку.
    • 0
      Кстати, идея… А что, если задать целочисленную цену (штраф) прохода у ячейки и задерживать волну в клетке соответственно штрафу прохода? Фронты волны двигать как в пошаговой стратегии — итерациями.
      • 0
        Тогда количество итераций будет расти вместе со «штрафом». Во взвешенном графе лучше искать алгоритмом Дейкстра.
      • 0
        Спасибо, на самом деле без терминов будет лучше, поправил
        • 0
          2) Конкретно в моей реализации нету возможности. А вообще такая возможность есть. тогда нужно клетке с плохой проходимостью ставить не 0, а например 2 если это поле, 4 если это болото и тд. В таком случае нужно будет поправить проверку на «уже помеченную клетку», так как сравнение с 0 не подойдет. Если будет необходимость, могу описать как это сделать или помочь в реализации.
          В эту стаью не включал, так как не хотел усложнять. Цель — максимально доступно и понятно описать алгоритм на практическом примере.
        • 0
          Кратчайший путь, по определению, имеющий минимальную длину в «километрах». Умный в гору не пойдёт, умный гору обойдёт. Но, если лезть через гору будет короче, то это и будет кратчайшим путём. А вот для поиска оптимального пути уже можно (нужно) учитывать скорость прохождения участков. Тогда нужно использовать взвешенный граф, а не просто граф, как при волновой трассировке.
        • 0
          Если у кого-то будут замечания по статье или коду, напишите мне на хабре или на почту devmobby@gmail.com. Исправлю.
          • 0
            Если карта не очень большая, может быть проще заранее посчитать кратчайшие пути из каждой точки в каждую точку (пропуская точки с препятствиями, конечно)? Например, алгоритмом Флойда-Уоршелла.
            • 0
              Если я правильно понял суть Вашей модификации алгоритма, то Ваш юнит застрянет, встретив на пути препятствие нетривиальной конфигурации.
              • 0
                Если Вы говорите о проблеме локального оптимума, то вот здесь автор предложил решение. Правда, в той статье рассматривался метод потенциальных полей, но, я думаю, идею можно адаптировать и для волнового алгоритма.
                • +1
                  Не знаю, что там с локальным оптимумом, я говорю конкретно вот об этом:
                  Теперь нам всеголишь нужно пройтись по соседним клеткам. Посчитать расстояние с каждой соседней клетки до объекта F и переместиться в ячейку с минимальным расстоянием.

                  И следующим за ним куском кода. То есть, автор взял волновой алгоритм и выкинул из него… волновой алгоритм. И теперь объект не ищет маршрут, а просто как по компасу стремится сократить расстояние между собой и целью. Что будет, если на пути его окажется препятствие — представить не трудно.
              • 0
                Код можно значительно ускорить и немного обезопасить:
                1. Ограничить количество шагов поиска пути, т.к. если юнит окажется заперт то алгоритм зациклится.
                2. Значительно увеличить скорость поиска пути можно проверяя только граничные клетки. Для этого можно сохранять их в массив например. Новые граничные клетки соответственно сохранять во второй массив и в конце итерации обменивать массивы местами. Тогда не придется при каждой итерации просматривать всю карту, это значительно повышает скорость работы. Особенно на очень запутанных картах.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.