# snake_ai

**Repository Path**: hez2010/snake_ai

## Basic Information

- **Project Name**: snake_ai
- **Description**: 智能蛇
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-01-05
- **Last Updated**: 2021-01-05

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 智能蛇
2018 软件工程 17364025 贺恩泽

## 整体框架
智能蛇的流程如下：

1. 清除屏幕
2. 生成食物
3. 输出地图
4. 如果游戏未结束
   1. 延时 1 秒
   2. 决策下一步并移动蛇，如果无法找出下一步则游戏结束
   3. 如果吃到食物则更新蛇的长度并生成新食物，如果蛇长度超过限制则游戏结束
   4. 清除屏幕
   5. 输出移动后的地图
   6. 重复上述过程
5. 如果游戏结束输出 `Game Over!!`

因此，会吃的蛇设计为以下几个函数：

- `print_map` 输出地图
- `snake_mode` 移动蛇
- `game_over` 结束游戏
- `generate_food` 生成食物
- `where_go_next` 决策下一步移动

用代码表示为：

```c
printf("\033[2J");
generate_food();
print_map();
while (!gameOver) {
    sleep(1);
    input = where_go_next();
    switch (input) {
    case 'A': // 向左移动
    case 'a':
        snake_move(0, -1);
        break;
    case 'D': // 向右移动
    case 'd':
        snake_move(0, 1);
        break;
    case 'W': // 向上移动
    case 'w':
        snake_move(-1, 0);
        break;
    case 'S': // 向下移动
    case 's':
        snake_move(1, 0);
        break;
    case 'Q':
    case 'q':
        gameOver = 1;
        break;
    default:
        continue;
    }
    printf("\033[2J");
    print_map();
}
```

### 清除屏幕
在 Linux 下可以通过输出 `\033[2J` 来清除屏幕。

```c
printf("\033[2J");
```

### 输出地图
首先利用打表的方式存储空地图：
```c
// 初始地图
char map[12][12] = {
    "************",
    "*          *",
    "*       *  *",
    "*    *     *",
    "*          *",
    "*          *",
    "*   *      *",
    "*          *",
    "*       *  *",
    "*    *     *",
    "*          *",
    "************"
};
```

为了记录蛇的位置，可以利用数组分别保存蛇的行列坐标：

```c
// 蛇身体的行坐标
int snakeX[SNAKE_MAX_LEN] = { 1,1,1,1,1 };

// 蛇身体的列坐标
int snakeY[SNAKE_MAX_LEN] = { 1,2,3,4,5 };
```

再用 `foodX` 和 `foodY` 保存食物的行列坐标：

```c
// 食物的行列坐标
int foodX = 0, foodY = 0;
```

这样一来，只需要判断坐标点是否记录在 `snakeX` 和 `snakeY` 中即可知道对应位置是不是蛇，根据 `foodX` 和 `foodY` 即可判断是不是食物：

```c
if (snakeX[k] == i && snakeY[k] == j) {
    ch = k == snakeLength - 1 ? SNAKE_HEAD : SNAKE_BODY;
}
if (i == foodX && j == foodY) {
    ch = SNAKE_FOOD;
}
```


然后根据位置输出对应的字符即可。

### 移动蛇
移动蛇的步骤为：

1. 计算蛇头的新位置
    ```c
    int i, x = snakeX[snakeLength - 1] + dx, y = snakeY[snakeLength - 1] + dy;
    ```
2. 判断是否吃到食物，若吃到则增加身体长度，若蛇超过最长长度则游戏结束
    ```c
    if (x == foodX && y == foodY) {
        // 若蛇超过最长长度则游戏结束
        if (snakeLength + 1 == SNAKE_MAX_LEN) {
            game_over();
            return;
        }
        snakeX[snakeLength] = x;
        snakeY[snakeLength] = y;
        snakeLength++;
        generate_food();
        return;
    }
    ```

3. 判断是否撞到障碍物，若撞到则游戏结束
    ```c
    if (map[x][y] == '*') {
        game_over();
        return;
    }
    ```
4. 判断是否撞到自身，若撞到则游戏结束
    ```c
    for (i = 1; i < snakeLength; i++) {
        if (snakeX[i] == x && snakeY[i] == y) {
            game_over();
            return;
        }
    }
    ```
5. 更新蛇的位置
    ```c
    for (i = 0; i < snakeLength - 1; i++) {
        snakeX[i] = snakeX[i + 1];
        snakeY[i] = snakeY[i + 1];
    }
    snakeX[snakeLength - 1] = x;
    snakeY[snakeLength - 1] = y;
    ```

### 结束游戏
程序中利用一个全局变量 `gameOver` 指示游戏是否结束，因此结束游戏只需要将这个变量设置为 `1` 即可。

```c
void game_over(void) {
    gameOver = 1;
}
```

### 生成食物
生成的食物需要确保食物出现在空白的位置，这个位置不能和蛇所在的位置重叠，也不能和障碍物重叠，因此只需要不断获取随机数直到找到满足要求的位置即可。

```c
void generate_food(void) {
    int canPlaceFood, i;
    do {
        canPlaceFood = 1;
        foodX = rand() % 10 + 1;
        foodY = rand() % 10 + 1;
        if (map[foodX][foodY] == '*') {
            canPlaceFood = 0;
        }
        for (i = 0; i < snakeLength; i++) {
            if (snakeX[i] == foodX && snakeY[i] == foodY) {
                canPlaceFood = 0;
                break;
            }
        }
    } while (!canPlaceFood);
}
```

### 决策下一步
决策下一步需要确保移动后蛇不会撞到自身，也不会撞到障碍物，并且要尽可能距离食物更进一步。

```c
char where_go_next() {
    char movable[] = { 'a','d','w','s' };
    // 移动方向
    int dx[] = { 0,0,-1,1 };
    int dy[] = { -1,1,0,0 };
    // 距离食物的位置
    int distance[] = { 0,0,0,0 };
    int i, j;
    for (i = 0; i < 4; i++) {
        // 计算新位置
        int x = snakeX[snakeLength - 1] + dx[i], y = snakeY[snakeLength - 1] + dy[i];
        // 计算距离食物的位置
        distance[i] = abs(foodX - x) + abs(foodY - y);
        // 不能撞到障碍物
        if (map[x][y] == '*') {
            distance[i] = 9999;
        }
        // 不能撞到自身
        for (j = 1; j < snakeLength; j++) {
            if (snakeX[j] == x && snakeY[j] == y) {
                distance[i] = 9999;
                break;
            }
        }
    }

    // 找出移动后可以使蛇头距离食物最近的方向
    int k = -1;
    int minValue = 9999;
    for (i = 0; i < 4; i++) {
        if (distance[i] < minValue) {
            k = i;
            minValue = distance[i];
        }
    }

    // 如果找不到则游戏结束
    return k == -1 ? 'q' : movable[k];
}
```

## 构建方法

```bash
mkdir build && cd build
cmake ..
make
```

然后运行 `build` 目录中的 `snake_ai` 程序即可。

## 效果测试
减少 `sleep` 时间后，测试效果如下：

![1](assets/1.gif)

### 一个长度为5的障碍物能困死该自动跑的蛇吗
游戏地图为 12\*12，空白区域为 10\*10，长度为5的障碍物不会困死蛇，但是随着蛇的长度变长（超过5），蛇可能会把自己困死，例如下面这种情况：

![2](assets/2.png)

## kbhit 实现
利用 `kbhit()` 可以检测 TTY 的输入，实现非阻塞地检测键盘输入。通过调用 `kbhit` 函数可以不需要回车就能捕获到用户输入。

```c
int main()
{
        // 设置终端进入非缓冲状态
        int tty_set_flag;
        tty_set_flag = tty_set();

        while(1) {
                if(kbhit()) {
                        char key = getchar();
                        printf("%c pressed\n", key);
                        if(key == 'q')
                                break;
                } else {
                       ;// fprintf(stderr, "<no key detected>\n");
                }
        }

        // 恢复终端设置
        if(tty_set_flag == 0) 
                tty_reset();
        return 0;
}
```