Экспериментируем с битбордом и битовыми операциями в Unreal 4
Идея прототипа игры
Главный герой Таичи застрял в мире клеток. Он пытается найти выход и может передвигаться только, если мы поможем ему раскрасить клетки, указав правильный путь.
В этом прототипе игры представлена сетка из клеток, а игрок должен решить, какую из них использовать, чтобы направить героя к выходу. Количество клеток, которые можно раскрасить, ограничено, благодаря чему эта небольшая игра превращается в интересное испытание.
Сетка состоит из нескольких заблокированных клеток, которые игрок не может выбрать, а Таичи перешагнуть. Игрок может щелкнуть по клетке и изменить ее, выбрав одну из следующих опций:
- Синяя клетка: Таичи движется по прямой линии
- Оранжевая клетка «повернуть налево»: Таичи поворачивает налево
- Оранжевая клетка «повернуть направо»: Таичи поворачивает направо.
Битовые операции и биты
Прежде чем перейти непосредственно к прототипу игры с Таичи в главной роли, разберемся в теории.
При написании кода мы объявляем такие переменные, как int, double, long, char… Но компьютер понимает только 0 и 1 (двоичные цифры).
Слишком много нулейВ таком случае воспользуемся магией битовых операций! Например, упакуем данные в одну переменную.
Представьте простую игру, в которой игрок должен найти выход из комнаты. Ему необходимо найти предметы, объединить их и использовать для побега.
Представим каждый найденный предмет как логическое значение, которое отображает и скрывает их, чтобы указать, владеет ли ими персонаж или нет. Попробуем применить колдовскую силу и используем одну переменную int для упаковки и переключения отображения.
Как это работает
У персонажа есть инвентарь, представленный целым числом (32 бита или, проще говоря, 32 двоичных числа, представленных 0 и 1). Предметы, которые Таичи находит в процессе игры, можно собрать в одну переменную!
Определяем инвентарь как int. Для простоты не будем вводить сейчас все 0, чтобы представить переменные (идею вы поняли).
int inventory = 0; // 32 bits or of 0 0x00000.... (32 times)Запускаем игру и в результате небольших поисков находим ключ, загадочную книгу и пончик (почему бы и нет). Предметы в комнате также представлены как int. Каждый элемент инициализируется с ID равным второй степени (это важно при применении битовых операций):
int key = 1; // 0x0001
int book = 2; // 0x0010
int doughnut = 4; // 0x0100
int inventory = 0; // 0x0000
Добавим эти предметы в инвентарь или… воспользуемся функцией переключения прямо в инвентаре!
В этом случае мы используем битовую операцию OR, представленную символом |.
Оператор OR (|) берет каждую двоичную цифру и устанавливает значение 1, если хотя бы одна из цифр равна 1:
int a = 5; 0x0101
int b = 3; 0x0011
// Результат a | b = 0x0111
Теперь добавляем к инвентарю ключ (на данный момент количество равно 0).
int inventory = 0; // 0x0000
int key = 1; // 0x0001
inventory |= book; // 0x0001
Первый предмет найден. Что еще можно найти? Продолжаем игру и находим таинственную книгу и пончик:
// В инвентаре уже есть ключ
// инвентарь = 0x0001
int book = 2; // 0x0010
int doughnut = 4; // 0x0100
inventory |= book; // 0x0011
inventory |= doughnut; // 0x0111
// Инвентарь заполнен, у персонажа есть книга, пончик и ключ
Настало время для побега и возможности воспользоваться некоторыми предметами. Находим платформу на полу. Если мы наступаем на нее, открывается потайная дверь, если отходим, дверь закрывается. Это выход? Давайте проверим!
Избавляемся от книги, оставив ее на платформе. Теперь ее нужно удалить из инвентаря, и для этой сложной задачи мы создадим маску с помощью операторов NOT (~) и AND:
- Битовый оператор AND представлен символом (&). Он принимает оба элемента и устанавливает новое значение 1, только если оба элемента равны 1:
int a = 5; // 0x0101
int b = 3; // 0x0011
a & b // // 0x0001
- Битовый оператор NOT представлен символом (~). Он принимает каждый бит переменной и изменяет значение на противоположное: 0 меняется на 1, а 1 на 0:
int c = 6; 0x0110
int maskB = ~c; 0x1001
Берем книгу из инвентаря:
// Устанавливаем маску NOT Book
int book = 2; // 0x0010
int maskNotbook ~= book; // 0x1101
// Применяем маску к инвентарю
// инвентарь 0x0111
inventory &= ~book; 0x1101
// инвентарь 0x0101
// Примечание: при буквальном чтении синтаксиса эти команды имеют смысл:
// Inventory and no book
// inventory &= ~book;
Вуаля! В инвентаре остались только ключ и пончик! С помощью маски сохраняются текущие элементы и удаляются ненужные.
А теперь настало время заговорить на языке ПК!
Вернемся к прототипу игры и повысим уровень волшебства с помощью битбордов!
Битборды
Битборд, также известный как битовая карта, — это простой способ представить доску, например, шахматную. Каждый бит в битборде соответствует игровому пространству.
В этом прототипе игры сетка состоит из 64 клеток (8х8). Используя преимущества битовых операций и битбордов, логику можно с легкостью упаковать в long long int, который равен 64 битам.
При использовании массива целых чисел для представления сетки доступ к одной клетке был бы таким же простым, как:
int grid[8][8];
// Нам нужно получить доступ к строке 2 в столбце 3
int tile = grid[2][3];
Этот процесс также можно упростить до одного массива из 64 элементов:
int grid[64];Чтобы получить доступ к одной клетке, нужно применить одну из моих любимых формул:
int indexTile = indexRow * numberColumns + indexColumn;
// indexTile = 2 * 8 + 3 = 18;
int tile = grid[indexTile];
Однако мы используем битборды, и у нас нет массива, а только 64 бита. Можно использовать ту же формулу, чтобы получить доступ к одной единственной сетке, с некоторыми настройками.
Для начала определяем битборды и функции для обработки. Из-за наличия различных типов клеток необходимо объявить битборд для каждого из них, а также несколько функций для доступа и применения логики к сетке.
Объявление каждого битборда и вспомогательных функций:
Функция ToggleTile использует оператор сдвига влево (<<). В предыдущем примере мы использовали ID для каждого элемента, который был возведен во вторую степень, поэтому единственными вариантами были 1, 2, 4, 8, 16…, но в этом случае понадобится больший диапазон значений. Используем битовый оператор сдвига влево, представленный символом (<<), а также все индексы.
Представим, что индекс для клетки равен 9 (это не степень 2!). Каким образом его можно использовать? Все очень просто, мы изменяем позиции 1, 9:
int64_t tempBitBoard = 1 << 9;
// Мы переводим это как: 0x100000000
В этом методе также используется битовый оператор XOR, с помощью которого можно переключать бит и менять его значение на противоположное (0 на 1 или 1 на 0), что идеально подходит для этого прототипа. Так можно изменить тип клетки в определенной строке и столбце. Как будет показано ниже, я экспериментирую с каждым битбордом для получения текущего состояния, удаления и изменения. Битовый оператор XOR (^) возвращает 1, только если ровно один бит установлен на 1 из 32 битов (исключающее OR).
Пример:
int a = 5; // 0x0101
int b = 3; // 0x0011
a ^ b; // 0101 ^ 0011 = 0110 -> 6
Теперь можно начать реализацию логики для игры. Начнем с построения сетки, расположения каждой клетки и Таичи в правильной позиции, а также добавления изначально заблокированных клеток. Затем реализуем логику нажатия на каждую клетку и изменяем ее тип. При каждом попадании мыши на клетку, она переключается на следующий тип (налево, направо, прямо, налево, направо…).
Мы не можем нажать на заблокированную клетку, и Таичи не может пройти по ней.
Когда игрок создаст для Таичи путь, он может начать движение и выбраться, если все окажется верным!
Клетки создаются и блокируются в методе BeginPlay.
И, наконец, переходим к коду, обрабатывающему нажатие на клетку.
При нажатии на клетку происходят следующие события:
- Отключение соответствующего битборда для выбранного типа клетки (устанавливается значение 0 в позиции индекса для строки и столбца).
- Использование вспомогательной функции, определение следующего типа клетки для той же строки и столбца.
- Включение соответствующего битборда в зависимости с этим новым типом, установление 1 в позиции индекса.
Метод обработки нажатия на клетку и изменение ее типа:
В этом случае функция переключения действует в обоих случаях. Быстро и просто.
Вот и все! Доберется ли Таичи до выхода?
Эх! Провал…Ссылка на полный прототип игры: TileGameAndBitboards.
Заключение
Мы рассмотрели альтернативный способ обработки сетки из клеток. Разобраться в битовых операциях при первом чтении кода не так просто, но в итоге с их помощью можно не только ускорить процесс, но и в некоторых случаях уменьшить размер.
Перевод статьи BlueBubbleBee: Playing with Bitboard and Bitwise Operations in Unreal 4
Комментарии