How to become an author
Search
Write a publication
Pull to refresh

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

Reading time9 min
Views92K
Game development*Unity3D*
From 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:
+10
Comments12
6
Karma
0
Rating
Дмитрий Куратник @KuratnikDmitry

User

Send message

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr