俄羅斯方塊AI（成果試玩版） | 程式專案

{"id":298675,"student_id":2589,"content":"{\"html\":\"\u003c!DOCTYPE html\u003e\\n\u003chtml lang=\\\"en\\\"\u003e\\n\\n\u003chead\u003e\\n    \u003cmeta charset=\\\"UTF-8\\\"\u003e\\n    \u003cmeta name=\\\"viewport\\\" content=\\\"width=device-width, initial-scale=1.0\\\"\u003e\\n    \u003cmeta http-equiv=\\\"X-UA-Compatible\\\" content=\\\"ie=edge\\\"\u003e\\n    \u003ctitle\u003eDocument\u003c/title\u003e\\n    \u003cstyle\u003e\\n        canvas { border: 1px solid #333333; }\\n    \u003c/style\u003e\\n\u003c/head\u003e\\n\\n\u003cbody\u003e\\n    \u003ccanvas id=\\\"stage\\\"\u003e\u003c/canvas\u003e\\n\u003c/body\u003e\\n\\n\u003c/html\u003e\",\"css\":\"/* 設定整個頁面內容水平置中、內寬為 30 像素：*/\\nbody {\\n    text-align: center;\\n    padding: 30px;\\n}\\n\\n/* 設定圖片的寬度為銀幕一半寬 */\\nimg {    \\n    max-width: 50%; \\n}\\n\\n/* 設定文字的顏色為淡黑色 */\\np {\\n    color: #555555;\\n}\",\"js\":\"\"}","created_at":"2021-09-23T17:56:03.666+08:00","updated_at":"2021-10-06T11:04:21.789+08:00","name":"俄羅斯方塊AI（成果試玩版）","language":"web","screenshot":{"url":null},"parent_id":3,"plugin":"const BLOCKS = [\n    [{x: 0, y: 2}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 1, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 2, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 3, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 2, y: 1}, {x: 3, y: 1}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 1, y: 1}, {x: 2, y: 1}, {x: 2, y: 2}, {x: 3, y: 2}],\n    [{x: 2, y: 1}, {x: 3, y: 1}, {x: 1, y: 2}, {x: 2, y: 2}],\n    \n]\nconst COLORS = ['#db312b', '#569f14', '#1366af', '#fd680b', '#d7b815', '#582479']\n\nclass Tetris {\n\n    constructor() {\n        this.width = 10\n        this.height = 20\n        this.blocks = []\n        this.posX = undefined\n        this.posY = undefined\n        this.status = 'playing' // playing, gameover\n        this.scores = 0\n        this.nextBlock = this.randomBlock()\n        this.loadBlocks()\n    }\n\n    getGrid () {\n        let grid = []\n        for (let y = 0; y \u003c this.height; y++) {\n            grid[y] = []\n            for (let x = 0; x \u003c this.width; x++) {\n                grid[y][x] = ' '\n            }\n        }\n        this.blocks.filter(b =\u003e b.state === 'fixed').forEach(b =\u003e grid[b.y][b.x] = '*')\n        return grid.map(row =\u003e row.join(''))\n    }\n\n    loadBlocks() {\n\n        if (this.status === 'gameover') return false\n        if (this.blocks.some(b =\u003e b.state === 'fixed' \u0026\u0026 b.y \u003c= 2)) {\n            return this.status = 'gameover'\n        }\n\n        const state = 'moving'\n        const color = this.nextBlock.color\n        const block = this.nextBlock.block\n\n        this.blocks = this.blocks.concat(block.map(b =\u003e {\n            return { color, state, x: b.x + 2, y: b.y }\n        }))\n\n        this.posX = 4\n        this.posY = 2\n\n        this.nextBlock = this.randomBlock()\n    }\n\n    randomBlock() {\n        const rand1 = Math.floor(Math.random() * BLOCKS.length)\n        const rand2 = Math.floor(Math.random() * COLORS.length)\n        return {\n            block: BLOCKS[rand1],\n            color: COLORS[rand2],\n        }\n    }\n\n    moveDownToEnd() {\n        while(this.moveDown()) {}\n    }\n\n    moveDown() {\n        const bool = this.move(this._moveDown)\n        if (bool) this.posY++\n        else {\n            this.blocks.forEach(b =\u003e b.state = 'fixed')\n            this.eraseLines()\n            this.loadBlocks()\n        }\n        return bool\n    }\n\n    moveRight() {\n        const bool = this.move(this._moveRight)\n        if (bool) this.posX++\n        return bool\n    }\n\n    moveLeft() {\n        const bool = this.move(this._moveLeft)\n        if (bool) this.posX--\n        return bool\n    }\n\n    turnRight() {\n        return this.move(this._turnRight.bind(this))\n    }\n\n    move(func) {\n        if (this.status === 'gameover') return false\n        const fixedBlocks = this.blocks.filter(b =\u003e b.state === 'fixed')\n        const movingBlocks = this.blocks.filter(b =\u003e b.state === 'moving')\n        const bool = movingBlocks.every(b =\u003e {\n            const pos = func(b)\n            return this._isValidPos(pos.x, pos.y) \u0026\u0026 !fixedBlocks.some(target =\u003e {\n                return target.x == pos.x \u0026\u0026 target.y == pos.y\n            })\n        })\n        if (bool) {\n            movingBlocks.forEach(b =\u003e {\n                const pos = func(b)\n                b.x = pos.x\n                b.y = pos.y\n            })\n        }\n        return bool\n    }\n\n    eraseLines() {\n        for (let y=0; y\u003cthis.height; y++) {\n            let row = this.blocks.filter(b =\u003e b.y === y)\n            if (row.length === this.width) {\n                this.blocks = this.blocks.filter(b =\u003e b.y !== y)\n                this.blocks.filter(b =\u003e b.y \u003c y).forEach(b =\u003e b.y++)\n                this.scores++\n            }\n        }\n    }\n\n    _moveDown(b) {\n        return { x: b.x, y: b.y + 1 }\n    }\n\n    _moveRight(b) {\n        return { x: b.x + 1, y: b.y }\n    }\n\n    _moveLeft(b) {\n        return { x: b.x - 1, y: b.y }\n    }\n\n    _turnRight (b) {\n        let vx = b.x - this.posX\n        let vy = b.y - this.posY\n        if (vx*vy !== 0 || vx === 0) vy *= -1\n        return {\n            x: this.posX + vy,\n            y: this.posY + vx,\n        }\n    }\n\n    _isValidPos(x, y) {\n        return y \u003e= 0 \u0026\u0026 y \u003c this.height \u0026\u0026\n               x \u003e= 0 \u0026\u0026 x \u003c this.width\n    }\n}\n\nclass Renderer {\n\n    constructor(canvasId, gameInstance, size = 25) {\n\n        const canvas = document.getElementById(canvasId) \n        canvas.width = size * gameInstance.width\n        canvas.height = size * gameInstance.height\n\n        this.ctx = canvas.getContext('2d')\n        this.size = size\n        this.game = gameInstance\n    }\n\n    render = () =\u003e {\n\n        this._clear()\n\n        this.game.blocks.forEach(this._drawRect)\n        this.game.blocks.forEach(this._drawRectStroke)\n\n        this.ctx.scale(0.3, 0.3)\n        this.game.nextBlock.block.forEach(this._drawRect)\n        this.game.nextBlock.block.forEach(this._drawRectStroke)\n\n        this.ctx.setTransform(1, 0, 0, 1, 0, 0)\n\n        this._drawText()\n    }\n\n    _clear = () =\u003e {\n        this.ctx.fillStyle = '#222222'\n        this.ctx.fillRect(0, 0, this.size * 10, this.size * 20)\n    }\n\n    _drawRect = (b) =\u003e {\n        const { size, ctx, game } = this\n        ctx.fillStyle = game.status === 'gameover' ? '#666' : b.color\n        ctx.fillRect(b.x * size, b.y * size, size, size)\n    }\n\n    _drawRectStroke = (b) =\u003e {\n        const { size, ctx } = this\n        ctx.lineWidth = 2\n        ctx.strokeStyle = '#111111'\n        ctx.beginPath()\n        ctx.rect(b.x * size, b.y * size, size, size)\n        ctx.stroke()\n    }\n\n    _drawText = () =\u003e {\n        const { size, ctx, game } = this\n        ctx.fillStyle = '#ffffff';\n        ctx.textAlign = 'end'\n        ctx.font = '20px Comic Sans MS';\n        ctx.fillText(game.scores, game.width * size - 10, 25);\n    }\n}\n\nfunction undoWrapper(game) {\n\n    const snapshot = []\n    const actions = []\n\n    function undo(i = 1) {\n        if (i \u003c= 0) return\n        const data = snapshot.splice(0, i).pop()\n        if (data) {\n            let d = JSON.parse(data)\n            game.blocks = d.blocks\n            game.scores = d.scores\n            game.status = d.status\n            game.nextBlock = d.nextBlock\n        }\n        actions.splice(0, i)\n    }\n\n    function decorator(method, action) {\n        return function () {\n            snapshot.unshift(JSON.stringify({\n                blocks: game.blocks,\n                scores: game.scores,\n                status: game.status,\n                nextBlock: game.nextBlock,\n            }))\n            actions.unshift(action)\n            let bool = method.call(game)\n            if (bool === false) {\n                snapshot.splice(0, 1)\n                actions.splice(0, 1)\n            }\n            return bool\n        }\n    }\n\n    function clearAllActions() {\n        actions.length = 0\n        snapshot.length = 0\n    }\n\n    game.moveRight = decorator(game.moveRight, 'R')\n    game.moveLeft = decorator(game.moveLeft, 'L')\n    game.turnRight = decorator(game.turnRight, 'T')\n    game.moveDownToEnd = decorator(game.moveDownToEnd, 'D')\n    game.snapshot = snapshot\n    game.actions = actions\n    game.undo = undo\n    game.clearAllActions = clearAllActions\n    \n    return game\n}\n\n\nwindow.Tetris = Tetris\nwindow.Renderer = Renderer\nwindow.undoWrapper = undoWrapper\n\n//======================== 遊戲初始化 ============================//\nvar game = undoWrapper(new Tetris()) //初始化遊戲\nvar renderer = new Renderer('stage', game) //初始化遊戲畫面\nvar actions = ['D', 'R', 'R', 'R'] // 儲存 AI 產生的移動步驟\n\ndocument.addEventListener('keydown', (e) =\u003e {\n    if (e.keyCode === 40) game.moveDownToEnd() //下鍵：向下移動到底\n    if (e.keyCode === 37) game.moveLeft() //左鍵：向左移動\n    if (e.keyCode === 39) game.moveRight() //右鍵：向右移動\n    if (e.keyCode === 38) game.turnRight() //上鍵：順時針旋轉\n    if (e.keyCode === 85) game.undo() // U按鍵：返回上一步\n    if (e.keyCode === 32) alert(evaluation(game)) //空白鍵：顯示評估分數\n})\n\n// 遊戲迴圈\nfunction gameloop () {\n    // game.moveDown() // 向下移動一格\n    \n    if (actions.length \u003e 0) {\n        var a = actions.pop()\n        if (a === 'R') game.moveRight() //向右移動\n        if (a === 'L') game.moveLeft() //向左移動\n        if (a === 'D') game.moveDownToEnd() //向下移動到底\n        if (a === 'T') game.turnRight() //順時針旋轉\n        if (a === 'D') actions = [] //清空觸發 AI\n    } else {\n        actions = AI(game)\n    }\n    renderer.render() //更新畫面\n}\n\n// 將低第二個參數數值可以加速 AI 測試\nsetInterval(gameloop, 20) //不斷執行遊戲迴圈\n\n//============================================================//\n\nvar bestScore = 0 // 紀錄當前找到最好的擺放分數\nvar bestActions = [] // 紀錄當前找到最好的擺放步驟\n\nfunction AI(game) {\n    bestScore = 0 // 重置分數\n    game.clearAllActions() //清空移動歷史紀錄\n    search(game, true) // 開始搜尋各種擺法\n    return bestActions // 返回最好的擺法步驟\n}\n\nfunction search(game, again) {\n\n    var step, turnStep\n    \n    for (turnStep = 0; turnStep \u003c 4; turnStep++) {\n\n        game.moveDownToEnd()\n        evaluation(game, again)\n        game.undo()\n\n        step = 0\n        while (game.moveRight()) {\n            step++\n            game.moveDownToEnd()\n            evaluation(game, again)\n            game.undo()\n        }\n        game.undo(step)\n\n        step = 0\n        while (game.moveLeft()) {\n            step++\n            game.moveDownToEnd()\n            evaluation(game, again)\n            game.undo()\n        }\n        game.undo(step)\n\n        game.turnRight()\n    }\n\n    game.undo(turnStep)\n}\n\n// 評估函式\nfunction evaluation(game, again) {\n\n    if (again) return search(game, false)\n\n    var score = 0\n    var grid = game.getGrid() // 取得格子狀態的二維陣列\n\n    for (var y = 0; y \u003c 20; y++) {\n        for (var x = 0; x \u003c 10; x++) {\n            if (grid[y][x] == ' ') {\n                score += 20;\n                if (x \u003e 0 \u0026\u0026 grid[y][x - 1] == '*') score -= 10\n                if (x \u003c 9 \u0026\u0026 grid[y][x + 1] == '*') score -= 10\n                if (y \u003e 0 \u0026\u0026 grid[y - 1][x] == '*') score -= 50\n                if (y \u003c 19 \u0026\u0026 grid[y + 1][x] == '*') score -= 5\n            } else {\n                score += y;\n            }\n        }\n    }\n\n    if (score \u003e bestScore) {\n        bestScore = score\n        bestActions = game.actions.slice() // 淺拷貝移動歷史紀錄\n    }\n\n    return score // 測試用\n}","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":122,"hashid":"vngsy8vvd","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}