Алгоритмы важны. Но реализовать их можно очень по-разному.

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

Любите оптимизации, специализированные структуры данных и трюки с битами? Тогда скорее под кат!

Интро

Алгоритмы на сегодня: A-star и greedy BFS. Оба отлично разобраны в статье Introduction to the A* Algorithm.

Поиск пути мне понадобился в игре Roboden. Написана она на Go с использованием движка Ebitengine, соответственно и библиотеку я искал для этого языка.

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

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

Существующие библиотеки

Открываем awesome-ebitengine и ищем модули для поиска пути:

• github.com/fzipp/astar
• github.com/beefsack/go-astar
• github.com/kelindar/tile
• github.com/s0rg/grid
• github.com/solarlune/paths

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

Напишем бенчмарки и измерим производительность этих пакетов. Бенчмарки отличаются своими картами проходимости: от открытых пространств до лабиринтов. Каждый бенчмарк выполняет поиск на матрице размером 50x50 клеток.

Библиотека	Тест no_walls	Тест simple_wall	Тест multi_wall
astar	948367 ns	1554290 ns	1842812 ns
go-astar	453939 ns	939300 ns	1032581 ns
tile	107632 ns	169613 ns	182342 ns
grid	1816039 ns	1154117 ns	1189989 ns
paths	6588751 ns	5158604 ns	6114856 ns

Для скромного поля в 50x50 клеток это плохие результаты.

А что там по выделению памяти?

Библиотека	Тест no_walls	Тест simple_wall	Тест multi_wall
astar	337336 B	511908 B	722690 B
go-astar	43653 B	93122 B	130731 B
tile	123118 B	32950 B	65763 B
grid	996889 B	551976 B	740523 B
paths	235168 B	194768 B	230416 B

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

Приятно удивляет только kelindar/tile, но к нему мы ещё вернёмся.

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

OS: Linux Mint 21.1
CPU: x86-64 12th Gen Intel(R) Core(TM) i5-1235U
Tools used: “go test -bench”, benchstat
Turbo boost: disabled (intel_pstate/no_turbo=1)
Go version: devel go1.21-c30faf9c54

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

Больше всего влияния на производительность оказывают:

• Матрица проходимости
• Представление результата поиска пути
• Priority queue для frontier
• Ассоциативный массив для хранения посещённых клеток

Матрица проходимости

Элементы матрицы будем называть клетками. У каждой клетки есть координата внутри матрицы.

type GridCoord struct {
  X int
  Y int
}

Grid map отображает рельеф местности с точки зрения алгоритма поиска пути. В самом простом виде каждая клетка хранит значение-перечисление тайла.

type CellType int

// У нас будет всего три вида тайлов.
const (
  CellPlain CellType = iota // 0
  CellSand                  // 1
  CellLava                  // 2
)

Три тайла можно уместить в два бита. Если каждая клетка в матрице занимает всего два бита, тогда карта из 3600 (60x60) клеток будет весить 900 байт.

type Grid struct {
  numCols uint
  numRows uint

  // Храним по 4 клетки в каждом байте.
  bytes []byte
}

Доступ к индивидуальной клетке будет требовать дополнительной арифметики.

func (g *Grid) GetCellTile(c GridCoord) uint8 {
  x := uint(c.X)
  y := uint(c.Y)
  if x >= g.numCols || y >= g.numRows {
    return 0 // Координата лежит вне матрицы
  }
  i := y*g.numCols + x
  byteIndex := i / 4
  shift := (i % 4) * 2
  return (g.bytes[byteIndex] >> shift) & 0b11
}

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

Разные виды юнитов могут иметь отличающиеся категории движения. Кто-то может перемещаться только по равнине, другие ещё и по пустыне, а летуны могут пересекать даже лаву.

Создавать по отдельному Grid'у для каждой категории — перерасход памяти и дублирование источников истины.

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

type GridLayer [4]byte

// i - это значение клетки, от 0 до 3.
func (l GridLayer) Get(i int) byte {
  return l[i]
}

От вставляемого компилятором неявного bound check можно избавиться:

- return l[i]
+ return l[i & 0b11]

Теперь мы можем расширять два бита в один байт. Договоримся, что нулевое значение — отсутствие прохода. Любое другое значение для greedy BFS будет означать допустимость перемещения с ценой 1, а конкретные веса будут учитываться только в реализации A*.

Создадим слои для разных категорий перемещения:

var NormalLayer = pathing.GridLayer{
  CellPlain: 1, // Перемещение разрешено
  CellSand:  0, // Нельзя перемещаться
  CellLava:  0, // Нельзя перемещаться
}

var FlyingLayer = pathing.GridLayer{
  CellPlain: 1, // Перемещение разрешено
  CellSand:  1, // Перемещение разрешено
  CellLava:  1, // Перемещение разрешено
}

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

Преимущества этой матрицы:

• 2 бита на клетку
• С помощью слоёв можно использовать одну матрицу для разных юнитов

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

Здесь можно было бы ещё попробовать Morton order. В теории, это могло бы сделать доступ более cache-friendly, хотя операция чтения стала бы более дорогой.

Репрезентация пути

Существующие библиотеки идут по наиболее интуитивному пути (хе-хе) — хранение маршрута как набора точек.

Возьмём для примера эту карту:

При построении пути от {0,1} к {2,3} мы получим такой набор точек:

{0,0} {1,0} {2,0} {2,1} {2,2} {2,3}

А вот другой способ представить этот же путь:

Up Right Right Down Down Down

Нам будет достаточно перечисления из четырёх значений:

type Direction int

const (
  DirRight Direction = iota
  DirDown
  DirLeft
  DirUp
)

Уже догадались, что произойдёт дальше? 4 значения — два бита.

Так как каждый шаг настолько компактен, мы можем поместить в uint64 целых 32 шага. Этого нам не хватит, поэтому возьмём пару uint64. Вместо 64 шагов мы сможем уместить только 56, потому что два байта нам нужно будет зарезервировать под пару служебных полей итератора пути.

const (
  gridPathBytes  = (16 - 2)          // Два байта служебных
  gridPathMaxLen = gridPathBytes * 4 // 56
)

type GridPath struct {
  bytes [gridPathBytes]byte
  len   byte
  pos   byte
}

GridPath занимает 16 байт, а в памяти будет выглядеть примерно так:

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

Свойства GridPath:

• Пути длиной до 56 клеток (будет важно далее)
• Не нужно аллокаций в куче — это 16 байтов на стеке (или в регистрах)
• Value-семантика, обычное присваивание выполняет глубокое копирование

В новых версиях Go всё больше аргументов передаются через регистры и текущий Go tip в godbolt генерирует одну инструкцию MOVUPS для передачи GridPath.

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

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

• Push(coord, p) — добавить координату в очередь
• Pop() -> (coord, p) — извлечь координату с минимальным p
• Reset() — очистить очередь, память переиспользовать

Приоритет p зависит от алгоритма. Для greedy BFS это Manhattan distance от coord к финишу.

По этому описанию нам могла бы подойти minheap. Для A* мы так и поступим, но greedy BFS можно ускорить ещё сильнее, если взять особую bucket queue. Её и разберём.

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

А вот извлечение из бакетной очереди требует изобретательности. В самом базовом варианте вам нужно перебирать бакеты до тех пор, пока не найдётся непустой. Лорд ужаса из WarCraft III сказал бы: "Дурацкий план."

Вспомним, что максимальная длина пути равна 56. Так как 56<64, uint64 хватит для хранения состояния всех бакетов.

type priorityQueue[T any] struct {
  buckets [64][]T
  mask    uint64
}

Операция добавления в очередь тривиальна:

func (q *priorityQueue[T]) Push(priority int, value T) {
  // Убираем bound check через операцию &, этот трюк вы уже видели.
  i := uint(priority) & 0b111111
  q.buckets[i] = append(q.buckets[i], value)
  q.mask |= 1 << i
}

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

Извлечение элемента немного сложнее, но тоже очень эффективное:

func (q *priorityQueue[T]) Pop() T {
  // TrailingZeros64 на amd64 - это пара машинных инструкций (BSF и CMOV).
  // За эти две инструкции мы находим необходимый
  // нам индекс непустого бакета.
  i := uint(bits.TrailingZeros64(q.mask))
  if i < uint(len(q.buckets)) {
    // Эти дви строчки извлекают последний элемент из бакета (pop).
    e := q.buckets[i][len(q.buckets[i])-1]
    q.buckets[i] = q.buckets[i][:len(q.buckets[i])-1]
    if len(q.buckets[i]) == 0 {
      // Если бакет стал пустым, зануляем нужный бит в маске.
      q.mask &^= 1 << i
    }
    return e
  }

  // Очередь пустая, возвращаем zero value.
  var x T
  return x
}

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

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

func (q *priorityQueue[T]) Reset() {
  mask := q.mask
  // Начинаем очищение с первого непустого бакета,
  // пропуская все пустые "справа".
  offset := uint(bits.TrailingZeros64(mask))
  mask >>= offset
  i := offset
  // Когда "слева" от окна все бакеты будут пустыми, цикл завершится.
  for mask != 0 {
    if i < uint(len(q.buckets)) {
      q.buckets[i] = q.buckets[i][:0]
    }
    mask >>= 1
    i++
  }
  q.mask = 0
}

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

В качестве бонуса, посмотрите как элегантно можно сделать операцию IsEmpty:

func (q *priorityQueue[T]) IsEmpty() bool {
  return q.mask == 0
}

И как после такого не любить пакет math/bits?

Хранение посещённых координат

Семантически, нам нужна map[GridCoord]T, только быстрая и с возможностью повторно использовать выделенную память.

GridCoord — это структура из двух полей, но её можно ужать до одного числа.

func packCoord(numCols int, c GridCoord) uint {
  return uint((c.Y * numCols) + c.X)
}

Так как максимальная длина пути равна 56, область поиска пути никогда не выйдет за пределы квадрата 56*2+1. Если мы будем преобразовывать координаты поиска из глобальных в локальные, то диапазон значений, возвращаемый packCoord будет равен [0-12544].

Это довольно скромное количество ключей, поэтому в голову приходит обычный слайс, где ключом будет прямой индекс. У этой структуры будет значительный минус — Reset потребует полного зануления слайса.

Если взять вместо слайса sparse map, то получим очень эффективный Reset за счёт более медленных Get и Set.

Лучшее от двух миров в данной задаче даёт generations map, о которой я недавно писал на Хабре. Эту структуру данных и выберем.

А что там со звездочкой?

Чтобы превратить greedy BFS в A* нам потребуется несколько изменений:

• Две generations map вместо одной
• Min heap вместо bucket queue
• Немного другая эвристика для p

В случае звёздочки алгоритм будет учитывать цену перемещения (нам это ничего не стоит).

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

Как выбрать между звёздочкой и greedy bfs для вашей задачи? Почти всегда A* будет предпочтительным вариантом, но greedy bfs работает немного быстрее и требует меньше рабочей памяти.

Greedy BFS довольно часто находит почти оптимальный путь, хотя очень сложный лабиринт может его расстроить. В случаях, когда звёздочка и greedy BFS оба находят оптимальные пути, обычно они отличаются. Используя это в игре, можно создавать менее предсказуемые маршруты для юнитов: часть маршрутов строить через A*, а другую — через greedy BFS.

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

Побеждаем в бенчмарках

Используя все рецепты выше, собираем свою библиотеку поиска пути.

pathing быстрее библиотеки paths примерно в 2000 раз! A* работает ощутимо медленнее greedy BFS, но всё ещё быстрее остальных реализаций.

Теперь аллокации:

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

Получилось в тысячи раз быстрее и без аллокаций (zero alloc). Оно того стоило.

Выводы

Алгоритмы важны, однако реализация — тоже. Иногда серия микрооптимизаций ведёт к феноменальному эффекту.

У моей библиотеки поиска пути есть два основных ограничения:

1. Максимальная длина пути — 56 шагов
2. На одной карте проходимости может быть только 4 вида тайлов (2 бита)

Однако с ними можно жить:

1. Частичные пути можно объединять в один
2. Отдельные enum'ы для биомов могут отложить проблему

Понравилась статья? У нас в сообществе разработки игр на Go всегда весело! Присоединяйтесь, будем создавать игрушки на нашем любимом языке программирования вместе.

Полезные ссылки:

• Исходники: github.com/quasilyte/pathing
• Запись доклада на эту тему
• Разбор структуры sparse map от Russ Cox
• Разбор структуры generations map от меня
• Исходники игры Roboden
• Пост о поиске пути в Factorio