SavePearlHarbor

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

—

от автора

admin

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

Теперь нам всеголишь нужно пройтись по окрестности Мура (соседним с объектом S 8-и клеткам). Посчитать расстояние с каждой соседней клетки до объекта 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.

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

ссылка на оригинал статьи http://habrahabr.ru/post/264189/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *