快捷導(dǎo)航

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

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

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

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

游戲規(guī)則

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

規(guī)則限制如下：

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

對于S點(diǎn)來說，X點(diǎn)就是它的左上方，因?yàn)閄點(diǎn)為障礙物，所以對于S點(diǎn)來說，可移動(dòng)的方向只有2個(gè)，分別是向左和向上。

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

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

路徑上的最大得分?jǐn)?shù)對應(yīng)的方案數(shù)：對于上圖來說，方案數(shù)是1。因?yàn)榇藭r(shí)符合題意的到達(dá)E點(diǎn)的方案數(shù)是2個(gè)，但是這2個(gè)方案對應(yīng)的得分?jǐn)?shù)卻不一樣，且最大值為7，所以此時(shí)的方案數(shù)是1。

游戲交互

起始點(diǎn)S與終點(diǎn)E，程序會用藍(lán)色框來標(biāo)注。
障礙物X，程序會用紅色標(biāo)注。
輸入框可以讓用戶來填寫答案，最后點(diǎn)擊提交進(jìn)行答案校驗(yàn)。

游戲效果

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

游戲算法講解

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

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

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

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)計(jì)最大路徑得分?jǐn)?shù)以及相應(yīng)方案？

根據(jù)游戲規(guī)則我們知道，的移動(dòng)的大方向一定是向上的（因?yàn)榻K點(diǎn)永遠(yuǎn)在第一層，起點(diǎn)永遠(yuǎn)在最后一層），

在大方向上，對于每個(gè)單元格的移動(dòng)方向又細(xì)分了3個(gè)方向（向左、向上、向左上）。

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

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

S點(diǎn) 到 E點(diǎn)的最大得分?jǐn)?shù) = Math.max(S點(diǎn)到E點(diǎn)右側(cè)的綠色框的得分?jǐn)?shù), S點(diǎn)到E點(diǎn)下側(cè)的綠色框的得分?jǐn)?shù))

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

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

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

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

let pathsWithMaxScore = () => {
    let n = arr.length;
    // 聲明二維數(shù)組dp來存儲每個(gè)單元格對應(yīng)的答案
    // 其中dp[i][j] 代表 單元格
    // dp[i][j][0] 代表 s點(diǎn)到當(dāng)前單元格的最大路徑得分
    // dp[i][j][1] 代表 s點(diǎn)到當(dāng)前單元格的最大路徑得分對應(yīng)的方案數(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;
            }
            // 當(dāng) i === n-1 && j === n - 2時(shí)
            // 此時(shí)位置正好是b點(diǎn)
            // 此時(shí)需要做出2件事...
        }
    }
}

當(dāng)我們到達(dá)b點(diǎn)時(shí)，我們需要考慮2件事：

1、什么時(shí)候應(yīng)該更新b點(diǎn)的最大得分?jǐn)?shù)？
2、b點(diǎn)的最大得分?jǐn)?shù)對應(yīng)的方案數(shù)應(yīng)該如何更新？

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

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

let pathsWithMaxScore = () => {
    let n = arr.length;
    // 聲明二維數(shù)組dp來存儲每個(gè)單元格對應(yīng)的答案
    // 其中dp[i][j] 代表 單元格
    // dp[i][j][0] 代表 s點(diǎn)到當(dāng)前單元格的最大路徑得分
    // dp[i][j][1] 代表 s點(diǎn)到當(dāng)前單元格的最大路徑得分對應(yīng)的方案數(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 = [ // 任意點(diǎn)的來源路徑集合
        [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;
            }
            // 當(dāng) i === n-1 && j === n - 2時(shí)
            // 此時(shí)位置正好是b點(diǎn)，我們需要先遍歷能到達(dá)b點(diǎn)的路徑有哪些
            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]);
                        // 此時(shí)為什么要更新路徑？因?yàn)橹暗膸讞l路對應(yīng)的得分不是最大的呀
                        dp[i][j][1] = dp[fromX][fromY][1];
                    }
            }
        }
    }
    return dp[0][0]; // dp[0][0]的值是一個(gè)長度為2的數(shù)組，數(shù)組第0項(xiàng)時(shí)得分，第一項(xiàng)是方案數(shù)
}

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

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

您可能感興趣的文章: