Карта


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

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

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

Пример работы системы
image

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

Для плоскостей я использовал простой SpriteRenderer, у этого компонента есть отличное свойство bounds с помощью которого можно легко узнать размеры карты.

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

Начнем со скриптов. И первым будет скрипт препятствия Obstacle.

Obstacle
public class Obstacle : MonoBehaviour {
 
}


Внутри класса Obstacle будем отлавливать все изменения препятствий на карте, к примеру изменение позиции или размера объекта.
Далее можно создать класс карты Map, на котором будет строиться сетка и унаследуем его от класса Obstacle.

Map
public sealed class Map : Obstacle {
 
}


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

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

Obstacle
public class Obstacle : MonoBehaviour {
 
 public new SpriteRenderer renderer { get; private set;}
 
 private Vector2 tempSize;
 private Vector2 tempPos;
 
 protected virtual void Awake() {
  this.renderer = GetComponent<SpriteRenderer>();
  this.tempSize = this.size;
  this.tempPos = this.position;
 }
 
 public virtual bool CheckChanges() {
  Vector2 newSize = this.size;
  float diff = (newSize - this.tempSize).sqrMagnitude;
  if (diff > 0.01f) {
   this.tempSize = newSize;
   return true;
  }
  Vector2 newPos = this.position;
  diff = (newPos - this.tempPos).sqrMagnitude;
  if (diff > 0.01f) {
   this.tempPos = newPos;
   return true;
  }
  return false;
 }
 
 public Vector2 size {
  get { return this.renderer.bounds.size;}
 }
 
 public Vector2 position {
  get { return this.transform.position;}
 }
 
}


Здесь переменная renderer будет иметь ссылку на компонент SpriteRenderer, а переменные tempSize и tempPos будут использоваться для отслеживания изменений размера и позиции объекта.

Виртуальный метод Awake будет использоваться для инициализации переменных, а виртуальный метод CheckChanges будет отслеживать текущие изменения размера и позиции объекта и возвращать boolean результат.

На этом пока оставим скрипт Obstacle и перейдем к самому скрипту карты Map где также наполним его необходимыми параметрами для работы.

Map
public sealed class Map : Obstacle {
 
 [Range(0.1f, 1f)]
 public float nodeSize = 0.5f;
 public Vector2 offset = new Vector2(0.5f, 0.5f);
 
}


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

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

Map
public sealed class Map : Obstacle {
 
 [Range(0.1f, 1f)]
 public float nodeSize = 0.5f;
 public Vector2 offset = new Vector2(0.5f, 0.5f);
 
 private float tempNodeSize;
 private Vector2 tempOffset;
 
 protected override void Awake() {
  base.Awake();
  this.tempNodeSize = this.nodeSize;
  this.tempOffset = this.offset;
 }
 
 public override bool CheckChanges() {
  float diff = Mathf.Abs(this.tempNodeSize - this.nodeSize);
  if (diff > 0.01f) {
   this.tempNodeSize = this.nodeSize;
   return true;
  }
  diff = (this.tempOffset - this.offset).sqrMagnitude;
  if (diff > 0.01f) {
   this.tempOffset = this.offset;
   return true;
  }
  return base.CheckChanges();
 }
 
}


Готово. Теперь на сцене можно создать спрайт карты и кинуть на него скрипт Map.

image

Тоже самое проделаем с препятствием — создадим простой спрайт на сцене и кинем на него скрипт Obstacle.

image

Теперь у нас есть на сцене объекты карты и препятствия.

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

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 private bool requireRebuild;
 
 private void Update() {
  UpdateChanges();
 }
 
 private void UpdateChanges() {
  if (this.requireRebuild) {
   print(“Что то изменилось, необходимо перестроить карту!”);
   this.requireRebuild = false;
  } else {
   this.requireRebuild = CheckChanges();
  }
 }
 
 /*...остальной код…*/
 
}


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

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

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

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 private static Map ObjInstance;
 
 private List<Obstacle> obstacles = new List<Obstacle>();
 
 /*...остальной код…*/
 
 public static bool RegisterObstacle(Obstacle obstacle) {
  if (obstacle == Instance) return false;
  else if (Instance.obstacles.Contains(obstacle) == false) {
   Instance.obstacles.Add(obstacle);
   Instance.requireRebuild = true;
   return true;
  }
  return false;
 }
 
 public static bool UnregisterObstacle(Obstacle obstacle) {
  if (Instance.obstacles.Remove(obstacle)) {
   Instance.requireRebuild = true;
   return true;
  }
  return false;
 }
 
 public static Map Instance {
  get {
   if (ObjInstance == null) ObjInstance = FindObjectOfType<Map>();
   return ObjInstance;
  }
 }
 
}


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

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

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

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

Теперь вернемся обратно в скрипт Obstacle где будем регистрировать препятствие на карте, для этого добавим в него пару методов OnEnable и OnDisable.

Obstacle
public class Obstacle : MonoBehaviour {
 
 /*...остальной код…*/
 
 protected virtual void OnEnable() {
  Map.RegisterObstacle(this);
 }
 
 protected virtual void OnDisable() {
  Map.UnregisterObstacle(this);
 }
 
}


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

Осталось только отследить изменения самих препятствий в скрипте Map в перегруженном методе CheckChanges.

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 public override bool CheckChanges() {
  float diff = Mathf.Abs(this.tempNodeSize - this.nodeSize);
  if (diff > 0.01f) {
   this.tempNodeSize = this.nodeSize;
   return true;
  }
  diff = (this.tempOffset - this.offset).sqrMagnitude;
  if (diff > 0.01f) {
   this.tempOffset = this.offset;
   return true;
  }
  foreach(Obstacle obstacle in this.obstacles) {
   if (obstacle.CheckChanges()) return true;
  }
  return base.CheckChanges();
 }
 
 /*...остальной код…*/
 
}


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

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


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

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

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

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

image
Почему координаты?
Дело в том, что в unity для указания позиции объекта в пространстве используется простой float который весьма неточен и может быть дробным или отрицательным числом, поэтому его будет сложно использовать для реализации поиска пути на карте. Координаты же выполнены в виде четкого int который всегда будет положительным и с которым работать намного проще при поиске соседних точек.

Для начала определим объект точки, это будет простая структур Node.

Node
public struct Node {
 
 public int id;
 public Vector2 position;
 public Vector2Int coords;
 
}


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

Проходимость точки будет указываться в виде ее boolean свойства, но так как мы не можем использовать преобразуемые типы данных в системе задач, то укажем ее проходимость в виде int числа, для этого я использовал простое перечисление NodeType, где: 0 — это не проходимая точка, а 1 — проходимая.

NodeType и Node
public enum NodeType {
 NonWalkable = 0,
 Walkable = 1
}
 
public struct Node {
 
 public int id;
 public Vector2 position;
 public Vector2Int coords;
 
 private int nodeType;
 
 public bool isWalkable {
  get { return this.nodeType == (int)NodeType.Walkable;}
 }
 
 public Node(int id, Vector2 position, Vector2Int coords, NodeType type) {
  this.id = id;
  this.position = position;
  this.coords = coords;
  this.nodeType = (int)type;
 }
 
}


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

Node
public struct Node {
 
 /*...остальной код…*/
 
 public override bool Equals(object obj) {
  if (obj is Node) {
   Node other = (Node)obj;
   return this.id == other.id;
  } else return base.Equals(obj);
 }
 
 public static implicit operator bool(Node node) {
  return node.id > 0;
 }
 
}


Так как номер id точки на сетке будет начинаться с 1 единицы, то я буду проверять существование точки как условие что ее id больше 0.

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

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 public bool rebuilding { get; private set; }
 
 public void Rebuild() {}
 
 private void OnRebuildStart() {}
 private void OnRebuildFinish() {}
 
 /*...остальной код…*/
 
}


Свойство rebuilding будет показывать идет ли процесс построения сетки. Метод Rebuild будет собирать данные и задачи для построения сетки, далее метод OnRebuildStart будет запускать процесс построения сетки и метод OnRebuildFinish будет выполнять сбор данных из задач.

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

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 public bool rebuilding { get; private set; }
 
 private void UpdateChanges() {
  if (this.rebuilding) {
   print(“Идет построение сетки...”);
  } else {
   if (this.requireRebuild) {
    print(“Что то изменилось, необходимо перестроить карту!”);
    Rebuild();
   } else {
    this.requireRebuild = CheckChanges();
   }
  }
 }
 
 public void Rebuild() {
  if (this.rebuilding) return;
  print(“Перестраиваю карту!”);
  OnRebuildStart();
 }
 
 private void OnRebuildStart() {
  this.rebuilding = true;
 }
 private void OnRebuildFinish() {
  this.rebuilding = false;
 }
 
 /*...остальной код…*/
 
}


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

Решение задачи


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

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

Постройка сетки
image

Кол-во вертикальных точек будет указывать на кол-во задач, в свою очередь каждая задача будет строить точки только по горизонтали, после выполнения всех задач точки суммируются в одном списке. Именно поэтому мне и необходимо использовать задачу типа IJobParallelFor, чтобы в метод Execute передавать индекс точки на сетке по горизонтали.

И так структура точек у нас есть, теперь можно создать саму структуру задачи Job и унаследовать ее от интерфейса IJobParallelFor, тут все просто.

Job
public struct Job : IJobParallelFor {
 
 public void Execute(int index) {}
 
}


Возвращаемся в методе Rebuild класса Map, где произведем нужные расчеты по замеру сетки.

Map
public sealed class Map : Obstacle {
 
 /*...остальной код...*/
 
 public void Rebuild() {
  if (this.rebuilding) return;
  print(“Перестраиваю карту!”);
 
  Vector2 mapSize = this.size - this.offset * 2f;
  int horizontals = Mathf.RoundToInt(mapSize.x / this.nodeSize);
  int verticals = Mathf.RoundToInt(mapSize.y / this.nodeSize);
  if (horizontals <= 0) {
   OnRebuildFinish();
   return;
  }
 
  Vector2 center = this.position;
  Vector2 origin = center - (mapSize / 2f);
 
  OnRebuildStart();
 }
 
 /*...остальной код...*/
 
}


В методе Rebuild рассчитаем точный размер карты mapSize с учетом отступа, далее в verticals запишем кол-во точек по вертикали, а в horizontals кол-во точек по горизонтали. Если кол-во точек по вертикали равна 0 значит прекращаем постройку карты и вызываем метод OnRebuildFinish, чтобы завершить процесс. Переменная origin укажет место откуда мы будем начинать строить сетку — в примере это левая нижняя точка на карте.

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

Job
public struct Job : IJobParallelFor {
 
 [WriteOnly]
 public NativeArray<Node> array;
 [ReadOnly]
 public NativeArray<Rect> bounds;
 
 public float nodeSize;
 public Vector2 startPos;
 public Vector2Int startCoords;
 
 public void Execute(int index) {}
 
}


Массив точек array я пометил атрибутом WriteOnly так как в задаче необходимо будет только “записывать” полученные точки в массив, напротив же массив препятствий bounds помечен атрибутом ReadOnly так как в задаче мы будем только “читать” данные из этого массива.

Ну и пока все, к расчету самих точек перейдем позже.

Теперь вернемся в класс Map где обозначим все переменные задействованные в задачах.
Здесь во-первых нам понадобиться глобальный handle задач, массив препятствий в виде NativeArray, список задач который будет содержать все точки полученные на сетке и Dictionary со всеми координатами и точками на карте, чтобы удобней было их искать потом.

Map
public sealed class Map : Obstacle {
 
 /*...остальной код...*/
 
 private JobHandle handle;
 private NativeArray<Rect> bounds;
 private HashSet<NativeArray<Node>> jobs = new HashSet<NativeArray<Node>>();
 private Dictionary<Vector2Int, Node> nodes = new Dictionary<Vector2Int, Node>();
 
 /*...остальной код...*/
 
}


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

Rebuild
public void Rebuild() {
 
 /*...остальной код...*/
 
 Vector2 center = this.position;
 Vector2 origin = center - (mapSize / 2f);
 
 int count = this.obstacles.Count;
 if (count > 0) {
  this.bounds = new NativeArray<Rect>(count, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
 }
 
 OnRebuildStart();
}


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

И так, далее наполним массив bounds данными.

Rebuild
public void Rebuild() {
 /*...остальной код...*/
 
 Vector2 center = this.position;
 Vector2 origin = center - (mapSize / 2f);
 
 int count = this.obstacles.Count;
 if (count > 0) {
  this.bounds = new NativeArray<Rect>(count, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
  for(int i = 0; i < count; i++) {
   Obstacle obs = this.obstacles[i];
   Vector2 position = obs.position;
   Rect rect = new Rect(Vector2.zero, obs.size);
   rect.center = position;
   this.bounds[i] = rect;
  }
 }
 
 OnRebuildStart();
}


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

Rebuild
public void Rebuild() {
 
 /*...остальной код...*/
 
 Vector2 center = this.position;
 Vector2 origin = center - (mapSize / 2f);
 
 int count = this.obstacles.Count;
 if (count > 0) {
  this.bounds = new NativeArray<Rect>(count, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
  for(int i = 0; i < count; i++) {
   Obstacle obs = this.obstacles[i];
   Vector2 position = obs.position;
   Rect rect = new Rect(Vector2.zero, obs.size);
   rect.center = position;
   this.bounds[i] = rect;
  }
 }
 
 for (int i = 0; i < verticals; i++) {
  float xPos = origin.x;
  float yPos = origin.y + (i * this.nodeSize) + this.nodeSize / 2f;
 }
 
 OnRebuildStart();
}


Для начала в xPos и yPos получаем начальную позицию ряда по горизонтали.

Rebuild
public void Rebuild() {
 
 /*...остальной код...*/
 
 Vector2 center = this.position;
 Vector2 origin = center - (mapSize / 2f);
 
 int count = this.obstacles.Count;
 if (count > 0) {
  this.bounds = new NativeArray<Rect>(count, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
  for(int i = 0; i < count; i++) {
   Obstacle obs = this.obstacles[i];
   Vector2 position = obs.position;
   Rect rect = new Rect(Vector2.zero, obs.size);
   rect.center = position;
   this.bounds[i] = rect;
  }
 }
 
 for (int i = 0; i < verticals; i++) {
  float xPos = origin.x;
  float yPos = origin.y + (i * this.nodeSize) + this.nodeSize / 2f;
 
  NativeArray<Node> array = new NativeArray<Node>(horizontals, Allocator.Persistent);
  Job job = new Job();
  job.startCoords = new Vector2Int(i * horizontals, i);
  job.startPos = new Vector2(xPos, yPos);
  job.nodeSize = this.nodeSize;
  job.bounds = this.bounds;
  job.array = array;
 }
 
 OnRebuildStart();
}


Далее создаем простой массив NativeArray куда будут помещаться точки в задаче, здесь для массива array нужно указать сколько точек будет создано по горизонтали и тип аллокации Persistent, ведь задача может выполняться дольше чем один кадр.
После, создаем сам экземпляр задачи Job, помещаем в нее начальные координаты ряда startCoords, начальную позицию ряда startPos, размер точек nodeSize, массив препятствий bounds и уже в конце сам массив точек array.
Осталось только поместить задачу в handle и глобальный список задач.

Rebuild
public void Rebuild() {
 
 /*...остальной код...*/
 
 Vector2 center = this.position;
 Vector2 origin = center - (mapSize / 2f);
 
 int count = this.obstacles.Count;
 if (count > 0) {
  this.bounds = new NativeArray<Rect>(count, Allocator.TempJob, NativeArrayOptions.UninitializedMemory);
  for(int i = 0; i < count; i++) {
   Obstacle obs = this.obstacles[i];
   Vector2 position = obs.position;
   Rect rect = new Rect(Vector2.zero, obs.size);
   rect.center = position;
   this.bounds[i] = rect;
  }
 }
 
 for (int i = 0; i < verticals; i++) {
  float xPos = origin.x;
  float yPos = origin.y + (i * this.nodeSize) + this.nodeSize / 2f;
 
  NativeArray<Node> array = new NativeArray<Node>(horizontals, Allocator.Persistent);
  Job job = new Job();
  job.startCoords = new Vector2Int(i * horizontals, i);
  job.startPos = new Vector2(xPos, yPos);
  job.nodeSize = this.nodeSize;
  job.bounds = this.bounds;
  job.array = array;
 
  this.handle = job.Schedule(horizontals, 3, this.handle);
  this.jobs.Add(array);
 }
 
 OnRebuildStart();
}


Готово. У нас есть список задач и их общий handle, теперь можно запустить этот handle вызвав его метод Complete в методе OnRebuildStart .

OnRebuildStart
private void OnRebuildStart() {
  this.rebuilding = true;
  this.handle.Complete();
 }


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

UpdateChanges
private void UpdateChanges() {
  if (this.rebuilding) {
   print(“Идет построение сетки...”);
   if (this.handle.IsCompleted) OnRebuildFinish();
  } else {
   if (this.requireRebuild) {
    print(“Что то изменилось, необходимо перестроить карту!”);
    Rebuild();
   } else {
    this.requireRebuild = CheckChanges();
   }
  }
 }


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

OnRebuildFinish
 private void OnRebuildFinish() {
  this.nodes.Clear();
 
  foreach (NativeArray<Node> array in this.jobs) {
   foreach (Node node in array) this.nodes.Add(node.coords, node);
   array.Dispose();
  }
  this.jobs.Clear();
 
  if (this.bounds.IsCreated) this.bounds.Dispose();
  this.requireRebuild = this.rebuilding = false;
 }


Для начала очищаем словарь nodes от предыдущих точек, далее с помощью цикла foreach перебираем все полученные точки из задач и помещаем их в словарь nodes , где ключ это координаты(НЕ позиция!) точки, а значение — сама точка. С помощью этого словаря нам будет проще искать соседние точки на карте. После наполнения очищаем массив array с помощью метода Dispose и в конце очищаем сам список задач jobs.

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

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

Примерно так
image

Для этого в классе Map создадим метод OnDrawGizmos где будем отрисовывать точки.

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 #if UNITY_EDITOR
 private void OnDrawGizmos() {}
 #endif
 
}


Теперь через цикл отрисуем каждую точку.

Map
public sealed class Map : Obstacle {
 
 /*...остальной код…*/
 
 #if UNITY_EDITOR
 private void OnDrawGizmos() {
  foreach (Node node in this.nodes.Values) {
   Gizmos.DrawWireSphere(node.position, this.nodeSize / 10f);
  }
 }
 #endif
 
}


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

Сетка
image

Для поиска соседних точек нам понадобиться просто найти нужную точку по ее координатам в 8 направлениях, поэтому в классе Map заведем простой статический массив направлений Directions и метод поиска ячейки по ее координатам GetNode.

Map
public sealed class Map : Obstacle {
 
 public static readonly Vector2Int[] Directions = {
  Vector2Int.up,
  new Vector2Int(1, 1),
  Vector2Int.right,
  new Vector2Int(1, -1),
  Vector2Int.down,
  new Vector2Int(-1, -1),
  Vector2Int.left,
  new Vector2Int(-1, 1),
 };
 
 /*...остальной код…*/
 
 public Node GetNode(Vector2Int coords) {
  Node result = default(Node);
  try {
   result = this.nodes[coords];
  } catch {}
  return result;
 }
 
 #if UNITY_EDITOR
 private void OnDrawGizmos() {}
 #endif
 
}


Метод GetNode будет возвращать точку по координатам из списка nodes, но делать это нужно осторожно ведь если координаты Vector2Int будут неправильными возникнет ошибка, поэтому здесь используем блок обхода исключений try catch, который поможет обойти исключение и не “повесить” все приложение с ошибкой.

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

OnDrawGizmos
 #if UNITY_EDITOR
 private void OnDrawGizmos() {
  Color c = Gizmos.color;
  foreach (Node node in this.nodes.Values) {
   Color newColor = Color.white;
   if (node.isWalkable) newColor = new Color32(153, 255, 51, 255);
   else newColor = Color.red;
   Gizmos.color = newColor;
   Gizmos.DrawWireSphere(node.position, this.nodeSize / 10f);
   newColor = Color.green;
   Gizmos.color = newColor;
   if (node.isWalkable) {
    for (int i = 0; i < Directions.Length; i++) {
     Vector2Int coords = node.coords + Directions[i];
     Node connection = GetNode(coords);
     if (connection) {
      if (connection.isWalkable) Gizmos.DrawLine(node.position, connection.position);
     }
    }
   }
  }
  Gizmos.color = c;
 }
 #endif


Теперь можно смело запустить игру и посмотреть, что же вышло.

Динамическая карта
image

В этом примере мы строили только сам граф с помощью задач, но вот, что получилось у меня после того как я прикрутил к этой системе сам алгоритм А*, который так же использует Job system для нахождения пути, исходник в конце статьи.

Карта и поиск пути
image

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

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

Исходник проекта поиска пути

Комментарии (4)


  1. Igor_Sib
    19.09.2018 05:26

    Немного покритикую:

    1) Наследование карты (Map) от препятствия (Obstacle) — лучше сделать им общего абстрактного предка. У Obstacle еще добавляется функционал и он весь будет унаследован картой.

    2) С точки зрения оптимизации каждый кадр в карте пробегать и проверять препятствия — не сдвинулись ли они и не поменяли ли размер — плохое решение. У большинства препятствий 99,9% времени размер и позиция не будут меняться. Лучше чтобы они при изменении позиции или размера уведомлять карту что было изменение (ставить флаг requireRebuild в True или если не хочется чтобы Obstacle знал о Map то завести статичный флаг, скажем, dirty — и его устанавливать при изменении позиции или размера, а из карты его чекать). Будет работать намного быстрее.

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

    4) «Дело в том, что в unity для указания позиции объекта в пространстве используется простой float который весьма неточен и может быть дробным или отрицательным числом, поэтому его будет сложно использовать для реализации поиска пути на карте. Координаты же выполнены в виде четкого int который всегда будет положительным и с которым работать намного проще при поиске соседних точек.» — не согласен. float-а вполне достаточно, просто чем делать карту и брать из неё точки лучше задать возможные переходы для каждой точки (и можно посчитать их стоимость — чтобы не тратить время в риалтайме), тогда все будет работать нормально, немного больше расход памяти, но работать будет быстрее. A* по большому счету без разницы — сетка это или просто графы, это алгоритм поиска по графам, а сетка лишь частный случай.

    5) Реализация A* ваша немного странная — не понял как идет выборка из открытого списка. Такое ощущение что не лучшее совпадение берется, а всегда первый попавшийся. Вы всегда берете первый элемент массива openList[0] без учета эвристики. Или он у вас где-то сортируется? Не очень понял этот момент.

    6) Для этого примера лучше бы подошел NavMesh — гораздо меньше узлов пришлось бы обработать, работало бы быстрее. Хотя если просто для примера — то нормально.

    7) По самой Job system — инфы мало, хотя статья о нем.

    PS: при изменении размеров и позиции препятствий боты глючат.


    1. dmitrik7 Автор
      19.09.2018 20:31

      Спасибо за конструктивный комментарий. Прежде всего скажу, что изначально предполагалось разобрать и поиск пути с помощью Job system, но тогда страшно представить какой был бы размер самой статьи.
      По пунктам:
      1) Создавать целый отдельный абстрактный класс для того чтобы вынести общий функционал!? — ну и зачем, чтобы все более лаконичней смотрелось, плюс дополнительные строки кода и текста.
      2) Можно вынести изменения размера и позиции в свойство или метод и устанавливать там параметр изменения, согласен, но опять же размер. К примеру чтобы отлавливать изменения в редакторе придется писать целый кастомный редактор, в общем в любом случае так или иначе нужен будет какой-либо update. Опять же смысла не вижу этого делать для статьи о системе задач в первую очередь.
      3) Да все верно, можно брать уже рассчитанные точки и исключать их или создавать новые там где нет препятствий. Но алгоритма как это сделать легко и просто, а еще и уместить в одну статью я так и не смог придумать, ну это моя вина.
      4) Да ради бога, как вам удобно так и реализуйте. Так то в принципе можно упрощать и упрощать.
      5) Да, здесь нет сортировки. Потестровав, я понял что нужно или сортировку переносить в многоступенчатую задачу IJobParallelFor или просто отказаться от нее, что даст более простую реализацию в коде, но меньшую скорость работы.
      6) Не совсем понял в чем смысл этого комментария, для 2D это в каком месте можно использовать NavMesh?
      7) В самом начале ссылка на статью именно о самой системе в деталях.

      "PS: при изменении размеров и позиции препятствий боты глючат."
      Каждый раз при перестройки карты боты также отправляют запрос на постройку нового пути, даже если они не находятся в той зоне где произошли изменения… Извиняюсь, это конечно моя недоработка, исправим!


      1. Igor_Sib
        20.09.2018 07:54

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

        5) Сортировка списка не нужна, это будет лишняя трата ресурсов, достаточно просто поиска минимума (это намного быстрее). Без неё (то что у вас сейчас) — это другой алгоритм, не A* (поиск в ширину по моему называется, точно не помню сейчас).

        6) Я не имел в виду использовать юнитевский, я имел в виду написать свой NavMesh.


        1. dmitrik7 Автор
          20.09.2018 08:23

          Да, я Вас понял — возвращать минимальную точку из открытого списка.
          На счет многопоточнго навмеша, а смысл? Многопоточные поиски пути уже давно не в новинку, я думаю штуки 2-3 на ассет сторе точно есть, и для 2д и для 3д, есть целые проекты направленные на это. А написание нового это — будет просто изобретение очередного велосипеда.