---
tags: 2022 iThome 鐵人賽
title: 9/18 Arcade也能學演算法Ouo!? 演算法遊戲(1)
AUTHOR: 鍾佳龍
---
# Arcade再進化
## Arcade也能學演算法Ouo!? 演算法遊戲!
### **第一篇：油漆桶遊戲-演算法篇**
> ### 大綱
> * 遊戲內容
> * 經典演算法-Flood fill
> * 自製演算法-地圖生成
> ## 成果預覽
在arcade的效果
在console的效果
> ## 經典演算法Flood fill
Flood fill 是什麼阿
Flood fill是一個用在圖像渲染的簡單演算法
藉由遞迴搜尋周圍相同顏色的單位對其執行動作
下面是演算法示意圖
> 上圖是由 André Karwath aka Aka - 自己的作品, CC BY-SA 2.5
> https://commons.wikimedia.org/w/index.php?curid=481651
接下來就上程式碼吧
```javascript
function flood_fill(old, chg, x, y) { // old: 舊顏色, chg: 新顏色, x: x座標, y: y座標
if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
return
}
if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
map[x][y] = chg; // 改變顏色
if (x > 0) {
flood_fill(old, chg, x - 1, y);
}
if (x < map.length - 1) {
flood_fill(old, chg, x + 1, y);
}
if (y > 0) {
flood_fill(old, chg, x, y - 1);
}
if (y < map.length - 1) {
flood_fill(old, chg, x, y + 1);
}
} else {
return;
}
}
```
**解析一下**
> 有些人可能不知道什麼是遞迴，在這邊補充一下，
> 簡單來說遞迴就是在函式內呼叫函式本身，
> 透過不斷疊層後達成目的
首先
```javascript
if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
return
}
```
這邊主要是做個防呆，避免重複執行浪費資源，節省不必要的錯誤。
```javascript
if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
map[x][y] = chg; // 改變顏色
if (x > 0) {
flood_fill(old, chg, x - 1, y);
}
if (x < map.length - 1) {
flood_fill(old, chg, x + 1, y);
}
if (y > 0) {
flood_fill(old, chg, x, y - 1);
}
if (y < map.length - 1) {
flood_fill(old, chg, x, y + 1);
}
} else {
return;
}
```
這邊就是演算法本人拉
往周圍尋找，尋找相鄰的是不是同一種的。
前文提到Flood fill是尋找周圍相同性質的單位並對其執行動作。
我們是填色遊戲，目的是變成相同顏色，所以我用`map[x][y] = chg`來改變這個像素的顏色，然後往四周尋找。
如果找的地方不是跟原來相同性質的，就代表遇到邊界了所以原地折返
> ## 自製地圖生成演算法
既然地圖不是亂數生成，特別寫一個演算法那就要有要達成的目的。
我想要做到
1. 可以控制顏色的數量
2. 可以設定顏色的分散程度
想好之後就來動工拉 先設定參數
```javascript
color_number = 9;
dispersion = 0.9;
map_width = 10;
map_height = 10;
```
由上到下 依序是顏色的數量 分散的程度 地圖的寬和高
有了參數之後先生成空白地圖
```javascript
var map = [];
for (let i = 0; i < map_width; i++) {
map.push([]);
for (let j = 0; j < map_height; j++) {
map[i].push(0);
}
}
```
這樣 你就得到了一個叫做map的10\*10陣列了
再來我還需要做一件事，那就是生成隨機的圖塊。
```javascript
function make_area(x, y, area_color, count) {
let now_x = x;
let now_y = y;
for (let i = 0; i < count; i++) {
...
}
}
```
我的想法是從一個起始點開始，接著讓那個點移動。
移動的路徑就是生成的圖塊，生成的次數則由`count`控制
```javascript
if (map[now_x][now_y] == area_color) {
i+1;
}
map[now_x][now_y] = area_color;
```
如果剛好找到的點是相同顏色的 則不計數
然後利用`map[now_x][now_y] = area_color`來上色
最後就是在找個方向延伸下去
```javascript
function make_area(x, y, area_color, count) {
let now_x = x;
let now_y = y;
for (let i = 0; i < count; i++) {
if (map[now_x][now_y] == area_color) {
i+1;
}
map[now_x][now_y] = area_color;
let direction = Math.floor(Math.random() * 4);
if (direction == 0 && now_x > 0) {
now_x -= 1;
} else if (direction == 1 && now_x < map.length - 1) {
now_x += 1;
} else if (direction == 2 && now_y > 0) {
now_y -= 1;
} else if (direction == 3 && now_y < map.length - 1) {
now_y += 1;
}
}
}
```
這邊用到js的math
`Math.random()` 可以生成0-1之間的數，乘以x再取整就可以獲得0到x-1的數了
---
最後讓我們利用今天所學，做一個console遊戲當作今天的結尾吧
```javascript=
/*
* AUTHOR rlongdragon
* DATE 2022-09-16
* VISON 1.0
*
* this probject used copilot
*/
//import
const readline = require("readline"); // 載入readline模組
//set up
color_number = 3; // 色彩的數量
dispersion = 0.5; // 分散度
map_width = 20; // 地圖寬度
map_height = 20; // 地圖高度
// 地圖初始化
var map = [];
for (let i = 0; i < map_width; i++) {
map.push([]);
for (let j = 0; j < map_height; j++) {
map[i].push(0);
}
}
// 生成斑點
function make_area(x, y, area_color, count) {
let now_x = x; // 生成斑點的x座標
let now_y = y; // 生成斑點的y座標
for (let i = 0; i < count; i++) { // 嘗試生成count次
if (map[now_x][now_y] == area_color) { // 如果已經是目標顏色，則不再生成
i + 1;
}
map[now_x][now_y] = area_color; // 生成斑點
let direction = Math.floor(Math.random() * 4); // 隨機製造下次生成的方向
if (direction == 0 && now_x > 0) {
now_x -= 1;
} else if (direction == 1 && now_x < map.length - 1) {
now_x += 1;
} else if (direction == 2 && now_y > 0) {
now_y -= 1;
} else if (direction == 3 && now_y < map.length - 1) {
now_y += 1;
}
}
}
// 地圖生成
function create_map() {
for (let i = 0; i < map.length; i++) {
for (let j = 0; j < map.length; j++) {
if (Math.random() > dispersion * 0.95) { // 有機率生成斑點
make_area(i, j, Math.floor(Math.random() * color_number), Math.floor((Math.random() + 1) * 5) * dispersion);
}
}
}
}
// 輸出地圖
function print_map(map) {
for (let i = 0; i < map.length; i++) { // 輸出地圖
let row = ""; // 一行的字串
for (let j = 0; j < map.length; j++) { // 輸出一行
if (j == map.length - 1) { // 如果是最後一個，則不加空格
row += map[i][j]; // 加入地圖的數字
} else { // 如果不是最後一個，則加空格
row += map[i][j] + " "; // 加入地圖的數字
}
}
console.log(row);
}
}
//flood fill 演算法
function flood_fill(old, chg, x, y) { // old: 舊顏色, chg: 新顏色, x: x座標, y: y座標
if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
return
}
if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
map[x][y] = chg; // 改變顏色
if (x > 0) {
flood_fill(old, chg, x - 1, y);
}
if (x < map.length - 1) {
flood_fill(old, chg, x + 1, y);
}
if (y > 0) {
flood_fill(old, chg, x, y - 1);
}
if (y < map.length - 1) {
flood_fill(old, chg, x, y + 1);
}
} else {
return;
}
}
// 檢查是否結束
function check_end() {
let end = true;
color = map[0][0]; // 設定初始顏色
for (let i = 0; i < map.length; i++) {
for (let j = 0; j < map.length; j++) {
if (map[i][j] != color) { // 如果有不同的顏色，則還沒結束
end = false;
return end;
}
}
}
return end;
}
//main
create_map(); // 生成地圖
print_map(map); // 輸出地圖
var rl = readline.createInterface({ // 載入readline模組
input: process.stdin,
output: process.stdout
});
rl.on('line', function (line) { // 輸入
let color = parseInt(line); // 輸入的顏色
flood_fill(map[0][0], color, 0, 0); // 塗色
print_map(map); // 輸出地圖
if (check_end()) { // 檢查是否結束
console.log("you win");
process.exit(); // 結束程式
}
});
```
---
> ## 下期預告
> **油漆桶遊戲-實作篇**
> \>\_將理論實踐到Arcade 發生什麼事呢
>
###### AUTHOR：rlongdragon
Sign in with Wallet
Connect another wallet