Spears & bits

В играх часто используется паттерн упаковки булевых значений в биты. Это удобно для оптимизации памяти и ускорения выполнения массовых проверок. Например, такие проверки могут включать нахождение игрока в тайле, определение доступности клеток на четырех- или шестигранной сетке, или другие пространственные проверки, которые необходимо выполнять быстро. Это не ракетостроение, но когда профайлер показал одну из таких функций в числе горячих, мне стало интересно, как именно она работает и можно ли её оптимизировать. Структура данных bitset — это способ эффективно представлять множество целых индексов, которое к тому же поддерживает различные операции над ним, например объединение, разность, пересечение.

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

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

Название статьи получилось как-то само собой: недалеко от моего дома есть хорошее кафе Chief&Bites, достаточно популярное у местных жителей, но пирожные там начинают делать после заказа, такой вот формат анти-кафе. Сами понимаете, прождать пока сделают свежайшее пирожное полчаса, а то и час - легко, там даже на чеке пишут время, когда начали делать именно твое пирожное. Заранее извиняюсь за "велосипеды" в коде, но, возможно, эта тема покажется кому-то полезной.