[Перевод] Карты из шестиугольников в Unity: поиск пути, отряды игрока, анимации
Части 1–3: сетка, цвета и высоты ячеек
Части 4–7: неровности, реки и дороги
Части 8–11: вода, объекты рельефа и крепостные стены
Части 12–15: сохранение и загрузка, текстуры, расстояния
- Подсвечиваем ячейки
- Выбираем целевую точку поиска
- Находим кратчайший путь
- Создаём очередь с приоритетом
Вычислив расстояния между ячейками, мы перешли к нахождению путей между ними.
Начиная с этой части, туториалы по картам из шестиугольников будут создаваться в 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();
highlight.enabled = false;
}
public void EnableHighlight () {
Image highlight = uiRect.GetChild(0).GetComponent();
highlight.enabled = true;
}
Наконец, мы можем указать цвет, чтобы при включении придавать подсветке оттенок.
public void EnableHighlight (Color color) {
Image highlight = uiRect.GetChild(0).GetComponent();
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 frontier = new List();
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* (произносится «А звезда»).
Идея добавления эвристики в алгоритм Дейкстры впервые была предложена Нильсом Нильссоном. Он назвал свой вариант A1. Позже Бертрам Рафаэль придумал лучшую версию, которую он назвал A2. Затем Питер Харт доказал, что при хорошей эвристике A2 оптимален, то есть более хорошей версии быть не может. Это заставило его назвать алгоритм A*, чтобы показать, что его невозможно будет улучшить, то есть A3 или A4 не появятся. Так что да, алгоритм A* — это лучшее, что мы можем получить, но он хорош настолько, насколько хороша его эвристика.
unitypackage
Очередь с приоритетом
Хоть A* и хороший алгоритм, наша реализация не так уж эффективна, потому что для хранения границы мы используем список, который нужно сортировать при каждой итерации. Как упоминалось в предыдущей части, нам нужна очередь с приоритетом, но её стандартной реализации не существует. Поэтому давайте создадим её самостоятельно.
Наша очередь должна поддерживать операцию постановки и исключения из очереди на основании приоритета. Также она должна поддерживать изменение приоритета ячейки, уже находящейся в очереди. В идеале мы реализуем её, минимизируя поиск сортировку и выделяемую память. Кроме того, она должна оставаться простой.
Создание собственной очереди
Создадим новый класс HexCellPriorityQueue с обязательными общими методами. Для отслеживания содержимого очереди мы используем простой список. Кроме того, добавим ей метод Clear для сброса очереди, чтобы её можно было использовать многократно.
using System.Collections.Generic;
public class HexCellPriorityQueue {
List list = new List();
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 frontier = new List();
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
- Находим пути для пошагового перемещения.
- Сразу же отображаем пути.
- Создаём более эффективный поиск.
- Визуализируем только путь.
В этой части мы разделим движение на ходы и максимально ускорим поиск.
Путешествие из нескольких ходов
Пошаговое движение
Стратегические игры, в которых используются сетки шестиугольников, почти всегда являются пошаговыми. Перемещающиеся по карте отряды имеют ограниченную скорость, которая ограничивает расстояние, проходимое за один ход.
Скорость
Чтобы обеспечить поддержку ограниченного перемещения, добавим в 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 единиц, то есть на одну больше имеющихся. Что нам нужно делать на этом этапе?
Существует два подхода к такой си
