• 用四个整数编写一个贪吃蛇游戏

    作者 | Andrei Cioban

    译者 | 弯月

    出品 | CSDN（ID：CSDNnews）

    b63844a16c01216d4011bc0891ee5423.gif

    记得上次编写贪吃蛇游戏还是很多年以前的事，如今我打算尽己所能，在一些很特别的方面做到极致：

    • 将游戏的地图保存到一个uint32_t中，其中的1表示蛇的身体。因此整个地图包括4x8个位置。

    • 用另一个unit64_t作为方向数组，这样可以实现蛇的移动，还可以保持不断增长的身体的位置。

    • 在另一个uint32_t中使用几个5比特数据来保存head（蛇头）、tail（蛇尾）、apple（苹果）和length（当前长度）。还有两个比特用来保存键盘输入。

    • 用一个8比特变量（uint8_t）作为循环变量。

    因为标准C没有提供键盘交互功能，因此必须依赖于curses，所以如果你想编译该程序，请确保计算机上安装了该库。如果你使用的是正确的操作系统，很可能curses已经存在了。如若不然，你可以使用任何包管理器进行安装。

    不幸的是，curses本身需要消耗内存，但毕竟处理各种转义字符和底层函数很麻烦，我不想自己实现。这种做法也许有点算作弊。

    在阅读本文之前，请记住文中的代码仅供娱乐，只是一个练习。出于前面提到的限制，本文会编写大量晦涩的宏来进行位操作，还会使用全局变量、重复使用同一个计数器，等等。这些都不是易读代码的最佳实践。

    代码

    完整的代码，请参见GitHub：

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

    编译和运行：

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

    内存布局

    首先定义4个整数，用于保存所有游戏数据：

    uint32_t map = ...;

    uint32_t vars = ...;

    uint64_t shape = ...;

    int8_t i = ...;    

    map

    map变量负责屏幕显示。map变量有32比特，利用curses渲染成4x8的方格：

    8af78723012ed017664a43adaab62d78.png

    访问每个比特并设置0或1，需要使用下面的宏：

    1. #define s_is_set(b) ((map&(1<<(b)))!=0) // checks if the b bit from the map is set to 1
    2. #define s_tog(b) (map^=(1<<(b))) // toggles the b bit of the map (currently not used)
    3. #define s_set_0(b) (map&=~(1<<b)) // sets to 0 the b bit from the map
    4. #define s_set_1(b) (map|=(1<<b)) // sets to 1 the b bit from the map

    vars

    vars是一个32位整数，用于保存下面的数据：

    17a623f54e72461551f76a0fb77056b1.png

    • hpos （比特0~4）表示蛇头的位置，表示为从map的最低位开始的偏移量；

    • tpos（比特5~9）表示蛇尾的位置，表示为从map的最低位开始的偏移量；

    • len（比特10~14）表示蛇的长度；

    • apos（比特15~19）表示苹果的位置，表示为从map的最低位开始的偏移量；

    • chdir（比特20~21）表示表示最后一次按下的键，2个比特足够了，因为只需要四个方向键；

    • 其余的比特没有使用。我们也可以把循环计数器的uint8_t放在这儿，但为了简单起见，我还是使用了单独的变量。

    我们定义了以下的宏来访问hpos、hpos等。这些宏就像是针对每个段的getter/setter一样。

    1. #define s_mask(start,len) (s_ls_bits(len)<<(start)) // creates a bitmask of len starting from position start
    2. #define s_prep(y,start,len) (((y)&s_ls_bits(len))<<(start)) // prepares the mask
    3.  
    4.  
    5. // Gets the the 'len' number of bits, starting from position 'start' of 'y'
    6. #define s_get(y,start,len) (((y)>>(start))&s_ls_bits(len)) 
    7. // Sets the the 'len' number of bits, starting from position 'start' of 'y' to the value 'bf'
    8. #define s_set(x,bf,start,len) (x=((x)&~s_mask(start,len))|s_prep(bf,start,len))
    9.  
    10.  
    11. #define s_hpos s_get(vars,0,5) // gets the last 5 bits of 'vars', which corresponds to s_hpos
    12. #define s_tpos s_get(vars,5,5) // sets the last 5 bits of 'vars', which corresonds to s_hpos
    13. #define s_len s_get(vars,10,5)
    14. #define s_apos s_get(vars,15,5)
    15. #define s_chdir s_get(vars,20,2)
    16. #define s_hpos_set(pos) s_set(vars,pos,0,5)
    17. #define s_tpos_set(pos) s_set(vars,pos,5,5)
    18. #define s_len_set(len) s_set(vars,len,10,5)
    19. #define s_apos_set(app) s_set(vars,app,15,5)
    20. #define s_chdir_set(cdir) s_set(vars,cdir,20,2)
    21. #define s_len_inc s_len_set(s_len+1)

    更多有关宏背后的技巧，请参见这篇文章：https://www.coranac.com/documents/working-with-bits-and-bitfields/

    shape

    shape用来保存蛇的每一节的方向。每个方向2比特就足够了，所以一共可以保存32个方向：

    e39502992bca6d6d677cca34eb62b81f.png

    方向的意义用下面的宏表示：

    1. #define SU 0 //UP                       
    2. #define SD 1 //DOWN                  
    3. #define SL 2 //LEFT                
    4. #define SR 3 //RIGHT

    每次蛇在map的方格中移动时，我们需要使用下述宏循环这些方向：

    1. #define s_hdir ((shape>>(s_len*2)&3)) // retrieves the head direction (based on s_slen)
    2. #define s_tdir (shape&3) // retrieves the last 2 bits which corresponds to the tail
    3. #define s_hdir_set(d) s_set(shape,d,s_len*2,2) // sets the head direction
    4. #define s_tdir_set(d) s_set(shape,d,0,2) // sets the tail direction 
    5. // Macros for changing the shape each time the snake moves
    6. #define s_shape_rot(nd) do { shape>>=2; s_hdir_set(nd); } while(0); 
    7. #define s_shape_add(nd) do { s_len_inc; shape<<=2; s_tdir_set(nd); } while(0);

    当蛇移动且没有吃掉苹果时，我们调用s_shape_rot宏，删除最后一个方向，然后添加一个新的蛇头（根据s_chdir）。

    这么看来，蛇的行为有点像队列：

    58dc1f573e31c8d3f5c3222a7ea8d64d.png

    当蛇移动并吃掉一个苹果时，我们调用s_shape_add，仅增加长度，并添加一个新的蛇尾s_tdir。

    主循环

    主循环如下所示。

    1. // Some macros to make the code more readable
    2. // (or unreadable depending on you)
    3. #define s_init do { srand(time(0)); initscr(); keypad(stdscr, TRUE); cbreak(); noecho(); } while(0);
    4. #define s_exit(e) do { endwin(); exit(e); } while(0);
    5. #define s_key_press(k1, k2) if (s_hdir==k2) break; s_chdir_set(k1); break;
    6.  
    7.  
    8. int main(void) {
    9.     s_init; // initialize the curses context
    10.     rnd_apple(); // creates a random position for the apple
    11.     while(1) {
    12.         show_map(); // renders the map on screen
    13.         timeout(80); // getch() timeouts after waiting for user input
    14.         switch (getch()) {
    15.             case KEY_UP : { s_key_press(SU, SD) }; 
    16.             case KEY_DOWN : { s_key_press(SD, SU) };
    17.             case KEY_LEFT : { s_key_press(SL, SR) };
    18.             case KEY_RIGHT : { s_key_press(SR, SL) };
    19.             case 'q' : exit(0); // Quits the game
    20.         }
    21.         move_snake(); // The snake moves inside the grid
    22.         s_shape_rot(s_chdir); // The shape is getting updated
    23.         napms(200); // frame rate :))
    24.     }
    25.     s_exit(0); // games exits
    26. }

    每当某个键按下时，就展开s_key_press，检查移动是否允许，然后更新s_chdir（使用s_chdir_set）。

    s_key_press有两个输入参数的作用是去除相反方向。例如，如果蛇当前向右移动（SR），那么SL就是不可能的输入，从而中断switch语句。

    移动蛇的函数

    move_snake()中实现了大部分逻辑：

    1. #define s_next_l s_mask5(s_hpos+1) // incrementing the offset to go right
    2. #define s_next_r s_mask5(s_hpos-1) // decrementing the offset to go left
    3. #define s_next_u s_mask5(s_hpos+8) // change row up, by adding 8 positions to the offset
    4. #define s_next_d s_mask5(s_hpos-8) // change row down, by removing 8 positions from the offset
    5.  
    6.  
    7. // Check if a left movement is possible. 
    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); }
    9. // Check if a right movement is possible. 
    10. 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); }
    11. // Check if a up movement is possible
    12. static void check_u() { if ((s_next_u < s_hpos) || s_is_set(s_next_u)) s_exit(-1); }
    13. // Check if a down movement is possible
    14. static void check_d() { if ((s_next_d > s_hpos) || s_is_set(s_next_d)) s_exit(-1); }
    15. static void move_snake() {
    16.     if (s_hdir==SL) { check_l(); s_hpos_set(s_hpos+1); } 
    17.     else if (s_hdir==SR) { check_r(); s_hpos_set(s_hpos-1); } 
    18.     else if (s_hdir==SU) { check_u(); s_hpos_set(s_hpos+8); }
    19.     else if (s_hdir==SD) { check_d(); s_hpos_set(s_hpos-8); }
    20.     // Sets the bit based on the current s_hdir and s_hpos
    21.     s_set_1(s_hpos);
    22.     // If an apple is eaten
    23.     if (s_apos==s_hpos) {
    24.         // We generate another apple so we don't starve
    25.         rnd_apple();
    26.         // Append to the tail
    27.         s_shape_add(s_tdir);
    28.         // We stop clearning the tail bit
    29.         return;
    30.     }
    31.     // Clear the tail bit
    32.     s_set_0(s_tpos);
    33.     // Update the t_pos so we can clear the next tail bit when the snake moves
    34.     if (s_tdir==SL) { s_tpos_set(s_tpos+1); } 
    35.     else if (s_tdir==SR) { s_tpos_set(s_tpos-1); } 
    36.     else if (s_tdir==SU) { s_tpos_set(s_tpos+8); } 
    37.     else if (s_tdir==SD) { s_tpos_set(s_tpos-8); }
    38. }

    为了验证蛇是否可以在方格中移动，我们实现了check_*()函数：

    • check_l()检查蛇的X坐标（s_hpos % 8）是否大于上一个位置的X坐标；

    • check_r()检查蛇的X坐标（s_hpos % 8）是否小于上一个位置的X坐标；

    • check_u()和check_d()的原理相同，检查增加s_hpos是否会导致溢出。如果溢出，表明移动超出了方格边界。这里溢出当做一个特性使用。

    显示蛇的函数

    这是需要实现的最后一个函数：

    1. static void show_map() {
    2.     clear();
    3.     i=32;
    4.     while(i-->0) { // !! Trigger warning for sensitive people, incoming '-->0'
    5.         // If the bit is an apple, we render the apple '@'
    6.         if (i==s_apos) { addch('@'); addch(' '); }
    7.         // We draw either the snake bit ('#') or the empty bit ('.')
    8.         else { addch(s_is_set(i) ? '#':'.'); addch(' '); }
    9.         // We construct the grid by inserting a new line
    10.         if (!s_mod_p2(i,8)) { addch('\n'); }
    11.     };
    12. }

    宏展开之后

    所有宏展开之后，代码如下所示：

    1. uint32_t map = 0x700;
    2. uint32_t vars = 0x20090a;
    3. uint64_t shape = 0x2a;
    4. int8_t i = 0;
    5. static void rnd_apple() {
    6.     i = (rand()&(32 -1));
    7.     while(((map&(1<<(i)))!=0)) i = (rand()&(32 -1));
    8.     (vars=((vars)&~(((1<<(5))-1)<<(15)))|(((i)&((1<<(5))-1))<<(15)));
    9. }
    10. static void show_map() {
    11.     wclear(stdscr);
    12.     i=32;
    13.     while(i-->0) {
    14.         if (i==(((vars)>>(15))&((1<<(5))-1))) { waddch(stdscr,'@'); waddch(stdscr,' '); }
    15.         else { waddch(stdscr,((map&(1<<(i)))!=0) ? '#':'.'); waddch(stdscr,' '); }
    16.         if (!(i&(8 -1))) { waddch(stdscr,'\n'); }
    17.     };
    18. }
    19. 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);; }
    20. 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);; }
    21. 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);; }
    22. 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);; }
    23. static void move_snake() {
    24.     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))); }
    25.     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))); }
    26.     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))); }
    27.     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))); }
    28.     (map|=(1<<(((vars)>>(0))&((1<<(5))-1))));
    29.     if ((((vars)>>(15))&((1<<(5))-1))==(((vars)>>(0))&((1<<(5))-1))) {
    30.         rnd_apple();
    31.         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);;
    32.         return;
    33.     }
    34.     (map&=~(1<<(((vars)>>(5))&((1<<(5))-1))));
    35.     if ((shape&3)==2) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))+1)&((1<<(5))-1))<<(5))); }
    36.     else if ((shape&3)==3) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))-1)&((1<<(5))-1))<<(5))); }
    37.     else if ((shape&3)==0) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))+8)&((1<<(5))-1))<<(5))); }
    38.     else if ((shape&3)==1) { (vars=((vars)&~(((1<<(5))-1)<<(5)))|((((((vars)>>(5))&((1<<(5))-1))-8)&((1<<(5))-1))<<(5))); }
    39. }
    40.  
    41.  
    42.  
    43.  
    44. int main(void) {
    45.     do { srand(time(0)); initscr(); keypad(stdscr, 1); cbreak(); noecho(); } while(0);;
    46.     rnd_apple();
    47.     while(1) {
    48.         show_map();
    49.         wtimeout(stdscr,80);
    50.         switch (wgetch(stdscr)) {
    51.             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; };
    52.             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; };
    53.             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; };
    54.             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; };
    55.             case 'q' : exit(0);
    56.         }
    57.         move_snake();
    58.         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);;
    59.         napms(200);
    60.     }
    61.     do { endwin(); exit(0); } while(0);;
    62. }

    上述代码非常难懂，上下滚动屏幕甚至会感到头晕。

    感想

    这个练习很有趣。完整的代码在此（https://github.com/nomemory/integers-snake/blob/main/snake.c），大约100行，只用了四个整数。

    如果在你的终端上蛇跑得太快，可以尝试增加s_napms。

    *本文由CSDN翻译，未经授权，禁止转载。

    原文链接：https://www.andreinc.net/2022/05/01/4-integers-are-enough-to-write-a-snake-game

  • 相关阅读:
    《2023中国企业数智化转型升级服务全景图/产业图谱2.0版》重磅发布
    猿创征文 |【算法面试入门必刷】动态规划-线性dp（三）
    【我是产品经理_注册安全分析报告】
    从指针开始变强(三）之超级详细运算题
    为什么Java能够称霸移动开发领域这么多年？
    【ACM】前言（1）
    Docker常见面试题整理
    intellij plugin(插件)的项目解析及研读
    MongoDB聚合运算符：$covarianceSamp
    easyexcel导入导出百万条数据思路分析
  • 原文地址：https://blog.csdn.net/csdnnews/article/details/125093329