Как написать «Змейку» в четыре переменные?

Пишем классическую «Змейку», как на КДПВ, в четыре переменные. По словам автора, «Можно написать и с двумя, но зачем осложнять себе жизнь?» К старту курса по разработке на С++ приглашаем под кат.

Давно я не писал «Змейку» и вот сегодня решил постараться сделать её с необычными ограничениями:

• Карту игры сохраним в uint32_t, где тело рептилии сформируется помощью 1s. В карте 4x8, то есть 32 положения. Для развлечения достаточно!

• Сохраним uint64_t — массив направлений движения змейки, пока её растущая форма остаётся нетронутой.

• Зашьём в uint32_t ещё несколько значений на 5 бит — для сохранения положения head («головы»), tail («хвоста»), apple («яблока») и length (текущей «длины»). Любые вводимые с клавиатуры данные сохраняются там же. Двух бит хватит.

• Сохраним 8-битную (uint8_t) переменную для зацикливания.

В языке C стандартного способа взаимодействия с клавиатурой не существует, поэтому придётся использовать curses. Установите её, чтобы скомпилировать программу. Если у вас подходящий тип операционной системы, curses в ней, скорее всего, уже есть. Если нет, можно установить с помощью диспетчера пакетов.

К сожалению, в самой curses используется дополнительная память. Но будем откровенны: взлом с применением таинственных escape-символов и низкоуровневых системных функций — это не так весело и уж точно не то, что мне самому хотелось попробовать. Да, жульничество, как и эта статья!

Прежде чем продолжить чтение (если вы ещё читаете), обратите внимание: код не следует воспринимать всерьёз; это такое упражнение в минимализме, если хотите. Макросы для побитовых операций, глобальных переменных, одного и того же счётчика и т. д. неприглядны из-за ограничений, так что получился не самый элегантный и удобный для восприятия код.

Код

Всё есть на GitHub:

git clone git@github.com:nomemory/integers-snake.git

Компилируем и запускаем программу:

gcc -Wall snake.c -lcurses && ./a.out

Схема распределения памяти

Начнём с определения четырёх целых чисел, в которых будут все игровые данные:

uint32_t map = ...;
uint32_t vars = ...;
uint64_t shape = ...;
int8_t i = ...;

map

map — это то, что отобразится на экране. Из 32 бит в map сформируется сетка 4x8, отображаемая с помощью curses:

Чтобы получить доступ к памяти и задать битам 0 или 1, нужны макросы:

#define s_is_set(b) ((map&(1<<(b)))!=0) // проверяет, установлен ли бит b в map в 1
#define s_tog(b) (map^=(1<<(b))) // переключает в map бит b (сейчас не используется)
#define s_set_0(b) (map&=~(1<<b)) // устанавливает бит b в map в 0
#define s_set_1(b) (map|=(1<<b)) // устанавливает бит b в map в 1

vars

vars — это 32-битное целое число, в котором будут храниться следующие данные:

• hpos (биты с 0 по 4) — положение головы змеи как смещение от младшего значащего бита map;

• tpos (биты с 5 по 9) — аналогично положение хвоста змеи;

• apos (биты с 15 по 19) — аналогично положение яблока;

• len (биты с 10 по 14) — длина змеи;

• chdir (биты с 20 по 21) — последняя нажатая клавиша (2 бит хватит, потому что регистрируются только стрелки, а их четыре);

• оставшиеся биты не используются. Здесь мог быть счётчик uint8_t, но ради простоты я выбрал отдельную переменную.

Для доступа к hpos, tpos и т. д. мы определили следующие макросы (каждый из них будет как геттер/сеттер для соответствующих сегментов):

#define s_mask(start,len) (s_ls_bits(len)<<(start)) // создаёт битовую маску len, начиная с позиции start
#define s_prep(y,start,len) (((y)&s_ls_bits(len))<<(start)) // подготавливает маску

// Получает количество битов 'len', начиная с позиции 'start' в 'y'.
#define s_get(y,start,len) (((y)>>(start))&s_ls_bits(len)) 
// Устанавливает количество битов 'len', начиная с позиции 'start' в 'y', в значение 'bf'
#define s_set(x,bf,start,len) (x=((x)&~s_mask(start,len))|s_prep(bf,start,len))

#define s_hpos s_get(vars,0,5) // получает последние 5 бит 'vars', что соответствует s_hpos
#define s_tpos s_get(vars,5,5) // устанавливает последние 5 бит 'vars', что соответствует s_hpos
#define s_len s_get(vars,10,5)
#define s_apos s_get(vars,15,5)
#define s_chdir s_get(vars,20,2)
#define s_hpos_set(pos) s_set(vars,pos,0,5)
#define s_tpos_set(pos) s_set(vars,pos,5,5)
#define s_len_set(len) s_set(vars,len,10,5)
#define s_apos_set(app) s_set(vars,app,15,5)
#define s_chdir_set(cdir) s_set(vars,cdir,20,2)
#define s_len_inc s_len_set(s_len+1)

Подробнее о работе макросов см. в статье Working with bits and bitfields («Работа с битами и битовыми полями»).

shape

В shape хранятся направления (всего 32) каждой клетки змейки. На направление хватает двух бит:

Возможные направления отображаются с помощью макросов:

#define SU 0 //ВВЕРХ                       
#define SD 1 //ВНИЗ                 
#define SL 2 //ВЛЕВО                
#define SR 3 //ВПРАВО

Когда змея перемещается внутри сетки map, мы с помощью макросов циклически проходим направления:

#define s_hdir ((shape>>(s_len*2)&3)) // извлекает направление головы (на основе s_slen).
#define s_tdir (shape&3) // извлекает последние 2 бита, которые соответствуют хвосту
#define s_hdir_set(d) s_set(shape,d,s_len*2,2) // задаёт направление движения головы
#define s_tdir_set(d) s_set(shape,d,0,2) // задаёт направление хвоста
// Макросы изменения формы при каждом движении змеи
#define s_shape_rot(nd) do { shape>>=2; s_hdir_set(nd); } while(0);
#define s_shape_add(nd) do { s_len_inc; shape<<=2; s_tdir_set(nd); } while(0);

Если змея при этом не съедает яблоко, вызываем макрос s_shape_rot, удаляя последнее направление и добавляя новую голову с помощью s_chdir.

Здесь shape напоминает очередь:

Если змея съедает яблоко, вызываем s_shape_add, увеличивая длину и добавляя новый хвост s_tdir.

Цикл игры

Цикл игры выглядит так:

// макросы, чтобы код стал читабельным
// (или нечитабельным, зависит от вас)
#define s_init do { srand(time(0)); initscr(); keypad(stdscr, TRUE); cbreak(); noecho(); } while(0);
#define s_exit(e) do { endwin(); exit(e); } while(0);
#define s_key_press(k1, k2) if (s_hdir==k2) break; s_chdir_set(k1); break;

int main(void) {
    s_init; // инициализирует контекст curses
    rnd_apple(); // создаёт случайную позицию яблока
    while(1) {
        show_map(); // отображает карту на экране
        timeout(80); // getch() таймаут после ожидания ввода пользователя
        switch (getch()) {
            case KEY_UP : { s_key_press(SU, SD) }; 
            case KEY_DOWN : { s_key_press(SD, SU) };
            case KEY_LEFT : { s_key_press(SL, SR) };
            case KEY_RIGHT : { s_key_press(SR, SL) };
            case 'q' : exit(0); // Выход из игры
        }
        move_snake(); // Змея движется внутри решётки
        s_shape_rot(s_chdir); // Очертания змеи обновляются
        napms(200); // частота кадров :))
    }
    s_exit(0); // выход из игры
}

При каждом нажатии клавиши развёртывается s_key_press и проверяется, возможно ли перемещение. Затем с помощью s_chdir_set обновляется s_chdir.

Зачем в s_key_press два входных параметра? Чтобы исключить противоположное направление. Например, если змея сейчас ползёт направо (SR), то SL невозможно, и поэтому в switch срабатывает break.

Функция перемещения змейки

Большая часть логики реализуется в move_snake():

#define s_next_l s_mask5(s_hpos+1) // увеличение смещения для перехода вправо
#define s_next_r s_mask5(s_hpos-1) // уменьшение смещения для перехода влево
#define s_next_u s_mask5(s_hpos+8) // изменяет ряд вверх, добавляя к смещению 8 позиций
#define s_next_d s_mask5(s_hpos-8) // изменяет ряд вниз, удаляя из смещения 8 позиций

// Проверяет возможность движения влево. 
static void check_l() { if ((s_mod_p2(s_next_l,8) < s_mod_p2(s_hpos,8)) || s_is_set(s_next_l)) s_exit(-1); }
// Проверяет возможность движения вправо.
static void check_r() { if ((s_mod_p2(s_next_r,8) > s_mod_p2(s_hpos,8)) || s_is_set(s_next_r)) s_exit(-1); }
// Проверяет возможность движения вверх.
static void check_u() { if ((s_next_u < s_hpos) || s_is_set(s_next_u)) s_exit(-1); }
// Проверяет возможность движения вниз.
static void check_d() { if ((s_next_d > s_hpos) || s_is_set(s_next_d)) s_exit(-1); }
static void move_snake() {
    if (s_hdir==SL) { check_l(); s_hpos_set(s_hpos+1); } 
    else if (s_hdir==SR) { check_r(); s_hpos_set(s_hpos-1); } 
    else if (s_hdir==SU) { check_u(); s_hpos_set(s_hpos+8); }
    else if (s_hdir==SD) { check_d(); s_hpos_set(s_hpos-8); }
    // Устанавливает бит на основе текущих s_hdir и s_hpos
    s_set_1(s_hpos);
    // Если яблоко съедено
    if (s_apos==s_hpos) {
        // Генерирует ещё яблоко, чтобы змея не умерла с голоду
        rnd_apple();
        // Прикрепляет яблоко к хвосту
        s_shape_add(s_tdir);
        // Перестаёт очищать хвостовой бит
        return;
    }
    // Очищает хвостовой бит
    s_set_0(s_tpos);
    // Обновляет t_pos, чтобы при движении змеи можно было очистить следующий бит хвоста
    if (s_tdir==SL) { s_tpos_set(s_tpos+1); } 
    else if (s_tdir==SR) { s_tpos_set(s_tpos-1); } 
    else if (s_tdir==SU) { s_tpos_set(s_tpos+8); } 
    else if (s_tdir==SD) { s_tpos_set(s_tpos-8); }
}

Чтобы проверить, может ли змея перемещаться по сетке, мы реализовали функции check_*():

• check_l() — проверяем, больше ли координата X змеи (модуль %8 от s_hpos), чем в предыдущем положении;

• check_r() — проверяем, меньше ли координата X змеи (модуль %8 от s_hpos), чем в предыдущем положении;

• Принцип работы check_u() и check_d похожий: в них отслеживается, не происходит ли переполнения при увеличении s_hpos. Если да, значит, мы вышли из сетки. Переполнения используются как функционал.

Функция для отображения змейки

Реализуем последнюю функцию:

static void show_map() {
    clear();
    i=32;
    while(i-->0) { // !! Триггерное предупреждение для чувствительных людей, идём к '-->0'
        // Если бит — это яблоко, оно отображается как "@".
        if (i==s_apos) { addch('@'); addch(' '); }
        // Рисуем змеиный бит ('#'), или пустой ('.').
        else { addch(s_is_set(i) ? '#':'.'); addch(' '); }
        // Строим сетку, вставляя новую строку
        if (!s_mod_p2(i,8)) { addch('\n'); }
    };
}

После развёртывания макроса

После развёртывания всех макросов получаем итоговый код:

uint32_t map = 0x700;
uint32_t vars = 0x20090a;
uint64_t shape = 0x2a;
int8_t i = 0;
static void rnd_apple() {
    i = (rand()&(32 -1));
    while(((map&(1<<(i)))!=0)) i = (rand()&(32 -1));
    (vars=((vars)&~(((1<<(5))-1)<<(15)))|(((i)&((1<<(5))-1))<<(15)));
}
static void show_map() {
    wclear(stdscr);
    i=32;
    while(i-->0) {
        if (i==(((vars)>>(15))&((1<<(5))-1))) { waddch(stdscr,'@'); waddch(stdscr,' '); }
        else { waddch(stdscr,((map&(1<<(i)))!=0) ? '#':'.'); waddch(stdscr,' '); }
        if (!(i&(8 -1))) { waddch(stdscr,'\n'); }
    };
}
static void check_l() { if ((((((((vars)>>(0))&((1<<(5))-1))+1)&0x1f)&(8 -1)) < ((((vars)>>(0))&((1<<(5))-1))&(8 -1))) || ((map&(1<<((((((vars)>>(0))&((1<<(5))-1))+1)&0x1f))))!=0)) do { endwin(); exit(-1); } while(0);; }
static void check_r() { if ((((((((vars)>>(0))&((1<<(5))-1))-1)&0x1f)&(8 -1)) > ((((vars)>>(0))&((1<<(5))-1))&(8 -1))) || ((map&(1<<((((((vars)>>(0))&((1<<(5))-1))-1)&0x1f))))!=0)) do { endwin(); exit(-1); } while(0);; }
static void check_u() { if (((((((vars)>>(0))&((1<<(5))-1))+8)&0x1f) < (((vars)>>(0))&((1<<(5))-1))) || ((map&(1<<((((((vars)>>(0))&((1<<(5))-1))+8)&0x1f))))!=0)) do { endwin(); exit(-1); } while(0);; }
static void check_d() { if (((((((vars)>>(0))&((1<<(5))-1))-8)&0x1f) > (((vars)>>(0))&((1<<(5))-1))) || ((map&(1<<((((((vars)>>(0))&((1<<(5))-1))-8)&0x1f))))!=0)) do { endwin(); exit(-1); } while(0);; }
static void move_snake() {
    if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==2) { check_l(); (vars=((vars)&~(((1<<(5))-1)<<(0)))|((((((vars)>>(0))&((1<<(5))-1))+1)&((1<<(5))-1))<<(0))); }
    else if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==3) { check_r(); (vars=((vars)&~(((1<<(5))-1)<<(0)))|((((((vars)>>(0))&((1<<(5))-1))-1)&((1<<(5))-1))<<(0))); }
    else if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==0) { check_u(); (vars=((vars)&~(((1<<(5))-1)<<(0)))|((((((vars)>>(0))&((1<<(5))-1))+8)&((1<<(5))-1))<<(0))); }
    else if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==1) { check_d(); (vars=((vars)&~(((1<<(5))-1)<<(0)))|((((((vars)>>(0))&((1<<(5))-1))-8)&((1<<(5))-1))<<(0))); }
    (map|=(1<<(((vars)>>(0))&((1<<(5))-1))));
    if ((((vars)>>(15))&((1<<(5))-1))==(((vars)>>(0))&((1<<(5))-1))) {
        rnd_apple();
        do { (vars=((vars)&~(((1<<(5))-1)<<(10)))|((((((vars)>>(10))&((1<<(5))-1))+1)&((1<<(5))-1))<<(10))); shape<<=2; (shape=((shape)&~(((1<<(2))-1)<<(0)))|((((shape&3))&((1<<(2))-1))<<(0))); } while(0);;
        return;
    }
    (map&=~(1<<(((vars)>>(5))&((1<<(5))-1))));
    if ((shape&3)==2) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))+1)&((1<<(5))-1))<<(5))); }
    else if ((shape&3)==3) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))-1)&((1<<(5))-1))<<(5))); }
    else if ((shape&3)==0) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))+8)&((1<<(5))-1))<<(5))); }
    else if ((shape&3)==1) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))-8)&((1<<(5))-1))<<(5))); }
}


int main(void) {
    do { srand(time(0)); initscr(); keypad(stdscr, 1); cbreak(); noecho(); } while(0);;
    rnd_apple();
    while(1) {
        show_map();
        wtimeout(stdscr,80);
        switch (wgetch(stdscr)) {
            case 0403 : { if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==1) break; (vars=((vars)&~(((1<<(2))-1)<<(20)))|(((0)&((1<<(2))-1))<<(20))); break; };
            case 0402 : { if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==0) break; (vars=((vars)&~(((1<<(2))-1)<<(20)))|(((1)&((1<<(2))-1))<<(20))); break; };
            case 0404 : { if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==3) break; (vars=((vars)&~(((1<<(2))-1)<<(20)))|(((2)&((1<<(2))-1))<<(20))); break; };
            case 0405 : { if (((shape>>((((vars)>>(10))&((1<<(5))-1))*2)&3))==2) break; (vars=((vars)&~(((1<<(2))-1)<<(20)))|(((3)&((1<<(2))-1))<<(20))); break; };
            case 'q' : exit(0);
        }
        move_snake();
        do { shape>>=2; (shape=((shape)&~(((1<<(2))-1)<<((((vars)>>(10))&((1<<(5))-1))*2)))|((((((vars)>>(20))&((1<<(2))-1)))&((1<<(2))-1))<<((((vars)>>(10))&((1<<(5))-1))*2))); } while(0);;
        napms(200);
    }
    do { endwin(); exit(0); } while(0);;
}

Не то чтобы красиво, но завораживает. Когда я прокручиваю код, эти побитовые перемещения меня укачивают.

Заключение

Это было интересное упражнение. Весь код (~100 строк и четыре целых числа) находится здесь.

Если змейка в терминале ползёт слишком быстро, увеличьте s_napms.

А мы поможем прокачать ваши навыки или с самого начала освоить профессию, актуальную в любое время:

• Профессия C++ разработчик

• Профессия «Белый» хакер