贪吃蛇AI人工智能C++实现

微信扫一扫

028-83195727 , 15928970361
business@forhy.com

贪吃蛇AI人工智能C++实现

c++,贪吃蛇,人工智能,算法,ai2016-07-12

引言：

贪吃蛇是一款非常经典的游戏，规则想必大部分人都知道，这里就不再叙述了。最近写了一个贪吃蛇的人工智能版本，想方设法让蛇吃掉更多的食物。

先上效果图：

这个项目并没有完全结束，目前的AI算法并不算很好，所以有兴趣的人可以加入我的项目一起完成，项目链接以及代码下载：Github: Snake-AI

AI算法：

贪吃蛇（S1）每次的移动方向经过以下几个步骤得出：

1. 搜索从S1的头部到食物的最短路径P1。

2. 让一条和S1完全相同的蛇（S2）沿路径P1移动并吃掉食物。

3. 搜索从S2的头部到达S2的尾部的最长路径P2，若P2存在，S1的移动方向设为P1的第一个位置所对应的方向，若P2不存在，继续第4步。

4. 搜索从S1的头部到达S1的尾部的最长路径P3，若P3存在，S1的移动方向设为P3的第一个位置所对应的方向，若P3不存在，继续第5步。

5. 在S1可以走到的上下左右四个位置中，选取离食物最远的位置，该位置对应的移动方向设为S1的移动方向。

其它算法：

1. 最短路径算法

目前采用的是Dijkstra + A*，A*的估值函数包含曼哈顿距离和几何距离，权重均为1。

下图为算法的演示（绿色是算法扫过的区域，红色是最终计算出的路径）：

2. 最长路径算法

最长路径本身为一个NP问题，通过完全枚举出所有可行的路径会耗费大量时间，目前采用的是DFS + A*，在遍历邻接点时，优先遍历离终点估值较远的点，从而得到近似的最长路径。

下图为算法的演示（绿色是算法扫过的区域，红色是最终计算出的路径）：

控制台颜色输出：

目前整个游戏界面是显示在控制台上的，控制台的输出颜色等信息通过一个类Console完成，该类的声明如下：

// Console color type
enum ColorType {
    BLACK,
    RED,
    GREEN,
    BLUE,
    YELLOW,
    CYAN,
    MAGENTA,
    WHITE,
};

// Console color class
struct ConsoleColor {
    ConsoleColor(const ColorType foreColor_, const ColorType backColor_, 
                 const bool &foreIntensified_ = false, const bool &backIntensified_ = false);
    ColorType foreColor;
    ColorType backColor;
    bool foreIntensified;
    bool backIntensified;
};

/*
A cross-platform class to control the output
attributes of the console(terminal).
*/
class Console {
public:
    /*
    Set console cursor position.
    The origin is at the left-top corner. Axis x extends to the right
    and axis y extends to the bottom.

    @param console x coordinate
    @param console y coordinate
    */
    static void setCursor(const int &x = 0, const int &y = 0);

    /*
    Clear the console.
    */
    static void clear();

    /*
    Write string to console

    @param str the string to write
    */
    static void write(const std::string &str);

    /*
    Write string to console with a given color.
    In linux platform, the intensified console color
    attribute is not supported.
    Reference:
    1. http://stackoverflow.com/questions/2616906/how-do-i-output-coloured-text-to-a-linux-terminal

    @param str the string to write
    @param color the output color
    */
    static void writeWithColor(const std::string &str, const ConsoleColor &consoleColor);

    /*
    A cross-platform getch() method.
    Reference:
    1. http://stackoverflow.com/questions/3276546/how-to-implement-getch-function-of-c-in-linux
    */
    static char getch();

    /*
    A cross-platform kbhit() method.
    Reference:
    1. http://cboard.cprogramming.com/c-programming/63166-kbhit-linux.html
    */
    static int kbhit();

private:
#ifdef WIN32
    /*
    Set console output color.
    Only available in windows platform.

    @param color the output color
    @return the origin console attribute
    */
    static WORD setColor(const ConsoleColor &consoleColor);

    /*
    Reset console output color to default.
    Only available in windows platform.

    @param attr the console attribute to restore
    */
    static void resetColor(const WORD &attr);
#endif
};

该类提供的功能是跨平台的，目前可以在windows和linux下使用。函数writeWithColor()实现了在控制台上的不同颜色的输出。

游戏运行：

整个游戏过程通过GameCtrl类控制，除了主线程外，还有5条线程分别完成不同的功能，它们分别是：

1. drawThread：完成每一帧的游戏界面的绘制。

2. keyboardThread：完成键盘指令的接受以及执行。

3. foodThread：完成食物的创建。

4. autoMoveThread：完成贪吃蛇的自动移动。

5. testThread：完成一些算法的展示，供测试用。

主函数的执行逻辑：

int main() {
    auto game = GameCtrl::getInstance();

    // Set map's size. Default is 20*20
    // The minimum size is 4*4.
    game->setMapRow(8);
    game->setMapColumn(8);

    // Set FPS. Default is 60.0
    game->setFPS(59.0);

    // Set whether to make the snake automove. Default is true
    game->setAutoMoveSnake(true);

    // Set interval time(ms) for automove. Default is 200 ms.
    // If setAutoMoveSnake(false), this code is useless.
    game->setAutoMoveInterval(50);

    // Set whether to enable the second snake. Default is false
    game->setEnableSecondSnake(false);

    // Set whether to enable the snake AI. Default is false
    // If setAutoMoveSnake(false), this code is useless.
    game->setEnableAI(true);

    // Set whether to run the test program. Default is false
    // Set the map size to 20*40 before setting this to true.
    game->setRunTest(false);

    // Set whether to write the map content to the file. Default is false
    // If set this attribute to true, the game map content will be written
    // to a file named "movements.txt" after each snake's movement.
    // PS: This is designed for debugging. Open this method may make the
    // snake move slower.
    game->setWriteToFile(false);

    return game->run();
}

具体实现：

程序中的几个核心的类：

1. Point类：该类只有两个属性x和y，对应为横坐标和纵坐标，在二维数组中，x为行号，y为列号。

2. Grid类和SearchableGrid类：该类为地图上的每一个最小单元，Grid类中只有一个属性就是方格的类型（包括空白、墙、蛇头、蛇身、蛇尾以及食物），SearchableGrid继承自Grid类，存放了图搜索算法中需要用到的变量。

3. Map类：该类为地图类，存放了由SearchableGrid组成的二维数组。该类提供了创建食物、搜索最长/最短路径的功能。

4. Snake类：该类代表一条实际的贪吃蛇，存放了蛇的每一节身体所对应的坐标以及一个Map实例，表示蛇的移动区域。该类提供了贪吃蛇的AI决策算法。

5. GameCtrl类：该类控制游戏的开始，运行以及结束。

上述几个类的实现代码较多，这里暂不一一叙述，若有需要请在评论区留言，详细请参考项目的源代码。如有任何问题，欢迎指出。