PatientZero 24 окт 2018 в 11:15

Карты из шестиугольников в Unity: поиск пути, отряды игрока, анимации

61 мин

15K

Перевод

Части 1-3: сетка, цвета и высоты ячеек

Части 4-7: неровности, реки и дороги

Части 8-11: вода, объекты рельефа и крепостные стены

Части 12-15: сохранение и загрузка, текстуры, расстояния

Части 16-19: поиск пути, отряды игрока, анимации

Части 20-23: туман войны, исследование карты, процедурная генерация

Части 24-27: круговорот воды, эрозия, биомы, цилиндрическая карта

Часть 16: поиск пути

Подсвечиваем ячейки
Выбираем целевую точку поиска
Находим кратчайший путь
Создаём очередь с приоритетом

Вычислив расстояния между ячейками, мы перешли к нахождению путей между ними.

Начиная с этой части, туториалы по картам из шестиугольников будут создаваться в Unity 5.6.0. Нужно учесть, что в 5.6 есть баг, разрушающий массивы текстур в сборках для нескольких платформ. Обойти его можно, включив в инспекторе массива текстур Is Readable.

Планируем путешествие

Подсвечиваемые ячейки

Чтобы искать путь между двумя ячейками, нам нужно сначала выбрать эти ячейки. Больше это не просто выбор одной ячейки и наблюдение за поиском по карте. Например, сначала мы выберем начальную клетку, а потом конечную. При этом было бы удобно, чтобы они стали подсвеченными. Поэтому давайте добавим такой функционал. Пока мы не будем создавать сложный или эффективный способ выделения, просто создадим нечто, помогающее нам в разработке.

Текстура-контур

Один из простых способов выделения ячеек — добавление к ним контура. Проще всего это сделать с помощью текстуры, содержащей шестиугольный контур. Здесь можно скачать такую текстуру. Она прозрачна, за исключением белого контура шестиугольника. Сделав её белой, мы в дальнейшем сможем раскрасить её, как нам нужно.

Контур ячейки на чёрном фоне

Импортируем текстуру и зададим для её Texture Type значнеие Sprite. Её Sprite Mode будет иметь значение Single с настройками по умолчанию. Так как это исключительно белая текстура, нам не нужно преобразование в sRGB. Альфа-канал обозначает прозрачность, поэтому включим Alpha is Transparency. Также я задал для Filter Mode текстуры значение Trilinear, потому что в ином случае mip-переходы для контуров могут становиться слишком заметными.

Параметры импорта текстуры

По одному спрайту на ячейку

Быстрее всего добавить к ячейкам возможный контур, добавив каждой собственный спрайт. Создадим новый игровой объект, добавим к нему компонент Image (Component / UI / Image) и назначим ему наш спрайт контура. Затем вставим экземпляр префаба Hex Cell Label в сцену, сделаем объект-спрайт его дочерним элементом и применим изменения к префабу, после чего избавимся от префаба.

Дочерний элемент выделения префаба

Теперь у каждой ячейки есть спрайт, но он будет слишком большим. Чтобы контуры соответствовали центрам ячеек, изменим Width и Height компонента transform спрайта на 17.

Спрайты выделения, частично скрытые рельефом

Рисование поверх всего

Так как контур накладывается на области рёбер ячеек, он часто оказывается под геометрией рельефа. Из-за этого часть контура исчезает. Этого можно избежать, немного подняв спрайты по вертикали, но не в случае обрывов. Вместо этого мы можем сделать следующее: всегда отрисовывать спрайты поверх всего другого. Для этого нужно создать собственный спрайтовый шейдер. Нам достаточно будет скопировать стандартный спрайтовый шейдер Unity и внести в него пару изменений.

Shader "Custom/Highlight" {
	Properties {
		[PerRendererData] _MainTex ("Sprite Texture", 2D) = "white" {}
		_Color ("Tint", Color) = (1,1,1,1)
		[MaterialToggle] PixelSnap ("Pixel snap", Float) = 0
		[HideInInspector] _RendererColor ("RendererColor", Color) = (1,1,1,1)
		[HideInInspector] _Flip ("Flip", Vector) = (1,1,1,1)
		[PerRendererData] _AlphaTex ("External Alpha", 2D) = "white" {}
		[PerRendererData] _EnableExternalAlpha ("Enable External Alpha", Float) = 0
	}

	SubShader {
		Tags { 
			"Queue"="Transparent"
			"IgnoreProjector"="True"
			"RenderType"="Transparent"
			"PreviewType"="Plane"
			"CanUseSpriteAtlas"="True"
		}

		Cull Off
		ZWrite Off
		Blend One OneMinusSrcAlpha

		Pass {
			CGPROGRAM
			#pragma vertex SpriteVert
			#pragma fragment SpriteFrag
			#pragma target 2.0
			#pragma multi_compile_instancing
			#pragma multi_compile _ PIXELSNAP_ON
			#pragma multi_compile _ ETC1_EXTERNAL_ALPHA
			#include "UnitySprites.cginc"
			ENDCG
		}
	}
}

Первое изменение — мы игнорируем буфер глубины, сделав так, что Z-тест всегда заканчивается удачей.

		ZWrite Off
		ZTest Always

Второе изменение — мы выполняем отрисовку после всей остальной прозрачной геометрии. Достаточно будет прибавить 10 к очереди прозрачности.

			"Queue"="Transparent+10"

Создадим новый материал, который будет использовать этот шейдер. Мы можем игнорировать все его свойства, придерживаясь значений по умолчанию. Затем сделаем так, чтобы префаб спрайта использовал этот материал.

Используем собственный материал спрайта

Теперь контуры выделения видны всегда. Даже если ячейка скрыта под более высоким рельефом, её контур всё равно будет отрисовываться поверх всего остального. Это может и не выглядит красиво, но выделенные клетки всегда будут видны, что полезно для нас.

Игнорируем буфер глубин

Контроль над выделением

Мы не хотим, чтобы одновременно были подсвечены все ячейки. На самом деле, изначально они все должны быть не выделенными. Мы можем реализовать это, отключив компонент Image объекта префаба Highlight.

Отключенный компонент Image

Чтобы включить выделение ячейки, добавим в HexCell метод EnableHighlight. Он должен брать единственный дочерний элемент своего uiRect и включать его компонент Image. Создадим также метод DisableHighlight.

	public void DisableHighlight () {
		Image highlight = uiRect.GetChild(0).GetComponent<Image>();
		highlight.enabled = false;
	}
	
	public void EnableHighlight () {
		Image highlight = uiRect.GetChild(0).GetComponent<Image>();
		highlight.enabled = true;
	}

Наконец, мы можем указать цвет, чтобы при включении придавать подсветке оттенок.

	public void EnableHighlight (Color color) {
		Image highlight = uiRect.GetChild(0).GetComponent<Image>();
		highlight.color = color;
		highlight.enabled = true;
	}

unitypackage

Нахождение пути

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

Начало поиска

Нам нужно выбрать две разные клетки, начальную и конечную точки поиска. Допустим, что для выбора начальной ячейки поиска надо удерживать при щелчке мыши левую клавишу Shift. При этом ячейка подсветится синим цветом. Нам нужно сохранить ссылку на эту ячейку для дальнейшего поиска. Кроме того, при выборе новой стартовой ячейки выделение старой нужно отключать. Поэтому добавим в HexMapEditor поле searchFromCell.

	HexCell previousCell, searchFromCell;

Внутри HandleInput мы можем использовать Input.GetKey(KeyCode.LeftShift) для проверки зажатой клавиши Shift.

			if (editMode) {
				EditCells(currentCell);
			}
			else if (Input.GetKey(KeyCode.LeftShift)) {
				if (searchFromCell) {
					searchFromCell.DisableHighlight();
				}
				searchFromCell = currentCell;
				searchFromCell.EnableHighlight(Color.blue);
			}
			else {
				hexGrid.FindDistancesTo(currentCell);
			}

Откуда искать

Конечная точка поиска

Вместо того, чтобы искать все расстояния до ячейки, мы теперь ищем путь между двумя конкретными ячейками. Поэтому переименуем HexGrid.FindDistancesTo в HexGrid.FindPath и дадим ему второй параметр HexCell.Также изменим метод Search.

	public void FindPath (HexCell fromCell, HexCell toCell) {
		StopAllCoroutines();
		StartCoroutine(Search(fromCell, toCell));
	}

	IEnumerator Search (HexCell fromCell, HexCell toCell) {
		for (int i = 0; i < cells.Length; i++) {
			cells[i].Distance = int.MaxValue;
		}

		WaitForSeconds delay = new WaitForSeconds(1 / 60f);
		List<HexCell> frontier = new List<HexCell>();
		fromCell.Distance = 0;
		frontier.Add(fromCell);
		…
	}

Теперь HexMapEditor.HandleInput должен вызывать изменённый метод, используя в качестве аргументов searchFromCell и currentCell. Кроме того, мы можем искать только тогда, когда знаем, из какой ячейки нужно искать. И мы не обязаны утруждаться поиском, если начальная и конечная точки совпадают.

			if (editMode) {
				EditCells(currentCell);
			}
			else if (Input.GetKey(KeyCode.LeftShift)) {
				…
			}
			else if (searchFromCell && searchFromCell != currentCell) {
				hexGrid.FindPath(searchFromCell, currentCell);
			}

Переходя к поиску, нам сначала нужно избавиться от всех предыдущих выделений. Поэтому заставим HexGrid.Search отключать выделение при сбросе расстояний. Так как при этом также отключится подсветка начальной ячейки, затем снова её включим. На этом этапе мы можем также выделить конечную точку. Давайте сделаем её красной.

	IEnumerator Search (HexCell fromCell, HexCell toCell) {
		for (int i = 0; i < cells.Length; i++) {
			cells[i].Distance = int.MaxValue;
			cells[i].DisableHighlight();
		}
		fromCell.EnableHighlight(Color.blue);
		toCell.EnableHighlight(Color.red);
		
		…
	}

Концевые точки потенциального пути

Ограничиваем поиск

На этом этапе наш поисковый алгоритм всё ещё вычисляет расстояния до всех ячеек, которые достижимы из начальной ячейки. Но больше это нам не нужно. Мы можем остановиться, как только найдём окончательное расстояние до конечной ячейки. То есть когда текущая ячейка является конечной, мы можем выйти из цикла алгоритма.

		while (frontier.Count > 0) {
			yield return delay;
			HexCell current = frontier[0];
			frontier.RemoveAt(0);

			if (current == toCell) {
				break;
			}

			for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
				…
			}
		}

Останавливаемся в конечной точке

Что произойдёт, если конечной точки нельзя достичь?

Тогда алгоритм продолжит работу, пока не найдёт все достижимые ячейки. Без возможности преждевременного выхода он будет работать как старый метод FindDistancesTo.

Отображение пути

Мы можем найти расстояние между началом и концом пути, но пока не знаем, каким будет настоящий путь. Чтобы найти его, нужно отслеживать, как достигнута каждая ячейка. Но как это сделать?

При добавлении ячейки к границе, мы делаем это, потому что она является соседом текущей ячейки. Единственным исключением является начальная ячейка. Все другие ячейки были достигнуты через текущую ячейку. Если мы будем отслеживать, из какой ячейки была достигнута каждая ячейка, то в результате получим сеть ячеек. Если точнее, древовидную сеть, корнем которой является начальная точка. Мы можем использовать её для построения пути после достижения конечной точки.

Древовидная сеть, описывающая пути до центра

Мы можем сохранить эту информацию, добавив в HexCell ссылку на ещё одну ячейку. Нам не нужно сериализовать эти данные, поэтому используем для этого стандартное свойство.

	public HexCell PathFrom { get; set; }

В HexGrid.Search зададим в качестве значения PathFrom соседа текущую ячейку при добавлении её к границе. Кроме того, нам нужно менять эту ссылку, когда мы найдём более короткий путь до соседа.

				if (neighbor.Distance == int.MaxValue) {
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					frontier.Add(neighbor);
				}
				else if (distance < neighbor.Distance) {
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
				}

Достигнув конечной точки, мы можем визуализировать путь, проследовав по этим ссылкам обратно к начальной ячейке, и выделить их.

			if (current == toCell) {
				current = current.PathFrom;
				while (current != fromCell) {
					current.EnableHighlight(Color.white);
					current = current.PathFrom;
				}
				break;
			}

Путь найден

Стоит учесть, что часто бывает несколько кратчайших путей. Найденный зависит от порядка обработки ячеек. Некоторые пути могут выглядеть хорошо, другие плохо, но более короткого пути никогда не бывает. Мы вернёмся к этому позже.

Изменение начала поиска

После выбора начальной точки изменение конечной точки вызовет запуск нового поиска. То же самое должно происходить при выборе новой начальной ячейки. Чтобы это стало возможно, HexMapEditor также должен запоминать конечную точку.

	HexCell previousCell, searchFromCell, searchToCell;

С помощью этого поля мы можем также инициировать новый поиск при выборе нового начала.

			else if (Input.GetKey(KeyCode.LeftShift)) {
				if (searchFromCell) {
					searchFromCell.DisableHighlight();
				}
				searchFromCell = currentCell;
				searchFromCell.EnableHighlight(Color.blue);
				if (searchToCell) {
					hexGrid.FindPath(searchFromCell, searchToCell);
				}
			}
			else if (searchFromCell && searchFromCell != currentCell) {
				searchToCell = currentCell;
				hexGrid.FindPath(searchFromCell, searchToCell);
			}

Кроме того, нам нужно избегать равенства начальной и конечной точек.

			if (editMode) {
				EditCells(currentCell);
			}
			else if (
				Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
			) {
				…
			}

unitypackage

Более умный поиск

Хоть наш алгоритм и находит кратчайший путь, он тратит много времени на исследование точек, которые очевидно не станут частью этого пути. По крайней мере, очевидно для нас. Алгоритм не может взглянуть на карту «свысока», он не может увидеть, что поиск в некоторых направлениях окажется бессмысленным. Он предпочитает двигаться по дорогам, несмотря на то, что они направляются в противоположную от конечной точки сторону. Можно ли сделать поиск умнее?

На данный момент при выборе ячейки, которую нужно обрабатывать следующей, мы рассматриваем только расстояние от ячейки до начала. Если мы хотим поступать умнее, то надо также учитывать расстояние до конечной точки. К сожалению, его мы пока не знаем. Но мы можем создать оценку оставшегося расстояния. Прибавление этой оценки к расстоянию до ячейки даёт нам понимание общей длины пути, проходящего через эту ячейку. Затем мы сможем использовать его для определения приоритетов поиска ячеек.

Эвристика поиска

Когда мы используем оценку или догадки вместо точно известных данных, то это называется использованием поисковых эвристик. Эта эвристика представляет собой наилучшую догадку об оставшемся расстоянии. Мы должны определить это значение для каждой ячейки, по которой выполняем поиск, поэтому добавим для него HexCell целочисленное свойство. Нам не нужно сериализовать его, поэтому достаточно будет ещё одного стандартного свойства.

	public int SearchHeuristic { get; set; }

Как нам сделать предположение об оставшемся расстоянии? В самом идеальном случае у нас будет дорога, ведущая прямиком к конечной точке. Если это так, то расстояние равно неизменённому расстоянию между координатами этой ячейки и конечной ячейки. Давайте воспользуемся этим в нашей эвристике.

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

				if (neighbor.Distance == int.MaxValue) {
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
					frontier.Add(neighbor);
				}

Приоритет поиска

С этого момента мы будем определять приоритет поиска на основе расстояния до ячейки плюс её эвристики. Давайте добавим для этого значения в HexCell свойство.

	public int SearchPriority {
		get {
			return distance + SearchHeuristic;
		}
	}

Чтобы это сработало, изменим HexGrid.Search так, чтобы он использовал это свойство для сортировки границы.

				frontier.Sort(
					(x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
				);

Поиск без эвристики и с эвристикой

Допустимая эвристика

Благодаря новым приоритетам поиска мы и в самом деле в результате посетим меньше ячеек. Однако на однообразной карте алгоритм по-прежнему обрабатывает ячейки, находящиеся в неверном направлении. Так происходит потому, что по умолчанию затраты на каждый шаг перемещения равны 5, а эвристика на шаг прибавляет всего 1. То есть влияние эвристики не очень сильно.

Если затраты на перемещение на всех карте одинаковы, то мы можем использовать такие же затраты при определении эвристики. В нашем случае это будет текущая эвристика, умноженная на 5. Это значительно снизит количество обрабатываемых ячеек.

Используем эвристику × 5

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

Переоценённая и допустимая эвристики

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

Строго говоря, вполне нормально использовать даже меньшие затраты, но это только сделает эвристику слабее. Минимальная возможная эвристика равна нулю, что даёт нам просто алгоритм Дейкстры. При ненулевой эвристике алгоритм называется A^* (произносится «А звезда»).

Почему его называют A*?

Идея добавления эвристики в алгоритм Дейкстры впервые была предложена Нильсом Нильссоном. Он назвал свой вариант A1. Позже Бертрам Рафаэль придумал лучшую версию, которую он назвал A2. Затем Питер Харт доказал, что при хорошей эвристике A2 оптимален, то есть более хорошей версии быть не может. Это заставило его назвать алгоритм A^*, чтобы показать, что его невозможно будет улучшить, то есть A3 или A4 не появятся. Так что да, алгоритм A^* — это лучшее, что мы можем получить, но он хорош настолько, насколько хороша его эвристика.

unitypackage

Очередь с приоритетом

Хоть A^* и хороший алгоритм, наша реализация не так уж эффективна, потому что для хранения границы мы используем список, который нужно сортировать при каждой итерации. Как упоминалось в предыдущей части, нам нужна очередь с приоритетом, но её стандартной реализации не существует. Поэтому давайте создадим её самостоятельно.

Наша очередь должна поддерживать операцию постановки и исключения из очереди на основании приоритета. Также она должна поддерживать изменение приоритета ячейки, уже находящейся в очереди. В идеале мы реализуем её, минимизируя поиск сортировку и выделяемую память. Кроме того, она должна оставаться простой.

Создание собственной очереди

Создадим новый класс HexCellPriorityQueue с обязательными общими методами. Для отслеживания содержимого очереди мы используем простой список. Кроме того, добавим ей метод Clear для сброса очереди, чтобы её можно было использовать многократно.

using System.Collections.Generic;

public class HexCellPriorityQueue {

	List<HexCell> list = new List<HexCell>();

	public void Enqueue (HexCell cell) {
	}

	public HexCell Dequeue () {
		return null;
	}
	
	public void Change (HexCell cell) {
	}
	
	public void Clear () {
		list.Clear();
	}
}

Мы храним приоритеты ячеек в самих ячейках. То есть перед добавлением ячейки в очередь её приоритет должен быть задан. Но в случае изменения приоритета вероятно будет полезно знать, каким был старый приоритет. Поэтому давайте добавим это в Change как параметр.

	public void Change (HexCell cell, int oldPriority) {
	}

Также полезно знать, сколько ячеек находится в очереди, поэтому добавим для этого свойство Count. Просто используем поле, для которого будем выполнять соответствующий инкремент и декремент.

	int count = 0;

	public int Count {
		get {
			return count;
		}
	}

	public void Enqueue (HexCell cell) {
		count += 1;
	}

	public HexCell Dequeue () {
		count -= 1;
		return null;
	}
	
	…
	
	public void Clear () {
		list.Clear();
		count = 0;
	}

Добавление в очередь

Когда ячейка добавляется в очередь, давайте сначала использовать её приоритет как индекс, обращаясь со списком как с простым массивом.

	public void Enqueue (HexCell cell) {
		count += 1;
		int priority = cell.SearchPriority;
		list[priority] = cell;
	}

Однако это работает только если список достаточно длинный, в противном случае мы выйдем за границы. Можно избежать этого, добавляя в список пустые элементы, пока он не достигнет требуемой длины. Эти пустые элементы не ссылаются на ячейку, поэтому их можно создавать, добавляя в список null.

		int priority = cell.SearchPriority;
		while (priority >= list.Count) {
			list.Add(null);
		}
		list[priority] = cell;

Список с дырами

Но так мы храним только по одной ячейке на приоритет, а их скорее всего будет несколько. Чтобы отслеживать все ячейки с одинаковым приоритетом, нам нужно использовать ещё один список. Хотя мы и можем использовать настоящий список на каждый приоритет, можно также добавить к HexCell свойство, чтобы связать их вместе. Это позволяет нам создавать цепочку ячеек, называемую связанным списком.

	public HexCell NextWithSamePriority { get; set; }

Для создания цепочки сделаем так, чтобы HexCellPriorityQueue.Enqueue заставлял новую добавленную ячейку ссылаться на текущее значение с тем же приоритетом, перед его удалением.

		cell.NextWithSamePriority = list[priority];
		list[priority] = cell;

Список связанных списков

Удаление из очереди

Для получения ячейки из очереди с приоритетом нам нужно получить доступ к связанному списку по наименьшему непустому индексу. Поэтому обойдём список в цикле, пока не найдём его. Если не найдём, то очередь пуста и мы возвращаем null.

Из найденной цепочки мы можем вернуть любую ячейку, потому что все они имеют одинаковый приоритет. Проще всего вернуть ячейку из начала цепочки.

	public HexCell Dequeue () {
		count -= 1;
		for (int i = 0; i < list.Count; i++) {
			HexCell cell = list[i];
			if (cell != null) {
				return cell;
			}
		}
		return null;
	}

Чтобы сохранить ссылку на оставшуюся цепочку, используем следующую ячейку с тем же приоритетом как новое начало. Если на этом уровне приоритетов была только одна ячейка, то элемент становится null и в будущем будет пропускаться.

			if (cell != null) {
				list[i] = cell.NextWithSamePriority;
				return cell;
			}

Отслеживание минимума

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

	int minimum = int.MaxValue;

	…
	
	public void Clear () {
		list.Clear();
		count = 0;
		minimum = int.MaxValue;
	}

При добавлении ячейки в очередь по необходимости изменяем минимум.

	public void Enqueue (HexCell cell) {
		count += 1;
		int priority = cell.SearchPriority;
		if (priority < minimum) {
			minimum = priority;
		}
		…
	}

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

	public HexCell Dequeue () {
		count -= 1;
		for (; minimum < list.Count; minimum++) {
			HexCell cell = list[minimum];
			if (cell != null) {
				list[minimum] = cell.NextWithSamePriority;
				return cell;
			}
		}
		return null;
	}

Это значительно снижает объём времени на обход в цикле списка приоритетов.

Изменение приоритетов

При изменении приоритета ячейки она должна удаляться из связанного списка, частью которого является. Для этого нам нужно проследовать по цепочке, пока мы не найдём её.

Начнём с объявления того, что голова старого списка приоритетов будет текущей ячейкой, а также будем отслеживать следующую ячейку. Мы можем сразу брать следующую ячейку, потому что знаем, что по этому индексу есть хотя бы одна ячейка.

	public void Change (HexCell cell, int oldPriority) {
		HexCell current = list[oldPriority];
		HexCell next = current.NextWithSamePriority;
	}

Если текущая ячейка является изменившейся ячейкой, то это головная ячейка и мы можем отсечь её, как будто вывели её из очереди.

		HexCell current = list[oldPriority];
		HexCell next = current.NextWithSamePriority;
		if (current == cell) {
			list[oldPriority] = next;
		}

Если это не так, то нам нужно проследовать по цепочке, пока мы не окажемся в ячейке перед изменившейся ячейкой. Она содержит ссылку на ячейку, которая была изменена.

		if (current == cell) {
			list[oldPriority] = next;
		}
		else {
			while (next != cell) {
				current = next;
				next = current.NextWithSamePriority;
			}
		}

На этом этапе мы можем удалить изменившуюся ячейку из связанного списка, пропустив её.

			while (next != cell) {
				current = next;
				next = current.NextWithSamePriority;
			}
			current.NextWithSamePriority = cell.NextWithSamePriority;

После удаления ячейки её нужно добавить снова, чтобы она оказалась в списке своего нового приоритета.

	public void Change (HexCell cell, int oldPriority) {
		…
		Enqueue(cell);
	}

Метод Enqueue увеличивает счётчик, но на самом деле мы не добавляем новую ячейку. Поэтому чтобы компенсировать это, нам придётся выполнить декремент счётчика.

		Enqueue(cell);
		count -= 1;

Использование очереди

Теперь мы можем воспользоваться нашей очередью с приоритетом в HexGrid. Это можно сделать с помощью одного экземпляра, многократно применяемого для всех операций поиска.

	HexCellPriorityQueue searchFrontier;
	
	…
	
	IEnumerator Search (HexCell fromCell, HexCell toCell) {
		if (searchFrontier == null) {
			searchFrontier = new HexCellPriorityQueue();
		}
		else {
			searchFrontier.Clear();
		}
		
		…
	}

Перед началом цикла метод Search должен сначала внести в очередь fromCell, а каждая итерация начинается с вывода ячейки из очереди. Этим мы заменим старый код границы.

		WaitForSeconds delay = new WaitForSeconds(1 / 60f);
//		List<HexCell> frontier = new List<HexCell>();
		fromCell.Distance = 0;
//		frontier.Add(fromCell);
		searchFrontier.Enqueue(fromCell);
		while (searchFrontier.Count > 0) {
			yield return delay;
			HexCell current = searchFrontier.Dequeue();
//			frontier.RemoveAt(0);
			…
		}

Изменим код так, чтобы он добавлял и изменял и соседа. Перед изменением будем запоминать старый приоритет.

				if (neighbor.Distance == int.MaxValue) {
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
//					frontier.Add(neighbor);
					searchFrontier.Enqueue(neighbor);
				}
				else if (distance < neighbor.Distance) {
					int oldPriority = neighbor.SearchPriority;
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					searchFrontier.Change(neighbor, oldPriority);
				}

Кроме того, нам больше не нужно сортировать границу.

//				frontier.Sort(
//					(x, y) => x.SearchPriority.CompareTo(y.SearchPriority)
//				);

Поиск при помощи очереди с приоритетом

Как говорилось ранее, находимый кратчайший путь зависит от порядка обработки ячеек. Наша очередь создаёт порядок, отличающийся от порядка отсортированного списка, поэтому мы можем получать другие пути. Так как мы и добавляем, и удаляем из головы связанного списка для каждого приоритета, они больше походят на стеки, чем на очереди. Ячейки, добавленные последними, обрабатываются первыми. Побочный эффект такого подхода заключается в том, что алгоритм склонен к зигзагам. Поэтому также повышается вероятность зигзагообразных путей. К счастью, такие пути обычно выглядят лучше, поэтому этот побочный эффект нам на пользу.

Отсортированный список и очередь с приоритетом

unitypackage

Часть 17: ограниченное перемещение

Находим пути для пошагового перемещения.
Сразу же отображаем пути.
Создаём более эффективный поиск.
Визуализируем только путь.

В этой части мы разделим движение на ходы и максимально ускорим поиск.

Путешествие из нескольких ходов

Пошаговое движение

Стратегические игры, в которых используются сетки шестиугольников, почти всегда являются пошаговыми. Перемещающиеся по карте отряды имеют ограниченную скорость, которая ограничивает расстояние, проходимое за один ход.

Скорость

Чтобы обеспечить поддержку ограниченного перемещения, добавим в HexGrid.FindPath и в HexGrid.Search целочисленный параметр speed. Он определяет запас движений на один ход.

	public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
		StopAllCoroutines();
		StartCoroutine(Search(fromCell, toCell, speed));
	}

	IEnumerator Search (HexCell fromCell, HexCell toCell, int speed) {
		…
	}

Разные типы отрядов в игре используют разные скорости. Кавалерия быстра, пехота медленна, и так далее. У нас ещё нет отрядов, поэтому пока будем использовать постоянную скорость. Давайте возьмём значение 24. Это достаточно большое значение, не делящееся на 5 (затраты на перемещение по умолчанию). Добавим как аргумент для FindPath в HexMapEditor.HandleInput постоянную скорость.

			if (editMode) {
				EditCells(currentCell);
			}
			else if (
				Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
			) {
				if (searchFromCell) {
					searchFromCell.DisableHighlight();
				}
				searchFromCell = currentCell;
				searchFromCell.EnableHighlight(Color.blue);
				if (searchToCell) {
					hexGrid.FindPath(searchFromCell, searchToCell, 24);
				}
			}
			else if (searchFromCell && searchFromCell != currentCell) {
				searchToCell = currentCell;
				hexGrid.FindPath(searchFromCell, searchToCell, 24);
			}

Ходы

Кроме отслеживания общих затрат на перемещение по пути нам также нужно теперь знать, сколько ходов потребуется на перемещение по нему. Но нам не нужно хранить эту информацию в каждой ячейке. Её можно получить, разделив пройденное расстояние на скорость. Так как это целые числа, мы воспользуемся целочисленным делением. То есть общие расстояния не больше 24 соответствуют ходу 0. Это значит, что весь путь можно пройти в текущем ходе. Если конечная точка находится на расстоянии 30, то это должен быть ход 1. Чтобы добраться до конечной точки, отряду придётся потратить всё своё движение в текущем ходу и в части следующего хода.

Давайте определять ход текущей ячейки и всех её соседей внутри HexGrid.Search. Ход текущей ячейки можно вычислять только один раз, прямо перед обходом в цикле соседей. Ход соседа можно определить, как только мы найдём расстояние до него.

			int currentTurn = current.Distance / speed;

			for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
				…
				int distance = current.Distance;
				if (current.HasRoadThroughEdge(d)) {
					distance += 1;
				}
				else if (current.Walled != neighbor.Walled) {
					continue;
				}
				else {
					distance += edgeType == HexEdgeType.Flat ? 5 : 10;
					distance += neighbor.UrbanLevel + neighbor.FarmLevel +
						neighbor.PlantLevel;
				}

				int turn = distance / speed;

				…
			}

Утерянное движение

Если ход соседа больше текущего хода, то мы пересекли границу хода. Если перемещение, необходимое, чтобы достичь соседа, было равно 1, то всё нормально. Но если перемещение в соседнюю ячейку более затратно, то всё становится сложнее.

Предположим, что мы перемещаемся по однородной карте, то есть для попадания в каждую ячейку нужно 5 единиц движения. Наша скорость равна 24. Через четыре шага мы потратили 20 единиц из нашего запаса движения, и осталось 4. На следующем шаге снова нужно 5 единиц, то есть на одну больше имеющихся. Что нам нужно делать на этом этапе?

Существует два подхода к такой ситуации. Первый — позволить отряду войти в пятую ячейку на текущем ходе, даже если у нас не хватает перемещения. Второй — запретить перемещение в течение текущего хода, то есть оставшиеся очки движения невозможно использовать и они будут утеряны.

Выбор варианта зависит от игры. В общем случае первый подход больше соответствует играм, в которых отряды могут двигаться всего на несколько шагов за ход, например, для игр серии Civilization. Это гарантирует, что отряды всегда смогут сдвинуться хотя бы на одну ячейку за ход. Если отряды могут двигаться на много ячеек за ход, как в Age of Wonders или в Battle for Wesnoth, то лучше подходит второй вариант.

Так как мы используем скорость 24, давайте выберем второй подход. Чтобы он начал работать, нам нужно изолировать затраты на попадание в соседнюю ячейку перед прибавлением её к текущему расстоянию.

//				int distance = current.Distance;
				int moveCost;
				if (current.HasRoadThroughEdge(d)) {
					moveCost = 1;
				}
				else if (current.Walled != neighbor.Walled) {
					continue;
				}
				else {
					moveCost = edgeType == HexEdgeType.Flat ? 5 : 10;
					moveCost  += neighbor.UrbanLevel + neighbor.FarmLevel +
						neighbor.PlantLevel;
				}

				int distance = current.Distance + moveCost;
				int turn = distance / speed;

Если в результате мы пересечём границу хода, то сначала используем все очки движения текущего хода. Мы можем сделать это, просто умножив ход на скорость. После этого мы прибавляем затраты на перемещение.

				int distance = current.Distance + moveCost;
				int turn = distance / speed;
				if (turn > currentTurn) {
					distance = turn * speed + moveCost;
				}

В результате этого мы будем заканчивать первый ход в четвёртой ячейке с 4 неиспользованными очками движения. Эти потерянные очки добавляются к затратам пятой ячейки, поэтому её расстояние становится 29, а не 25. В результате расстояния оказываются больше, чем раньше. Например, у десятой ячейки было расстояние 50. Но теперь чтобы добраться в неё, нам нужно пересечь границы двух ходов, теряя 8 очков движения, то есть расстояние до неё теперь становится равным 58.

Дольше, чем ожидалось

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

Отображение ходов вместо расстояний

Когда мы играем в игру, нам не очень интересны значения расстояний, использованные для поиска кратчайшего пути. Нас интересует количество ходов, требующихся для попадания в конечную точку. Поэтому давайте вместо расстояний будем отображать ходы.

Во-первых, избавимся от UpdateDistanceLabel и его вызова в HexCell.

	public int Distance {
		get {
			return distance;
		}
		set {
			distance = value;
//			UpdateDistanceLabel();
		}
	}
	
	…
	
//	void UpdateDistanceLabel () {
//		UnityEngine.UI.Text label = uiRect.GetComponent<Text>();
//		label.text = distance == int.MaxValue ? "" : distance.ToString();
//	}

Вместо него мы добавим в HexCell общий метод SetLabel, получающий произвольную строку.

	public void SetLabel (string text) {
		UnityEngine.UI.Text label = uiRect.GetComponent<Text>();
		label.text = text;
	}

Используем этот новый метод в HexGrid.Search при очистке ячеек. Чтобы скрыть ячейки, просто присвоим им null.

		for (int i = 0; i < cells.Length; i++) {
			cells[i].Distance = int.MaxValue;
			cells[i].SetLabel(null);
			cells[i].DisableHighlight();
		}

Затем присвоим метке соседа значение его хода. После этого мы сможем увидеть, сколько дополнительных ходов потребуется для прохождения всего пути.

				if (neighbor.Distance == int.MaxValue) {
					neighbor.Distance = distance;
					neighbor.SetLabel(turn.ToString());
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
					searchFrontier.Enqueue(neighbor);
				}
				else if (distance < neighbor.Distance) {
					int oldPriority = neighbor.SearchPriority;
					neighbor.Distance = distance;
					neighbor.SetLabel(turn.ToString());
					neighbor.PathFrom = current;
					searchFrontier.Change(neighbor, oldPriority);
				}

Количество ходов, необходимое для перемещения по пути

unitypackage

Мгновенные пути

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

Без корутин

Для медленного прохождения по алгоритму мы использовали корутину. Больше нам этого делать не нужно, поэтому избавимся от вызовов StartCoroutine и StopAllCoroutines в HexGrid. Вместо этого мы просто вызываем Search как обычный метод.

	public void Load (BinaryReader reader, int header) {
//		StopAllCoroutines();
		…
	}

	public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
//		StopAllCoroutines();
//		StartCoroutine(Search(fromCell, toCell, speed));
		Search(fromCell, toCell, speed);
	}

Так как мы больше не используем Search как корутину, ему не нужен yield, поэтому избавимся от этого оператора. Это означает, что мы также удалим объявление WaitForSeconds и изменим возвращаемый тип метода на void.

	void Search (HexCell fromCell, HexCell toCell, int speed) {
		…

//		WaitForSeconds delay = new WaitForSeconds(1 / 60f);
		fromCell.Distance = 0;
		searchFrontier.Enqueue(fromCell);
		while (searchFrontier.Count > 0) {
//			yield return delay;
			HexCell current = searchFrontier.Dequeue();
			…
		}
	}

Мгновенные результаты

Определение времени поиска

Теперь мы можем получать пути мгновенно, но насколько быстро они вычисляются? Короткие пути отображаются почти сразу, но длинные пути на больших картах могут казаться немного тормозными.

Давайте измерим, сколько времени уходит на поиск и отображение пути. Для определения времени поиска мы можем использовать профайлер, но это немного чересчур и создаёт дополнительные затраты. Давайте используем вместо этого Stopwatch, который находится в пространстве имён System.Diagnostics. Так как мы используем его только временно, я не будут добавлять конструкцию using в начало скрипта.

Прямо перед выполнением поиска создадим новый stopwatch и запустим его. После завершения поиска остановим stopwatch и выведем в консоль прошедшее время.

	public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
		System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
		sw.Start();
		Search(fromCell, toCell, speed);
		sw.Stop();
		Debug.Log(sw.ElapsedMilliseconds);
	}

Давайте выберем наихудший для нашего алгоритма случай — поиск из нижнего левого в верхний правый угол большой карты. Хуже всего однообразная карта, потому что алгоритму придётся обрабатывать все 4 800 ячеек карты.

Поиск в наихудшем случае

Потраченное на поиск время может быть разным, потому что редактор Unity — это не единственный процесс, запущенный на вашей машине. Поэтому протестируйте его несколько раз, чтобы получить понимание средней длительности. В моём случае поиск занимает около 45 миллисекунд. Это не очень много и соответствует 22,22 путям в секунду; обозначим это как 22 pps (paths per second). Это означает, что частота кадров игры тоже снизится максимум на 22 fps в том кадре, когда вычисляется этот путь. И это без учёта всей другой работы, например, рендеринга самого кадра. То есть мы получим довольно большое снижение частоты кадров, она снизится до 20 fps.

При выполнении подобного тестирования производительности нужно учитывать, что производительность редактора Unity будет не такой высокой, как производительность готового приложения. Если я выполню тот же тест со сборкой, то в среднем он будет занимать всего 15 мс. То есть 66 pps, что намного лучше. Тем не менее, это всё равно большая часть выделенных на кадр ресурсов, поэтому частота кадров станет ниже 60 fps.

Где можно посмотреть журнал отладки для сборки?

Приложения Unity выполняют запись в файл журнала, который сохраняется в системе. Его местоположение зависит от платформы. Чтобы узнать, как найти файлы журналов в своей системе, прочитайте документацию Unity по Log Files.

Выполняем поиск только при необходимости

Мы можем внести простую оптимизацию — выполнять поиск только тогда, когда он нужен. Пока мы инициируем новый поиск в каждом кадре, в котором зажата клавиша мыши. Поэтому частота кадров будет постоянно занижаться при перетаскивании. Мы можем избежать этого, инициируя новый поиск в HexMapEditor.HandleInput только тогда, когда действительно имеем дело с новой конечной точкой. Если нет, то верным по-прежнему является текущий видимый путь.

			if (editMode) {
				EditCells(currentCell);
			}
			else if (
				Input.GetKey(KeyCode.LeftShift)  && searchToCell != currentCell
			) {
				if (searchFromCell != currentCell) {
					if (searchFromCell) {
						searchFromCell.DisableHighlight();
					}
					searchFromCell = currentCell;
					searchFromCell.EnableHighlight(Color.blue);
					if (searchToCell) {
						hexGrid.FindPath(searchFromCell, searchToCell, 24);
					}
				}
			}
			else if (searchFromCell && searchFromCell != currentCell) {
				if (searchToCell != currentCell) {
					searchToCell = currentCell;
					hexGrid.FindPath(searchFromCell, searchToCell, 24);
				}
			}

Показываем метки только для пути

Отображение меток хода — довольно затратная операция, особенно потому, что мы используем неоптимизированный подход. Выполнение этой операции для всех ячеек совершенно точно затормозит выполнение. Поэтому давайте пропускать задание меток в HexGrid.Search.

				if (neighbor.Distance == int.MaxValue) {
					neighbor.Distance = distance;
//					neighbor.SetLabel(turn.ToString());
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
					searchFrontier.Enqueue(neighbor);
				}
				else if (distance < neighbor.Distance) {
					int oldPriority = neighbor.SearchPriority;
					neighbor.Distance = distance;
//					neighbor.SetLabel(turn.ToString());
					neighbor.PathFrom = current;
					searchFrontier.Change(neighbor, oldPriority);
				}

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

			if (current == toCell) {
				current = current.PathFrom;
				while (current != fromCell) {
					int turn = current.Distance / speed;
					current.SetLabel(turn.ToString());
					current.EnableHighlight(Color.white);
					current = current.PathFrom;
				}
				break;
			}

Отображаем метки только для ячеек пути

Теперь мы включаем только метки ячеек, находящихся между начальной и конечной. Но конечная точка — это самое важное, ей мы тоже должны задать метку. Можно сделать это, начав цикл пути с конечной ячейки, а не с ячейки перед ней. При этом посветка конечной точки с красной сменится на белую, поэтому её подсветку мы уберём под цикл.

		fromCell.EnableHighlight(Color.blue);
//		toCell.EnableHighlight(Color.red);

		fromCell.Distance = 0;
		searchFrontier.Enqueue(fromCell);
		while (searchFrontier.Count > 0) {
			HexCell current = searchFrontier.Dequeue();

			if (current == toCell) {
//				current = current.PathFrom;
				while (current != fromCell) {
					int turn = current.Distance / speed;
					current.SetLabel(turn.ToString());
					current.EnableHighlight(Color.white);
					current = current.PathFrom;
				}
				toCell.EnableHighlight(Color.red);
				break;
			}
			
			…
		}

Информация о ходе важнее всего для конечной точки

После этих изменений время наихудшего случая снизилось до 23 миллисекунд в редакторе и до 6 миллисекунд в готовой сборке. Это 43 pps и 166 pps — намного лучше.

unitypackage

Самый умный поиск

В предыдущей части мы сделали процедуру поиска умнее, реализовав алгоритм A^*. Однако на самом деле мы всё ещё не выполняем поиск наиболее оптимальным образом. В каждой итерации мы вычисляем расстояния от текущей ячейки до всех её соседей. Это верно для ячеек, которые пока не являются или являются в текущий момент частью границы поиска. Но ячейки, которые уже удалены из границы, больше рассматривать не нужно, потому что мы уже нашли кратчайший путь к этим ячейкам. Правильная реализация A^* пропускает эти ячейки, поэтому мы можем сделать так же.

Фаза поиска ячеек

Как мы узнаем, что ячейка уже покинула границу? Пока мы не можем этого определить. Поэтому нужно отслеживать в какой фазе поиска находится ячейка. Она ещё не находилась в границе или находится в ней сейчас, или находится за границей. Мы можем отслеживать это, добавив в HexCell простое целочисленное свойство.

	public int SearchPhase { get; set; }

Например, 0 означает, что ячейки ещё не достигли, 1 — что ячейка находится в границе сейчас, а 2 — что она уже удалена из границы.

Попадание в границу

В HexGrid.Search мы можем сбросить все ячейки на 0 и всегда использовать 1 для границы. Или мы можем увеличивать число границы при каждом новом поиске. Благодаря этому нам не придётся заниматься сбросом ячеек, если мы будем каждый раз увеличивать число границы на два.

	int searchFrontierPhase;
						
	…

	void Search (HexCell fromCell, HexCell toCell, int speed) {
		searchFrontierPhase += 2;
		…
	}

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

		fromCell.SearchPhase = searchFrontierPhase;
		fromCell.Distance = 0;
		searchFrontier.Enqueue(fromCell);

А также каждый раз, когда мы добавляем соседа к границе.

				if (neighbor.Distance == int.MaxValue) {
					neighbor.SearchPhase = searchFrontierPhase;
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
					searchFrontier.Enqueue(neighbor);
				}

Проверка границы

До данного момента для проверки того, что ячейку пока не добавляли к границе, мы использовали расстояние, равное int.MaxValue. Теперь мы можем сравнивать фазу поиска ячейки с текущей границей.

//				if (neighbor.Distance == int.MaxValue) {
				if (neighbor.SearchPhase < searchFrontierPhase) {
					neighbor.SearchPhase = searchFrontierPhase;
					neighbor.Distance = distance;
					neighbor.PathFrom = current;
					neighbor.SearchHeuristic =
						neighbor.coordinates.DistanceTo(toCell.coordinates);
					searchFrontier.Enqueue(neighbor);
				}

Это значит, что нам больше не нужно сбрасывать расстояния ячеек перед поиском, то есть придётся выполнять меньше работы, что хорошо.

		for (int i = 0; i < cells.Length; i++) {
//			cells[i].Distance = int.MaxValue;
			cells[i].SetLabel(null);
			cells[i].DisableHighlight();
		}

Покидание границы

Когда ячейка убирается из границы, мы обозначаем это увеличением её фазы поиска. Это ставит её за текущей границей и перед следующей.

		while (searchFrontier.Count > 0) {
			HexCell current = searchFrontier.Dequeue();
			current.SearchPhase += 1;
			
			…
		}

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

			for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
				HexCell neighbor = current.GetNeighbor(d);
				if (
					neighbor == null ||
					neighbor.SearchPhase > searchFrontierPhase
				) {
					continue;
				}
				…
			}

На этом этапе наш алгоритм по-прежнему создаёт те же результаты, но более эффективно. На моей машине поиск в наихудшем случае занимает 20 мс в редакторе и 5 мс в сборке.

Также мы можем подсчитать, сколько раз ячейка была обработана алгоритмом, увеличивая счётчик при вычислении расстояния до ячейки. Раньше наш алгоритм в худшем случае вычислял 28 239 расстояний. В готовом алгоритме A^* мы вычисляем вего 14 120 расстояний. Количество снизилось на 50%. Степень влияния этих показателей на производительность зависит от расходов при вычислении затрат на перемещение. В нашем случае работы здесь не так много, поэтому улучшение в сборке не очень велико, но сильно заметно в редакторе.

unitypackage

Очистка пути

При инициировании нового поиска нам сначала нужно очистить визуализацию предыдущего пути. Пока мы это делаем, отключая выделение и убирая метки у каждой ячейки сетки. Это очень тяжеловесный подход. В идеале нам нужно сбрасывать только те ячейки, которые являлись частью предыдущего пути.

Только поиск

Давайте начнём с того, что полностью уберём код визуализации из Search. Ему нужно только выполнять поиск пути и не обязательно знать, что мы сделаем с этой информацией.

	void Search (HexCell fromCell, HexCell toCell, int speed) {
		searchFrontierPhase += 2;
		if (searchFrontier == null) {
			searchFrontier = new HexCellPriorityQueue();
		}
		else {
			searchFrontier.Clear();
		}

//		for (int i = 0; i < cells.Length; i++) {
//			cells[i].SetLabel(null);
//			cells[i].DisableHighlight();
//		}
//		fromCell.EnableHighlight(Color.blue);

		fromCell.SearchPhase = searchFrontierPhase;
		fromCell.Distance = 0;
		searchFrontier.Enqueue(fromCell);
		while (searchFrontier.Count > 0) {
			HexCell current = searchFrontier.Dequeue();
			current.SearchPhase += 1;

			if (current == toCell) {
//				while (current != fromCell) {
//					int turn = current.Distance / speed;
//					current.SetLabel(turn.ToString());
//					current.EnableHighlight(Color.white);
//					current = current.PathFrom;
//				}
//				toCell.EnableHighlight(Color.red);
//				break;
			}

			…
		}
	}

Чтобы сообщить о том, что Search нашёл путь, мы будем возвращать boolean.

	bool Search (HexCell fromCell, HexCell toCell, int speed) {
		searchFrontierPhase += 2;
		if (searchFrontier == null) {
			searchFrontier = new HexCellPriorityQueue();
		}
		else {
			searchFrontier.Clear();
		}

		fromCell.SearchPhase = searchFrontierPhase;
		fromCell.Distance = 0;
		searchFrontier.Enqueue(fromCell);
		while (searchFrontier.Count > 0) {
			HexCell current = searchFrontier.Dequeue();
			current.SearchPhase += 1;

			if (current == toCell) {
				return true;
			}

			…
		}
		return false;
	}

Запоминаем путь

Когда путь найден, нам нужно его запомнить. Благодаря этому мы сможем очищать его в дальнейшем. Поэтому будем отслеживать концевые точки и то, есть ли между ними путь.

	HexCell currentPathFrom, currentPathTo;
	bool currentPathExists;
	
	…
	
	public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
		System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
		sw.Start();
		currentPathFrom = fromCell;
		currentPathTo = toCell;
		currentPathExists = Search(fromCell, toCell, speed);
		sw.Stop();
		Debug.Log(sw.ElapsedMilliseconds);
	}

Снова отображаем путь

Мы можем использовать записанные нами данные поиска, чтобы снова визуализировать путь. Создадим для этого новый метод ShowPath. Он будет проходить в цикле от конца до начала пути, подсвечивая ячейки и присваивая их меткам значение хода. Для этого нам нужно знать скорость, поэтому сделаем её параметром. Если у нас нет пути, то метод просто выделит концевые точки.

	void ShowPath (int speed) {
		if (currentPathExists) {
			HexCell current = currentPathTo;
			while (current != currentPathFrom) {
				int turn = current.Distance / speed;
				current.SetLabel(turn.ToString());
				current.EnableHighlight(Color.white);
				current = current.PathFrom;
			}
		}
		currentPathFrom.EnableHighlight(Color.blue);
		currentPathTo.EnableHighlight(Color.red);
	}

Вызовем этот метод в FindPath после поиска.

		currentPathExists = Search(fromCell, toCell, speed);
		ShowPath(speed);

Подчистка

Мы снова видим путь, но теперь он не удаляется. Чтобы очистить его, создадим метод ClearPath. По сути он является копией ShowPath, за исключением того, что отключает выделение и метки, а не включает их. Сделав это, он должен очистить записанные данные пути, которые больше не являются действительными.

	void ClearPath () {
		if (currentPathExists) {
			HexCell current = currentPathTo;
			while (current != currentPathFrom) {
				current.SetLabel(null);
				current.DisableHighlight();
				current = current.PathFrom;
			}
			current.DisableHighlight();
			currentPathExists = false;
		}
		currentPathFrom = currentPathTo = null;
	}

С помощью этого метода мы можем очищать визуализацию старого пути, посещая только необходимые ячейки, размер карты больше не важен. Вызовем его в FindPath перед запуском нового поиска.

		sw.Start();
		ClearPath();
		currentPathFrom = fromCell;
		currentPathTo = toCell;
		currentPathExists = Search(fromCell, toCell, speed);
		if (currentPathExists) {
			ShowPath(speed);
		}
		sw.Stop();

Кроме того, будем очищать путь при создании новой карты.

	public bool CreateMap (int x, int z) {
		…

		ClearPath();
		if (chunks != null) {
			for (int i = 0; i < chunks.Length; i++) {
				Destroy(chunks[i].gameObject);
			}
		}

		…
	}

А также перед загрузкой другой карты.

	public void Load (BinaryReader reader, int header) {
		ClearPath();
		…
	}

Визуализация путей снова очищается, как и до этого изменения. Но теперь мы используем более эффективный подход, и в наихудшем случае поиска время снизилось до 14 миллисекунд. Достаточно серьёзное улучшение только благодаря более умной очистке. Время в сборке снизилось до 3 мс, что составляет 333 pps. Благодаря этому поиск путей совершенно точно применим в реальном времени.

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

	public void FindPath (HexCell fromCell, HexCell toCell, int speed) {
//		System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
//		sw.Start();
		ClearPath();
		currentPathFrom = fromCell;
		currentPathTo = toCell;
		currentPathExists = Search(fromCell, toCell, speed);
		ShowPath(speed);
//		sw.Stop();
//		Debug.Log(sw.ElapsedMilliseconds);
	}

unitypackage

Часть 18: отряды

Размещаем отряды на карте.
Сохраняем и загружаем отряды.
Находим пути для отрядов.
Перемещаем отряды.

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

Подкрепление прибыло

Создание отрядов

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

Префаб отряда

Для работы с отрядами создадим новый тип компонента HexUnit. Пока начнём с пустого MonoBehaviour, а позже добавим к нему функционал.

using UnityEngine;

public class HexUnit : MonoBehaviour {
}

Создадим пустой игровой объект с этим компонентом, который должен стать префабом. Это будет корневой объект отряда.

Префаб отряда.

Добавим в качестве дочернего объекта 3D-модель, символизирующую отряд. Я использовал простой отмасштабированный куб, которому создал синий материал. Корневой объект определяет уровень земли отряда, поэтому соответствующим образом сместим дочерний элемент.

Дочерний элемент-куб

Добавим отряду коллайдер, чтобы в дальнейшем его было легче выбирать. Нам вполне подойдёт коллайдер стандартного куба, только сделаем так, чтобы коллайдер помещается в одну ячейку.

Создание экземпляров отрядов

Так как у нас пока нет игрового процесса, то создание отрядов происходит в режиме редактирования. Поэтому этим должен заниматься HexMapEditor. Для этого ему нужен префаб, поэтому добавим поле HexUnit unitPrefab и подключим его.

	public HexUnit unitPrefab;

Подключение префаба

При создании отрядов мы будем размещать их на ячейке, находящейся под курсором. В HandleInput есть код для нахождения этой ячейки при редактировании рельефа. Теперь он нам нужен и для отрядов, поэтому переместим соответствующий код в отдельный метод.

	HexCell GetCellUnderCursor () {
		Ray inputRay = Camera.main.ScreenPointToRay(Input.mousePosition);
		RaycastHit hit;
		if (Physics.Raycast(inputRay, out hit)) {
			return hexGrid.GetCell(hit.point);
		}
		return null;
	}

Теперь мы можем использовать этот метод в HandleInput, упростив его.

	void HandleInput () {
//		Ray inputRay = Camera.main.ScreenPointToRay(Input.mousePosition);
//		RaycastHit hit;
//		if (Physics.Raycast(inputRay, out hit)) {
//			HexCell currentCell = hexGrid.GetCell(hit.point);

		HexCell currentCell = GetCellUnderCursor();
		if (currentCell) {
			…
		}
		else {
			previousCell = null;
		}
	}

Далее добавим новый метод CreateUnit, который тоже использует GetCellUnderCursor. Если есть ячейка, мы будем создавать новый отряд.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell) {
			Instantiate(unitPrefab);
		}
	}

Чтобы иерархия была чистой, давайте используем сетку как родительский элемент для всех игровых объектов отрядов.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell) {
			HexUnit unit = Instantiate(unitPrefab);
			unit.transform.SetParent(hexGrid.transform, false);
		}
	}

Проще всего добавить в HexMapEditor поддержку создания отрядов через нажатие клавиши. Изменим метод Update так, чтобы он вызывал CreateUnit при нажатии клавиши U. Как и в случае с HandleInput, это должно происходить, если курсор не находится поверх элемента GUI. Сначала проверим, должны ли мы редактировать карту, и если нет, то проверим, должны ли мы добавлять отряд. Если да, то вызываем CreateUnit.

	void Update () {
//		if (
//			Input.GetMouseButton(0) &&
//			!EventSystem.current.IsPointerOverGameObject()
//		) {
//			HandleInput();
//		}
//		else {
//			previousCell = null;
//		}

		if (!EventSystem.current.IsPointerOverGameObject()) {
			if (Input.GetMouseButton(0)) {
				HandleInput();
				return;
			}
			if (Input.GetKeyDown(KeyCode.U)) {
				CreateUnit();
				return;
			}
		}
		previousCell = null;
	}

Созданный экземпляр отряда

Размещение отрядов

Теперь мы можем создавать отряды, но они появляются в точке начала координат карты. Нам нужно помещать их в нужное место. Для этого необходимо, чтобы отряды знали о своей позиции. Поэтому добавим в HexUnit свойство Location, обозначающее занимаемую ими ячейку. При задании свойства изменим позицию отряда так, чтобы он соответствовал позиции ячейки.

	public HexCell Location {
		get {
			return location;
		}
		set {
			location = value;
			transform.localPosition = value.Position;
		}
	}

	HexCell location;

Теперь HexMapEditor.CreateUnit должен присвоить позиции отряда ячейку под курсором. Тогда отряды будут находиться там, где должны.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell) {
			HexUnit unit = Instantiate(unitPrefab);
			unit.transform.SetParent(hexGrid.transform, false);
			unit.Location = cell;
		}
	}

Расположенные на карте отряды

Ориентация отрядов

Пока все отряды имеют одинаковую ориентацию, что выглядит довольно неестественно. Чтобы оживить их, добавим в HexUnit свойство Orientation. Это значение float, обозначающее поворот отряда по оси Y в градусах. При его задании будем соответствующим образом менять поворот самого игрового объекта.

	public float Orientation {
		get {
			return orientation;
		}
		set {
			orientation = value;
			transform.localRotation = Quaternion.Euler(0f, value, 0f);
		}
	}

	float orientation;

В HexMapEditor.CreateUnit назначим случайный поворот от 0 до 360 градусов.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell) {
			HexUnit unit = Instantiate(unitPrefab);
			unit.transform.SetParent(hexGrid.transform, false);
			unit.Location = cell;
			unit.Orientation = Random.Range(0f, 360f);
		}
	}

Разные ориентации отрядов

По одному отряду на ячейку

Отряды выглядят неплохо, если не создаются в одной ячейке. В этом случае мы получаем скопление странно выглядящих кубов.

Наложенные друг на друга отряды

Некоторые игры допускают размещение нескольких отрядов на одном месте, другие нет. Так как проще работать с одним отрядом на ячейку, я выберу этот вариант. Это значит, что мы должны создавать новый отряд только тогда, когда текущая ячейка не занята. Чтобы это можно было узнать, добавим в HexCell стандартное свойство Unit.

	public HexUnit Unit { get; set; }

Используем это свойство в HexUnit.Location, чтобы ячейка узнала, стоит ли на ней отряд.

	public HexCell Location {
		get {
			return location;
		}
		set {
			location = value;
			value.Unit = this;
			transform.localPosition = value.Position;
		}
	}

Теперь HexMapEditor.CreateUnit может проверять, свободна ли текущая ячейка.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && !cell.Unit) {
			HexUnit unit = Instantiate(unitPrefab);
			unit.Location = cell;
			unit.Orientation = Random.Range(0f, 360f);
		}
	}

Редактирование занятых ячеек

Изначально отряды размещаются правильно, но всё может измениться, если в дальнейшем их ячейки будут редактироваться. Если высота ячейки изменится, то занимающий её отряд или будет висеть над ней, или погрузится в неё.

Висящие и утонувшие отряды

Решение заключается в проверке позиции отряда после внесения изменений. Для этого добавим метод в HexUnit. Пока нас интересует только позиция отряда, поэтому просто зададим её заново.

	public void ValidateLocation () {
		transform.localPosition = location.Position;
	}

Мы должны согласовывать позицию отряда при обновлении ячейки, что происходит, когда вызываются методы Refresh, или RefreshSelfOnly объекта HexCell. Разумеется, это необходимо, только когда в ячейке действительно есть отряд.

	void Refresh () {
		if (chunk) {
			chunk.Refresh();
			…
			if (Unit) {
				Unit.ValidateLocation();
			}
		}
	}

	void RefreshSelfOnly () {
		chunk.Refresh();
		if (Unit) {
			Unit.ValidateLocation();
		}
	}

Удаление отрядов

Кроме создания отрядов полезно было бы их и уничтожать. Поэтому добавим в HexMapEditor метод DestroyUnit. Он должен проверять, есть ли в ячейке под курсором отряд, и если есть, то уничтожать игровой объект отряда.

	void DestroyUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && cell.Unit) {
			Destroy(cell.Unit.gameObject);
		}
	}

Учтите, чтобы добраться до отряда, мы проходим через ячейку. Для взаимодействия с отрядом достаточно навести мышь на его ячейку. Поэтому чтобы это работало, отряду не обязательно иметь коллайдер. Однако добавление коллайдера упрощает их выделение, потому что он блокирует лучи, которые в противном случае столкнулись бы с ячейкой за отрядом.

Давайте для уничтожения отряда в Update используем комбинацию левого Shift+U.

			if (Input.GetKeyDown(KeyCode.U)) {
				if (Input.GetKey(KeyCode.LeftShift)) {
					DestroyUnit();
				}
				else {
					CreateUnit();
				}
				return;
			}

В случае, когда мы создаём и уничтожаем несколько отрядов, давайте будем аккуратными и очистим свойство при удалении отряда. То есть мы явным образом очистим ссылку ячейки на отряд. Добавим в HexUnit метод Die, который займётся этим, а также уничтожением собственного игрового объекта.

	public void Die () {
		location.Unit = null;
		Destroy(gameObject);
	}

Будем вызывать этот метод в HexMapEditor.DestroyUnit, а не уничтожать отряд напрямую.

	void DestroyUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && cell.Unit) {
//			Destroy(cell.Unit.gameObject);
			cell.Unit.Die();
		}
	}

unitypackage

Сохранение и загрузка отрядов

Теперь, когда у нас на карте могут быть отряды, мы должны включить их в процесс сохранения и загрузки. Мы можем подойти к этой задаче двумя способами. Первый — записывать данные отряда при записи ячейки, чтобы данные ячейки и отряда были перемешаны. Второй способ — сохранять данные ячеек и отрядов по отдельности. Хотя может показаться, что первый подход проще в реализации, второй даёт нам более структурированные данные. Если мы разделим данные, то с ними будет проще работать в будущем.

Отслеживание отрядов

Чтобы сохранить все отряды вместе, нам нужно их отслеживать. Мы сделаем это, добавив в HexGrid список отрядов. Этот список должен содержать все отряды на карте.

	List<HexUnit> units = new List<HexUnit>();

При создании или загрузке новой карты нам нужно избавиться от всех отрядов, находящихся на карте. Чтобы упростить этот процесс, создадим метод ClearUnits, который убивает всех в списке и очищает его.

	void ClearUnits () {
		for (int i = 0; i < units.Count; i++) {
			units[i].Die();
		}
		units.Clear();
	}

Вызовем этот метод в CreateMap и в Load. Давайте делать это после очистки пути.

	public bool CreateMap (int x, int z) {
		…

		ClearPath();
		ClearUnits();
		…
	}
	
	…
	
	public void Load (BinaryReader reader, int header) {
		ClearPath();
		ClearUnits();
		…
	}

Добавление отрядов к сетке

Теперь при создании новых отрядов нам нужно добавлять их в список. Давайте зададим для этого метод AddUnit, который также займётся расположением отряда и заданием параметров его родительского объекта.

	public void AddUnit (HexUnit unit, HexCell location, float orientation) {
		units.Add(unit);
		unit.transform.SetParent(transform, false);
		unit.Location = location;
		unit.Orientation = orientation;
	}

Теперь HexMapEditor.CreatUnit будет достаточно вызвать AddUnit с новым экземпляром отряда, его местоположением и случайной ориентацией.

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && !cell.Unit) {
//			HexUnit unit = Instantiate(unitPrefab);
//			unit.transform.SetParent(hexGrid.transform, false);
//			unit.Location = cell;
//			unit.Orientation = Random.Range(0f, 360f);
			hexGrid.AddUnit(
				Instantiate(unitPrefab), cell, Random.Range(0f, 360f)
			);
		}
	}

Удаление отрядов из сетки

Добавим метод для удаления отряда и в HexGrid. Просто удалим отряд из списка и прикажем ему умереть.

	public void RemoveUnit (HexUnit unit) {
		units.Remove(unit);
		unit.Die();
	}

Вызовем этот метод в HexMapEditor.DestroyUnit, вместо уничтожения отряда напрямую.

	void DestroyUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && cell.Unit) {
//			cell.Unit.Die();
			hexGrid.RemoveUnit(cell.Unit);
		}
	}

Сохранение отрядов

Так как мы собираемся сохранять все отряды вместе, нам нужно запомнить, какие ячейки они занимают. Наиболее надёжный способ заключается в сохранении координат их местоположения. Чтобы это было возможно, добавим в HexCoordinates метод Save, записывающий его поля X и Z.

using UnityEngine;
using System.IO;

[System.Serializable]
public struct HexCoordinates {

	…
	
	public void Save (BinaryWriter writer) {
		writer.Write(x);
		writer.Write(z);
	}
}

Метод Save для HexUnit теперь может записывать координаты и ориентацию отряда. Это все данные отрядов, которые у нас есть на данный момент.

using UnityEngine;
using System.IO;

public class HexUnit : MonoBehaviour {

	…

	public void Save (BinaryWriter writer) {
		location.coordinates.Save(writer);
		writer.Write(orientation);
	}
}

Так как HexGrid отслеживает отряды, его метод Save займётся записью данных отрядов. Сначала запишем общее количество отрядов, а затем обойдём их все в цикле.

	public void Save (BinaryWriter writer) {
		writer.Write(cellCountX);
		writer.Write(cellCountZ);

		for (int i = 0; i < cells.Length; i++) {
			cells[i].Save(writer);
		}

		writer.Write(units.Count);
		for (int i = 0; i < units.Count; i++) {
			units[i].Save(writer);
		}
	}

Мы изменили сохраняемые данные, поэтому увеличим номер версии в SaveLoadMenu.Save до 2. Старый код загрузки всё равно будет работать, потому что он просто не будет считывать данные отрядов. Тем не менее, нужно увеличить номер версии, чтобы сообщить, что в файле есть данные отрядов.

	void Save (string path) {
		using (
			BinaryWriter writer =
			new BinaryWriter(File.Open(path, FileMode.Create))
		) {
			writer.Write(2);
			hexGrid.Save(writer);
		}
	}

Загрузка отрядов

Так как HexCoordinates является структурой, то не имеет особого смысла добавлять ему обычный метод Load. Сделаем его статическим методом, который считывает и возвращает сохранённые координаты.

	public static HexCoordinates Load (BinaryReader reader) {
		HexCoordinates c;
		c.x = reader.ReadInt32();
		c.z = reader.ReadInt32();
		return c;
	}

Так как количество отрядов является переменным, у нас нет заранее существующих отрядов, в которые можно загружать данные. Мы можем создать новые экземпляры отрядов до загрузки их данных, но для этого потребуется, чтобы HexGrid создавал экземпляры новых отрядов во время загрузки. Так что лучше оставить это HexUnit. Также мы используем статический метод HexUnit.Load. Давайте начнём с простого считывания данных отрядов. Для считывания значения float ориентации воспользуемся методом BinaryReader.ReadSingle.

Почему Single?

Тип float представляет собой числа с плавающей запятой одинарной точности, которые имеют длину четыре байта. Существуют также числа двойной точности, задаваемые как double, которые имеют длину восемь байтов. В Unity они используются редко.

	public static void Load (BinaryReader reader) {
		HexCoordinates coordinates = HexCoordinates.Load(reader);
		float orientation = reader.ReadSingle();
	}

Следующим этапом будет создание экземпляра нового отряда. Однако для этого нам нужна ссылка на префаб отряда. Чтобы пока не усложнять, давайте для этого добавим в HexUnit статический метод.

	public static HexUnit unitPrefab;

Чтобы задать эту ссылку, давайте ещё раз воспользуемся HexGrid, как мы это делали с текстурой шума. Когда нам нужно будет поддерживать много типов отрядов, мы перейдём к более хорошему решению.

	public HexUnit unitPrefab;

	…

	void Awake () {
		HexMetrics.noiseSource = noiseSource;
		HexMetrics.InitializeHashGrid(seed);
		HexUnit.unitPrefab = unitPrefab;
		CreateMap(cellCountX, cellCountZ);
	}

	…

	void OnEnable () {
		if (!HexMetrics.noiseSource) {
			HexMetrics.noiseSource = noiseSource;
			HexMetrics.InitializeHashGrid(seed);
			HexUnit.unitPrefab = unitPrefab;
		}
	}

Передаём префаб отряда

После подключения поля нам больше не нужна прямая ссылка в HexMapEditor. Вместо неё он может использовать HexUnit.unitPrefab.

//	public HexUnit unitPrefab;

	…

	void CreateUnit () {
		HexCell cell = GetCellUnderCursor();
		if (cell && !cell.Unit) {
			hexGrid.AddUnit(
				Instantiate(HexUnit.unitPrefab), cell, Random.Range(0f, 360f)
			);
		}
	}

Теперь мы можем создать экземпляр нового отряда в HexUnit.Load. Вместо того, чтобы возвращать его, мы можем использовать загруженные координаты и ориентацию, чтобы добавить его на сетку. Чтобы это было возможно, добавим параметр HexGrid.

	public static void Load (BinaryReader reader, HexGrid grid) {
		HexCoordinates coordinates = HexCoordinates.Load(reader);
		float orientation = reader.ReadSingle();
		grid.AddUnit(
			Instantiate(unitPrefab), grid.GetCell(coordinates), orientation
		);
	}

В конце HexGrid.Load считаем количество отрядов и используем его для загрузки всех сохранённых отрядов, передавая себя в качестве дополнительного аргумента.

	public void Load (BinaryReader reader, int header) {
		…

		int unitCount = reader.ReadInt32();
		for (int i = 0; i < unitCount; i++) {
			HexUnit.Load(reader, this);
		}
	}

Разумеется, это сработает только для файлов сохранений с версией не ниже 2, в младших версиях отрядов для загрузки нет.

		if (header >= 2) {
			int unitCount = reader.ReadInt32();
			for (int i = 0; i < unitCount; i++) {
				HexUnit.Load(reader, this);
			}
		}

Теперь мы можем корректно загружать файлы версии 2, поэтому в SaveLoadMenu.Load увеличим номер поддерживаемой версии до 2.

	void Load (string path) {
		if (!File.Exists(path)) {
			Debug.LogError("File does not exist " + path);
			return;
		}
		using (BinaryReader reader = new BinaryReader(File.OpenRead(path))) {
			int header = reader.ReadInt32();
			if (header <= 2) {
				hexGrid.Load(reader, header);
				HexMapCamera.ValidatePosition();
			}
			else {
				Debug.LogWarning("Unknown map format " + header);
			}
		}
	}

unitypackage

Перемещение отрядов

Отряды мобильны, поэтому мы должны иметь возможность перемещать их по карте. У нас уже есть код поиска пути, но пока мы тестировали его только для произвольных мест. Теперь нам нужно удалить старый тестовый UI и создать новый UI для управления отрядами.

Подчистка редактора карты

Перемещение отрядов по путям — это часть настоящего геймплея, оно не относится к редактору карт. Поэтому избавимся в HexMapEditor от всего кода, связанного с поиском пути.

//	HexCell previousCell, searchFromCell, searchToCell;
	HexCell previousCell;
	
	…
	
		void HandleInput () {
		HexCell currentCell = GetCellUnderCursor();
		if (currentCell) {
			if (previousCell && previousCell != currentCell) {
				ValidateDrag(currentCell);
			}
			else {
				isDrag = false;
			}
			if (editMode) {
				EditCells(currentCell);
			}
//			else if (
//				Input.GetKey(KeyCode.LeftShift) && searchToCell != currentCell
//			) {
//				if (searchFromCell != currentCell) {
//					if (searchFromCell) {
//						searchFromCell.DisableHighlight();
//					}
//					searchFromCell = currentCell;
//					searchFromCell.EnableHighlight(Color.blue);
//					if (searchToCell) {
//						hexGrid.FindPath(searchFromCell, searchToCell, 24);
//					}
//				}
//			}
//			else if (searchFromCell && searchFromCell != currentCell) {
//				if (searchToCell != currentCell) {
//					searchToCell = currentCell;
//					hexGrid.FindPath(searchFromCell, searchToCell, 24);
//				}
//			}
			previousCell = currentCell;
		}
		else {
			previousCell = null;
		}
	}

После удаления этого кода больше не имеет смысла оставлять редактор активным, когда мы не находимся в режиме редактирования. Поэтому вместо поля для отслеживания режима мы просто можем включать или отключать компонент HexMapEditor. Кроме того, теперь редактор не должен заниматься метками UI.

//	bool editMode;
	
	…
	
	public void SetEditMode (bool toggle) {
//		editMode = toggle;
//		hexGrid.ShowUI(!toggle);
		enabled = toggle;
	}
	
	…
	
	void HandleInput () {
		HexCell currentCell = GetCellUnderCursor();
		if (currentCell) {
			if (previousCell && previousCell != currentCell) {
				ValidateDrag(currentCell);
			}
			else {
				isDrag = false;
			}
//			if (editMode) {
			EditCells(currentCell);
//			}
			previousCell = currentCell;
		}
		else {
			previousCell = null;
		}
	}

Так как по умолчанию мы не находимся в режиме редактирования карты, в Awake мы будем отключать редактор.

	void Awake () {
		terrainMaterial.DisableKeyword("GRID_ON");
		SetEditMode(false);
	}

Использовать raycast для поиска текущей ячейки под курсором необходимо и при редактировании карты, и для управления отрядами. Возможно, в будущем он пригодится нам и для чего-то другого. Давайте переместим логику raycasting из HexGrid в новый метод GetCell с параметром-лучом.

	public HexCell GetCell (Ray ray) {
		RaycastHit hit;
		if (Physics.Raycast(ray, out hit)) {
			return GetCell(hit.point);
		}
		return null;
	}

HexMapEditor.GetCellUniderCursor может просто вызывать этот метод с лучом курсора.

	HexCell GetCellUnderCursor () {
		return
			hexGrid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
	}

Игровой UI

Для управления UI игрового режима мы воспользуемся новым компонентом. Пока он будет заниматься только выбором и перемещением отрядов. Создадим для него новый тип компонента HexGameUI. Для выполнения своей работы ему достаточно ссылки на сетку.

using UnityEngine;
using UnityEngine.EventSystems;

public class HexGameUI : MonoBehaviour {

	public HexGrid grid;
}

Добавим этот компонент к новому игровому объекту в иерархии UI. Он не обязан иметь собственный объект, но так нам будет очевидно, что существует отдельный UI для игры.

Объект Game UI

Добавим HexGameUI метод SetEditMode, как и в HexMapEditor. Игровой UI должен быть включен, когда мы не находимся в режиме редактирования. Кроме того, здесь нужно включить метки, потому что игровой UI работает с путями.

	public void SetEditMode (bool toggle) {
		enabled = !toggle;
		grid.ShowUI(!toggle);
	}

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

Несколько методов события.

Отслеживание текущей ячейки

В зависимости от ситуации HexGameUI нужно знать, какая ячейка в данный момент находится под курсором. Поэтому добавим ему поле currentCell.

	HexCell currentCell;

Создадим метод UpdateCurrentCell, который использует HexGrid.GetCell с лучом курсора для обновления этого поля.

	void UpdateCurrentCell () {
		currentCell =
			grid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
	}

При обновлении текущей ячейки нам может понадобиться узнать, изменилась ли она. Заставим UpdateCurrentCell возвращать эту информацию.

	bool UpdateCurrentCell () {
		HexCell cell =
			grid.GetCell(Camera.main.ScreenPointToRay(Input.mousePosition));
		if (cell != currentCell) {
			currentCell = cell;
			return true;
		}
		return false;
	}

Выбор отряда

Прежде чем переместить отряд, его нужно выбрать и отслеживать. Поэтому добавим поле selectedUnit.

	HexUnit selectedUnit;

Когда мы пытаемся выполнить выбор, то нужно начинать с обновления текущей ячейки. Если текущая ячейка есть то занимающий эту ячейку отряд становится выбранным отрядом. Если в ячейке нет отряда, то никакой отряд не выбирается. Создадим для этого метод DoSelection.

	void DoSelection () {
		UpdateCurrentCell();
		if (currentCell) {
			selectedUnit = currentCell.Unit;
		}
	}

Мы реализуем выбор отрядов простым нажатием мыши. Поэтому добавим метод Update, выполняющий выбор при активации кнопки мыши 0. Разумеется, нам нужно выполнять его, только когда курсор не находится над элементом GUI.

	void Update () {
		if (!EventSystem.current.IsPointerOverGameObject()) {
			if (Input.GetMouseButtonDown(0)) {
				DoSelection();
			}
		}
	}

На данном этапе мы научились выбирать по одному отряду за раз с помощью нажатия мыши. При нажатии на пустую ячейку выбор любого отряда снимается. Но пока мы не получаем никакого визуального подтверждения этого.

Поиск пути отрядом

Когда отряд выбран, мы можем использовать его местоположение как начальную точку для поиска пути. Чтобы активировать это, мы не будем требовать ещё одно нажатие кнопки мыши. Вместо этого будем автоматически находить и показывать путь между позицией отряда и текущей ячейкой. Всегда будем делать это в Update, за исключением момента, когда выполняется выбор. Для этого когда у нас есть отряд, мы вызываем метод DoPathfinding.

	void Update () {
		if (!EventSystem.current.IsPointerOverGameObject()) {
			if (Input.GetMouseButtonDown(0)) {
				DoSelection();
			}
			else if (selectedUnit) {
				DoPathfinding();
			}
		}
	}

DoPathfinding просто обновляет текущую ячейку и вызывает HexGrid.FindPath, если есть конечная точка. Мы снова используем постоянную скорость 24.

	void DoPathfinding () {
		UpdateCurrentCell();
		grid.FindPath(selectedUnit.Location, currentCell, 24);
	}

Учтите, что мы должны находить новый путь не при каждом обновлении, а только при изменении текущей ячейки.

	void DoPathfinding () {
		if (UpdateCurrentCell()) {
			grid.FindPath(selectedUnit.Location, currentCell, 24);
		}
	}

Поиск пути для отряда

Теперь мы видим пути, появляющиеся при перемещении курсора после выбора отряда. Благодаря этому очевидно, какой отряд выбран. Однако пути не всегда очищаются правильно. Для начала давайте очищать старый путь, если курсор оказывается за пределами карты.

	void DoPathfinding () {
		if (UpdateCurrentCell()) {
			if (currentCell) {
				grid.FindPath(selectedUnit.Location, currentCell, 24);
			}
			else {
				grid.ClearPath();
			}
		}
	}

Разумеется, для этого нужно, чтобы HexGrid.ClearPath был общим, поэтому внесём такое изменение.

	public void ClearPath () {
		…
	}

Во-вторых, будем очищать старый путь при выборе отряда.

	void DoSelection () {
		grid.ClearPath();
		UpdateCurrentCell();
		if (currentCell) {
			selectedUnit = currentCell.Unit;
		}
	}

Наконец, станем очищать путь при изменении режима редактирования.

	public void SetEditMode (bool toggle) {
		enabled = !toggle;
		grid.ShowUI(!toggle);
		grid.ClearPath();
	}

Поиск только для допустимых конечных точек

Мы не всегда можем найти путь, потому что иногда достичь конечной ячейки невозможно. Это нормально. Но иногда сама конечная ячейка является недопустимой. Например, мы решили, что пути не могут включать в себя подводные ячейки. Но это может зависеть от отряда. Давайте добавим в HexUnit метод, сообщающий нам, является ли ячейка допустимой конечной точкой. Подводные ячейки ими не являются.

	public bool IsValidDestination (HexCell cell) {
		return !cell.IsUnderwater;
	}

Кроме того, мы разрешили стоять в ячейке только одному отряду. Поэтому конечная ячейка не будет допустимой, если она занята.

	public bool IsValidDestination (HexCell cell) {
		return !cell.IsUnderwater && !cell.Unit;
	}

Используем этот метод в HexGameUI.DoPathfinding, чтобы игнорировать недопустимые конечные точки.

	void DoPathfinding () {
		if (UpdateCurrentCell()) {
			if (currentCell && selectedUnit.IsValidDestination(currentCell)) {
				grid.FindPath(selectedUnit.Location, currentCell, 24);
			}
			else {
				grid.ClearPath();
			}
		}
	}

Перемещение к конечной точке

Если у нас есть допустимый путь, то мы имеем возможность переместить отряд в конечную точку. HexGrid знает, когда это можно сделать. Сделаем так, чтобы он передавал эту информацию в новом свойстве только для чтения HasPath.

	public bool HasPath {
		get {
			return currentPathExists;
		}
	}

Чтобы переместить отряд, добавим в HexGameUI метод DoMove. Этот метод будет вызываться при подаче команды и в случае, если отряд выбран. Поэтому он должен проверять, есть ли путь, и если есть, менять местоположение отряда. Пока мы сразу телепортируем отряд в конечную точку. В одном из следующих туториалов мы сделаем так, чтобы отряд на самом деле проходил весь путь.

	void DoMove () {
		if (grid.HasPath) {
			selectedUnit.Location = currentCell;
			grid.ClearPath();
		}
	}

Давайте для подачи команды используем кнопку мыши 1 (нажатие правой кнопки). Будем проверять это, если выбран отряд. Если кнопка не нажата, то мы выполняем поиск пути.

	void Update () {
		if (!EventSystem.current.IsPointerOverGameObject()) {
			if (Input.GetMouseButtonDown(0)) {
				DoSelection();
			}
			else if (selectedUnit) {
				if (Input.GetMouseButtonDown(1)) {
					DoMove();
				}
				else {
					DoPathfinding();
				}
			}
		}
	}

Теперь мы можем перемещать отряды! Но иногда они отказываются находить путь к некоторым ячейкам. В частности, к тем ячейкам, в которых раньше был отряд. Так происходит, потому что HexUnit не обновляет старое местоположение при задании нового. Чтобы исправить это, будем очищать ссылку на отряд в его старом местоположении.

	public HexCell Location {
		get {
			return location;
		}
		set {
			if (location) {
				location.Unit = null;
			}
			location = value;
			value.Unit = this;
			transform.localPosition = value.Position;
		}
	}

Избегаем отрядов

Поиск пути сейчас работает верно, а отряды могут телепортироваться по карте. Хотя они не могут перемещаться в ячейки, в которых уже есть отряд, пока игнорируются отряды, стоящие на пути.

Отряды на пути игнорируются

Отряды одной фракции обычно могут перемещаться друг через друга, но пока у нас нет фракций. Поэтому давайте считать все отряды несвязанными друг с другом и блокирующими пути. Это можно реализовать, пропуская занятые ячейки в HexGrid.Search.

				if (
					neighbor == null ||
					neighbor.SearchPhase > searchFrontierPhase
				) {
					continue;
				}
				if (neighbor.IsUnderwater || neighbor.Unit) {
					continue;
				}

Избегаем отрядов

unitypackage

Часть 19: анимация движения

Перемещаем отряды между ячейками.
Визуализируем пройденный путь.
Перемещаем отряды по кривым.
Заставляем отряды смотреть в сторону движения.

В этой части мы заставим отряды вместо телепортации двигаться по путям.

Отряды в пути

Движение по пути

В предыдущей части мы добавили отряды и возможность их перемещения. Хоть мы и использовали для определения допустимых конечных точек поиск пути, после подачи команды отряды просто телепортировались в конечную ячейку. Чтобы они на самом деле следовали по найденному пути, нам нужно отслеживать этот путь и создать процесс анимации, заставляющий отряд перемещаться от ячейки к ячейке. Так как глядя на анимации сложно заметить, как перемещался отряд, мы также визуализируем пройденный путь с помощь gizmos. Но прежде чем двинуться дальше, нам нужно исправить ошибку.

Ошибка с поворотами

Из-за недосмотра мы неверно вычисляем ход, на котором будет достигнута ячейка. Сейчас мы определяем ход делением общего расстояния на скорость отряда $inline$ , и отбрасывая остаток. Ошибка происходит, когда для попадания в ячейку нужно потратить ровно все оставшиеся очки движения на ход.

Например, когда каждый шаг стоит 1, а скорость равна 3, то мы можем перемещаться на три ячейки за ход. Однако при существующих вычислениях мы сможем сделать только два шага за первый ход, потому что для третьего шага $inline$ .

Суммируемые затраты на перемещение с неверно определяемыми ходами, скорость 3

Для правильного вычисления ходов нам нужно переместить границу на один шаг от начальной ячейке. Мы можем сделать это, перед вычислением хода уменьшив расстояние на 1. Тогда ход для третьего шага будет $inline$

Правильные ходы

Мы можем это сделать, изменив формулу вычислений на $inline$ . Внесём это изменение в HexGrid.Search.

	bool Search (HexCell fromCell, HexCell toCell, int speed) {
		…
		while (searchFrontier.Count > 0) {
			…

			int currentTurn = (current.Distance - 1) / speed;

			for (HexDirection d = HexDirection.NE; d <= HexDirection.NW; d++) {
				…

				int distance = current.Distance + moveCost;
				int turn = (distance - 1) / speed;
				if (turn > currentTurn) {
					distance = turn * speed + moveCost;
				}

				…
			}
		}
		return false;
	}

Изменим также метки ходов.

	void ShowPath (int speed) {
		if (currentPathExists) {
			HexCell current = currentPathTo;
			while (current != currentPathFrom) {
				int turn = (current.Distance - 1) / speed;
				…
			}
		}
		…
	}

Заметьте, что при таком подходе ход начальной ячейки равен −1. Это нормально, потому что мы не отображаем его, а алгоритм поиска остаётся исправным.

Получение пути

Перемещение по пути — это задача отряда. Чтобы он мог это делать, ему необходимо знать путь. Эта информация есть у HexGrid, поэтому добавим к нему метод для получения текущего пути в виде списка ячеек. Он может брать его из пула списков и возвращать, если путь действительно есть.

	public List<HexCell> GetPath () {
		if (!currentPathExists) {
			return null;
		}
		List<HexCell> path = ListPool<HexCell>.Get();
		return path;
	}

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

		List<HexCell> path = ListPool<HexCell>.Get();
		for (HexCell c = currentPathTo; c != currentPathFrom; c = c.PathFrom) {
			path.Add(c);
		}
		return path;

В данном случае нам нужен весь путь, который включает в себя и начальную ячейку.

		for (HexCell c = currentPathTo; c != currentPathFrom; c = c.PathFrom) {
			path.Add(c);
		}
		path.Add(currentPathFrom);
		return path;

Теперь у нас есть путь в обратном порядке. Мы можем с ним работать, но это будет не очень интуитивно понятно. Давайте перевернём список, чтобы он шёл от начала к концу.

		path.Add(currentPathFrom);
		path.Reverse();
		return path;

Запрос движения

Теперь мы можем добавить в HexUnit метод, приказывающий ему следовать по пути. Изначально мы просто позволяли ему телепортироваться к конечной ячейке. Мы не будем сразу же возвращать список в пул, потому что он нам пригодится на какое-то время.

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

public class HexUnit : MonoBehaviour {

	…

	public void Travel (List<HexCell> path) {
		Location = path[path.Count - 1];
	}

	…
}

Чтобы запросить движение, изменим HexGameUI.DoMove так, чтобы он вызывал новый метод с текущим путём, а не просто задавал местоположение отряда.

	void DoMove () {
		if (grid.HasPath) {
//			selectedUnit.Location = currentCell;
			selectedUnit.Travel(grid.GetPath());
			grid.ClearPath();
		}
	}

Визуализация пути

Прежде чем мы начнём анимировать отряд, давайте проверим, что пути верны. Мы будем это делать, приказав HexUnit запомнить путь, по которому он должен перемещаться, чтобы можно было визуализировать его с помощью gizmos.

	List<HexCell> pathToTravel;

	…

	public void Travel (List<HexCell> path) {
		Location = path[path.Count - 1];
		pathToTravel = path;
	}

Добавим метод OnDrawGizmos, чтобы показать последний путь, по которому нужно пройти (если он существует). Если отряд пока не двигался, путь должен быть равен null. Но из-за сериализации Unity во время редактирования после рекомпиляции в режиме Play он также может быть пустым списком.

	void OnDrawGizmos () {
		if (pathToTravel == null || pathToTravel.Count == 0) {
			return;
		}
	}

Проще всего показать путь — отрисовать сферу-гизмо для каждой ячейки пути. Нам подойдёт сфера радиусом 2 единицы.

	void OnDrawGizmos () {
		if (pathToTravel == null || pathToTravel.Count == 0) {
			return;
		}

		for (int i = 0; i < pathToTravel.Count; i++) {
			Gizmos.DrawSphere(pathToTravel[i].Position, 2f);
		}
	}

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

Gizmos отображают последние пройденные пути

Чтобы лучше показать соединения ячеек, нарисуем в цикле несколько сфер на прямой между предыдущей и текущей ячейками. Для этого нам нужно начать процесс со второй ячейки. Сферы можно располагать с помощью линейной интерполяции с инкрементом 0.1 единиц, так что у нас получится по десять сфер на сегмент.

		for (int i = 1; i < pathToTravel.Count; i++) {
			Vector3 a = pathToTravel[i - 1].Position;
			Vector3 b = pathToTravel[i].Position;
			for (float t = 0f; t < 1f; t += 0.1f) {
				Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
			}
		}

Более очевидные пути

Скольжение по пути

Тем же способом можно воспользоваться для перемещения отрядов. Давайте создадим для этого корутину. Вместо отрисовки гизмо будем задавать позицию отряда. Воспользуемся вместо инкремента 0.1 дельтой времени, и будем выполнять yield для каждой итерации. При этом отряд будет двигаться от одной ячейки к следующей за одну секунду.

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

public class HexUnit : MonoBehaviour {

	…
	
	IEnumerator TravelPath () {
		for (int i = 1; i < pathToTravel.Count; i++) {
			Vector3 a = pathToTravel[i - 1].Position;
			Vector3 b = pathToTravel[i].Position;
			for (float t = 0f; t < 1f; t += Time.deltaTime) {
				transform.localPosition = Vector3.Lerp(a, b, t);
				yield return null;
			}
		}
	}
	
	…
}

Начнём корутину в конце метода Travel. Но прежде остановим все существующие корутины. Так мы гарантируем, что одновременно не запустятся две корутины, иначе это привело бы к очень странным результатам.

	public void Travel (List<HexCell> path) {
		Location = path[path.Count - 1];
		pathToTravel = path;
		StopAllCoroutines();
		StartCoroutine(TravelPath());
	}

Перемещение по одной ячейке за секунду — это довольно медленно. Игрок в процессе игры не захочет ждать так долго. Можно сделать скорость перемещения отряда опцией конфигурации, но пока давайте используем константу. Я присвоил ей значение в 4 ячейки за секунду; это довольно быстро, но позволяет заметить, что происходит.

	const float travelSpeed = 4f;

	…

	IEnumerator TravelPath () {
		for (int i = 1; i < pathToTravel.Count; i++) {
			Vector3 a = pathToTravel[i - 1].Position;
			Vector3 b = pathToTravel[i].Position;
			for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
				transform.localPosition = Vector3.Lerp(a, b, t);
				yield return null;
			}
		}
	}

Так же, как мы можем визуализировать несколько путей одновременно, можно заставить путешествовать одновременно несколько отрядов. С точки зрения игрового состояния движение по-прежнему является телепортацией, анимации исключительно визуальные. Отряды мгновенно занимают конечную ячейку. Можно даже найти пути и начать новое перемещение, пока они ещё не прибыли. В этом случае визуально они телепортируются к началу нового пути. Этого можо избежать, заблокировав отряды или даже весь UI, пока они двигаются, но такая быстрая реакция довольно удобна при разработке и тестировании перемещений.

Перемещающиеся отряды.

А как насчёт разницы в высотах?

Так как мы выполняем интерполяцию между позициями ячеек, мы интерполируем и вертикальную позицию отряда. Так как это не соответствует настоящей геометрии, при движении отряд может висеть над рельефом или утопать в нём. Так как анимация быстра и обычно наблюдается издалека, это не очень заметно. Игроки заняты игрой, а не рассматриванием движения отдельных отрядов. Если проанализировать игры с изменяемой высотой, например Endless Legend, то можно заметить, что отряды нам тоже висят или утопают в рельефе. Если это устраивает разработчиков игры, то нас и подавно.

Позиция после компиляции

Один из недостатков корутин заключается в том, что они не «выживают» при рекомпиляции в режиме Play. Хоть игровое состояние всегда верно, это может привести к тому, что отряды застрянут где-нибудь на своём последнем пути, если запустить рекомпиляцию, когда они ещё движутся. Чтобы смягчить последствия, давайте сделаем так, чтобы после рекомпиляции отряды всегда находились в правильной позиции. Это можно сделать, обновляя их позиции в OnEnable.

	void OnEnable () {
		if (location) {
			transform.localPosition = location.Position;
		}
	}

unitypackage

Плавное перемещение

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

Двигаемся от ребра к ребру

Отряд начинает своё путешествие с центра ячейки. Он проходит к середине ребра ячейки, после чего входит в следующую ячейку. Вместо того, чтобы двигаться к центру, он может направиться сразу к следующему ребру, которое должен пересечь. По сути, отряд будет срезать путь, когда ему нужно сменить направление. Это возможно для всех ячеек, кроме концевых точек пути.

Три способа двигаться от ребра к ребру

Давайте адаптируем OnDrawGizmos под отображение путей, сгенерированных таким образом. Он должен выполнять интерполяцию между рёбрами ячеек, которые можно найти усреднением позиций соседних ячеек. Нам достаточно вычислять по одному ребру на итерацию, повторно используя значение из предыдущей итерации. Таким образом мы сможем заставить работать способ и для начальной ячейки, только вместо ребра возьмём её позицию.

	void OnDrawGizmos () {
		if (pathToTravel == null || pathToTravel.Count == 0) {
			return;
		}

		Vector3 a, b = pathToTravel[0].Position;

		for (int i = 1; i < pathToTravel.Count; i++) {
//			Vector3 a = pathToTravel[i - 1].Position;
//			Vector3 b = pathToTravel[i].Position;
			a = b;
			b = (pathToTravel[i - 1].Position + pathToTravel[i].Position) * 0.5f;
			for (float t = 0f; t < 1f; t += 0.1f) {
				Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
			}
		}
	}

Чтобы достичь центра конечной ячейки, нам нужно использовать в качестве последней точки позицию ячейки, а не ребро. Можно добавить проверку этого случая в цикл, но это такой простой код, что нагляднее будет просто дублировать код и немного изменить его.

	void OnDrawGizmos () {
		…
		
		for (int i = 1; i < pathToTravel.Count; i++) {
			…
		}

		a = b;
		b = pathToTravel[pathToTravel.Count - 1].Position;
		for (float t = 0f; t < 1f; t += 0.1f) {
			Gizmos.DrawSphere(Vector3.Lerp(a, b, t), 2f);
		}
	}

Пути на основе рёбер

Получающиеся пути меньше походят на зигзаги, а максимальный угол поворота снижается с 120° до 90°. Это можно считать улучшением, поэтому применим те же изменения в корутине TravelPath, чтобы посмотреть, как это выглядит в анимации.

	IEnumerator TravelPath () {
		Vector3 a, b = pathToTravel[0].Position;

		for (int i = 1; i < pathToTravel.Count; i++) {
//			Vector3 a = pathToTravel[i - 1].Position;
//			Vector3 b = pathToTravel[i].Position;
			a = b;
			b = (pathToTravel[i - 1].Position + pathToTravel[i].Position) * 0.5f;
			for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
				transform.localPosition = Vector3.Lerp(a, b, t);
				yield return null;
			}
		}

		a = b;
		b = pathToTravel[pathToTravel.Count - 1].Position;
		for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
			transform.localPosition = Vector3.Lerp(a, b, t);
			yield return null;
		}
	}

Перемещение с изменяющейся скоростью

После срезания углов длина сегментов пути стала зависимой от изменения направления. Но мы задали скорость в ячейках в секунду. В результате скорость отряда меняется хаотически.

Следование по кривым

Мгновенное изменение направления и скорости при пересечении границ ячеек выглядит некрасиво. Лучше использовать постепенное изменение направления. Мы можем добавить поддержку этого, заставив отряды следовать по кривым, а не по прямым линиям. Для этого можно использовать кривые Безье. В частности, можно взять квадратичные кривые Безье, в которых средними контрольными точками будут центры ячеек. При этом касательные соседних кривых будут зеркальными отражениями друг друга, то есть весь путь превратится в непрерывную плавную кривую.

Кривые от ребра до ребра

Создадим вспомогательный класс Bezier с методом для получения точки на квадратичной кривой Безье. Как объяснено в туториале Curves and Splines, для этого используется формула $inline$ , где $inline$ , $inline$ и $inline$ — это контрольные точки, а t — интерполятор.

using UnityEngine;

public static class Bezier {

	public static Vector3 GetPoint (Vector3 a, Vector3 b, Vector3 c, float t) {
		float r = 1f - t;
		return r * r * a + 2f * r * t * b + t * t * c;
	}
}

Разве GetPoint не должен ограничиваться в интервале 0-1?

Так как мы используем интерполяторы только в интервале 0-1, нам необязательно их ограничивать. На практике при интерполяции по кривым такое происходит почти всегда. Если хотите, можете создать версию GetPointClamped, которая содержит параметр t. Или сделать его поведением по умолчанию, а приведённый выше метод назвать GetPointUnclamped.

Чтобы показать кривой путь в OnDrawGizmos, нам нужно отслеживать не две, а три точки. Дополнительная точка — это центр ячейки, с которой мы работаем на текущей итерации, имеющая индекс i - 1, потому что цикл начинается с 1. Получив все точки, мы можем заменить Vector3.Lerp на Bezier.GetPoint.

В начальной и конечной ячейках вместо конечной и средней точки мы можем просто использовать центр ячейки.

	void OnDrawGizmos () {
		if (pathToTravel == null || pathToTravel.Count == 0) {
			return;
		}

		Vector3 a, b, c = pathToTravel[0].Position;

		for (int i = 1; i < pathToTravel.Count; i++) {
			a = c;
			b = pathToTravel[i - 1].Position;
			c = (b + pathToTravel[i].Position) * 0.5f;
			for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
				Gizmos.DrawSphere(Bezier.GetPoint(a, b, c, t), 2f);
			}
		}

		a = c;
		b = pathToTravel[pathToTravel.Count - 1].Position;
		c = b;
		for (float t = 0f; t < 1f; t += 0.1f) {
			Gizmos.DrawSphere(Bezier.GetPoint(a, b, c, t), 2f);
		}
	}

Пути, созданные с помощью кривых Безье

Кривой путь выглядит намного лучше. Применим те же изменения в TravelPath и посмотрим, как анимируются отряды при таком подходе.

	IEnumerator TravelPath () {
		Vector3 a, b, c = pathToTravel[0].Position;

		for (int i = 1; i < pathToTravel.Count; i++) {
			a = c;
			b = pathToTravel[i - 1].Position;
			c = (b + pathToTravel[i].Position) * 0.5f;
			for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
				transform.localPosition = Bezier.GetPoint(a, b, c, t);
				yield return null;
			}
		}

		a = c;
		b = pathToTravel[pathToTravel.Count - 1].Position;
		c = b;
		for (float t = 0f; t < 1f; t += Time.deltaTime * travelSpeed) {
			transform.localPosition = Bezier.GetPoint(a, b, c, t);
			yield return null;
		}
	}

Перемещаемся по кривым

Анимация тоже стала плавной, даже когда скорость отряда непостоянна. Так как касательные кривой соседних сегментов совпадают, скорость непрерывна. Изменение скорости происходит постепенно и случается, когда отряд проходит через ячейку, замедляясь при смене направления. Если он идёт прямо, то скорость остаётся постоянной. Кроме того, отряд начинает и заканчивает свой путь с нулевой скоростью. Это имитирует естественное движение, поэтому оставим его таким.

Отслеживание времени

До этого момента мы начинали итерацию по каждому из сегментов с 0, продолжая, пока не достигнем 1. Это работает нормально при увеличении на постоянную величину, но наша итерация зависит от дельты времени. Когда итерация по одному сегменту завершается, мы скорее всего превзойдём 1 на какую-то величину, зависящую от дельты времени. Это незаметно при высокой частоте кадров, но может привести к рывкам при низкой частоте кадров.

Чтобы избежать потерь времени, нам нужно передавать оставшееся время от одного сегмента к следующему. Это можно сделать, отслеживая t на протяжении всего пути, а не только в каждом сегменте. Затем в конце каждого сегмента будем вычитать из него 1.

	IEnumerator TravelPath () {
		Vector3 a, b, c = pathToTravel[0].Position;

		float t = 0f;
		for (int i = 1; i < pathToTravel.Count; i++) {
			a = c;
			b = pathToTravel[i - 1].Position;
			c = (b + pathToTravel[i].Position) * 0.5f;
			for (; t < 1f; t += Time.deltaTime * travelSpeed) {
				transform.localPosition = Bezier.GetPoint(a, b, c, t);
				yield return null;
			}
			t -= 1f;
		}

		a = c;
		b = pathToTravel[pathToTravel.Count - 1].Position;
		c = b;
		for (; t < 1f; t += Time.deltaTime * traveSpeed) {
			transform.localPosition = Bezier.GetPoint(a, b, c, t);
			yield return null;
		}
	}

Если уж мы этим занялись, давайте ещё сделаем так, чтобы дельта времени учитывалась в начале пути. Это значит, что мы начнём двигаться сразу же, а не будем простаивать один кадр.

		float t = Time.deltaTime * travelSpeed;

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

	IEnumerator TravelPath () {
		…

		transform.localPosition = location.Position;
	}

unitypackage

Анимация ориентации

Отряды начали двигаться по плавной кривой, но они не меняют ориентацию в соответствии с направлением движения. В результате кажется, что они скользят. Чтобы перемещение выглядело как настоящее движение, нам нужно их поворачивать.

Смотрим вперёд

Как и в туториале Curves and Splines, для определения ориентации отряда мы можем использовать производную кривой. Формула производной квадратичной кривой Безье: $inline$ . Добавим в Bezier метод для её вычисления.

	public static Vector3 GetDerivative (
		Vector3 a, Vector3 b, Vector3 c, float t
	) {
		return 2f * ((1f - t) * (b - a) + t * (c - b));
	}

Вектор производной расположен на одной прямой с направлением движения. Мы можем использовать метод Quaternion.LookRotation, чтобы преобразовать его в поворот отряда. Будем выполнять это на каждом шагу в HexUnit.TravelPath.

				transform.localPosition = Bezier.GetPoint(a, b, c, t);
				Vector3 d = Bezier.GetDerivative(a, b, c, t);
				transform.localRotation = Quaternion.LookRotation(d);
				yield return null;
		
		…
		
			transform.localPosition = Bezier.GetPoint(a, b, c, t);
			Vector3 d = Bezier.GetDerivative(a, b, c, t);
			transform.localRotation = Quaternion.LookRotation(d);
			yield return null;

Разве в начале пути не возникнет ошибка?

Путь начинается с кривой, идущей от центра начальной ячейки до её ребра. Мы сделали точки $inline$ и $inline$ кривой равными, поэтому получим красивое ускорение. Однако это значит, что когда $inline$ , то вектор производной равен нулю, а его нельзя использовать в Quaternion.LookRotation. Поэтому да, такой подход не сработает, если мы начинаем с $inline$ для первого сегмента. Но мы и не будем. Мы сразу же начинаем с дельты времени, поэтому $inline$ и способ всегда работает.
То же самое относится и к концу получившейся кривой, потому что мы присваиваем $inline$ .

В отличие от позиции отряда, неидеальность его ориентации в конце пути не важна. однако нам нужно гарантировать, что его ориентация соответствует окончательному повороту. Для этого после завершения приравняем его ориентацию к его повороту по Y.

		transform.localPosition = location.Position;
		orientation = transform.localRotation.eulerAngles.y;

Теперь отряды смотрят точно в направлении движения, и по горизонтали, и по вертикали. Это значит, что они будут наклоняться вперёд и назад, спускаясь со склонов и поднимаясь на них. Чтобы они всегда стояли прямо, принудительно обнулим компонент Y вектора направления перед его использованием для определения поворота отряда.

				Vector3 d = Bezier.GetDerivative(a, b, c, t);
				d.y = 0f;
				transform.localRotation = Quaternion.LookRotation(d);
		
		…
		
			Vector3 d = Bezier.GetDerivative(a, b, c, t);
			d.y = 0f;
			transform.localRotation = Quaternion.LookRotation(d);

Смотрим вперёд при движении

Смотрим на точку

На протяжении всего пути отряды смотрят вперёд, но перед началом движения они могут смотреть в другом направлении. В таком случае они мгновенно меняют свою ориентацию. Будет лучше, если они будут поворачиваться в направлении пути ещё до начала движения.

Взгляд в нужном направлении может быть полезен и в других ситуациях, поэтому давайте создадим метод LookAt, заставляющий отряд менять ориентацию, чтобы посмотреть на определённую точку. Требуемый поворот можно задать с помощью метода Transform.LookAt, сделав сначала так, чтобы точка находилась в той же вертикальной позиции, что и отряд. После этого мы можем извлечь ориентацию отряда.

	void LookAt (Vector3 point) {
		point.y = transform.localPosition.y;
		transform.LookAt(point);
		orientation = transform.localRotation.eulerAngles.y;
	}

Чтобы отряд на самом деле поворачивался, мы превратим метод в ещё одну корутину, которая будет вращать его с постоянной скоростью. Скорость поворота тоже может быть настраиваемой, но мы снова воспользуемся константой. Поворот должен быть быстрым, примерно 180° в секунду.

	const float rotationSpeed = 180f;
	
	…

	IEnumerator LookAt (Vector3 point) {
		…
	}

Возиться с ускорением поворота необязательно, потому что оно незаметно. Нам достаточно будет просто выполнить интерполяцию между двумя ориентациями. К сожалению, это сделать не так просто, как в случае с двумя числами, потому что углы круговые. Например, переход из 350° в 10° должен привести к повороту на 20° по часовой стрелке, но простая интерполяция заставит выполнить поворот на 340° против часовой стрелки.

Проще всего создать правильный поворот, выполняя интерполяцию между двумя кватернионами с помощью сферической интерполяции. Это приведёт к самому краткому повороту. Чтобы сделать это, получим кватернионы начала и конца, а потом выполним между ними переход с помощью Quaternion.Slerp.

	IEnumerator LookAt (Vector3 point) {
		point.y = transform.localPosition.y;
		Quaternion fromRotation = transform.localRotation;
		Quaternion toRotation =
			Quaternion.LookRotation(point - transform.localPosition);
		
		for (float t = Time.deltaTime; t < 1f; t += Time.deltaTime) {
			transform.localRotation =
				Quaternion.Slerp(fromRotation, toRotation, t);
			yield return null;
		}

		transform.LookAt(point);
		orientation = transform.localRotation.eulerAngles.y;
	}

Это сработает, но интерполяция всегда идёт от 0 до 1, вне зависимости от угла поворота. Чтобы обеспечить равномерную угловую скорость, нам нужно замедлять интерполяцию при увеличении угла поворота.

		Quaternion fromRotation = transform.localRotation;
		Quaternion toRotation =
			Quaternion.LookRotation(point - transform.localPosition);
		float angle = Quaternion.Angle(fromRotation, toRotation);
		float speed = rotationSpeed / angle;
		
		for (
			float t = Time.deltaTime * speed;
			t < 1f;
			t += Time.deltaTime * speed
		) {
			transform.localRotation =
				Quaternion.Slerp(fromRotation, toRotation, t);
			yield return null;
		}

Зная угол, мы можем полностью пропустить поворот, если он оказывается нулевым.

		float angle = Quaternion.Angle(fromRotation, toRotation);

		if (angle > 0f) {
			float speed = rotationSpeed / angle;
			for (
				…
			) {
				…
			}
		}

Теперь мы можем добавить поворот отряда в TravelPath, просто выполняя перед перемещением yield LookAt с позицией второй ячейки. Unity будет автоматически запускать корутину LookAt, а TravelPath будет ждать её завершения.

	IEnumerator TravelPath () {
		Vector3 a, b, c = pathToTravel[0].Position;
		yield return LookAt(pathToTravel[1].Position);

		float t = Time.deltaTime * travelSpeed;
		…
	}

Если проверить работу кода, то отряд телепортируется в конечную ячейку, повернётся там, а затем телепортируется обратно к началу пути и начнёт оттуда движение. Так происходит, потому что мы присваиваем значение свойству Location до начала корутины TravelPath. Чтобы избавиться от телепортации, мы можем в начале TravelPath возвращать позицию отряда в начальную ячейку.

		Vector3 a, b, c = pathToTravel[0].Position;
		transform.localPosition = c;
		yield return LookAt(pathToTravel[1].Position);

Поворот перед движением

Подчистка

Получив нужное нам движение, мы можем избавиться от метода OnDrawGizmos. Удалите его или закомментируйте на случай, если нам потребуется в будущем видеть пути.

//	void OnDrawGizmos () {
//		…
//	}

Так как нам больше не нужно запоминать, по какому пути мы двигались, то в конце TravelPath можно освобождать список ячеек.

	IEnumerator TravelPath () {
		…
		ListPool<HexCell>.Add(pathToTravel);
		pathToTravel = null;
	}

А как насчёт настоящих анимаций отрядов?

Так как в качестве отряда я использую простой куб, анимировать нам нечего. Но при использовании 3D-моделей для реалистичности движений нужно создать им анимации. Анимации не обязаны быть очень сложными. Для мелких отрядов стратегических игр достаточно простейших эффектов, например анимации ожидания и движения. Для смешения между ними нужно использовать Mecanim, а управлять анимациями через TravelPath.

unitypackage

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку