Змейка на C

Тем, кому не интересно читать пост, а интересно сразу увидеть код и/или историю коммитов, предлагаю пойти поглядеть на репозиторий.

Небольшой дисклеймер

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

Немного пояснений

C — довольно низкоуровневый язык, и уж никак не "кроссплатформенный по-умолчанию", как, например, Python. Тот факт, что я не использую ncurses, ещё больше усугубляет ситуацию.
Очень многое в игре реализовано путём функций, имеющихся лишь в POSIX-системах, а то и вообще лишь в Linux и glibc. Windows POSIX-системой не является, да и терминал там вряд ли настолько же функционален, потому собрать stupid-snake под Windows у вас, скорее всего, никак не получится. На OS X — не знаю, пусть кто-то попробует и доложит об успехах.
Может также и не на каждом дистрибутиве Linux собраться, в таком случае напишите мне — помогу и добавлю нужные флаги в мейкфайл.

Если своего линукса у вас нигде не завалялось, а испытать игру очень хочется, рекомендую использовать VirtualBox или иной софт для работы с виртуальными машинами, какой вы предпочитаете.
Если же вам интересен сам процесс и разъяснения к коду — вы совершенно ничего не теряете, читая этот пост хоть с Windows, хоть с Linux, хоть с OS/2.

Почему терминал? Почему даже без ncurses? Зачем так усложнять себе жизнь?
Во-первых потому, что мне так захотелось. Во-вторых потому, что ncurses — это очень большая, толстая и сложная либа, так что не факт, что было бы проще. Пояснять, скорее всего, стало бы лишь сложнее.

Я пойму пост, если не знаю C?
Понятия не имею. Если вы действительно не знаете ни C, ни преступно подобных ему языков (типа C++) — напишите, пожалуйста, поняли вы или нет. Мне интересно.
Пост планировался как понятный полным "чайникам", но получилось ли у меня — совсем другой вопрос.

Если я прочитаю пост, я выучу C?
Нет.

Если я прочитаю пост, я научусь писать игры?
Нет. Скорее всего.

Зачем тогда мне читать пост?
Откуда я знаю, зачем вам читать пост? Может, вам интересно смотреть, как другие люди мыслят и решают задачи. Может, вам интересно узнать, какой это он — C в консолечке юниксовой. Может, просто скучно.
Впрочем, я думаю, в моём посте можно будет отыскать некоторые интересные факты и подходы, до сих пор вам неизвестные.

Какъ собрать и запустить ваше игрище бѣсовское, сударь?
Для бояр, которые этого до сих пор никогда не делали, а гуглить лень, кратенькое пояснение:
$ git clone 'https://gitlab.com/saxahoid/stupid-snake.git'
$ cd stupid-snake
$ make
$ ./snake

Управление?
Стрелки, выход — Ctrl+C или врубиться в стенку/себя.

А вот я вижу место, где как-то очень хитроподвывернуто сделано, нельзя ли проще?
Скорее всего, нет. Как я дальше поясню в посте, в процессе разработки вылезло несколько очень интересных особенностей работы с терминалом, и эти хитроподвывернутые костыли — единственный рабочий вариант.

Поехали

Давайте-ка сделаем игру

Что нужно, дабы сделать игру для терминала? Знать какой-нибудь язык программирования более-менее уверенно и уметь гуглить, чтобы разобраться с некоторыми особенностями этого самого терминала.
Знать кучу библиотек (ну разве только ncurses, если хочется более серьёзную игру, чем у меня, с минимумом геморроя), особенности работы вашей любимой оконной системы, да ещё заодно щедрую дозу компьютерной графики и уж тем более быть дизайнером-художником абсолютно не обязательно и даже вредно. Потому что так не интересно.

Текстовый ввод/вывод — один из самых простых и основных для любого современного ЯП. Если вы уверенно (да даже если криво сикось накось) знаете какой-нибудь, то вы знаете и как работать с текстом. Поэтому для создания игры, использующей текст для общения с пользователем, не нужно знать ничего специфичного. Поэтому же такие игры, даже если примитивные по сегодняшним меркам, становятся неплохими упражнениями для мозга.

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

Дизайн

Прошу заметить, что имеется в виду не тот дизайн, которым занимается Артемий Лебедев, а технический дизайн. Оно же проектирование.

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

Комплексная задача (игра "Змейка") разбивается на более мелкие:
• Обновление экрана;
Очевидно, для того, чтобы игра была динамической и отвечала на пользовательский ввод, нужно периодически обновлять экран. Так как "змейка" — не походовая забава, делать это необходимо по таймеру.
На нашем ламерском уровне более чем достаточно воспользоваться командой вроде sleep (приказать программе ничего не делать 1/fps часть секунды, где fps — желаемая кадровая частота), но это неинтересно и вообще я болею перфекционизмом, потому буду использовать часы реального времени.

• Визуализация змейки;
Терминал современного Linux поддерживает юникод — вот уж где простор для фантазии! Но по моему мнению реализация юникода в самом C не то чтобы очевидная, потому (для начала, во всяком случае) решаю использовать самый стандартный из всех стандартов — ASCII. Прямое тело змеи изображать буду символами "-|", повороты — "/\", направленную в разные стороны голову (распахнутую пасть) — "V<^>".
На том бы и остановиться, вот только неинтересно (и я болею перфекционизмом, помните?). Нужна ещё анимация. Как насчёт заставлять змейку закрывать рот каждый ход? Досточно будет заменить символ "головы" на соответствующий направлению символ "тела". Переход "<" ➛ "-" сносно создаёт иллюзию закрывшегося рта.
Так же стоит "выпрямлять" повороты тела змеи, когда они становятся последним сегментом (не бывает же у змей таких загнутых хвостов).

• Связь между элементами игры;
Змейка должна погибнуть, наткнувшись на стену, и вырасти, съев пищу. Для того, чтобы увязать меж собой положение стен, еды, головы, тела и хвоста змейки, необходимо использовать общую для них всех систему координат. И самый очевидный вариант — применить стандартные координаты терминала (0, 0 — верхний левый угол, и разрешение, разумеется, посимвольное — про пиксели терминал ничего знать не знает).
Дальше остаётся в общем два пути: 1) Создать все требующие учёта элементы как отдельные сущности, свойствами которых являются координаты; 2) Создать одну сущность — координатное поле — служащую отображением нынешнего состояния терминала, и разместить элементы-символы в ней.
Первый путь — очень громоздкий. Например, для учёта положения еды необходимо будет создать массив (а то и список) сущностей типа "еда", у каждой из которых будет свой набор координат. Чтобы проверить, не съела ли змейка еду, нужно будет каждый раз проходиться по всему этому массиву/списку. Аналогично при выводе на экран будет необходимо обойти каждую сущность-элемент, чтобы узнать нужные координаты для вывода.
Второй путь — намного более легковесный и удобный. Чтобы проверить, не наткнулась ли змея на что-то, достаточно перед её перемещением проверить "новую" позицию — нет ли там уже чего? С выводом на экран тоже легко: просто print каждый элемент из координатной сетки. Но есть и проблема у второго пути — как найти саму змею? Обходить всё координатное поле поиском?
Как часто бывает, идеальный вариант — комбинированный. Так как интересует меня в основном змея, а всё остальное — уже относительно неё, для удобства нахождения змейки в координатном поле изобразим её ещё и отдельной сущностью, хранящей в себе нынешние координаты.
И да, если вы подумали, что первый вариант — без координатного поля — бесполезен, то вы сильно ошибаетесь! У него есть свои применения. Например, если полное отображение координатного поля потребует десятка гибибайт памяти, тогда как сущностей создать нужно было бы всего десяток-другой. Но подобные расклады настолько же далеки от "змейки", насколько автор этого поста — от мирового господства.

• Передвижение змейки;
Чтобы передвигать змейку, необходимо знать нынешнюю позицию головы, следующую позицию головы, нынешнюю позицию хвоста и следующую позицию хвоста. При выполнении "хода" нарисовать голову на новой позиции, сегмент тела — на старой; старую позицию хвоста очистить. Новую позицию хвоста надо знать лишь для того, чтобы запомнить её на будущее.
Здесь возможны разнообразные варианты. С учётом уже имеющейся в дизайне отдельной сущности "змея", хранящей координаты её головы для быстрого нахождения, мне показалось самым разумным в эту же сущность добавить также координаты хвоста. Для определения новой позиции головы достаточно сохранить её (головы) направление (и инкрементировать/декрементировать координаты нынешней позиции в зависимости от направления, чтобы получить новую). Аналогично поступить с хвостом — хранить его направление.
Но тут возникает проблема: если с переменой направления головы всё ясно (игрок нажал влево — повернуть голову влево), то как быть с хвостом? Не желая хранить дополнительную информацию в больших объёмах исключительно для правильной обработки хвоста, я прибегаю к простому трюку: зная направление хвоста и следующий в этом направлении сегмент тела, новое направление определить очень легко.
Например, если хвост двигался ВПРАВО, и следующий справа сегмент — "-", хвост продолжает двигаться ВПРАВО. Если наблюдается сегмент "\", хвост поворачивает ВНИЗ. Если "/" — ВВЕРХ. Если "|", то что-то сломалось; такого случиться никогда не должно.

• Генерация еды;
Генерируем, разумеется, случайным образом. Количество генерируемой еды зависит от размеров поля; скажем, 1 единица на каждые 512 пустых позиций.

• Обработка стенок;
Можно держать стенки внутри координатного поля (и проверять столкновение по принципу "Является ли следующая позиция головы занята символом стены?". Можно держать их снаружи (и проверять столкновение по принципу "Не вышла ли голова змеи за разрешённые пределы координат?"). Мне больше понравился второй способ. Он также кажется более гибким (позволяет легко заменить логику столкновения со стеной на логику "телепортации" на другой край поля — тоже интересный подход).

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

Код

Откройте исходник, я буду ссылаться на номера строк (в квадратных скобках), функции и так далее.
Немного слов о файловой структуре кода. Она очень простая — один исходник (snake.c), один makefile. LICENSE и README.md не используются при сборке совершенно никак и не важны для понимания программы. По-хорошему функции надо было бы вынести в отдельные файлы и сгруппировать таким образом по их предназначению, но мне показалось более правильным использовать структуру попроще.

main() — строка 515
main — основная функция программы; сама программа, если пожелаете. Исполнение начинается отсюда. Так как мне нет нужды на данный момент принимать какие-либо аргументы из командной строки, main я объявляю без параметров (void).

В начале вызываются несколько инициализирующих функций (переключение терминала в нужный режим, установка обработчика сигнала INT (Ctrl+C) и инициализация генератора псевдослучайных чисел), затем объявляются нужные переменные, затем производится ещё несколько инициализаций — уже касающихся самой игры — и первый вывод картинки в терминал.
Наконец, получив значение начального момента времени, код входит в цикл обновления изображения.

Этот цикл имеет несколько интересных особенностей. Начнём с условия — while(run). run является [64] переменной особого типа sig_atomic_t, придуманного специально для использования в обработчиках сигналов. Свой кастомный обработчик [82] я устанавливаю на строке [517], и всё, что он делает — сбрасывает при вызове этот самый run в 0. Обрабатывать SIGINT нужно затем, чтобы корректно выйти из игры и вернуть терминал в адекватное состояние — стандартный предоставляемый системой обработчик просто завершает программу "здесь и сейчас".

Следующий интересный момент — обновление экрана. Не мудрствуя лукаво, я использую здесь самый банальный подход: прямую зависимость скорости змеи от частоты кадров. Два кадра — один ход и одна анимация. При 10 fps получаем 5 ходов за секунду; при 200 fps — 100.
Работает это так: при каждой итерации цикла сохраняется момент времени [541], после чего рассчитывается разность [542] меж ним и моментом, когда в прошлый раз был отрисован кадр. Затем полученная разность сравнивается с кадровой задержкой (задержка = 1 секунда / fps), и если она превышает задержку — кадр обновляется, сохранив новый момент обновления.
FPS не является чётко заданным конкретным числом, а находится как "(уровень + 1) * 5". Иными словами, на первом уровне имеем частоту 10, на втором — 15, на третьем — 20, и так далее.

Кадров бывает два вида: полноценный и анимационный. Определяю я, какой из них надо рисовать, простым флагом animation_frame. В случае анимационного кадра отрисовывается исключительно анимация; в случае полноценного — перерисовывается всё игровое поле, а также генерируется пища, производится по необходимости левел-ап и всё такое.

set_terminal_mode — строка 90
reset_input_mode — строка 74
Здесь происходит терминальная магия. В первой функции устанавливается нужный режим, во второй возвращается старый. В чём дело?

Для работы с параметрами терминала используется набор функций termios. Происходит это так: вынуть нынешние параметры в структуру termios с помощью функции tcgetattr [105], отредактировать её, запихнуть обратно в терминал с помощью tcsetattr [109].

По-умолчанию юниксовый терминал ждёт ввода полной строки (нажатия Return) и позволяет перед вводом эту строку всячески редактировать. Это называется каноническим режимом. Чтобы нажатия передавались нашей игре сразу, без необходимости клацать Enter, необходимо переключить терминал в режим неканонический.
Также по-умолчанию юниксовый терминал сразу выводит любую нажатую клавишу на экран. Это называется эхо-режимом. Чтобы этого не происходило, надо выключить эхо.
Канонический режим и эхо-режим выключаю одновременно [106]. Это битовые флаги, и если вы не понимаете вообще, что там происходит, то советую почитать где-нибудь о побитовых операциях — тема объёмная и полезная.

Устанавливаю VMIN [107] и VTIME [108] в массиве параметров c_cc в нулевые значения.
VMIN отвечает за минимальное количество символов, которого будет дожидаться терминал в неканоническом режиме. Если там будет что-то кроме нуля, любая попытка читать с терминала заблокирует программу до получения VMIN символов. Мне это совершенно не нужно, блокироваться — плохая идея, надо кадры обновлять.
VTIME отвечает за то, сколько (при ненулевом VMIN) терминал будет ожидать символы.
Вообще говоря, достаточно установить в 0 один из этих параметров, но и оба сразу — не повредит.

И в set_terminal_mode, и в reset_terminal_mode имеются очень странные printf. Это — вывод в терминал особых последовательностей байтов, которые терминал, следующий стандарту ANSI, обязан понимать и интерпретировать. Как символы они записаны исключительно для удобства. Полное описание есть на википедии.
Не вдаваясь в подробности, "\x1b[?25l" означает "выключить отображение курсора", а "\x1b[?25h" — "включить".

Интересна также функция atexit [113]. Она регистрирует любую другую функцию в системе так, чтобы та была запущена при корректном выходе из программы. Ключевой момент тут — корректный выход; именно чтобы обеспечить его я перехватываю SIGINT.

Набор функций turn_<direction> — строки со 121 по 219
Эти четыре функции очень схожи между собой. Они устанавливают новое направление головы змеи и рисуют новый сегмент тела на месте головы, если определённый поворот возможен из нынешней позиции. Возвращают int, работающий в качестве булевой переменной (можно было бы обойтись char, но мне почему-то захотелось int).

Рассмотрим на примере turn_right [196]. Определяется нынешнее направление движения [201], и в зависимости от него определяются дальнейшие действия. Если змея двигалась вертикально (вверх [202] или вниз [205]), поворот вправо возможен — turn_right вернёт 1 и установит соответствующий повороту сегмент тела на поле. Если змея и так двигалась вправо или вообще получила неправильный аргумент [210], turn_right просто вернёт 1 и ничего больше не сделает (это нужно для эффекта ускорения при нажатой клавише). Если змея двигалась влево [208], поворот направо невозможен — turn_right вернёт 0.


process_key — строка 223
Эта функция считывает с терминала три байта [227] (именно тремя байтами кодируется нажатие клавиши-стрелки). Если эти три байта соответствуют одной из заранее определённых констант [55], вызывается функция соответствующего поворота.
Очень важно, что в данном случае переменная c инициализируется в 0: так четвёртый байт, который не считывается, но всё равно остаётся "болтаться", будет нулевым и не станет мешать. Вместо переменной int можно было использовать массив char, но сравнивать с трёхбайтными константами его намного сложнее, чем простым switch.

Возвращает функция 1 или 0 в зависимости от того, смогла ли сдвинуться змея в ответ на нажатие клавиши.

init_playfield — строка 251
Простенькая функция инициализации игрового поля. Просто забивает его всё пробелами.

init_snake — строка 259
Функция посложнее, инициализация змеи. Голова змеи устанавливается в условный центр поля и изначально смотрит вправо. Ровно в ту же позицию помещается хвост, длина змеи устанавливается в 1 и буфер длины — в 4. Таким образом, начальная длина змейки — 5.


redraw_all — строка 278
Функция отрисовки игрового поля.

Вначале курсор помещается в стартовую позицию 0, 0 (верхний левый угол) с помощью ещё одного управляющего спец-символа [279]. Далее за несколько циклов выводятся сначала верхняя стенка [281], затем боковые и само поле [286], затем нижняя стенка [295] и немного информации: длина змеи, уровень [300]. Ничего интересного здесь нет; такое писал каждый, кто когда-либо выводил матрицы на экран.

redraw_animation — строка 305
Немного более интересная функция, которая отвечает за анимацию.

С использованием, опять же, спец-символа (но в этот раз динамически сгенерированного) курсор устанавливается на координаты головы змеи [307] (поправки +2 нужны из-за того, что в змее хранятся координаты относительно игрового поля-матрицы, а нужны координаты относительно экрана). Далее вместо головы рисуется "закрытый рот" (просто сегмент тела, соответствующий направлению) [309].

Затем курсор путём всё той же манипуляции со спец-символом устанавливается на позицию змеиного хвоста [317] и с хвостом происходит анимация выпрямления (при условии, что он ещё не прямой), в общем-то идентичная таковой для головы.

move_snake — строка 338
Самая сложная, интересная и важная функция. Перемещает змею в игровом поле и вообще обновляет её состояние.

Если направление змеи не менялось (поля dir и new_dir одинаковы), значит, была нажата клавиша того же направления, либо не была нажата никакая. В обеих этих случаях функции turn_<direction> ничего не рисуют, потому необходимо нарисовать новый сегмент тела [345-350]. Не рисуют turn_* именно потому, что возможных случая тут два (нажата та же, либо не нажата никакая), и во втором случае turn_* вызваны не будут. Получается, для этого второго случая отрисовку внутри move_snake предусматривать всё равно придётся, а раз она тут уже нужна, зачем повторно в turn_*?
Если же направление поменялось, new_dir сохраняется как dir [352].

Далее определяется символ для отображения головы и обновляются её координаты ("голова сдвинулась на новое место"). Это зависит исключительно от направления головы и обрабатывается простым switch [357].

Затем новая позиция головы анализируется. Если там на данный момент стена [379], еда [392] или что угодно ещё кроме пробела (это может быть только тело змеи во всех его разнообразных вариациях) [397], выполняются соответствующие действия (game over или съедение еды). Встреча со стеной определяется как выход за рамки позволенных координат (это позволяет, например, очень легко не рисовать стены или заменить символ стены на какой-то ещё, да к тому же позволяет не занимать память зазря символами стен, никогда не меняющимися).

Наконец, после того как все возможные проблемы с новой позицией улажены (и game over не наступил), туда помещается голова змеи [407].

И теперь обрабатывается хвост [411]. Если у змеи не пустой буфер длины, она должна вырасти; в этом случае с хвостом ничего не происходит и он остаётся на старом месте [412]. Если же буфер пустой, всё намного интереснее.
Первым делом хвост заменяется пробелом [415]. Затем координаты хвоста обновляются, чтобы он занял новую позицию: следующий после старого хвоста сегмент тела [418]. Этот switch очень похож на таковой для головы [357], но ничего не рисуется.
Дальнейшая задача — определить новое направление хвоста. Сделать это можно, проанализировав сегмент на новой позиции. Если он прямой, направление хвоста остаётся прежним [437-439]. Если он "/", новое направление определяется в зависимости от старого [441]. Если он "\", направление определяется аналогично, но с другими значениями [359].

Например, если хвост двигался вверх, но выглядит как "/", то дальше ему нужно двигаться вправо.

gen_food — строка 483
Функция генерации пищи. Она управляется константой FOOD_RARITY, определяющей частоту еды на поле как "на FOOD_RARITY доступного пространства должен приходиться 1 юнит пищи". Соответственно, необходимое кол-во еды определяется простым делением [487]. +1 там нужно для округления вверх (то есть чтобы, например, при установленной FOOD_RARITY 512 и размере поля 600, на нём был не 1, а 2 куска еды).

Если еды на поле недостаточно (следить за её количеством можно через переменную food_cnt), генерируется новый кусок [490]. Координаты еды определяются генератором случайных чисел и подгоняются в заданные координатные рамки путём операции суммы по модулю (%), или же остатка. Полученная позиция проверяется, и если она пуста — туда помещается пища, а если занята — генерация выполняется вновь.

Из-за того, что генерироваться еда будет "до упора", в случае, близком к победе (всё поле занято змеёй), игра может начать тормозить, а когда места для необходимого кол-ва еды просто не останется, банально уйдёт в бесконечный цикл. Если вы когда-либо добьётесь такой ситуации — вы победили! И удачи с выключением игры, Ctrl+C не сработает — он перехвачен.

level_up — строка 502
Довольно простая функция, повышающая игровой уровень (а значит — скорость) по достижению змеи очередной LVLUP_LENGTH. Например, в моём случае LVLUP_LENGTH установлена в 50 — так левелап будет происходить каждые 50 очков длины.

Исползуется static (сохраняющая своё значение меж вызовами функции) переменная upped_already, чтобы избежать проблем при нескольких вызовах level_up за те хода, пока длина змеи сохраняется кратной LVLUP_LENGTH. Она устанавливается в 1 после повышения уровня, и в 0, когда длина змеи не соответствует нужному для левел-апа значению. Так как длина может лишь расти, это адекватный подход.

Послесловие

Надеюсь, кому-то было интересно прочитать про то, как можно упорото и хардкорно написать змейку.

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