Pull to refresh

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

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

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

Tags:
Hubs:
Total votes 20: ↑15 and ↓5 +10
Views 81K
Comments Comments 12