前言这两天在网上看到一张让人涨姿势的图片，图片中展示的是贪吃蛇游戏， 估计大部分人都玩过。但如果仅仅是贪吃蛇游戏，那么它就没有什么让人涨姿势的地方了。 问题的关键在于，图片中的贪吃蛇真的很贪吃XD，它把矩形中出现的食物吃了个遍， 然后华丽丽地把整个矩形填满，真心是看得赏心悦目。作为一个CSer， 第一个想到的是，这东西是写程序实现的(因为，一般人干不出这事。 果断是要让程序来干的)第二个想到的是，写程序该如何实现，该用什么算法？ 既然开始想了，就开始做。因为Talk is cheap，要show me the code才行。 (从耗子叔那学来的)开始之前，让我们再欣赏一下那只让人涨姿势的贪吃蛇吧：( 如果下面的动态图片浏览效果不佳的话，可以右键保存下来查看)语言选择Life is short, use python! 所以，根本就没多想，直接上python。最初版本先让你的程序跑起来首先，我们第一件要做的就是先不要去分析这个问题。 你好歹先写个能运行起来的贪吃蛇游戏，然后再去想AI部分。这个应该很简单， c\c++也就百来行代码(如果我没记错的话。不弄复杂界面，直接在控制台下跑)， python就更简单了，去掉注释和空行，5、60行代码就搞定了。而且，最最关键的， 这个东西网上肯定写滥了，你没有必要重复造轮子， 去弄一份来按照你的意愿改造一下就行了。简单版本我觉得直接写perfect版本不是什么好路子。因为perfect版本往往要考虑很多东西， 直接上来就写这个一般是bug百出的。所以， 一开始我的目标仅仅是让程序去控制贪吃蛇运动，让它去吃食物，仅此而已。 现在让我们来陈述一下最初的问题：在一个矩形中，每一时刻有一个食物，贪吃蛇要在不撞到自己的条件下，
找到一条路(未必要最优)，然后沿着这条路运行，去享用它的美食我们先不去想蛇会越来越长这个事实，问题基本就是，给你一个起点(蛇头)和一个终点( 食物)，要避开障碍物(蛇身)，从起点找到一条可行路到达终点。 我们可以用的方法有：BFSDFSA*只要有选择，就先选择最简单的方案，我们现在的目标是要让程序先跑起来， 优化是后话。so，从BFS开始。我们最初将蛇头位置放入队列，然后只要队列非空， 就将队头位置出队，然后把它四领域内的4个点放入队列，不断地循环操作， 直到到达食物的位置。这个过程中，我们需要注意几点：1.访问过的点不再访问。 2.保存每个点的父结点(即每个位置是从哪个位置走到它的， 这样我们才能把可行路径找出来)。3.蛇身所在位置和四面墙不可访问。通过BFS找到食物后，只需要让蛇沿着可行路径运动即可。这个简单版本写完后， 贪吃蛇就可以很欢快地运行一段时间了。看图吧：(不流畅的感觉来自录屏软件＠_＠)为了尽量保持简单，我用的是curses模块，直接在终端进行绘图。 从上面的动态图片可以看出，每次都单纯地使用BFS，最终有一天， 贪吃蛇会因为这种不顾后果的短视行为而陷入困境。 而且，即使到了那个时候，它也只会BFS一种策略， 导致因为当前看不到目标(食物)，认为自己这辈子就这样了，破罐子破摔， 最终停在它人生中的某一个点，不再前进。(我好爱讲哲理XD)BFS+Wander上一节的简单版本跑起来后，我们认识到，只教贪吃蛇一种策略是不行的。 它这么笨一条蛇，你不多教它一点，它分分钟就会挂掉的。 所以，我写了个Wander函数，顾名思义，当贪吃蛇陷入困境后， 就别让它再BFS了，而是让它随便四处走走，散散心，思考一下人生什么的。 这个就好比你困惑迷茫的时候还去工作，效率不佳不说，还可能阻碍你走出困境； 相反，这时候你如果放下手中的工作，停下来，出去旅个游什么的。回来时， 说不定就豁然开朗，土地平旷，屋舍俨然了。Wander函数怎么写都行，但是肯定有优劣之分。我写了两个版本，一个是在可行的范围内， 朝随机方向走随机步。也就是说，蛇每次运动的方向是随机出来的， 总共运动的步数也是随机的。Wander完之后，再去BFS一下，看能否吃到食物， 如果可以那就皆大欢喜了。如果不行，说明思考人生的时间还不够，再Wander一下。 这样过程不断地循环进行。可是就像“随机过程随机过”一样，你“随机Wander就随机挂”。 会Wander的蛇确实能多走好多步。可是有一天，它就会把自己给随机到一条死路上了。 陷入困境还可以Wander，进入死胡同，那可没有回滚机制。所以， 第二个版本的Wander函数，我就让贪吃蛇贪到底。在BFS无解后， 告诉蛇一个步数step(随机产生step)，让它在空白区域以S形运动step步。 这回运动方向就不随机了，而是有组织有纪律地运动。先看图，然后再说说它的问题：没错，最终还是挂掉了。S形运动也是无法让贪吃蛇避免死亡的命运。 贪吃蛇可以靠S形运动多存活一段时间，可是由于它的策略是：问题就出在蛇发现它自己和食物间有路径，就二话不说跑去吃食物了。 它没有考虑到，你这一去把食物给吃了后形成的局势(蛇身布局)， 完全就可能让你挂掉。(比如进入了一个自己蛇身围起来的封闭小空间)so，为了能让蛇活得久一些，它还要更高瞻远瞩才行。高瞻远瞩版本我们现在已经有了一个比较低端的版本，而且对问题的认识也稍微深入了一些。 现在可以进行一些比较慎密和严谨的分析了。首先，让我们罗列一些问题： (像头脑风暴那样，想到什么就写下来即可)蛇和食物间有路径直接就去吃，不可取。那该怎么办？如果蛇去吃食物后，布局是安全的，是否就直接去吃？(这样最优吗？)怎样定义布局是否安全？蛇和食物之间如果没有路径，怎么办？最短路径是否最优？(这个明显不是了)那么，如果布局安全的情况下，最短路径是否最优？除了最短路径，我们还可以怎么走？S形？最长？怎么应对蛇身越来越长这个问题？食物是随机出现的，有没可能出现无解的布局？暴力法(brute force)能否得到最优序列？(让贪吃蛇尽可能地多吃食物)只要去想，问题还挺多的。这时让我们以面向过程的思想，带着上面的问题， 把思路理一理。一开始，蛇很短(初始化长度为1)，它看到了一个食物， 使用BFS得到矩形中每个位置到达食物的最短路径长度。在没有蛇身阻挡下， 就是曼哈顿距离。然后，我要先判断一下，贪吃蛇这一去是否安全。 所以我需要一条虚拟的蛇，它每次负责去探路。如果安全，才让真正的蛇去跑。 当然，虚拟的蛇是不会绘制出来的，它只负责模拟探路。那么， 怎么定义一个布局是安全的呢？ 如果你把文章开头那张动态图片中蛇的销魂走位好好的看一下， 会发现即使到最后蛇身已经很长了，它仍然没事一般地走出了一条路。而且， 是跟着蛇尾走的！嗯，这个其实不难解释，蛇在运动的过程中，消耗蛇身， 蛇尾后面总是不断地出现新的空间。蛇短的时候还无所谓，当蛇一长， 就会发现，要想活下来，基本就只能追着蛇尾跑了。在追着蛇尾跑的过程中， 再去考虑能否安全地吃到食物。(下图是某次BFS后，得到的一个布局， 0代表食物，数字代表该位置到达食物的距离，+号代表蛇头，*号代表蛇身， -号代表蛇尾，#号代表空格，外面的一圈#号代表围墙)经过上面的分析，我们可以将布局是否安全定义为蛇是否可以跟着蛇尾运动， 也就是蛇吃完食物后，蛇头和蛇尾间是否存在路径，如果存在，我就认为是安全的。OK，继续。真蛇派出虚拟蛇去探路后，发现吃完食物后的布局是安全的。那么， 真蛇就直奔食物了。等等，这样的策略好吗？未必。因为蛇每运动一步， 布局就变化一次。布局一变就意味着可能存在更优解。比如因为蛇尾的消耗， 原本需要绕路才能吃到的食物，突然就出现在蛇眼前了。所以，真蛇走一步后， 更好的做法是，重新做BFS。然后和上面一样进行安全判断，然后再走。接下来我们来考虑一下，如果蛇和食物之间不存在路径怎么办？ 上文其实已经提到了做法了，跟着蛇尾走。只要蛇和食物间不存在路径， 蛇就一直跟着蛇尾走。同样的，由于每走一步布局就会改变， 所以每走一步就重新做BFS得到最新布局。好了，问题又来了。如果蛇和食物间不存在路径且蛇和蛇尾间也不存在路径， 怎么办？这个我是没办法了，选一步可行的路径来走就是了。还是一个道理， 每次只走一步，更新布局，然后再判断蛇和食物间是否有安全路径； 没有的话，蛇头和蛇尾间是否存在路径；还没有，再挑一步可行的来走。上面列的好几个问题里都涉及到蛇的行走策略，一般而言， 我们会让蛇每次都走最短路径。这是针对蛇去吃食物的时候， 可是蛇在追自己的尾巴的时候就不能这么考虑了。我们希望的是蛇头在追蛇尾的过程中， 尽可能地慢。这样蛇头和蛇尾间才能腾出更多的空间，空间多才有得发展。 所以蛇的行走策略主要分为两种：1. 目标是食物时，走最短路径
2. 目标是蛇尾时，走最长路径那第三种情况呢？与食物和蛇尾都没路径存在的情况下， 这个时候本来就只是挑一步可行的步子来走，最短最长关系都不大了。 至于人为地让蛇走S形，我觉得这不是什么好策略，最初版本中已经分析过它的问题了。 (当然，除非你想使用最最无懈可击的那个版本，就是完全不管食物， 让蛇一直走S，然后在墙边留下一条过道即可。这样一来， 蛇总是可以完美地把所有食物吃完，然后占满整个空间，可是就很boring了。 没有任何的意思)上面还提到一个问题：因为食物是随机出现的，有没可能出现无解的局面？ 答案是：有。我运行了程序，然后把每一次布局都输出到log，发现会有这样的情况：其中，+号是蛇头，-号是蛇尾，*号是蛇身，0是食物，#号代表空格，外面一圈# 号代表墙。这个布局上，食物已经在蛇头面前了，可是它能吃吗？不能！ 因为它吃完食物后，长度加1，蛇头就会把0的位置填上，布局就变成：此时，由于蛇的长度加1，蛇尾没有动，而蛇头被自己围着，挂掉了。可是， 我们却还有一个空白的格子#没有填充。按照我们之前教给蛇的策略， 面对这种情况，蛇头就只会一直追着蛇尾跑，每当它和食物有路径时， 它让虚拟的蛇跑一遍发现，得到的新布局是不安全的，所以不会去吃食物， 而是选择继续追着蛇尾跑。然后它就这样一直跑，一直跑。死循环， 直到你按ESC键为止。由于食物是随机出现的，所以有可能出现上面这种无解的布局。当然了， 你也可以得到完满的结局，贪吃蛇把整个矩形都填充满。上面的最后一个问题，暴力法是否能得到最优序列。从上面的分析看来， 可以得到，但不能保证一定得到。最后，看看高瞻远瞩的蛇是怎么跑的吧：矩形大小10*20，除去外面的边框，也就是8*18。Linux下录完屏再转成GIF格式的图片， 优化前40多M，真心是没法和Windows的比。用下面的命令优化时， 有一种系统在用生命做优化的感觉：最后还是拿到Windows下用AE，三下五除二用图片序列合成的动态图片 (记得要在format options里选looping，不然图片是不会循环播放的)Last but not least另外，本文的贪吃蛇程序使用了curses模块， 类Unix系统都默认安装的，使用Windows的童鞋需要安装一下这个模块。以上的代码仍然可以继续改进(现在加注释不到300行，优化一下可以更少)， 也可用pygame或是pyglet库把界面做得更加漂亮，Enjoy！

这段代码使用了嵌套的for循环来判断2到9之间的每一个整数是否是质数（只能被1和本身整除的整数）。代码的具体执行过程如下：首先，从2开始循环到9，循环变量为num。这个循环使用了Python内置的range函数，其中参数2表示起始数字，10表示终止数字（不包含），步长默认为1。所以循环会遍历2, 3, 4, 5, 6, 7, 8, 9这些数字。在每一轮循环中，先判断num是否大于1。因为1不是质数，所以小于等于1的数字都不用判断了。如果num小于等于1，则跳过后面的循环，进入下一轮。如果num大于1，则进入第二个for循环。在这个循环中，从2到num-1遍历每一个数字，循环变量为i。在每一轮循环中，判断num是否能被i整除。如果可以整除，则说明num不是质数，退出循环（这里使用了break语句）。如果不能整除，继续下一轮循环，直到循环结束。如果第二个for循环正常结束（即没有被break语句中断），则说明num是质数，打印出来。这里使用了Python的else语句，它和if语句一样，是Python中的控制流语句，不同的是，else语句在if语句条件不成立时执行，而在for循环没有被break语句中断时执行。循环继续，遍历下一个数字，直到9这个数字结束。最终输出结果为2,3,5,7这几个质数，其中end参数指定了输出的结尾符号，这里使用了逗号。

前几章讨论了如何对 Python 进行扩展，也就是如何用 C 函数库 扩展 Python 的功能。反过来也是可以的：将 Python 嵌入到 C/C++ 应用程序中丰富其功能。这种嵌入可以让应用程序用 Python 来实现某些功能，而不是用 C 或 C++ 。用途会有很多；比如允许用户用 Python 编写一些脚本，以便定制应用程序满足需求。如果某些功能用 Python 编写起来更为容易，那么开发人员自己也能这么干。Python 的嵌入类似于扩展，但不完全相同。不同之处在于，扩展 Python 时应用程序的主程序仍然是 Python 解释器，而嵌入 Python 时的主程序可能与 Python 完全无关——而是应用程序的某些部分偶尔会调用 Python 解释器来运行一些 Python 代码。因此，若要嵌入 Python，就要提供自己的主程序。此主程序要做的事情之一就是初始化 Python 解释器。至少得调用函数 Py_Initialize()。还有些可选的调用可向 Python 传递命令行参数。之后即可从应用程序的任何地方调用解释器了。调用解释器的方式有好几种：可向 PyRun_SimpleString() 传入一个包含 Python 语句的字符串，也可向 PyRun_SimpleFile() 传入一个 stdio 文件指针和一个文件名（仅在错误信息中起到识别作用）。还可以调用前面介绍过的底层操作来构造并使用 Python 对象。1.1. 高层次的嵌入最简单的 Python 嵌入形式就是采用非常高层的接口。该接口的目标是只执行一段 Python 脚本，而无需与应用程序直接交互。比如以下代码可以用来对某个文件进行一些操作。#define PY_SSIZE_T_CLEAN
#include <Python.h>
int
main(int argc, char *argv[])
{
wchar_t *program = Py_DecodeLocale(argv[0], NULL);
if (program == NULL) {
fprintf(stderr, "Fatal error: cannot decode argv[0]\n");
exit(1);
}
Py_SetProgramName(program);
/* optional but recommended */
Py_Initialize();
PyRun_SimpleString("from time import time,ctime\n"
"print('Today is', ctime(time()))\n");
if (Py_FinalizeEx() < 0) {
exit(120);
}
PyMem_RawFree(program);
return 0;
}
在 Py_Initialize() 之前，应该先调用 Py_SetProgramName() 函数，以便向解释器告知 Python运行库的路径。接下来，Py_Initialize()
会初始化 Python 解释器，然后执行硬编码的 Python 脚本，打印出日期和时间。之后，调用 Py_FinalizeEx() 关闭解释器，程序结束。在真实的程序中，可能需要从其他来源获取 Python 脚本，或许是从文本编辑器例程、文件，或者某个数据库。利用 PyRun_SimpleFile() 函数可以更好地从文件中获取 Python 代码，可省去分配内存空间和加载文件内容的麻烦。1.2. 突破高层次嵌入的限制：概述高级接口能从应用程序中执行任何 Python 代码，但至少交换数据可说是相当麻烦的。如若需要交换数据，应使用较低级别的调用。几乎可以实现任何功能，代价是得写更多的 C 代码。应该注意，尽管意图不同，但扩展 Python 和嵌入 Python 的过程相当类似。前几章中讨论的大多数主题依然有效。为了说明这一点，不妨来看一下从
Python 到 C 的扩展代码到底做了什么：将 Python 的数据转换为 C 格式，
用转换后的数据执行 C 程序的函数调用，
将调用返回的数据从 C 转换为 Python 格式。
嵌入 Python 时，接口代码会这样做：将 C 数据转换为 Python 格式，
用转换后的数据执行对 Python 接口的函数调用，
将调用返回的数据从 Python 转换为 C
格式。
可见只是数据转换的步骤交换了一下顺序，以顺应跨语言的传输方向。唯一的区别是在两次数据转换之间调用的函数不同。在执行扩展时，调用一个 C 函数，而执行嵌入时调用的是个 Python 函数。本文不会讨论如何将数据从 Python 转换到 C 去，反之亦然。另外还假定读者能够正确使用引用并处理错误。由于这些地方与解释器的扩展没有区别，请参考前面的章节以获得所需的信息。1.3. 只做嵌入第一个程序的目标是执行 Python 脚本中的某个函数。就像高层次接口那样，Python 解释器并不会直接与应用程序进行交互（但下一节将改变这一点）。要运行 Python 脚本中定义的函数，代码如下：#define PY_SSIZE_T_CLEAN
#include <Python.h>
int
main(int argc, char *argv[])
{
PyObject *pName, *pModule, *pFunc;
PyObject *pArgs, *pValue;
int i;
if (argc < 3) {
fprintf(stderr,"Usage: call pythonfile funcname [args]\n");
return 1;
}
Py_Initialize();
pName = PyUnicode_DecodeFSDefault(argv[1]);
/* Error checking of pName left out */
pModule = PyImport_Import(pName);
Py_DECREF(pName);
if (pModule != NULL) {
pFunc = PyObject_GetAttrString(pModule, argv[2]);
/* pFunc is a new reference */
if (pFunc && PyCallable_Check(pFunc)) {
pArgs = PyTuple_New(argc - 3);
for (i = 0; i < argc - 3; ++i) {
pValue = PyLong_FromLong(atoi(argv[i + 3]));
if (!pValue) {
Py_DECREF(pArgs);
Py_DECREF(pModule);
fprintf(stderr, "Cannot convert argument\n");
return 1;
}
/* pValue reference stolen here: */
PyTuple_SetItem(pArgs, i, pValue);
}
pValue = PyObject_CallObject(pFunc, pArgs);
Py_DECREF(pArgs);
if (pValue != NULL) {
printf("Result of call: %ld\n", PyLong_AsLong(pValue));
Py_DECREF(pValue);
}
else {
Py_DECREF(pFunc);
Py_DECREF(pModule);
PyErr_Print();
fprintf(stderr,"Call failed\n");
return 1;
}
}
else {
if (PyErr_Occurred())
PyErr_Print();
fprintf(stderr, "Cannot find function \"%s\"\n", argv[2]);
}
Py_XDECREF(pFunc);
Py_DECREF(pModule);
}
else {
PyErr_Print();
fprintf(stderr, "Failed to load \"%s\"\n", argv[1]);
return 1;
}
if (Py_FinalizeEx() < 0) {
return 120;
}
return 0;
}
上述代码先利用 argv[1] 加载 Python 脚本，再调用 argv[2] 指定的函数。函数的整数参数是 argv 数组中的其余值。如果 编译并链接 该程序（此处将最终的可执行程序称作 call）, 并用它执行一个 Python 脚本，例如：def multiply(a,b):
print("Will compute", a, "times", b)
c = 0
for i in range(0, a):
c = c + b
return c
然后结果应该是：$ call multiply multiply 3 2
Will compute 3 times 2
Result of call: 6
尽管相对其功能而言，该程序体积相当庞大，但大部分代码是用于 Python 和 C 之间的数据转换，以及报告错误。嵌入 Python 的有趣部分从此开始：Py_Initialize();
pName = PyUnicode_DecodeFSDefault(argv[1]);
/* Error checking of pName left out */
pModule = PyImport_Import(pName);
初始化解释器之后，则用 PyImport_Import() 加载脚本。此函数的参数需是个 Python 字符串，一个用 PyUnicode_FromString() 数据转换函数构建的字符串。pFunc = PyObject_GetAttrString(pModule, argv[2]);
/* pFunc is a new reference */
if (pFunc && PyCallable_Check(pFunc)) {
...
}
Py_XDECREF(pFunc);
脚本一旦加载完毕，就会用 PyObject_GetAttrString() 查找属性名称。如果名称存在，并且返回的是可调用对象，即可安全地视其为函数。然后程序继续执行，照常构建由参数组成的元组。然后用以下方式调用 Python 函数：pValue = PyObject_CallObject(pFunc, pArgs);
当函数返回时，pValue 要么为 NULL，要么包含对函数返回值的引用。请确保用完后释放该引用。1.4. 对嵌入 Python 功能进行扩展到目前为止，嵌入的 Python 解释器还不能访问应用程序本身的功能。Python API 通过扩展嵌入解释器实现了这一点。 也就是说，用应用程序提供的函数对嵌入的解释器进行扩展。虽然听起来有些复杂，但也没那么糟糕。只要暂时忘记是应用程序启动了 Python 解释器。而把应用程序看作是一堆子程序，然后写一些胶水代码让 Python 访问这些子程序，就像编写普通的 Python 扩展程序一样。 例如：static int numargs=0;
/* Return the number of arguments of the application command line */
static PyObject*
emb_numargs(PyObject *self, PyObject *args)
{
if(!PyArg_ParseTuple(args, ":numargs"))
return NULL;
return PyLong_FromLong(numargs);
}
static PyMethodDef EmbMethods[] = {
{"numargs", emb_numargs, METH_VARARGS,
"Return the number of arguments received by the process."},
{NULL, NULL, 0, NULL}
};
static PyModuleDef EmbModule = {
PyModuleDef_HEAD_INIT, "emb", NULL, -1, EmbMethods,
NULL, NULL, NULL, NULL
};
static PyObject*
PyInit_emb(void)
{
return PyModule_Create(&EmbModule);
}
在 main() 函数之前插入上述代码。并在调用 Py_Initialize() 之前插入以下两条语句：numargs = argc;
PyImport_AppendInittab("emb", &PyInit_emb);
这两行代码初始化了 numargs 变量，并让 emb.numargs() 函数能被嵌入的 Python 解释器访问到。有了这些扩展，Python 脚本可以执行类似以下功能：import emb
print("Number of arguments", emb.numargs())
在真实的应用程序中，这种方法将把应用的 API 暴露给 Python 使用。1.5. 在 C++ 中嵌入 Python还可以将 Python 嵌入到 C++ 程序中去；确切地说，实现方式将取决于 C++ 系统的实现细节；一般需用 C++ 编写主程序，并用 C++ 编译器来编译和链接程序。不需要用 C++ 重新编译 Python 本身。