可以發(fā)現(xiàn)，這種算法，位置編號(hào)小的比位置編號(hào)大的少了一位。也就是說，我們應(yīng)該盡量把出現(xiàn)頻率較高的位置放在前面。

生成各棋子的位置列表

const RedAllCandidates = new Array(90).fill(0).map((a, i) => 89 - i);const BlackAllCandidates = new Array(90).fill(0).map((a, i) => i);const RedSoliderCandidates = new Array(45).fill(0).map((a, i) => 44 - i);const BlackSoliderCandidates = new Array(45).fill(0).map((a, i) => 45 + i);// 分別是將、士、士、……const PieceCandidates = [  [85, 86, 84, 76, 77, 75, 67, 68, 66, 127],  [127, 86, 84, 76, 68, 66],  [127, 84, 86, 76, 66, 68],  [127, 87, 67, 71, 51, 83, 47, 63],  [127, 83, 67, 63, 47, 87, 51, 71],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, ...RedAllCandidates],  [127, 62, 53, ...RedSoliderCandidates],  [127, 60, 51, ...RedSoliderCandidates],  [127, 58, 49, ...RedSoliderCandidates],  [127, 56, 47, ...RedSoliderCandidates],  [127, 54, 45, ...RedSoliderCandidates],  [4, 3, 5, 13, 12, 14, 22, 21, 23, 127],  [127, 3, 5, 13, 21, 23],  [127, 5, 3, 13, 23, 21],  [127, 2, 22, 18, 38, 6, 42, 26],  [127, 6, 22, 26, 42, 2, 38, 18],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, ...BlackAllCandidates],  [127, 27, 36, ...BlackSoliderCandidates],  [127, 29, 38, ...BlackSoliderCandidates],  [127, 31, 40, ...BlackSoliderCandidates],  [127, 33, 42, ...BlackSoliderCandidates],  [127, 35, 44, ...BlackSoliderCandidates],];

解釋：

提前計(jì)算log

為了提高效率，我應(yīng)該避免在JS中計(jì)算Math.log2，而要提前定義好運(yùn)算結(jié)果。

const ceilLog2Map = new Map([  [1, 0],  [2, 1],  [3, 2],  [4, 2],  [6, 3],  [8, 3],  [10, 4],  [17, 5],  [48, 6],  [91, 7],]);const floorLog2Map = new Map([  [1, 0],  [2, 1],  [3, 1],  [4, 2],  [6, 2],  [8, 3],  [10, 3],  [17, 4],  [48, 5],  [91, 6],]);

按照編碼規(guī)則encode

基于文章《JS 按自定義格式 拼接二進(jìn)制串 解析二進(jìn)制串》提到的concatBits函數(shù)，我寫了concatFlexibleBits函數(shù)：

function concatFlexibleBits(current: number, offset: number, candidateIndex: number, candidateLength: number): [number, number, number[]] {  const floorLog = floorLog2Map.get(candidateLength)!;  const ceilLog = ceilLog2Map.get(candidateLength)!;  const last = 2 ** floorLog;  const beyond = candidateLength - last;  if (floorLog === ceilLog || candidateIndex < last - beyond) {    return concatBits(current, offset, candidateIndex, floorLog);  }  let newCurrent = current;  let newOffset = offset;  const array: number[] = [];  let newUint8: number[];  if (candidateIndex < last) {    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, candidateIndex, floorLog);    array.push(...newUint8);    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, 0, 1);    array.push(...newUint8);  } else {    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, candidateIndex - beyond, floorLog);    array.push(...newUint8);    [newCurrent, newOffset, newUint8] = concatBits(newCurrent, newOffset, 1, 1);    array.push(...newUint8);  }  return [newCurrent, newOffset, array];}

這里encode規(guī)則，就是按照上面提到的算法實(shí)現(xiàn)的。不過多解釋了。

按照編碼規(guī)則decode

基于文章《JS 按自定義格式 拼接二進(jìn)制串 解析二進(jìn)制串》的readBits函數(shù)，我寫了readFlexibleBits函數(shù)：

function readFlexibleBits(array: Uint8Array, bitsOffset: number, candidateLength: number) {  const floorLog = floorLog2Map.get(candidateLength)!;  const ceilLog = ceilLog2Map.get(candidateLength)!;  const last = 2 ** floorLog;  const beyond = candidateLength - last;  const [number, offset] = readBits(array, bitsOffset, floorLog);  if (floorLog === ceilLog || number < last - beyond) {    return [number, offset];  }  const [current, offset2] = readBits(array, offset, 1);  if (current) {    return [number + beyond, offset2];  }  return [number, offset2];}

這里decode規(guī)則，是按照上面算法解析的。先讀取floorLog位，如果總位置數(shù)就是2的次方，則結(jié)束。如果讀取到的數(shù)比較小，也結(jié)束。如果讀取到的數(shù)超過某個(gè)臨界值，就需要多讀取一位，決定它代表誰。

結(jié)論

方案三可以實(shí)現(xiàn)，并且比方案一節(jié)約了35%-45%的空間。

關(guān)于性能：編碼、解碼邏輯全都位于用戶瀏覽器中執(zhí)行，對(duì)服務(wù)器無影響，瀏覽器也會(huì)在人感知不到的耗時(shí)內(nèi)運(yùn)算完。

有什么用？

我在開發(fā)《象棋》時(shí)，期望通過URL來分享棋局。我希望分享的URL能永久有效，而且不喜歡給服務(wù)器太多債務(wù)（不采用token+數(shù)據(jù)庫存儲(chǔ)棋盤信息）。那么URL中必須包含完整的棋盤信息。

如果把棋盤信息存到URL中，那么URL越短，越好。

例如：game.hullqin.cn/xq?p=gSQCL5P5oIDhCFJCIBJ4eQCAkX8&r=86pU6-4nbSh38OCojLarcupWOb1rXw&s=1 ，點(diǎn)開后就能立馬展現(xiàn)某場對(duì)局。

這個(gè)URL里，保存了棋盤所有棋子信息、所有歷史記錄（10個(gè)回合即20步）。方便大家保存、分享。

保存歷史記錄，也是通過類似的手段實(shí)現(xiàn)的，占用空間非常小（長度兩百的字符串，足夠存儲(chǔ)大部分常規(guī)對(duì)局的歷史記錄）。

歡迎觀看 【可以「旋轉(zhuǎn)棋盤」的聯(lián)機(jī)象棋】 - 嗶哩嗶哩

寫在最后

我是HullQin，公眾號(hào)線下聚會(huì)游戲的作者（歡迎關(guān)注我，交個(gè)朋友）。轉(zhuǎn)發(fā)本文前需獲得作者HullQin授權(quán)。我獨(dú)立開發(fā)了《聯(lián)機(jī)桌游合集》，是個(gè)網(wǎng)頁，可以很方便的跟朋友聯(lián)機(jī)玩UNO、飛行棋、斗地主、五子棋、一夜狼、狼人殺、象棋、德國心臟病、達(dá)芬奇密碼等游戲，不收費(fèi)無廣告。還開發(fā)了《Dice Crush》參加Game Jam 2022。喜歡可以關(guān)注我噢～我有空了會(huì)分享做游戲的相關(guān)技術(shù)，會(huì)在這個(gè)專欄里分享：《教你做小游戲》。

關(guān)鍵詞：