# Sprout Project 1: Sprout Crush ## 公告 - 4/29 20:59 ai 分數獲取方式說明 - 4/28 21:14 新增時限規定 - 4/26 13:11 add some hints about task 1 - 4/23 11:00 新增 FAQ - 4/23 19:51 新增 `moved_tags` 使用說明 - 4/23 18:13 新增 `gen_rand_type()` 使用範例 - 4/22 13:31 新增 `gameboard` 使用範例 - 4/16 00:02 繳交壓縮檔檔名修正 - 4/15 23:28 新增 `check_eliminate()` 函式更多的說明。 - 4/15 23:07 修正 release 的一些錯誤，不會影響到同學們的程式碼正確性，可以安心服用。 ## 遊戲規則 ### 基礎介紹 - 有一個 $10 \times 10$ 的棋盤，棋盤上每個方格中都有不同顏色的寶石。玩家的目標是盡可能的使三個以上相同的寶石連成一條直線，只要滿足條件的寶石就會被消除，並且由上方的寶石來替補他們的位置，而最上方的寶石則會由隨機產生的合法寶石替補。若是替補過程中產生了新的直線，一樣會進行消除、週而復始。 - 玩家在每一輪操作中，可以選擇兩個相鄰的方格並交換裡面的寶石，如果交換寶石後可以消除，則會開始進行消除，否則為一次無效的操作。 - 當盤面上無法進行任何有效操作時，盤面會刷新。 ### 特殊寶石 - 十字寶石 **+**： - **生成**：四個相同的寶石連線並消除後，會立刻在「最後被移動的寶石」的位置產生一個同色的 **+**，並接著進行後續的掉落等程序，若是「最後被移動的寶石」有複數個，生成位置則在那些「最後被移動的寶石」中隨機產生。 - **功能**：在消去 **+** 時，會一併消除同行、列的所有字母。 - 閃電寶石 **z**： - **生成**：五個以上相同的寶石連成直線並消除後，會立刻在「最後被移動的寶石」的位置產生一個寶石 **z**，並接著進行後續的掉落等程序，若是「最後被移動的寶石」有複數個，生成位置則在那些「最後被移動的寶石」中隨機產生。 - **功能**：寶石 **z** 與相鄰的寶石替換時，不論是否產生連線皆為有效操作，替換後會消去自己以及所有與替換對象同種類的寶石。如果該寶石是被十字寶石觸發，消去的種類與該十字寶石相同；若是被不穩定寶石觸發，隨機選擇消去的種類。該寶石不能與寶石 **Q** 替換。如果與 **z** 交換則不會發動能力，只會讓兩個 **z** 消失而已。 - 不穩定寶石 **Q**： - **生成**：五個以上相同的寶石在消除時若是相鄰，且不滿足 **+** 或是 **z** 的生成條件，會立刻在「最後被移動的寶石」的位置產生一個寶石 **Q**，並接著進行後續的掉落等程序，若是「最後被移動的寶石」有複數個，生成位置則在那些「最後被移動的寶石」中隨機產生。 - **功能**：字母 **Q** 與相鄰的寶石替換時，不論是否產生連線皆為有效操作，替換時會消去自己以及周圍 5*5 範圍的所有寶石。但該寶石不能與寶石 **z** 替換。 ### 遊戲得分 - 原則上每消除一個寶石或生成一個特殊寶石+100，而combo數會讓加的分數變多，公式如下： $final\_score=basic\_score\times(1+{combo\over10})$ ### 遊戲模式 - 模式一：在有限步數中獲得最多分數。 - 模式二：用最少步數達到目標分數。 ## 編譯選項1：使用Dev-C++ - 打開Dev-C++，按左上角「檔案」&rarr;「開新檔案」&rarr;「專案」&rarr;「Empty Project」&rarr;「確定」 - 將專案存在一個你會記得在哪裡的地方。 - 在專案資料夾上按右鍵，選擇「New File」新增檔案。 ![](https://i.imgur.com/kBXTxXD.png) - 照著上一個步驟新增四個檔案，分別是`main.cpp`, `ai.cpp`, `splendor.hpp`和`splendor.cpp`。 - 接著就可以把[需要的檔案](https://drive.google.com/file/d/1OvJJCY5tymgTeRfKK3W73wx6JWJ5QjBJ/view?usp=sharing)下載下來後解壓縮，把程式碼複製到專案中同名的檔案內。 **注意：不能直接把解壓縮後的檔案搬移到專案資料夾內，那樣Dev-C++不會認為是屬於這份專案的檔案！** - 由於編譯這份專案需要使用C++ 2011版本，因此我們要修改編譯指令。點一下「工具」&rarr;「編譯器選項」。 ![](https://i.imgur.com/hft40mQ.png) - 接著把「呼叫編譯器時加入以下的命令」**左側格子打勾**，下方輸入`-std=c++11`，再按下確認，就可以讓dev-c++編譯時使用正確版本。 ![](https://i.imgur.com/Fse3lD7.png) - 寫好程式要編譯與執行時，按一下「編譯並執行」。如果跑出來的終端機一直是黑色的，沒有反應，就到專案所在位置把所有執行檔(副檔名`.exe`的檔案)都刪掉，再重新編譯與執行。 ![](https://i.imgur.com/cnNOqPe.png) ## 編譯選項2：手動安裝環境 ### Step 1. 安裝 `g++`, `make` 如果你已經可以在終端機中使用 `g++`, `make` 指令，請跳過這個步驟。 依照下列步驟安裝完畢後，請利用以下兩個指令測試： ```bash g++ -v make -v ``` 如果沒有報錯就沒有問題。 #### Windows user 在[這裡](https://github.com/skeeto/w64devkit/releases)下載 `w64devlit-x.xx.x.zip`，解壓縮後將裡面的 `bin` 這個目錄加進環境變數。然後重新開機。 #### Linux user 依照各個 package manager 相應的作法安裝。 #### Mac user 先參考[這裡](https://brew.sh/)安裝 homebrew (如果已經安裝請跳過) 然後 ```bash brew install gcc brew install make ``` ### Step 2. 下載作業檔案 把[需要的檔案](https://drive.google.com/drive/folders/1KjjUfWM2x-vIxUVlTWJGGneoIPCW0BHJ?usp=share_link)下載下來後解壓縮。 ### Step 3. 編譯程式碼 在解壓縮後的目錄中開啟終端機，並執行 `make` 即可。 如果要以 AI 模式進行編譯，請先改成執行 `make MODE=ai`。 每次要換模式編譯之前記得先執行 `make clean` 哦。 ### Step 4. 執行遊戲程式 編譯完成後，執行 `bin/main.exe` 就可以開始遊戲了！ ## 程式碼導覽 ### 程式碼架構 ```bash . ├── Makefile # Help compiling the source code ├── README.md # Introduction to this game └── src ├── ai.cpp # Your AI implementation ├── main.cpp # Main executor of the game ├── splendor.cpp # Implementation of required functions └── splendor.hpp # Prototype of required functions ``` ### 變數與函式介紹 #### 全域變數 - MODE_\*：遊戲模式 - EXIT：結束遊戲 - STEP：模式1，有限步數 - SCORE：模式2，目標分數 - BOARD_\*：棋盤屬性 - WIDTH：棋盤寬度 - HEIGHT：棋盤高度 - GEM_\*：寶石種類 - NULL：沒有寶石 - RUBY - LAPIZ - EMERALD - AMBER - AMETHYST - COLOR_\*：寶石顏色 - 表示同名寶石的顏色 - ABI_\*：寶石特殊效果 - NORMAL：一般寶石 - CROSS：十字寶石 **+** - BOMB：不穩定寶石 **Q** - KILLSAME：閃電寶石 **z** - DRAW_PAUSE_TIME：顯示盤面前等待的時間，單位是毫秒(ms)。 - STEP_LIMIT：模式1的步數限制。 - SCORE_TARGET：模式2的目標分數。 - RND_SEED：亂數種子碼，如果想要產生其他盤面請修改這裡的值。 #### Struct - Pos ```cpp struct Pos { int x, y; // The (x, y) position of certain gem. }; ``` - Gem ```cpp struct Gem { int type; // The type of gem, one of GEM_* constants. int ability; // The ability of gem, one of ABI_* constants. }; ``` - ElimiData ```cpp struct ElimiData { int total_elimi; // The number of gem eliminated. int mid_elimi; // The number of the line consist of three gem int rnd_cnt; // Moved gem count }; ``` - GemData ```cpp struct GemData { Pos pos; // Gem position Gem gem; // Gem attributes }; ``` #### <font color="#f00">工具函式介紹</font> - `gen_rand_type()`: 隨機回傳一個 $1$ 到 $5$ 的數字（剛好對應五種寶石的編號） - `dist_sq(Pos a, Pos b)`: 回傳兩個位置的距離平方 - `get_score()`: 回傳目前遊戲分數，由於原本沒有、但還滿必要的，所以需要的同學可以自己實做： 1. 在 `splender.hpp` 裡面加入 `int get_score()` 2. 在 `splender.cpp` 最下面加入 `int get_score() {return player_score;}` #### <font color="#f00">很重要的變數</font> - `gameboard[x][y]` ![](https://i.imgur.com/lCqU9KD.png) x 是由上到下、 y 是由左到右 ex. `gameboard[1][2]` 是藍色的寶石 - `moved_tags[x][y]`: 紀錄各個位置的寶石是否剛被移動過（用於決定特殊寶石生成的位置），如果位置為 $(x, y)$ 的寶石剛被移動過，`moved_tags[x][y]` 就會是 `true`， 反之則為 `false` ## TODO ### Task 0 (0pt) - 可以將你在各個 Task 中的想法、遇到的問題標示好題號後寫在 `report.pdf` 中，儘管寫錯了還是有機會獲得部份分哦。 ### Task 1-1 (6pt) - 實作`check_inboard`函式，檢查輸入的參數`t`的位置是否在盤面內，是的話回傳`true`，否則回傳`false`。 <font color="#f00">Hint: </font> ```= check_inboard ((x, y)): if x, y is between 1 and BOARD_HEIGHT, BOARD_WEIGHT respectively: return true else: return false ``` ### Task 1-2 (7pt) - 實作`check_eliminate`函式，檢查盤面上是否有可以消除的三點直線。如果有的話，把任意一個直線的中心點存在函式的參數`pos`中。(請參考`struct Pos`的定義) - <font color="#f00">這裡傳入的 `pos` 是一個 `Pos` 的指標，而且他有可能會是空指標 `nullptr`，如果是空指標的話，不用對中心位置進行任何處理，只需要回傳是否存在可消除的連線即可，修改 `pos` 的方式請參考下列片段：</font> ```c++ Pos pos = {1, 2}; Pos *pos_ptr = &pos; (*pos_ptr).x = 2; (*pos_ptr).y = 3; cout << pos.x << ' ' << pos.y << '\n'; // output: 2 3 ``` <font color="#f00">Hint: </font> ```= check_eliminate ((ret_x, ret_y)): for all (x, y) in board: if is_line(x, y): if we should return the pos: ret_x = x ret_y = y return true return false ``` ### Task 1-3 (7pt) - 實作`check_swap`函式，檢查輸入的兩個位置上的寶石交換後是否可以消除，是的話回傳`true`，否則回傳`false`。 - 請注意特殊寶石不一定要連線才能消除！ <font color="#f00">Hint: </font> ```= check_swap ((x1, y1), (x2, y2)): if at least one of the two position is not in-board: return false if they are not adjacent: return false if their ability are ABI_KILLSAME and ABI_BOMB: return false if only one of their type are ABI_KILLSAME or ABI_BOMB: return true ret = false swap gems at (x1, y1) and (x2, y2) if there are something can be eliminated: ret = true swap gems at (x1, y1) and (x2, y2) back return ret ``` ### Task 2-1 (5pt) - 實作`apply_bomb`函式，消除參數`pos`周圍 $5\times 5$ 範圍的寶石，如果有因此消除特殊寶石，需要遞迴發動該寶石的能力 ### Task 2-2 (5pt) - 實作`apply_killsame`函式，消除和參數`tar`對應寶石一樣顏色的寶石，如果有因此消除特殊寶石，需要遞迴發動該寶石的能力，請特別注意不同消除方式時的對應作法。 ### Task 2-3 (5pt) - 實作`apply_cross`函式，消除和參數`pos`同行及同列的寶石，如果有因此消除特殊寶石，需要遞迴發動該寶石的能力。 ### Task 2-4 (5pt) - 實作`apply_special`函式，根據參數`pos`對應的特殊寶石決定要呼叫`apply_bomb`、`apply_killsame`或是`apply_cross`。 ### Task 3 (10pt) - `dropping`函式中有bug，請你找出它藏在哪裡並修好它。 - 修復正確 (5pt) - edit distance $<= 15$ (3pt) - edit distance $<= 10$ (2pt) - edit distance $< 10$ (bonus: 2pt) > 什麼是 edit distance? 兩個字串 $A, B$ 的 edit distance 指的就是要把 $A$ 變成 $B$ 至少需要經過幾次（加入/刪除/更改）字元的操作。可以使用[這個網站](https://planetcalc.com/1721/)協助計算。 > 在計算 edit distance 時，我們會將空格與換行通通移除後比較。 ### Task 4 (50pt) **會在原始規則下進行評分，與 bonus 的創意題無關** - 請你設計一套演算法，根據當前盤面情況決定要移動哪兩個寶石以獲得最佳結果，例如用最少步數達到指定分數。 - 決定要移動的寶石後，請將兩個寶石的位置存在參數`pos1`和`pos2`中再結束函式。 - 在模式一中獲得 $1$ 分（10pt） - 在模式一中獲得 $6000$ 分（10pt） - 在模式一中獲得 $12000$ 分（5pt） - 在模式一中獲得 $15000$ 分 (5pt) - 在模式二中以 $30$ 步達成目標 (10pt) - 在模式二中獲得前 $10n\%, 1\le n\le 10, n\in\mathbb{N}$ 的排名 (n pt) - 在模式二中獲得 30000 分 (bonus: 5pt) - 在模式一中戰勝講師 ai (bonus: 4pt) - 在模式二中戰勝講師 ai (bonus: 4pt) <font color="#f00">另外，對於所有模式一的測試，時限皆為 10 秒，如果進行超過 10 秒，將會以 10 秒當下的分數作為最終分數。 而對於所有模式二的測試，時限皆為 30 秒，如果運行超過 30 秒，將會視為花費 31 步達成目標。 時限的計算不包含那些渲染時的等待時間，基本上不要暴力遞迴模擬應該都不會超過。</font> > 我們將會使用另外的固定種子碼來測試你們的 ai ，也就是說自己在測試的結果**不代表**你們會得到的成績。 > 為了降低運氣因素，兩種模式各會進行 3 次測試，取最高分作為成績。 ### Task Bonus-1 (10pt) - 發揮創意，新增一些酷酷的新功能吧！ - 請為新增的功能寫一份說明，放在 `report.pdf` 檔案中。 ## 繳交相關 ### 繳交格式 請繳交 `splendor.cpp`, `ai.cpp`, `report.pdf`, `main.cpp`, `splendor.hpp` 以及創意題新增的檔案，並壓縮成 zip 檔，壓縮後的檔名為 `[你的 judge id].zip` （不用中括號），解壓縮後的檔案架構應該長這樣： ```bash 9876 ├── ai.cpp ├── main.cpp ├── splendor.cpp ├── splendor.hpp ├── make_bomb_stronger_or_something_else.cpp └── report.pdf ``` 不可以包含 `*.exe`, `*.o` 等等的垃圾檔案 ### 繳交表單 [表單](https://docs.google.com/forms/d/e/1FAIpQLSdwRtDKVp1Ee1QcPDxhdxnGF5N5XcY3ZL6cd566Q20sianaXQ/viewform?usp=sf_link)。 交完後悔的話可以再重新編輯哦！ ### 死線 5/5 23:59 沒有遲交這回事。 ### 違規事項 - 繳交格式錯誤（-10pt） - 使用非正規方式操作 ai (-$\min(50, \text{your score in task 4})$pt) - 課程作業規範中所禁止的事項 (-?pt) ## FAQ ### Q: kill_same的random要怎麼用啊? A: 更新在 Spec 上囉 ### Q: 如果沒做完會怎樣嗎 A: 拿不到全部的分數、而分數會跟結業等等有些關係，詳情請參考課程介紹。但只要有寫就會有一些部份分，有時候最關鍵的就是這幾分，所以很鼓勵各位同學盡自己所能的推進大作業進度ㄛ ### Q: 一定要相鄰才能交換嗎? A: Yes ### Q: 希望可以有遊戲的執行檔可以看執行起來是什麼樣子，當作對照組 A: 無法，講師這裡編出來的東西不一定能在同學們的作業系統上跑。有對照需求的話可以參考講師上傳的影片 ### Q: 還沒想好ai的部分怎辦 A: 可以多加利用 Task 1 寫出來的工具函式哦！順帶一提，由於評分時我們會使用我們自己的 `splendor.cpp`, `splendor.hpp`，所以就算 Task 1, 2, 3 沒有寫出來，也可以使用那些工具函式來完成哦（只是沒辦法測試） ### Q: 大作業跟段考、備審 blablabla 的都好近 A: 據說是考量到我們早點改完、證書早點發可能來得及讓你們放備審，~~而且我也一樣燒，大作業 release 那周是我段考周，根本森林大火~~。 ### Q: 之前有幾堂課聽不懂... A: 有什麼問題都可以在 dc 上發問哦，不管是對課程還是對作業的問題都可以，講師們都很樂意提供協助～（不要害羞～ DC 應該滿匿名的 ### Q: 大作業如果用vscode編譯，要從哪裡測試遊戲🤔️ ~~可以先教我怎麼用 vscode 編譯嗎？ vscode 是編輯器餒。~~ 理論上在 vscode 的終端機也是可以使用 `make` 來編譯、然後下 `bin/main.exe` 來執行，但畫面的部份不保證安好。 建議還是另外在作業的根目錄下開終端機來跑會比較好一點 #### Mode 2 累積分數 14 竹區 葉南俊+7 14 竹區 陳明揚+7 9 竹區 劉亮渝+8 6 北區 廖培君+10 6 北區 賴柏岑+10 11 北區 張以緹+8 6 北區 張九勻+10 8 北區 陳慶鴻+9 11 北區 張以靖+8 8 北區 蕭立安+9 12 北區 彭博礫+8 7 北區 李瑞茵+9 6 北區 楊晉宇+10 14 北區 劉起維+7 13 北區 陳詣安+8 6: 4(100%) 7: 1(93%) 8: 2(91%) 9: 1(87%) 11: 2(85%) 12: 1(82%) 13: 1(80%) 14: 3(78%) 31: 40(0%)