基于JavaScript動態(tài)規(guī)劃編寫一個益智小游戲

更新時間：2023年06月19日 11:23:42 作者：小九九的爸爸

最近在學習動態(tài)規(guī)劃相關(guān)的知識，所以本文將利用動態(tài)規(guī)劃編寫一個簡單的益智小游戲，文中的示例代碼講解詳細，感興趣的小伙伴可以了解一下

首先要在這里感謝宮水三葉大佬，最近在學習動態(tài)規(guī)劃相關(guān)的知識，這位大佬的很多題解給都了我不錯的靈感。其實動態(tài)規(guī)劃大家真的應該重視起來，如果將動態(tài)規(guī)劃這類問題可視化出來，你會發(fā)現(xiàn)，原來我們每天生活中都在跟動態(tài)規(guī)劃打交道。這不，今天我就將一道lc變種成一個益智小游戲了，那么我們抓緊開始吧。

游戲規(guī)則

給你一張n*n的地圖，讓你給出從S點到E點的路徑上的最大得分數(shù)以及路徑上的最大得分數(shù)對應的方案數(shù)。

規(guī)則限制如下：

1、起始點始終為S，終點始終為E。
2、X為障礙物，你不能移動到障礙物上，也就是說遇到障礙物需要繞道而行。
3、移動的方向只有三個：向左、向左上、向上。

對于S點來說，X點就是它的左上方，因為X點為障礙物，所以對于S點來說，可移動的方向只有2個，分別是向左和向上。

這里再對返回值做如下說明：

路徑上的最大得分數(shù)：對于上圖來說，從S點到E點的路徑上的最大得分數(shù)是7（路徑如下圖）。

路徑上的最大得分數(shù)對應的方案數(shù)：對于上圖來說，方案數(shù)是1。因為此時符合題意的到達E點的方案數(shù)是2個，但是這2個方案對應的得分數(shù)卻不一樣，且最大值為7，所以此時的方案數(shù)是1。

游戲交互

起始點S與終點E，程序會用藍色框來標注。
障礙物X，程序會用紅色標注。
輸入框可以讓用戶來填寫答案，最后點擊提交進行答案校驗。

游戲效果

“好的食材往往需要最簡單的烹飪方式” 這句話很適用我們今天做的這個小游戲，最開始給用戶一個 2*2 規(guī)模的圖，然后點擊提交按鈕，我們會校驗你給出的答案，如果答案錯誤，我們會給出失敗的提示語；如果成功，程序會給出“敢繼續(xù)挑戰(zhàn)嘛”的提示框，如果此時你點擊“繼續(xù)”，那么我們的規(guī)模將逐步的提升，由 2*2 會提升到 3*3，后面可能會逐步提升到8*8。所以勇士們，證明你們的時刻到了，come on！

游戲算法講解

地圖的數(shù)據(jù)結(jié)構(gòu)展示

首先對于地圖的數(shù)據(jù)結(jié)構(gòu)，我們可以使用二維數(shù)組來表示。我們以下圖來舉例：

對于這個地圖，我們就可以這樣表示：

let arr = [
    ['E', '2', '3'],
    ['2', 'X', '2'],
    ['1', '2', 'S']
];
let showContent = (item, x, y) => {
    let { arr } = this.state;
    if (x === y && x === 0){
        return 'E'
    }
    if (x === y && x === arr.length - 1){
        return 'S'
    }
    return item;
}
// 循環(huán)上圖
<div>
    arr.map((item, itemIndex) => {
        return item.map((child, childIndex) => {
            return <div>
                {showContent(child, itemIndex, childIndex)}
            </div> 
        })
    })
</div>

如何統(tǒng)計最大路徑得分數(shù)以及相應方案？

根據(jù)游戲規(guī)則我們知道，的移動的大方向一定是向上的（因為終點永遠在第一層，起點永遠在最后一層），

在大方向上，對于每個單元格的移動方向又細分了3個方向（向左、向上、向左上）。

對于移動方向的規(guī)則這個是基本點，所以一定不能忘了。有了這個基本點，我們繼續(xù)往下分析。

對于E點來說，他的答案一定可以通過它右邊的綠色框與下面的綠色框來得出答案。比如現(xiàn)在來求一下S到E點的最大路徑得分數(shù)，下面這個等式是一定成立的：

S點到 E點的最大得分數(shù) = Math.max(S點到E點右側(cè)的綠色框的得分數(shù), S點到E點下側(cè)的綠色框的得分數(shù))

根據(jù)上面的等式成立，所以我們思路就可以轉(zhuǎn)變到S點到任意一點（除障礙物外）的最大得分數(shù)以及相應的方案數(shù)。

我們可以使用二維數(shù)組的方式來存儲每個單元格對應的答案。

let arr = [
    ['E', '2', '3'],
    ['2', 'X', '2'],
    ['1', '2', 'S']
];
let pathsWithMaxScore = () => {
    let n = arr.length;
    // 聲明二維數(shù)組dp來存儲每個單元格對應的答案
    // 其中dp[i][j] 代表 單元格
    // dp[i][j][0] 代表 s點到當前單元格的最大路徑得分
    // dp[i][j][1] 代表 s點到當前單元格的最大路徑得分對應的方案數(shù)
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => [-1, 0]));
}

接著上面的思路，我們來求任意點對應的最大路徑以及方案數(shù)。我們這里以下圖的b點為例。

let pathsWithMaxScore = () => {
    let n = arr.length;
    // 聲明二維數(shù)組dp來存儲每個單元格對應的答案
    // 其中dp[i][j] 代表 單元格
    // dp[i][j][0] 代表 s點到當前單元格的最大路徑得分
    // dp[i][j][1] 代表 s點到當前單元格的最大路徑得分對應的方案數(shù)
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => [-1, 0]));
    for (let i = n - 1; i >= 0; i--){
        for (let j = n - 1; j >= 0; j--){
            if (arr[i][j] === 'X'){
                // 根據(jù)題意，遇到障礙物就要繞行
                continue;
            }
            // 當 i === n-1 && j === n - 2時
            // 此時位置正好是b點
            // 此時需要做出2件事...
        }
    }
}

當我們到達b點時，我們需要考慮2件事：

1、什么時候應該更新b點的最大得分數(shù)？
2、b點的最大得分數(shù)對應的方案數(shù)應該如何更新？

對于第一個問題，當前循環(huán)到b點時，b點一定知道能夠到達這個點的來源路徑(fromX, fromY)是哪些，當dp[fromX][fromY][0] + arr[i][j] > dp[i][j][0] 成立時，就可以b點原先存儲的最大數(shù)了。

對于第二個問題，又分為了2種情況。如果dp[fromX][fromY][0] + arr[i][j] === dp[i][j][0]，說明這個新來的路徑也算是一條有效方案，此時應該+1（dp[i][j][1] + 1）。還有一種就是 dp[fromX][fromY] + arr[i][j] > dp[i][j][0] 的時候，此時應該將 dp[i][j][1] 更新為dp[fromX][fromY][1]。

let pathsWithMaxScore = () => {
    let n = arr.length;
    // 聲明二維數(shù)組dp來存儲每個單元格對應的答案
    // 其中dp[i][j] 代表 單元格
    // dp[i][j][0] 代表 s點到當前單元格的最大路徑得分
    // dp[i][j][1] 代表 s點到當前單元格的最大路徑得分對應的方案數(shù)
    let dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => [-1, 0]));
    arr[0][0] = arr[n-1][n-1] = 0;
    dp[n - 1] [n - 1] = [0, 1];
    let fromPath = [ // 任意點的來源路徑集合
        [0, 1],
        [1, 1],
        [1, 0]
    ];
    for (let i = n - 1; i >= 0; i--){
        for (let j = n - 1; j >= 0; j--){
            if (arr[i][j] === 'X'){
                // 根據(jù)題意，遇到障礙物就要繞行
                continue;
            }
            // 當 i === n-1 && j === n - 2時
            // 此時位置正好是b點，我們需要先遍歷能到達b點的路徑有哪些
            for (let [sx, sy] of fromPath){
                    let fromX = i + sx;
                    let fromY = j + sy;
                    if (lx < 0 || lx >= n || ly < 0 || ly >= n || arr[lx][ly] === 'X' || f[lx][ly][1] === 0) {
                        // 超出地圖范圍的，都過濾掉
                        continue;
                    }
                    if (dp[i][j][0] === dp[fromX][fromY][0] + Number(arr[i][j])){
                        dp[i][j][1] += dp[fromX][fromY][1];
                    } else if (dp[i][j][0] < dp[fromX][fromY][0] + Number(arr[i][j])){
                        dp[i][j][0] = dp[fromX][fromY][0] + Number(arr[i][j]);
                        // 此時為什么要更新路徑？因為之前的幾條路對應的得分不是最大的呀
                        dp[i][j][1] = dp[fromX][fromY][1];
                    }
            }
        }
    }
    return dp[0][0]; // dp[0][0]的值是一個長度為2的數(shù)組，數(shù)組第0項時得分，第一項是方案數(shù)
}

到此，我們的算法也就講完了。感興趣的小伙伴可以把這個算法吸收一下，或者自己喂個數(shù)據(jù)跑一下。

到此這篇關(guān)于基于JavaScript動態(tài)規(guī)劃編寫一個益智小游戲的文章就介紹到這了,更多相關(guān)JavaScript益智游戲內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: