【Atmel XMEGA-A3BU手记】NO！

nemon

除了火山地震洪水泥石流干旱瘟疫，人类基本上在地球上算是称王称霸了，至少一向感觉如此。但是在趾高气扬地凌驾于其他一切物种的表象背后，人们从没有停止过关于地球换老大的担忧，按Discover分析，这个后备老大的名单虽然不长，但种类还挺丰富，有哺乳动物老鼠、还有软体动物章鱼……如果哪天由好莱坞的编剧来续写这个名单，那一张纸就绝对不够了，哥斯拉、机器人、病毒、冰川……还有，很早之前就已经确定的——猩猩。

早在70年代，美国人就开始玩穿越了，说一人穿到了两千年后，发现地球上的人类文明已经衰落，倒是猩猩很兴旺，不仅会说英语，还组织起军队和元老院，准备消灭人类。后来又出了个续集，说那个时代有一对猩猩夫妇，回到了过去，但是人类视其为异类，诛之。

2011年，这个关于猩猩占地球的故事有了开头——20世纪福克斯公司拍摄了前传《猩球崛起》，解答了为什么猩猩能够成为地球主宰的问题：一个为了治疗父亲的阿尔茨海默（大脑退化）病的生物学家威尔‧罗德曼在其供职的公司里发明了一种利用病毒修复大脑的药物“ALZ-112”，在一只雌性猩猩身上做实验，结果猩猩智商大增。

但是这只变聪明的雌性猩猩为了保护幼崽大闹威尔的增资说明会，不仅自己命丧黄泉，也导致了“ALZ-112”计划被撤销。威尔不忍心给这个幼崽注射药物安乐死，把它偷偷带回了家，取名凯撒。由于从母体获得了“ALZ-112”，凯撒的智商进步神速，2岁时就相当于8岁的人类。又过了5年，威尔的父亲开始出现免疫反应对抗“ALZ-112”，阿尔茨海默病更加严重，威尔只好说服公司使用更危险的病毒制造“ALZ-113”希望能挽救自己的父亲。一次，凯撒为了保护和邻居争执的老罗德曼攻击了人类，当时威尔专注于“ALZ-113”，没有刻意罩着凯撒，凯撒被关进了猩猩馆。和一群普通猩猩在一起，受尽管理员欺侮的凯撒最终意识到，作为人类的异类，只有反抗才能获得自由。

于是凯撒用“ALZ-112”把整个猩猩馆的智商提升了，然后带着这群新兵抢劫了“ALZ-113”，把整个曼哈顿的猩猩都“解放”了，并且第一次与人类进行了战斗，击溃了前来屠杀的警察，最后跑进了红杉树林里。影片结束后一道道黄线覆盖全世界，不知是指“ALZ-113”病毒危及了没有抵抗力的人类，还是说凯撒带领的猩猩占领了整个地球？其实都一样，随着凯撒“不！”的一声怒吼，猩球崛起了。

楼主东拉西扯的老毛病又犯了，请大家原谅一下。下面说主题，估计有童鞋早就独具慧眼、目光如炬、聚精会神、神行合一、一针见血、血溅当场的发现了雌猩猩玩的——汉诺塔。

据wiki和baidu说：

最早发明这个问题的人是法国数学家爱德华·卢卡斯。
大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。婆罗门以上述规则移动这些盘子；预言说当这些盘子移动完毕，世界就会灭亡。这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说，还是他受他人启发。
若传说属实，僧侣们需要264 − 1步才能完成这个任务；若他们每秒可完成一个盘子的移动，就需要5846亿年才能完成。整个宇宙现在也不过137亿年。

像电影里猩猩玩的那个4层的塔，应该用2^4-1即15步移完，过程如下所示：

那么在XMEGA-A3BU上如何实现呢？
首先，定义三根柱子，注意每个数组的第一个元素记录的是这根柱子上有几个盘子，或者说最上边的盘子在第几层：

1. unsigned char hanoi_data[3][9]=
   
2. {
   
3.         {8,  8,7,6,5,4,3,2,1},
   
4.         {0,  0,0,0,0,0,0,0,0},
   
5.         {0,  0,0,0,0,0,0,0,0}
   
6. };

复制代码

然后，定义拿着盘子的机械手在第几根柱子上方、机械手里拿着多大的盘子：

1. char hand_position=0;//0,1,2
   
2. char hand_tick=0;//blank

复制代码

之后是拿着盘子的机械手的图像：

1. PROGMEM_DECLARE(gfx_mono_color_t, bitmap_hand_empty_data[8])={OOOOOOOO,OOOOOOOO,OOOOOOOO,OOOOOOOO,OOOOOOOO,OOOOOOOO,OOOOOOOO,OOOOOOOO};
   
2. struct gfx_mono_bitmap bitmap_hand_empty = { .height = 8, .width = 8, .type = GFX_MONO_BITMAP_PROGMEM, .data.progmem = bitmap_hand_empty_data};
   
3. PROGMEM_DECLARE(gfx_mono_color_t, bitmap_hand_atick_data[8])={OlllOOOO,OOOOlOOO,lllOOlll,lllOOlll,lllOOlll,lllOOlll,OOOOlOOO,OlllOOOO};
   
4. struct gfx_mono_bitmap bitmap_hand_atick = { .height = 8, .width = 8, .type = GFX_MONO_BITMAP_PROGMEM, .data.progmem = bitmap_hand_atick_data};
   
5. PROGMEM_DECLARE(gfx_mono_color_t, bitmap_hand_disab_data[8])={OlllOOOO,OOOOlOOO,lOlOOlll,OlOOOlll,OlOOOlll,lOlOOlll,OOOOlOOO,OlllOOOO};
   
6. struct gfx_mono_bitmap bitmap_hand_disab = { .height = 8, .width = 8, .type = GFX_MONO_BITMAP_PROGMEM, .data.progmem = bitmap_hand_disab_data};
   
7. PROGMEM_DECLARE(gfx_mono_color_t, bitmap_hand_enabl_data[8])={OOllOOOO,OlOOlOOO,lOOOOlll,OOOOOlll,OOOOOlll,lOOOOlll,OlOOlOOO,OOllOOOO};
   
8. struct gfx_mono_bitmap bitmap_hand_enabl = { .height = 8, .width = 8, .type = GFX_MONO_BITMAP_PROGMEM, .data.progmem = bitmap_hand_enabl_data};

复制代码

先在excel里定义：

画出来是这样的：

之后，是画机械手的函数，注意需要先擦掉再画：

1. void paintHand(char bar_id,struct gfx_mono_bitmap* type_ptr)
   
2. {
   
3.         gfx_mono_put_bitmap(&bitmap_hand_empty,0*38+29,0);
   
4.         gfx_mono_put_bitmap(&bitmap_hand_empty,1*38+29,0);
   
5.         gfx_mono_put_bitmap(&bitmap_hand_empty,2*38+29,0);
   
6.         
   
7.         
   
8.         gfx_mono_put_bitmap(type_ptr,bar_id*38+29,0);        
   
9. }        

复制代码

画一根竖着的柱子：

1. void paintBar(char bar_id){
   
2.         gfx_mono_generic_draw_filled_rect(bar_id*38+18,0,2,32, GFX_PIXEL_SET);
   
3. }

复制代码

画一个盘子，注意使用的颜色是GFX_PIXEL_XOR，这样擦除和画新的可以用相同函数，还可以使柱子反显：

1. void paintTick(char bar_id,char level_id){
   
2.         gfx_mono_generic_draw_filled_rect(bar_id*38+(1+(8-hanoi_data[bar_id][level_id])*2),(8-level_id)*4+1,hanoi_data[bar_id][level_id]*4+4,3, GFX_PIXEL_XOR);
   
3. }

复制代码

柱子和盘子结合起来就会是这样的效果：

游戏初始化：

1. void init_game(void)
   
2. {
   
3.         int i;
   
4.         gfx_mono_draw_filled_rect(0, 0, 128, 32, GFX_PIXEL_CLR);
   
5.         
   
6.         paintBar(0);
   
7.         paintBar(1);
   
8.         paintBar(2);
   
9.         
   
10.         for(i=1;i<=8;i++)
    
11.         {
    
12.                 hanoi_data[0][i]=9-i;
    
13.                 paintTick(0,i);
    
14.                 hanoi_data[1][i]=0;
    
15.                 hanoi_data[2][i]=0;
    
16.         }
    
17.         hanoi_data[0][0]=8;
    
18.         hanoi_data[1][0]=0;
    
19.         hanoi_data[2][0]=0;
    
20. 
    
21.         hand_position=0;//0,1,2
    
22.         hand_tick=0;//blank
    
23.         
    
24.         paintHand(hand_position,&bitmap_hand_enabl);
    
25. }

复制代码

处理上下左右键：

1. static void when_key_up(void)
   
2. {
   
3.         if(0==hand_tick && 0!=hanoi_data[hand_position][hanoi_data[hand_position][0]])
   
4.         {
   
5.                 paintTick(hand_position,hanoi_data[hand_position][0]);
   
6.                 //pikup
   
7.                 hand_tick=hanoi_data[hand_position][hanoi_data[hand_position][0]];
   
8.                 hanoi_data[hand_position][hanoi_data[hand_position][0]]=0;
   
9.                 hanoi_data[hand_position][0]-=1;
   
10.                 //redraw
    
11.                 paintHand(hand_position,&bitmap_hand_atick);
    
12.                 gfx_mono_draw_char('0'+hand_tick,120,8,&sysfont);
    
13.         }
    
14. }
    
15. static void when_key_down(void)
    
16. {
    
17.         if(0!=hand_tick && (0==hanoi_data[hand_position][0] || hand_tick<hanoi_data[hand_position][hanoi_data[hand_position][0]] ))
    
18.         {
    
19.                 //putdown
    
20.                 hanoi_data[hand_position][0]+=1;
    
21.                 hanoi_data[hand_position][hanoi_data[hand_position][0]]=hand_tick;
    
22.                 hand_tick=0;
    
23.                 //redraw
    
24.                 paintTick(hand_position,hanoi_data[hand_position][0]);
    
25.                 paintHand(hand_position,&bitmap_hand_enabl);
    
26.                 gfx_mono_draw_char(' ',120,8,&sysfont);
    
27.         }}
    
28. static void when_key_left(void)
    
29. {
    
30.         //change position to new bar
    
31.         hand_position=(0==hand_position)?2:hand_position-1;
    
32.         //draw hand
    
33.         if(0==hand_tick)
    
34.         {
    
35.                 paintHand(hand_position,&bitmap_hand_enabl);
    
36.         }
    
37.         else
    
38.         {
    
39.                 if(hand_tick<hanoi_data[hand_position][hanoi_data[hand_position][0]])
    
40.                 {
    
41.                         paintHand(hand_position,&bitmap_hand_atick);
    
42.                 }
    
43.                 else
    
44.                 {
    
45.                         paintHand(hand_position,&bitmap_hand_disab);
    
46.                 }
    
47.         }
    
48. }
    
49. static void when_key_right(void)
    
50. {
    
51.         //change position to new bar
    
52.         hand_position=(2==hand_position)?0:hand_position+1;
    
53.         //draw hand
    
54.         if(0==hand_tick)
    
55.         {
    
56.                 paintHand(hand_position,&bitmap_hand_enabl);
    
57.         }
    
58.         else
    
59.         {
    
60.                 if(0==hanoi_data[hand_position][0] || hand_tick<hanoi_data[hand_position][hanoi_data[hand_position][0]] )
    
61.                 {
    
62.                         paintHand(hand_position,&bitmap_hand_atick);
    
63.                 }
    
64.                 else
    
65.                 {
    
66.                         paintHand(hand_position,&bitmap_hand_disab);
    
67.                 }
    
68.         }
    
69. }

复制代码

检查游戏是否结束，只需看第三根柱子的第8层是否是1号盘子，方法狡猾吧？

1. char check_game(void)
   
2. {
   
3.         if(1==hanoi_data[2][8])
   
4.         {
   
5.                 return 1;
   
6.         }
   
7.         else
   
8.         {
   
9.                 return 0;
   
10.         }        
    
11. }

复制代码

下面是主函数，由于逻辑都分担出去了，所以很简单：

1. void game_3_Hanoi (void)
   
2. {
   
3.         struct keyboard_event input;
   
4.         init_game();
   
5.         while(1)
   
6.         {
   
7.                 do {
   
8.                         //exit when 5th button pressed
   
9.                         if( get_lightsensor_value()<100)
   
10.                         {
    
11.                                 return;
    
12.                         }
    
13.                         //exit when game passed
    
14.                         if(1==check_game())
    
15.                         {
    
16.                                 gfx_mono_draw_filled_rect(0, 0, 128, 32, GFX_PIXEL_CLR);
    
17.                                 gfx_mono_draw_string("YOU WIN !", 8, 16, &sysfont);
    
18.                                 delay_ms(1000);
    
19.                                 return;
    
20.                         }
    
21.                        
    
22.                         keyboard_get_key_state(&input);
    
23.                         // Wait for key release
    
24.                 } while (input.type != KEYBOARD_RELEASE);
    
25. 
    
26.                 switch (input.keycode)
    
27.                 {
    
28.                         case BTN_GO_LEFT:
    
29.                         when_key_left();
    
30.                         break;
    
31. 
    
32.                         case BTN_GO_UP:
    
33.                         when_key_up();
    
34.                         break;
    
35. 
    
36.                         case BTN_GO_DOWN:
    
37.                         when_key_down();
    
38.                         break;
    
39. 
    
40.                         case BTN_GO_RIGHT:
    
41.                         when_key_right();
    
42.                         break;
    
43. 
    
44.                         default:
    
45.                        
    
46.                         break;
    
47.                 }
    
48.         }
    
49. }

复制代码

下面视频：


刚才提到过，n层盘子要经过2^n-1个步骤，那么8层盘子需要255步，加入1步用1秒，也就4分多钟。虽然用时不是很长，不过鉴于即使楼主没有猩猩聪明，地球也暂时不会换老大，我就不把这个游戏玩到最后了。有不同意见的童鞋可以吱一声，如果着急的话可以多吱几声，就像这样——吱，吱吱，吱吱吱吱……

Hayasaky

这是个数学达人啊

小马哈

佩服，佩服，真有闲心来研究这些东西。