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


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

  • Карту игры сохраним в 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.

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

Комментарии (15)


  1. FilimoniC
    11.08.2022 23:26
    +8

    Странный способ завлечь на "профессию: C++ разработчик" кодом, за появление которого в продукте автора погонят на улицу с огромной вероятностью.


    1. stranger777
      11.08.2022 23:49
      +3

      Интерес здесь пробуждается не кодом, а головоломкой, вызовом, ведь начать карьеру со сложного CPP — это значит ответить на вызов, захотеть разбираться в языке. При этом автор честно предупреждает, что код далёк от идеала; мы со своей стороны указываем хаб «Ненормальное программирование», а «Программирование», конечно, не указываем


      1. TheCalligrapher
        12.08.2022 03:30
        +2

        Но целью автора кода было именно подчеркнутое использование только и исключительно С, а не С++. Почему вдруг зашла речь о С++?


    1. Mishootk
      12.08.2022 12:33

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


      1. FilimoniC
        12.08.2022 16:08

        Не соглашусь, т.к. аналогия плохая.
        Уроки на роликах начинаются с обучения падению т.к. это мало зависящее от твоего сознательного поведения событие (по крайней мере, первое время). Можно сказать, вырабатывают рефлекс и это вынужденная мера.
        А вот показывать плохой пример новичку в программировании и объяснять его это примерно как учить кататься на роликах с падением на лицо. Это не вынужденная мера - давать странный код и долбанутых заказчиков джуну никто не будет.

        Если вы почуствовали что падаете, отведите плечи и руки за спину, выпрямите и напрягите тело, подайте лицо вперед. И как это необычно, а главное - вы сэкономили почти на всей экипировке, потому что при этом стиле торможения она вам не нужна! Мы научим вас кататься на роликах!


        1. Mishootk
          12.08.2022 18:33

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


  1. baldr
    12.08.2022 00:02
    +2

    Я понимаю что это перевод и автор моего комментария тут не увидит..

    Но если уж хочется себя чем-то ограничить и взять на себя челлендж - так уж лучше написать эту змейку на ассемблере. Причем не для современных процессоров с новомодными 64-битными (и шире!) регистрами в количестве до 30 штук, а для, скажем, x86-32 процессора в реальном режиме с прямым доступом к видеопамяти. Звучит сложно, но, на самом деле, не так уж тяжело в реализации.


    1. randomsimplenumber
      12.08.2022 09:03

      Игры для Радио 86рк были на ассемблере. В том числе и змейка.


    1. PrinceKorwin
      12.08.2022 11:43

      В детстве писал змейку для Корвета на асемблере. Правда не графикой, а символами. Ничего сложного вообще не было в этом. По моему был в классе 9-м. А писал код в тетрадке, сам транслировал в HEX-коды и уже их вбивал в файл на исполнение. Было весело!


  1. GennPen
    12.08.2022 00:32
    +12

    Что то ну очень замудреный алгоритм. Чем плох алгоритм со временем жизни ячеек?

    Hidden text

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

    По сути получается нужны только массив данных, длина змейки и текущие координаты головы.


    1. gchebanov
      12.08.2022 00:59
      +1

      тут 4 бита на ячейку, а так нужно log(n*m).


    1. fire_engel
      12.08.2022 01:38

      можно даже запихнуть координату головы в одну переменную


      1. GennPen
        12.08.2022 02:13

        Да можно еще и длину, и еще чего нть, например переменную цикла обхода клеток(если обычный for используется, а не foreach). Ну а что, как и у автора: те же 4 байта, только не по отдельности по разным переменным, а в одну все запихано.

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


  1. TheCalligrapher
    12.08.2022 01:52
    +7

    #define s_exit(e) do { endwin(); exit(e); } while(0);

    Что это за белиберда?

    Вся идея идиомы do { ... } while(0) в макросах критически основана на том, что в самом макросе ни в коем случае не должно быть ; после while (0). Кто и зачем влепил туда эту ;?

    Если у автора это "работает" в коде, значит ему вообще не нужна была эта идиома. Можно было пользоваться просто парой { ... }. Зачем он слепо вставлял в свои макросы все это do { ... } while(0)?

    Это просто классический пример карго-культа: где-то в чьих-то макросах увидел это do { } while(0) и слепо повторяет, совершенно не понимая, зачем все это делается и как это должно работать.


  1. nickolaym
    12.08.2022 19:18

    Лайк за ненормальное программирование!

    ---

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

    В одной из этих строчек ошибкоопасный код :)

    Вопрос к автору кода, почему. Было лень копипастить, руками набрал и кое-что забыл?