代码： 全选
這是一段極具挑戰性且對效能要求極高的演算法！你的核心邏輯已經建立得非常好，利用 `Int32Array` 和位元運算來壓縮座標與狀態，大幅減少了記憶體分配 (GC) 帶來的負擔。
針對你提出的計分規則，這本質上是一個**帶有依賴轉移的動態規劃 (DP) / 深度優先搜尋 (DFS)** 問題。為了達到極致效能，我們可以採用以下策略：
1. **全圖單次掃描**：只掃描一次找出所有藍色棋子，避免重複遍歷。
2. **狀態記憶化 (Memoization)**：將 `(起始列, 起始欄, 玩家, 層級)` 壓成單一整數（或字串）作為 Key 進行快取，因為「同層遞推」會導致大量重複檢查。
3. **位元提取**：完全利用你定義的 `_getPlayer`, `_getType` 來快速拆解 `val`。
以下是為你優化的 `calculateScores` 實現，以及一個可直接執行的 HTML 視覺化/測試工具。
### 1. 高效 `calculateScores` 實現
將這段程式碼替換進你的 `TriangleStrategyGame` 類別中：
```javascript
/**
* 高效計算雙方得分 (O(N) N為藍色棋子數量)
* 利用記憶化遞迴與位元運算，避免重複計算同層依賴
*/
calculateScores() {
let scores = [0, 0];
const bluePieces = [];
// 1. 找出所有藍色棋子 (利用 Chunk 遍歷，避開全圖)
for (const [chunkKey, chunk] of this.board.chunks.entries()) {
const chunkR = chunkKey >> 16;
const chunkC = (chunkKey << 16) >> 16;
for (let i = 0; i < 1024; i++) {
const val = chunk[i];
if (val !== 0 && this._getType(val) === 0) {
const r = (chunkR << 5) + (i >> 5);
const c = (chunkC << 5) + (i & 31);
// 藍色棋子佔兩格，只記錄 parity 為 0 (左側) 的座標，避免重複計算
if (((r + c) & 1) === 0) {
bluePieces.push({ r, c, p: this._getPlayer(val) });
}
}
}
}
// 2. 記憶化快取：避免同層遞迴重複計算
// Key: `${R}_${C}_${layerIndex}`
const memo = new Map();
/**
* 檢查特定層是否為「滿層」
* 回傳 Boolean
*/
const isLayerFull = (startR, startC, player, layerIndex) => {
const key = `${startR}_${startC}_${layerIndex}`;
if (memo.has(key)) return memo.get(key);
// dir: 我方(0)往下(+1)，對方(1)往上(-1)
// 位元技巧：若 player 為 0，(player << 1) - 1 = -1。這裡直接用三元運算子較清晰
const dir = player === 0 ? 1 : -1;
const R = startR + (layerIndex * dir);
const C_start = startC - layerIndex;
const C_end = startC + 1 + layerIndex;
let redCount = 0;
let orangeCount = 0;
let blues = [];
let hasEmpty = false;
for (let c = C_start; c <= C_end; c++) {
const val = this.board.get(R, c);
if (val === 0) {
hasEmpty = true;
break;
}
const type = (val >> 4) & 15;
if (type === 1) redCount++;
else if (type === 2) orangeCount++;
else if (type === 0) {
// 提取藍棋左側座標作為唯一識別
const parity = (R + c) & 1;
const blueLeftC = parity === 0 ? c : c - 1;
let found = false;
for (let i = 0; i < blues.length; i++) {
if (blues[i].c === blueLeftC) { found = true; break; }
}
if (!found) blues.push({ c: blueLeftC, p: val >> 8 });
}
}
// 斷層直接出局
if (hasEmpty) {
memo.set(key, false);
return false;
}
let full = false;
// 條件 A：1紅 (2格) + 1橙 (2格) = 滿層 (只有 layer 1 有可能 4 格)
if (redCount === 2 && orangeCount === 2 && blues.length === 0) {
full = true;
}
// 條件 B：同層依賴 (交由同層藍棋的第 1 層決定)
else if (blues.length > 0) {
for (let i = 0; i < blues.length; i++) {
if (isLayerFull(R, blues[i].c, blues[i].p, 1)) {
full = true;
break;
}
}
}
memo.set(key, full);
return full;
};
/**
* 計算從某一層開始的連續滿層分數
*/
const getConsecutiveScore = (startR, startC, player, layerIndex) => {
if (isLayerFull(startR, startC, player, layerIndex)) {
return 1 + getConsecutiveScore(startR, startC, player, layerIndex + 1);
}
return 0;
};
// 3. 為每個藍色棋子計算總分
for (let i = 0; i < bluePieces.length; i++) {
const bp = bluePieces[i];
scores[bp.p] += getConsecutiveScore(bp.r, bp.c, bp.p, 1);
}
return scores;
}
```
---
### 2. 棋局資料格式建議與 HTML 視覺化工具
你原本提到的 `[(0,0),(1,0)] [(0,-1),(0,-2)]` 雖然直觀，但在程式處理上缺乏玩家(Player)**與**棋子類型(Type)的資訊，這會導致無法使用 `_encodeCell`。
**強烈建議使用自定義字串格式 (CSV Style)：**
`Player,Type,R1,C1,R2,C2`
例如：`0,0,0,0,0,1` 代表 `玩家0 (我方), 藍色棋子, 佔據(0,0)與(0,1)`。這不僅容易 parse，且完美契合你的資料結構。
以下是完整的 HTML 測試工具（你可以直接存成 `.html` 檔案在瀏覽器打開）。它包含了你的核心邏輯，並提供了輸入與結果輸出的介面。
```html
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Triangle Strategy Game - Engine Test</title>
<style>
body { font-family: system-ui, -apple-system, sans-serif; padding: 20px; background: #f5f7fa; color: #333; }
.container { max-width: 800px; margin: 0 auto; background: white; padding: 20px; border-radius: 8px; box-shadow: 0 4px 6px rgba(0,0,0,0.1); }
textarea { width: 100%; height: 120px; padding: 10px; font-family: monospace; border: 1px solid #ccc; border-radius: 4px; box-sizing: border-box; }
.controls { margin-top: 15px; display: flex; gap: 10px; align-items: center; flex-wrap: wrap; }
select, button { padding: 8px 12px; font-size: 14px; border-radius: 4px; border: 1px solid #ccc; }
button { background: #007bff; color: white; border: none; cursor: pointer; transition: 0.2s; }
button:hover { background: #0056b3; }
.output { margin-top: 20px; padding: 15px; background: #282c34; color: #61dafb; border-radius: 4px; font-family: monospace; white-space: pre-wrap; }
.help-text { font-size: 13px; color: #666; margin-bottom: 10px; }
</style>
</head>
<body>
<div class="container">
<h2>UltraFast Triangle Grid Engine</h2>
<div class="help-text">
<strong>輸入格式：</strong>每行一個棋子，格式為 <code>玩家,類型,R1,C1,R2,C2</code><br>
(玩家: 0=我方, 1=敵方 | 類型: 0=藍, 1=紅, 2=橙)
</div>
<textarea id="boardInput" placeholder="0,0,0,0,0,1 1,1,1,0,2,0"></textarea>
<div class="controls">
<button onclick="runScoring()">計算雙方分數</button>
<span style="color: #ccc;">|</span>
<select id="simPlayer">
<option value="0">玩家 0 (我方)</option>
<option value="1">玩家 1 (敵方)</option>
</select>
<select id="simType">
<option value="0">藍棋 (0)</option>
<option value="1">紅棋 (1)</option>
<option value="2">橙棋 (2)</option>
</select>
<button onclick="runValidMoves()" style="background: #28a745;">取得合法落子座標</button>
</div>
<div id="output" class="output">等待指令...</div>
</div>
<script>
// === 將你原本的 class 與上方提供的 calculateScores 實作貼在此處 ===
class UltraFastTriangleGrid {
constructor() { this.chunks = new Map(); }
_getCoordinates(r, c) {
const chunkR = r >> 5; const chunkC = c >> 5;
const localR = r & 31; const localC = c & 31;
const localIndex = (localR << 5) | localC;
const chunkKey = (chunkR << 16) | (chunkC & 0xFFFF);
return { chunkKey, localIndex };
}
set(r, c, val) {
const { chunkKey, localIndex } = this._getCoordinates(r, c);
if (val !== 0) {
let chunk = this.chunks.get(chunkKey);
if (!chunk) { chunk = new Int32Array(1024); this.chunks.set(chunkKey, chunk); }
chunk[localIndex] = val;
} else {
const chunk = this.chunks.get(chunkKey);
if (chunk) chunk[localIndex] = 0;
}
}
get(r, c) {
const { chunkKey, localIndex } = this._getCoordinates(r, c);
const chunk = this.chunks.get(chunkKey);
return chunk ? chunk[localIndex] : 0;
}
getNeighbors(r, c) {
const neighbors = [ ((r - 1) << 16) | (c & 0xFFFF), ((r + 1) << 16) | (c & 0xFFFF) ];
if (((r + c) & 1) === 0) neighbors.push((r << 16) | ((c + 1) & 0xFFFF));
else neighbors.push((r << 16) | ((c - 1) & 0xFFFF));
return neighbors;
}
}
class TriangleStrategyGame {
constructor() {
this.board = new UltraFastTriangleGrid();
this.pieceCount = 0;
this.floodQueue = new Int32Array(2048);
this.visited = new Uint8Array(65536);
}
_encodeCell(player, pieceType, pieceId) { return (player << 8) | (pieceType << 4) | pieceId; }
_getPlayer(val) { return val >> 8; }
_getType(val) { return (val >> 4) & 15; }
_getId(val) { return val & 15; }
_packCoord(r, c) { return (r << 16) | (c & 0xFFFF); }
_unpackR(coord) { return coord >> 16; }
_unpackC(coord) { return (coord << 16) >> 16; }
calculateScores() {
let scores = [0, 0];
const bluePieces = [];
for (const [chunkKey, chunk] of this.board.chunks.entries()) {
const chunkR = chunkKey >> 16;
const chunkC = (chunkKey << 16) >> 16;
for (let i = 0; i < 1024; i++) {
const val = chunk[i];
if (val !== 0 && this._getType(val) === 0) {
const r = (chunkR << 5) + (i >> 5);
const c = (chunkC << 5) + (i & 31);
if (((r + c) & 1) === 0) {
bluePieces.push({ r, c, p: this._getPlayer(val) });
}
}
}
}
const memo = new Map();
const isLayerFull = (startR, startC, player, layerIndex) => {
const key = `${startR}_${startC}_${layerIndex}`;
if (memo.has(key)) return memo.get(key);
const dir = player === 0 ? 1 : -1;
const R = startR + (layerIndex * dir);
const C_start = startC - layerIndex;
const C_end = startC + 1 + layerIndex;
let redCount = 0; let orangeCount = 0;
let blues = []; let hasEmpty = false;
for (let c = C_start; c <= C_end; c++) {
const val = this.board.get(R, c);
if (val === 0) { hasEmpty = true; break; }
const type = (val >> 4) & 15;
if (type === 1) redCount++;
else if (type === 2) orangeCount++;
else if (type === 0) {
const parity = (R + c) & 1;
const blueLeftC = parity === 0 ? c : c - 1;
let found = false;
for (let i = 0; i < blues.length; i++) {
if (blues[i].c === blueLeftC) { found = true; break; }
}
if (!found) blues.push({ c: blueLeftC, p: val >> 8 });
}
}
if (hasEmpty) { memo.set(key, false); return false; }
let full = false;
if (redCount === 2 && orangeCount === 2 && blues.length === 0) full = true;
else if (blues.length > 0) {
for (let i = 0; i < blues.length; i++) {
if (isLayerFull(R, blues[i].c, blues[i].p, 1)) {
full = true; break;
}
}
}
memo.set(key, full); return full;
};
const getConsecutiveScore = (startR, startC, player, layerIndex) => {
if (isLayerFull(startR, startC, player, layerIndex)) {
return 1 + getConsecutiveScore(startR, startC, player, layerIndex + 1);
}
return 0;
};
for (let i = 0; i < bluePieces.length; i++) {
const bp = bluePieces[i];
scores[bp.p] += getConsecutiveScore(bp.r, bp.c, bp.p, 1);
}
return scores;
}
// (為了保持範例可執行，假設 getValidMoves 已完整實作)
getValidMoves(pieceType, player) { return /* 依據你的代碼回傳 */ []; }
}
// === 結束 ===
let game = null;
function parseBoard() {
game = new TriangleStrategyGame();
const lines = document.getElementById('boardInput').value.split('\n');
let idCounter = 1;
lines.forEach(line => {
const parts = line.split(',').map(s => parseInt(s.trim()));
if (parts.length === 6 && !parts.some(isNaN)) {
const [player, type, r1, c1, r2, c2] = parts;
const encoded = game._encodeCell(player, type, idCounter++);
game.board.set(r1, c1, encoded);
game.board.set(r2, c2, encoded);
}
});
}
function runScoring() {
parseBoard();
const t0 = performance.now();
const scores = game.calculateScores();
const t1 = performance.now();
document.getElementById('output').innerText =
`【計分結果】\n玩家 0 分數: ${scores[0]}\n玩家 1 分數: ${scores[1]}\n\n(耗時: ${(t1 - t0).toFixed(3)} ms)`;
}
function runValidMoves() {
parseBoard();
const player = parseInt(document.getElementById('simPlayer').value);
const type = parseInt(document.getElementById('simType').value);
const t0 = performance.now();
// 若使用你的完整代碼，這裡會呼叫 getValidMoves
// const moves = game.getValidMoves(type, player);
const t1 = performance.now();
// document.getElementById('output').innerText =
// `【合法落子點 (Player ${player}, Type ${type})】\n共找到 ${moves.length} 種下法。\n\n(耗時: ${(t1 - t0).toFixed(3)} ms)`;
document.getElementById('output').innerText = "由於範例省略了 getValidMoves 的實作細節，請將你原先寫好的 getValidMoves 貼入 HTML 的 class 中以啟用此功能。";
}
</script>
</body>
</html>
```
代码： 全选
抱歉，在先前的回覆中為了專注於計分邏輯與 HTML 介面，我省略了 `getValidMoves` 的具體實作。
你原本的設計思路非常精確！利用奇偶性（Parity）來過濾形狀，並透過 Flood-fill 偵測死胡同，是維持高效能的絕佳策略。
以下為你補齊完整且經過優化的 `getValidMoves`，以及與其配套的 `_formsHole` 方法。你可以直接將這兩個方法放入你的 `TriangleStrategyGame` 類別中。
### 完整 `getValidMoves` 與 `_formsHole` 實作
```javascript
/**
* 高效找出棋子能落下的所有合法座標對
* @param {number} pieceType - 0(藍), 1(紅), 2(橙)
* @param {number} player - 0(我方), 1(敵方)
* @returns {Array} - 回傳格式為 [[r1, c1, r2, c2], ...]
*/
getValidMoves(pieceType, player) {
const validMoves = [];
const checked = new Set();
const edgeEmpties = [];
let hasPieces = false;
// 1. 找出所有與現有棋子相鄰的「邊緣空位」
for (const [chunkKey, chunk] of this.board.chunks.entries()) {
const chunkR = chunkKey >> 16;
const chunkC = (chunkKey << 16) >> 16; // 確保保留負號
for (let i = 0; i < 1024; i++) {
if (chunk[i] !== 0) {
hasPieces = true;
const r = (chunkR << 5) + (i >> 5);
const c = (chunkC << 5) + (i & 31);
const neighbors = this.board.getNeighbors(r, c);
for (let n of neighbors) {
if (this.board.get(this._unpackR(n), this._unpackC(n)) === 0) {
edgeEmpties.push(n);
}
}
}
}
}
// 開局特判：如果棋盤全空，預設允許下在原點 (0,0) 附近
if (!hasPieces) {
edgeEmpties.push(this._packCoord(0, 0));
}
// 2. 針對每個邊緣空位，尋找符合棋子形狀的相鄰空位
for (let coord1 of edgeEmpties) {
const r1 = this._unpackR(coord1);
const c1 = this._unpackC(coord1);
const parity = (r1 + c1) & 1;
let possibleR2 = null;
let possibleC2 = null;
// 根據奇偶性與要求形狀決定第二個三角形
// 統一由特定的 Parity 作為起點搜尋，避免同一種下法被正反掃描兩次
if (pieceType === 0) {
// 藍棋 (水平)：偶數(尖端朝上) 往右找奇數
if (parity === 0) { possibleR2 = r1; possibleC2 = c1 + 1; }
} else if (pieceType === 1) {
// 紅棋 (垂直)：偶數(尖端朝上) 往下找奇數
if (parity === 0) { possibleR2 = r1 + 1; possibleC2 = c1; }
} else if (pieceType === 2) {
// 橙棋 (垂直)：奇數(尖端朝下) 往下找偶數
if (parity === 1) { possibleR2 = r1 + 1; possibleC2 = c1; }
}
if (possibleR2 !== null && possibleC2 !== null) {
if (this.board.get(possibleR2, possibleC2) === 0) {
const coord2 = this._packCoord(possibleR2, possibleC2);
// 使用字串當 Key 去重，確保不會重複運算相同的座標組合
const moveKey = (coord1 > coord2) ? `${coord1}_${coord2}` : `${coord2}_${coord1}`;
if (!checked.has(moveKey)) {
checked.add(moveKey);
// 3. 執行空洞檢測
if (!this._formsHole(coord1, coord2)) {
// 解壓縮座標方便外部直接使用
validMoves.push([r1, c1, possibleR2, possibleC2]);
}
}
}
}
}
return validMoves;
}
/**
* 空洞檢測：純數字堆疊 Flood-fill，零物件配置
* 原理：假設落下這兩子，其周圍的空位如果無法向外擴散超過 40 步 (棋盤最大延伸極限)，即視為死胡同(空洞)
*/
_formsHole(c1, c2) {
// 暫時放置標記 (用 -1 代表虛擬佔用，避免與真實棋子混淆)
this.board.set(this._unpackR(c1), this._unpackC(c1), -1);
this.board.set(this._unpackR(c2), this._unpackC(c2), -1);
let isHole = false;
const neighborsToTest = [
...this.board.getNeighbors(this._unpackR(c1), this._unpackC(c1)),
...this.board.getNeighbors(this._unpackR(c2), this._unpackC(c2))
];
for (let startNode of neighborsToTest) {
if (this.board.get(this._unpackR(startNode), this._unpackC(startNode)) !== 0) continue;
// 清理 visited 陣列
this.visited.fill(0);
let head = 0;
let tail = 0;
this.floodQueue[tail++] = startNode;
// 將座標映射到 0~255 範圍作為 visited 索引
const baseR = this._unpackR(startNode) + 128;
const baseC = this._unpackC(startNode) + 128;
this.visited[(baseR << 8) | baseC] = 1;
let count = 0;
let escaped = false;
while (head < tail) {
const curr = this.floodQueue[head++];
count++;
// 擴散超過 40 步，視為連通外部，未形成空洞
if (count > 40) {
escaped = true;
break;
}
const nR = this._unpackR(curr);
const nC = this._unpackC(curr);
const nexts = this.board.getNeighbors(nR, nC);
for (let n of nexts) {
if (this.board.get(this._unpackR(n), this._unpackC(n)) === 0) {
const vR = this._unpackR(n) - this._unpackR(startNode) + 128;
const vC = this._unpackC(n) - this._unpackC(startNode) + 128;
const vIdx = (vR << 8) | vC;
// 只檢查邊界內的相對座標
if (vR >= 0 && vR < 256 && vC >= 0 && vC < 256 && this.visited[vIdx] === 0) {
this.visited[vIdx] = 1;
this.floodQueue[tail++] = n;
}
}
}
}
// 如果有任何一個周圍空格無法逃逸，代表形成了死胡同
if (!escaped) {
isHole = true;
break;
}
}
// 復原棋盤
this.board.set(this._unpackR(c1), this._unpackC(c1), 0);
this.board.set(this._unpackR(c2), this._unpackC(c2), 0);
return isHole;
}
```
### HTML 更新提醒
若你將上述程式碼貼入先前提供的 HTML 測試工具中，請找到 `runValidMoves()` 函式，將被註解掉的程式碼解開替換：
```javascript
function runValidMoves() {
parseBoard();
const player = parseInt(document.getElementById('simPlayer').value);
const type = parseInt(document.getElementById('simType').value);
const t0 = performance.now();
const moves = game.getValidMoves(type, player);
const t1 = performance.now();
// 格式化輸出前 10 筆結果避免畫面過載
const movesText = moves.slice(0, 10)
.map(m => `(${m[0]}, ${m[1]}) 與 (${m[2]}, ${m[3]})`)
.join('\n');
let outputStr = `【合法落子點 (Player ${player}, Type ${type})】\n共找到 ${moves.length} 種下法。\n\n`;
if (moves.length > 0) outputStr += `前 10 種下法範例：\n${movesText}\n\n`;
outputStr += `(耗時: ${(t1 - t0).toFixed(3)} ms)`;
document.getElementById('output').innerText = outputStr;
}
```
