Движение по клеткам, волновой алгоритм

Наша задача, организовать движение юнитов по клеткам, как в пошаговых стратегиях, наподобие King's Bounty и похожих. То есть, речь идет о небольшом поле, типа шахматной доски, где собственно и происходит бой юнитов. Существуют различные алгоритмы поиска пути в двумерном массиве, у каждого из них есть свои достоинства и недостатки. В нашем же случаи, мы будем использовать волновой алгоритм (Алгоритм Ли), он отлично подходит под наши задачи, понятен и прост в освоении. Реализация проекта, состоит из двух частей. Первая, это сам алгоритм и подготовка поля боя (массива) для него. Вторая часть, управление юнитами, создание маршрута движения и вектора вращения.


Тем кто играл в игры с пошаговыми боями, хорошо известно, что в процессе боя, на поле могут появляться временные объекты. Исходя из этого, нам нужно учитывать, что состояние клеток поля может меняться не только после хода, но и до него. Поэтому, для обновления состояния поля, мы будем использовать рейкаст, чтобы проверить занята-ли клетка и какой объект ее занимает.

Пара слов о модели юнита:

Движение по клеткам, волновой алгоритм

Модель нужно создавать так, чтобы "лицо" юнита было по направлению оси Z. Так же, у юнита должен быть коллайдер и установлен стандартный тег Player, данный тег означает, что объектом можно управлять. Для 2D спрайта "лицо" модельки, это ось Х.

Шаблон клетки, это квадрат, мы рекомендуем стандартный Quad, так как его начальный размер равен единице. На шаблоне так же должен быть коллайдер, в режиме триггера, плюс, нужно установить для него отдельный слой, который потом указывается в настройках скрипта, это нужно, чтобы луч поиска клетки не "цеплялся" за другие объекты.

На шаблон клетки вешаем скрипт:

using System.Collections;
using UnityEngine;

public class PathfindingNode : MonoBehaviour {

	public int x { get; set; }
	public int y { get; set; }
	public int cost { get; set; }
	public Transform target { get; set; }
	public bool isLock { get; set; }
	public bool isPlayer { get; set; }
	public MeshRenderer mesh; // указываем меш клетки

}

Здесь у нас несколько переменных для хранения данных массива и состояния поля.

Волновой алгоритм с поиском пути:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class Pathfinding {

	public static List<PathfindingNode> Find(PathfindingNode start, PathfindingNode end, PathfindingNode[,] map, int width, int height)
	{
		int x, y, cost = 0, step = 0;

		map[end.x, end.y].cost = 0; // начало поиска с точки назначения

		if(start.x - 1 >= 0)
		{
			if(map[start.x-1, start.y].cost == -2) step++;
		}
		else step++;

		if(start.y-1 >= 0)
		{
			if(map[start.x, start.y-1].cost == -2) step++;
		}
		else step++;

		if(start.x+1 < width)
		{
			if(map[start.x+1, start.y].cost == -2) step++;
		}
		else step++;

		if(start.y+1 < height)
		{
			if(map[start.x, start.y+1].cost == -2) step++;
		}
		else step++;

		// проверка на доступность (например, юнит окружен)
		if(step == 4) return null; else step = 0;

		while(true) // цикл поиска
		{
			for(y = 0; y < height; y++)
			{
				for(x = 0; x < width; x++)
				{
					if(map[x, y].cost == step) // находим клетку, соответствующую текущему шагу
					{
						if(x-1 >= 0) // если не выходим за границы массива
						if(map[x-1, y].cost == -1) // если клетка еще не проверялась
						{
							cost = step + 1; // сохраняем стоимость клетки
							map[x-1, y].cost = cost; // назначаем стоимость
						}

						if(y-1 >= 0)
						if(map[x, y-1].cost == -1)
						{
							cost = step + 1;
							map[x, y-1].cost = cost;
						}

						if(x+1 < width)
						if(map[x+1, y].cost == -1)
						{
							cost = step + 1;
							map[x+1, y].cost = cost;
						}

						if(y+1 < height)
						if(map[x, y+1].cost == -1)
						{
							cost = step + 1;
							map[x, y+1].cost = cost;
						}
					}
				}
			}

			step++; // следующий шаг/волна

			if(map[start.x, start.y].cost != -1) break; // если путь найден, выходим из цикла
			if(step != cost || step > width * height) return null; // если путь найти невозможно, возврат
		}

		List<PathfindingNode> result = new List<PathfindingNode>(); // массив пути

		// начало поиска со старта
		x = start.x;
		y = start.y;

		step = map[x, y].cost; // определяем базовую стоимость

		while(x != end.x || y != end.y) // прокладка пути
		{
			if(x-1 >= 0 && y-1 >= 0) // если не выходим за границы массива
			if(map[x-1, y-1].cost >= 0) // если клетка проходима
			if(map[x-1, y-1].cost < step) // если эта клетка дешевле, базовой стоимости
			{
				step = map[x-1, y-1].cost; // новая базовая стоимость
				result.Add(map[x-1, y-1]); // добавляем клетку в массив пути
				x--;
				y--;
				continue; // переходим на следующий цикл
			}

			if(y-1 >= 0 && x+1 < width)
			if(map[x+1, y-1].cost >= 0)
			if(map[x+1, y-1].cost < step)
			{
				step = map[x+1, y-1].cost;
				result.Add(map[x+1, y-1]);
				x++;
				y--;
				continue;
			}

			if(y+1 < height && x+1 < width)
			if(map[x+1, y+1].cost >= 0)
			if(map[x+1, y+1].cost < step)
			{
				step = map[x+1, y+1].cost;
				result.Add(map[x+1, y+1]);
				x++;
				y++;
				continue;
			}

			if(y+1 < height && x-1 >= 0)
			if(map[x-1, y+1].cost >= 0)
			if(map[x-1, y+1].cost < step)
			{
				step = map[x-1, y+1].cost;
				result.Add(map[x-1, y+1]);
				x--;
				y++;
				continue;
			}

			if(x-1 >= 0)
			if(map[x-1, y].cost >= 0)
			if(map[x-1, y].cost < step)
			{
				step = map[x-1, y].cost;
				result.Add(map[x-1, y]);
				x--;
				continue;
			}

			if(y-1 >= 0)
			if(map[x, y-1].cost >= 0)
			if(map[x, y-1].cost < step)
			{
				step = map[x, y-1].cost;
				result.Add(map[x, y-1]);
				y--;
				continue;
			}

			if(x+1 < width)
			if(map[x+1, y].cost >= 0)
			if(map[x+1, y].cost < step)
			{
				step = map[x+1, y].cost;
				result.Add(map[x+1, y]);
				x++;
				continue;
			}

			if(y+1 < height)
			if(map[x, y+1].cost >= 0)
			if(map[x, y+1].cost < step)
			{
				step = map[x, y+1].cost;
				result.Add(map[x, y+1]);
				y++;
				continue;
			}

			return null; // текущая клетка не прошла проверку, ошибка пути, возврат
		}

		return result; // возвращаем найденный маршрут
	}
}

Конечный результат выдается в виде массива клеток, которые ведут от юнита и до цели.

Далее, на сцену вешаем:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class PathfindingField : MonoBehaviour {

	[SerializeField] private Color defaultColor; // цвет клетки по умолчанию
	[SerializeField] private Color pathColor; // подсветка пути
	[SerializeField] private Color cursorColor; // подсветка указателя
	[SerializeField] private LayerMask layerMask; // маска клетки
	[SerializeField] private int width;
	[SerializeField] private int height;
	[SerializeField] [Range(1f, 10f)] private float moveSpeed = 1;
	[SerializeField] [Range(0.1f, 1f)] private float rotationSpeed = 0.25f;
	[SerializeField] private PathfindingNode[] grid;
	private List<PathfindingNode> path;
	private List<TargetPath> pathTarget;
	private PathfindingNode start, end, last;
	private Transform target;
	private int hash, index;
	private bool move;
	private PathfindingNode[,] map;
	private static PathfindingField _inst;

	void Awake()
	{
		_inst = this;
		BuildMap();
	}

	// обновление состояния клеток поля, эту функцию нужно вызывать, если на поле появляются новые объекты или уничтожаются имеющиеся
	public static void UpdateNodeState()
	{
		_inst.UpdateNodeState_inst();
	}

	void BuildMap() // инициализация двумерного массива
	{
		map = new PathfindingNode[width, height];
		int i = 0;
		for(int y = 0; y < height; y++)
		{
			for(int x = 0; x < width; x++)
			{
				grid[i].x = x;
				grid[i].y = y;
				map[x,y] = grid[i];
				i++;
			}
		}

		UpdateNodeState_inst();
	}

	Vector3 NormalizeVector(Vector3 val) // округляем вектор до сотых
	{
		val.x = Mathf.Round(val.x * 100f)/100f;
		val.y = Mathf.Round(val.y * 100f)/100f;
		val.z = Mathf.Round(val.z * 100f)/100f;
		return val;
	}

	struct TargetPath
	{
		public Vector3 direction, position;
	}

	void BuildUnitPath() // создание точек движения и вектора вращения для юнита, на основе найденного пути
	{
		TargetPath p = new TargetPath();
		pathTarget = new List<TargetPath>();
		Vector3 directionLast = (path[0].transform.position - target.position).normalized;

		p.direction = directionLast;
		p.position = NormalizeVector(target.position);
		pathTarget.Add(p);

		if(end.target != null) path.RemoveAt(path.Count-1);

		for(int i = 0; i < path.Count; i++)
		{
			int id = (i+1 < path.Count-1) ? i+1 : path.Count-1;
			Vector3 direction = (path[id].transform.position - path[i].transform.position).normalized;

			if(direction != directionLast)
			{
				p = new TargetPath();
				p.direction = (i < path.Count-1) ? direction : directionLast;
				p.position = NormalizeVector(path[i].transform.position);
				pathTarget.Add(p);
			}

			directionLast = direction;
		}
	}

	void UpdateMove()
	{
		if(!move) return;

		if(NormalizeVector(pathTarget[index].direction) != NormalizeVector(target.forward))
		{
			// анимация поворота юнита по вектору движения
			target.rotation = Quaternion.Lerp(target.rotation, Quaternion.LookRotation(pathTarget[index].direction), rotationSpeed);
		}
		else if(index < pathTarget.Count-1)
		{
			// анимация движения к следующей точке
			target.position = Vector3.MoveTowards(target.position, pathTarget[index+1].position, moveSpeed * Time.deltaTime);
			if(Vector3.Distance(target.position, pathTarget[index+1].position) < 0.1f)
			{
				target.position = pathTarget[index+1].position;
				index++;
			}
		}
		else if(pathTarget.Count > 0 && index == pathTarget.Count-1 && end.target != null && start.isPlayer)
		{
			// если юнита направили на другого юнита, когда он дойдет до него
			// добавляем еще одну точку с текущей позицией и новым направлением, чтобы юнит развернулся "носом" к цели
			TargetPath p = new TargetPath();
			p.direction = (end.target.position - target.position).normalized;
			p.position = target.position;
			pathTarget.Add(p);
			start.isPlayer = false;
			index++;
		}
		else // если юнит достиг цели
		{
			if(end.target == null)
			{
				// анимация ожидания
			}
			else
			{
				// анимация атаки
			}

			UpdateNodeState_inst();
			start.isPlayer = false;
			start = null;
			end = null;
			hash = 0;
			move = false;
		}
	}

	void LateUpdate()
	{
		UpdateMove();
		if(move) return;

		RaycastHit hit;
		Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
		if(Physics.Raycast(ray, out hit, Mathf.Infinity, layerMask))
		{
			PathfindingNode node = hit.transform.GetComponent<PathfindingNode>();

			if(node == null || node.isLock && node.target == null) return;

			if(Input.GetMouseButtonDown(0))
			{
				if(node.target != null && end == null)
				{
					if(start != null) start.isPlayer = false;
					start = node;
					node.isPlayer = true;
					node.cost = -1;
					node.mesh.material.color = pathColor;
				}
				else if(end != null)
				{
					target = start.target;
					BuildUnitPath();
					index = 0;
					move = true;
				}
			}
			else if(Input.GetMouseButtonDown(1) && start != null)
			{
				start.isPlayer = false;
				FieldUpdate();
				start = null;
				end = null;
				hash = 0;
			}

			if(hash != node.GetInstanceID())
			{
				if(last != null && !last.isPlayer) last.mesh.material.color = defaultColor;
				if(!node.isPlayer) node.mesh.material.color = cursorColor;

				if(start != null && end != null)
				{
					FieldUpdate();
					end = null;
				}

				if(start != null && node != null)
				{
					end = node;

					path = Pathfinding.Find(start, node, map, width, height);

					if(path == null)
					{
						FieldUpdate();
						start = null;
						end = null;
						hash = 0;
						return;
					}

					for(int i = 0; i < path.Count; i++)
					{
						path[i].mesh.material.color = pathColor;
					}
				}
			}

			last = node;
			hash = node.GetInstanceID();
		}
	}

	void UpdateNodeState_inst() // обновления поля, после совершения действия
	{
		for(int i = 0; i < grid.Length; i++)
		{
			RaycastHit hit; // пускаем луч сверху на клетку, проверяем занята она или нет
			Physics.Raycast(grid[i].transform.position + Vector3.up * 100f, Vector3.down, out hit, 100f, ~layerMask);

			if(hit.collider == null) // пустая клетка
			{
				grid[i].target = null;
				grid[i].isLock = false;
				grid[i].isPlayer = false;
				grid[i].cost = -1; // свободное место
			}
			else if(hit.collider.tag == "Player") // найден юнит
			{
				grid[i].target = hit.transform;
				grid[i].isLock = true;
				grid[i].isPlayer = false;
				grid[i].cost = -2; // препятствие
			}
			else // любой другой объект/препятствие
			{
				grid[i].isLock = true;
				grid[i].cost = -2;
			}

			grid[i].mesh.material.color = defaultColor;
		}
	}

	void FieldUpdate() // обновление поля, перед подсветкой пути
	{
		for(int i = 0; i < grid.Length; i++)
		{
			if(grid[i].isPlayer)
			{
				grid[i].cost = -1;
			}
			else if(grid[i].isLock)
			{
				grid[i].cost = -2;
				grid[i].mesh.material.color = defaultColor;
			}
			else
			{
				grid[i].mesh.material.color = defaultColor;
				grid[i].cost = -1;
			}
		}
	}

	#if UNITY_EDITOR
	[SerializeField] private PathfindingNode sample; // шаблон клетки
	[SerializeField] private float sampleSize = 1; // размер клетки
	public void CreateGrid()
	{
		for(int i = 0; i < grid.Length; i++)
		{
			if(grid[i] != null) DestroyImmediate(grid[i].gameObject);
		}

		grid = new PathfindingNode[width * height];

		float posX = -sampleSize * width / 2f - sampleSize / 2f;
		float posY = sampleSize * height / 2f - sampleSize / 2f;
		float Xreset = posX;
		int z = 0;
		for(int y = 0; y < height; y++)
		{
			posY -= sampleSize;
			for(int x = 0; x < width; x++)
			{
				posX += sampleSize;
				PathfindingNode clone = Instantiate(sample, new Vector3(posX, 0, posY), Quaternion.identity, transform) as PathfindingNode;
				clone.transform.name = "Node-" + z;
				grid[z] = clone;
				z++;
			}
			posX = Xreset;
		}
	}
	#endif
}

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


Добавим кнопку в инспектор:

#if UNITY_EDITOR
using System.Collections;
using UnityEngine;
using UnityEditor;
[CustomEditor(typeof(PathfindingField))]
public class PathfindingEditor : Editor {

	public override void OnInspectorGUI()
	{
		DrawDefaultInspector();
		PathfindingField e = (PathfindingField)target;
		if(GUILayout.Button("Создать / Обновить игровое поле")) e.CreateGrid();
	}
}
#endif

Стоит отметить, что игровое поле нужно делать только через данный метод в редакторе.

Если на игровом поле был удален объект или добавлен новый:

PathfindingField.UpdateNodeState();

Нужно сделать вызов данного метода, чтобы обновить состояние клеток.

Скачать проект:

У вас нет доступа!
У вас нет доступа!
Тестировалось на: Unity 2017.1.0
Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.
  • Дешевый хостинг
  • Яндекс.Метрика