# 2021 資芽 C/C++ 大作業二 - SPEC

> 官網: <https://tw-csie-sprout.github.io/c2021/#!project2.md>
> 說明影片: <https://youtu.be/8FDU-efmm34>

[TOC]

## 介紹

### Pacman 遊戲
[Pacman](https://www.google.com/search?q=pacman)
- 用鍵盤控制 pacman 吃豆子
- pacman 不能被鬼抓到
- 吃到「大力丸」可以反過來吃鬼

我們要做的遊戲呢？
- 有兩種 "Game Mode"
- 1P 的單人遊玩
- 4P 的多人遊玩
- 有多種的 "Player Mode"
- 手動：用鍵盤控制 pacman 移動
- 隨機：Pacman 隨機上下左右移動
- AI：我們寫好控制 pacman 的程式，讓 pacman 根據當下地圖的狀態，決定如何移動
- 有多種道具
- 蘋果、鳳梨、鞋子、星星、斗篷...等一下會一一解釋

### 地圖
- 其中一個評（ㄙㄨㄥˋ）分項目
- 只要自製一張合法的地圖，就可以拿到 5% 分數
- 200 ≤ H × M ≤ 2000
- 牆壁的數量不得少於 1/4 且不得多於 3/4
- 邊界是聯通的


15 72
#####.###########.#################.#################.############.#####
#.....#..................#...................#...................#.....#
..#.###.##################.#################.###################.###.#..
###.#..............................................................#.###
#...#.#..########.########.########.########.#......#.#########..#.#...#
#.#.#.#..#........#......#.#......#.#......#.#......#.....#......#.#.#.#
#.#.#.#..#........#......#.#......#.#......#.#......#.....#......#.#.#.#
#.#......########.########.########.#......#.#......#.....#......#...#.#
#.#.#.#.........#.#........#.##.....#......#.#......#.....#......#.#.#.#
#.#.#.#.........#.#........#...##...#......#.#......#.....#......#.#.#.#
#...#.#..########.#........#.....##.########.########.....#......#.#...#
###.#..............................................................#.###
..#.###.##################.#################.###################.###.#..
#.....#..................#...................#...................#.....#
#####.###########.#################.#################.############.#####
1 1
1 1 13 1 1 68 13 68

- Line 1: 15 和 72 分別代表長和寬
- Line 2~16: 用 . 代表走道，用 # 代表牆壁
- Line 17: 在 1P 模式下，pacman 的起始點
- 最左上角是 0 0
- Line 18: 在 4P 模式下，4 個 pacman 各自的起始點

> 途中 `S` 的左邊左邊有不對稱的情形會在正式 release 版修正！

#### 座標世界
- 座標軸和日常世界的方向不太一樣， *x* 是朝下的、 *y* 是朝右的
- 和 *二維陣列* 的方向是一樣的喔！
- 記得從 **0** 開始數

### 道具
- 蘋果
- 相當於 pacman 遊戲中的豆子，吃了會加 5 分
- 鳳梨
- 升級版的蘋果？吃了會加 50 分
- 鞋子（有效時間：300 *ticks*）
- 吃了可以進入「加速模式」（speedup mode），會加快 pacman 的移動速度兩倍。
- 斗篷（有效時間：300 *ticks*）
- 吃了可以進入「鬼人模式」（ghost mode），可以穿過牆壁
- 星星（有效時間：150 *ticks*）
- 出現在 4P 模式
- 吃了可以進入「強化模式」（powerup mode）與其他 pacman 相撞時，可以從對方奪取一半的分數。
- 被吃的人會有進入「不被侵犯模式」（no-dead mode）90 ticks。
- 道具的圖片放在 /img 底下

### 遊戲實作細節
> 實作細節很多大家不需要知道 > <
> 想知道還是可以去偷看我們寫的 code 喔！

#### Tick 的概念
- 程式 (遊戲) 裡面的世界並不像現實世界 (?) 一樣是分頭進行的，一次只會有一件事情正在進行。記得我們之前寫程式的時候也是一行一行執行吧！
- 但要怎麼樣讓遊戲看起來像是一瞬間發生很多事呢？<br>⟹**Tick** 的概念！
- 一個 tick 裡面有相當多的判斷發生，包含偵測你的 keyboard、讓 Pacman 移動、計算分數、看有沒有撞到鬼......
- 當很多判斷結束後才會更新一次螢幕！

#### 我們的遊戲中的一個 Tick (概念)
> 斜體字的 *controller* 和 *ACTION* 會在下面有更多的講解！

1. 更新視窗的顯示
2. 讓 *controller* 做出 *ACTION*
- ==你們只需要管這邊==，其他我們幫你 handle 好了
- 只有在 pacman 處在 **可以移動的狀態** 才可以做決定
- 當 pacman 決定要走時，他其實會走 8 個 tick，也就是 8 個 tick 後才能走
3. 遊戲讓 *pacman* 真的移動、做了很多運算包含確定該步合法性、計分......


## 如何玩遊戲？
### 環境設定與編譯遊戲
#### Windows
[安裝影片](https://drive.google.com/file/d/1QyQPO52HhtMxk3LxnTQSysuW-tUxOI-e/view?usp=sharing)
##### 環境設定
<font color="#f00">5/29 17:30 更新安裝包連結
.
如果已經下載過安裝包 而且已經開始寫作業
請幫我刪除大作業檔案中的 build.bat，然後下載最新的 [build_v2.bat](https://drive.google.com/file/d/1glIKz7dbwNnft50DSZ_7IX-jbzC5bg3e/view?usp=sharing ) 至原本 build.bat 的位置
</font>
> https://drive.google.com/file/d/1vjKv9Vp1m2Hb5IWAgGgAcLMdcuaLiWEH/view?usp=sharing
1. 下載檔案並解壓縮
##### 編譯遊戲
<font color="#f00">6/14 補充說明編譯＋執行
1. 打開命令提示字元
2. `cd <Directory>` 進入作業資料夾
- 例如：`cd Download`
3. build_v2.bat 編譯
4. bin\main 1 0 2021 maps\sprout.txt imgs\ 執行
</font>

指令版
1. 進入下載檔案的資料夾
2. 右鍵「在這裡開啟 PowerShell 視窗」
3. 在 PowerShell 視窗輸入 `.\build_v2.bat`
- 鍵盤上的`TAB` 會幫你把指令自動補齊
- 輸入 `.\bu` 按 `TAB`，`.\build_v2.bat` 就會跑出來了
#### MacOS
[安裝影片](https://drive.google.com/file/d/1-GMMUBv3RsdvdBXglSfxWy8NJ6MWdk7F/view?usp=sharing)
##### 環境設定
> https://drive.google.com/file/d/1psNHpFntDnSS3f5wZB4Lcm4bKVqLE7tm/view?usp=sharing
1. 開啟終端機，輸入以下指令

/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"
brew install gcc
brew install sdl2
brew install sdl2_image
brew install sdl2_gfx
brew install sdl2_ttf

##### 編譯遊戲
1. 開啟終端機
2. 拖曳檔案資料夾到終端機
- 或是用 `cd` 進入資料夾
4. 輸入 `make`

#### Linux Like
[安裝影片](https://drive.google.com/file/d/1zNepeIeez4Oj7k4lUDhokRZCRyPrOJO7/view?usp=sharing)
##### 環境設定
> https://drive.google.com/file/d/1psNHpFntDnSS3f5wZB4Lcm4bKVqLE7tm/view?usp=sharing
1. 開啟終端機，輸入以下指令

sudo apt install gcc
sudo apt install libsdl2-dev
sudo apt install libsdl2-image-dev
sudo apt install libsdl2-gfx-dev
sudo apt install libsdl2-ttf-dev

##### 編譯遊戲
1. 以終端機進入檔案位置
2. 輸入 `make`
### 執行遊戲
#### Windows
開啟<font color="#f00">命令提示字元</font>，輸入

bin\main GAME_MODE PLAYER_MODE RANDOM_SEED MAP_TXT IMAGE_DIR

如：

bin\main 1 0 2021 maps\sprout.txt imgs\

#### MacOS/Linux

bin/main GAME_MODE PLAYER_MODE RANDOM_SEED MAP_TXT IMAGE_DIR

如：

bin/main 1 0 2021 maps/sprout.txt imgs/

### 參數說明

依照空白切格
- `bin/main`：遊戲執行檔
- `GAME_MODE`：遊戲模式
- `1`：單人遊玩
- `4`：四人模式
- `PLAYER_MODE`：玩家模式
- `0`：手動模式
- `1`：隨機模式
- `2`：AI 1-1
- `3`：AI 1-2
- `4`：AI 2-1
- `5`：AI 2-2
- `6`：Example Controller
- `RANDOM_SEED`：亂數種子 (一個整數)
- `MAP_TXT`：地圖的文字檔
- `IMAGE_DIR`：遊戲介面圖示資料夾

## 你需要做什麼？

### 1. 送分的啦 (20%)
1. 截圖遊戲畫面 (10%)
- 只要將遊戲下載下來、完成安裝相關套件並讓遊戲可以成功執行
2. 自製地圖 (5%)
- 圖需要有以下條件
1. 200 ≤ H × M ≤ 2000
2. 牆壁的數量不得少於 1/4 且不得多於 3/4
3. 更換地圖造型 (5%)
- 請在 `imgs_custom/` 下面參考 `imgs/` 完成新的地圖造型
- 圖片請使用 PNG 檔

### 2. 一人遊玩 (40% + 10% bonus)
請實作一個 AI 讓他可以「聰明的」玩這個遊戲！
1. 吃最近的蘋果！ (20%)
- 若有多個蘋果，則吃哪個都可以！
- 鳳梨不是蘋果
2. 請想一個自己的策略讓你的 AI 比 (1) 還要好！(20% + 10% bonus)
- 強度 (20%)：只要比 (1) 好都能拿到這邊的分數
- 創意分數 (10% bonus)：我們會根據你的策略給出創意分數
> 如果使用我們提供的一些想法、和很多同學的策略雷同，則這邊的 bonus 分數不會拿太多喔！
- 一些想法提供
- 改善 (1) 讓你的 AI 也吃鳳梨呢？

> 這邊和一般的作業一樣有時間限制，請將你的 AI 判斷時間控制在 0.1s 內！

### 3. 四人遊玩 (40% + 10% bonus)
請實作一個 AI 讓他可以「聰明的」玩這個遊戲！
1. 有無敵果實就吃無敵果實，其他時間吃最近的蘋果！ (20%)
2. 請想一個自己的策略讓你的 AI 比 (1) 還要好！(20% + 10% bonus)
- 強度 (20%)：只要比三個隨機亂走的的 bot 好都能拿到這邊的分數
- 比 10 場，一局中第一名 +2 分、第二名 + 1 分、第三名 + 0.5 分
- 創意分數 (10% bonus)：我們會根據你的策略給出創意分數
> 如果使用我們提供的一些想法、和很多同學的策略雷同，則這邊的 bonus 分數不會拿太多喔！

### 4. Bonus (10%)
- 你的 4P 遊玩會和兩位出作業講師寫的兩個 AI 以及一個 random 的 bot 比
- 比 5 場，一局中第一名 +2 分、第二名 + 1 分、第三名 + 0.5 分

## 如何寫我們的 AI？

### Controller & Helper
- 要寫一個 *AI* 還是太難了一點
> (STRONGLY DISCOURAGED) 想要的人可以自己去查 *Reinforcement Learning*
- 我們的 AI 會比較簡單一點
- 實作一個 controller
- 一個 helper 當作眼睛、軍師！
- 其實就是寫一個 function
- 使用 helper 幫你看遊戲的局面
- 使用 helper 的東西給你一些「有用的資訊」
- 回傳一個 ACTION

### ACTION
總共有五個 ACTION
- `ACTION::NO_OP`：不要動
- `ACTION::GO_DOWN`：往下走
- `ACTION::GO_RIGHT`：往右走
- `ACTION::GO_UP`：往上走
- `ACTION::GO_LEFT`：往左走

### STL 超前部署

#### Pair (Coordinate)
> 一個把兩個型態綁在一起的型態

- 以下會看到的 *Coordinate* 其實就只是一個 `pair<int, int>`。
- 有點像之前介紹過的 `struct`，可以藉由 `.first`、`.second` 分別拿到這兩個東西。
- 可以使用 `std::make_tuple(a, b)` 將兩個整數包成一個 `Coordinate`（需要 `#include <algorithm>`）

Coordinate p = std::make_tuple(1, 2);
std::cout << p.first << " " << p.second << "\n";

#### Vector
> 一個不用指定大小的動態陣列，滿了會幫你自動變大，空了會幫你自動變小！

- 可以直接像陣列一樣使用 `[i]` 得到第 i 個值
- 可以用 `.size()` 得到這個 vector 的長度

### Controller
- 是一個 *class*
- 可以用 `.index` 得知自己的 pacman 的序號 (index)
- 在你們的視角都會拿到 `0`

### Helper 函式們

// Map related
bool is_wall(int x, int y);
Coordinate get_map_size();

// Pacman related
Coordinate get_pacman_coord(int index);
int get_pacman_moving_cd(int index);
int get_pacman_powerup_cd(int index);
int get_pacman_speedup_cd(int index);
int get_pacman_ghost_cd(int index);
int get_pacman_no_dead_cd(int index);

// Item related
vector<Coordinate> get_all_apples();
vector<Coordinate> get_all_apples_sorted(Coordinate coord);

vector<Coordinate> get_all_pineapples();
vector<Coordinate> get_all_pineapples_sorted(Coordinate coord);

vector<Coordinate> get_all_boots();
vector<Coordinate> get_all_boots_sorted(Coordinate coord);

vector<Coordinate> get_all_cloaks();
vector<Coordinate> get_all_cloaks_sorted(Coordinate coord);

vector<Coordinate> get_all_stars();
vector<Coordinate> get_all_stars_sorted(Coordinate coord);

// Useful function
int calc_distance(Coordinate a, Coordinate b);
vector<ACTION> calc_shortest_path(Coordinate a, Coordinate b);
void sort_coords_by_distance(vector<Coordinate> &items, Coordinate coord);

### 範例 Controller

#### `example_controller.hpp`

#ifndef _CONTROLLERS_EXAMPLE_CONTROLLER_HPP
#define _CONTROLLERS_EXAMPLE_CONTROLLER_HPP

#include <queue>
#include <utility>

#include "controllers/base.hpp"

using std::pair;
using std::queue;

class ExampleController : public Controller {
   public:
    using Controller::Controller;
    ~KeyboardController();
    void initialize();
    ACTION decide(Helper &helper);
};

#endif

#### `example_controller.cpp`
每次先往上走，不行就往右，再不行往下，還是不行往左

#include "controllers/example_controller.hpp"

#include "game_utils.hpp"

// leave blank if you don't need it :)
ExampleController::~ExampleController(){};

// leave blank if you don't need it :)
void ExampleController::initialize() {}

ACTION ExampleController::decide(Helper &helper) {
    Coordinate my_coord = helper.get_pacman_coord(this->index);

    int x = my_coord.first, y = my_coord.second;
    if (!helper.is_wall(x - 1, y)) {
        return ACTION::GO_UP;
    } else if (!helper.is_wall(x, y + 1)) {
        return ACTION::GO_RIGHT;
    } else if (!helper.is_wall(x + 1, y)) {
        return ACTION::GO_DOWN;
    } else if (!helper.is_wall(x, y - 1)) {
        return ACTION::GO_LEFT;
    } else {
        return ACTION::NO_OP;
    }
}

## 繳交作業
> UPDATED ON 06/05 16:00
- 日期: **06/25 (Fri.) 23:59**
- 方式: Google 表單 [link](https://forms.gle/mLWKccH4b5wTi7Jj6)
- 請上傳一個 zip 檔，包含你的「整個遊戲資料夾」
- 請參考以下資料夾樹狀圖，有星星的部分請特別注意！
- `custom_imgs`: 包含第一題第三小題（更換遊戲圖片）的所有圖片
- `maps/custom_map.txt`: 包含第一題第二小題（更換遊戲地圖）的地圖檔
- `report.pdf`: 包含第一題第一小題（遊玩畫面截圖）及第二、第三題的創意 AI 發想說明。必須為一個 `pdf` 檔！
- `src/controllers/ai_controller*`: 關於實作的四種 AI 的八個檔案。
- 為了避免檔案過大，請將 `bin/` 資料夾刪除後再壓縮資料夾！
- 壓縮方式參考：
- Windows: https://support.microsoft.com/zh-tw/windows/壓縮與解壓縮-8d28fa72-f2f9-712f-67df-f80cf89fd4e5
- MacOS: https://support.apple.com/zh-tw/guide/mac-help/mchlp2528/mac

.
├── Makefile
├── README.md
├── build.bat
├── fonts
│   └── ...
├── imgs
│   └── ...
├── custom_imgs (*)
│   └── ...
├── maps
│   ├── custom_map.txt  (*)
│   ├── README.md
│   ├── sprout.txt
│   └── test.txt
├── report.pdf  (*)
├── src
│   ├── controllers
│   │   ├── ai_controller_1_1.cpp   (*)
│   │   ├── ai_controller_1_1.hpp   (*)
│   │   ├── ai_controller_1_2.cpp   (*)
│   │   ├── ai_controller_1_2.hpp   (*)
│   │   ├── ai_controller_2_1.cpp   (*)
│   │   ├── ai_controller_2_1.hpp   (*)
│   │   ├── ai_controller_2_2.cpp   (*)
│   │   ├── ai_controller_2_2.hpp   (*)
│   │   └── ...
│   └── ...
└── tools
    └── ...

## FAQ
- 為什麼遊戲會自己結束？
- 遊戲預設是兩分鐘
- Windows 沒有以終端機開啟的選項怎麼辦？
1. 複製檔案路徑
3. 搜尋「命令提示字元」
4. 輸入 cd 貼上路徑
- 地圖太大電腦螢幕放不下怎麼辦？
- 打開大作業資料夾裡面 src/constants.hpp
- 修改底下兩行程式碼

        const int SCREEN_MAX_WIDTH = 960;
        const int SCREEN_MAX_HEIGHT = 640;

- 把 bin 資料夾刪除後，重新編譯