В играх часто используется паттерн упаковки булевых значений в биты. Это удобно для оптимизации памяти и ускорения выполнения массовых проверок. Например, такие проверки могут включать нахождение игрока в тайле, определение доступности клеток на четырех‑ или шестигранной сетке, или другие пространственные проверки, которые необходимо выполнять быстро. Это не ракетостроение, но когда профайлер показал одну из таких функций в числе горячих, мне стало интересно, как именно она работает и можно ли её оптимизировать. Структура данных bitset — это способ эффективно представлять множество целых индексов, которое к тому же поддерживает различные операции над ним, например объединение, разность, пересечение.
Итак — каждый юнит может занимать один или несколько тайлов, особенно если это большой юнит, вроде колесницы или требюшета и мы хотим создать производную карту, которая хранит другие признаки, например: есть ли в тайле юнит, или фильтр по здоровью юнитов. Такие карты используютя для разных быстрых проверок, вроде такой: можно ли переместиться в точку, или каких юнитов имеет смысл атаковать.
Для представления данных мы можем использовать индекс юнита в тайле. В качестве типовой задачу проверять будем только юнитов, у которых здоровье превышает определённое значение. Это условие не взято с потолка. Например, некоторые юниты используют стратегии вроде «убей слабейшего» или «нападай стаей». Для таких стратегий поюнитный обход всех юнитов вокруг (особенно если это выполняют все юниты в группе) может стать крайне затратной по времени операцией.
Название статьи получилось как‑то само собой: недалеко от моего дома есть хорошее кафе Chief&Bites, достаточно популярное у местных жителей, но пирожные там начинают делать после заказа, такой вот формат анти‑кафе. Сами понимаете, прождать пока сделают свежайшее пирожное полчаса, а то и час — легко, там даже на чеке пишут время, когда начали делать именно твое пирожное. Заранее извиняюсь за «велосипеды» в коде, но, возможно, эта тема покажется кому‑то полезной.
