老鼠走迷宮 - DFS 演算法 | JavaScript 程式專案

{"id":46434,"student_id":248,"content":"var maze = [];\nvar width = 20;\nvar row = 640/width;\nvar col = 480/width;\n\n(function () {\n    for (var x = 0; x \u003c row; x++) {\n        maze[x] = [];\n        for (var y = 0; y \u003c col; y++) {\n            maze[x][y] = {\n                color: '#ffffff',\n                top: false,\n                right: false,\n                bottom: false,\n                left: false\n            };\n        }\n    }\n    \n    forever(function() {\n        for (var cx = 0; cx \u003c row; cx++) {\n            for (var cy = 0; cy \u003c col; cy++) {\n                \n                var cell = maze[cx][cy];\n                pen.size = 0.001;\n                pen.fillColor = cell.color;\n                pen.drawRect(cx*width, cy*width, width, width);\n                \n                pen.size = 1;\n                var x = cx*width;\n                var y = cy*width;\n                if (!cell.top) pen.drawLine(x, y, x + width, y);\n                if (!cell.right) pen.drawLine(x + width, y, x + width, y + width);\n                if (!cell.bottom) pen.drawLine(x, y + width, x + width, y + width);\n                if (!cell.left) pen.drawLine(x, y + width, x, y);\n            }\n        }\n    });\n    \n    var x = 0;\n    var y = 0;\n    var steps = [];\n    maze[0][0].color = 'lightblue';\n    \n    while(true) {\n        pen.fillColor = 'red';\n        pen.drawRect(x*width, y*width, width, width);\n    \n        var next = getNeighbors();\n        if (next.length \u003e 0) {\n            steps.push({x: x, y: y});\n            \n            var rand = Math.floor(Math.random()*next.length);\n            if (next[rand] == 'top') {\n                maze[x][y].top = true;\n                y -= 1;\n                maze[x][y].bottom = true;\n            }\n            if (next[rand] == 'right') {\n                maze[x][y].right = true;\n                x += 1;\n                maze[x][y].left = true;\n            }\n            if (next[rand] == 'bottom') {\n                maze[x][y].bottom = true;\n                y += 1;\n                maze[x][y].top = true;\n            }\n            if (next[rand] == 'left') {\n                maze[x][y].left = true;\n                x -= 1;\n                maze[x][y].right = true;\n            }\n            maze[x][y].color = 'lightblue';\n        } else {\n            maze[x][y].color = 'white';\n            if (steps.length \u003e 0) {\n                var back = steps.pop();\n                x = back.x;\n                y = back.y;\n            }\n        }\n        \n        var count = 0;\n        for (var c1 = 0; c1 \u003c row; c1++) {\n            for (var c2 = 0; c2 \u003c col; c2++) {\n                if (maze[c1][c2].color == 'white') {\n                    count++;\n                }\n            }\n        }\n        if (count \u003e= row*col) break;\n    };\n    \n    function getNeighbors () {\n        var arr = [];\n        if (check(x + 1, y)) {\n            arr.push('right');\n        }\n        if (check(x - 1, y)) {\n            arr.push('left');\n        }\n        if (check(x, y + 1)) {\n            arr.push('bottom');\n        }\n        if (check(x, y - 1)) {\n            arr.push('top');\n        }\n        return arr;\n    }\n    \n    function check (x, y) {\n        return x \u003e= 0 \u0026\u0026 x \u003c row \u0026\u0026\n               y \u003e= 0 \u0026\u0026 y \u003c col \u0026\u0026\n               maze[x][y].color == '#ffffff';\n    }\n})();\n\n// // 老鼠初始化的位置\n// var x = 0;\n// var y = 0;\n\n// forever(function(){\n\n//     // 繪製紅色老鼠\n//     pen.fillColor = 'red';\n//     pen.drawRect(x*width + 1, y*width + 1, width - 2, width - 2);\n    \n//     // // 設定終點為 (31, 23) 到達時暫停\n//     // if (x == 31 \u0026\u0026 y == 23)  stop();\n    \n//     // maze[x][y].color = 'lightblue';\n//     // if (maze[x][y].right \u0026\u0026 maze[x + 1][y].color == 'white') {\n//     //     x += 1;\n//     // }\n//     // else if (maze[x][y].left \u0026\u0026 maze[x - 1][y].color == 'white') {\n//     //     x -= 1;\n//     // }\n//     // else if (maze[x][y].bottom \u0026\u0026 maze[x][y + 1].color == 'white') {\n//     //     y += 1;\n//     // }\n//     // else if (maze[x][y].top \u0026\u0026 maze[x][y - 1].color == 'white') {\n//     //     y -= 1;\n//     // }\n//     // else {\n//     //     maze[x][y].color = 'yellow';\n//     //     if (maze[x][y].top \u0026\u0026 maze[x][y - 1].color == 'lightblue') {\n//     //         y -= 1;\n//     //     }\n//     //     else if (maze[x][y].right \u0026\u0026 maze[x + 1][y].color == 'lightblue') {\n//     //         x += 1;\n//     //     }\n//     //     else if (maze[x][y].bottom \u0026\u0026 maze[x][y + 1].color == 'lightblue') {\n//     //         y += 1;\n//     //     }\n//     //     else if (maze[x][y].left \u0026\u0026 maze[x - 1][y].color == 'lightblue') {\n//     //         x -= 1;\n//     //     }\n//     // }\n// });","created_at":"2018-10-26T14:24:27.399+08:00","updated_at":"2019-11-11T22:28:41.432+08:00","name":"老鼠走迷宮 - DFS 演算法","language":"javascript","screenshot":{"url":"https://cdn1.koding.school/uploads/project/screenshot/46434/c2df2557ad0224a7f2e3d39b8ab32157.jpg"},"parent_id":2,"plugin":"// var maze = [];\n// var width = 20;\n// var row = 640/width;\n// var col = 480/width;\n\n// (function () {\n//     for (var x = 0; x \u003c row; x++) {\n//         maze[x] = [];\n//         for (var y = 0; y \u003c col; y++) {\n//             maze[x][y] = {\n//                 color: '#ffffff',\n//                 top: false,\n//                 right: false,\n//                 bottom: false,\n//                 left: false\n//             };\n//         }\n//     }\n    \n//     forever(function() {\n//         for (var cx = 0; cx \u003c row; cx++) {\n//             for (var cy = 0; cy \u003c col; cy++) {\n                \n//                 var cell = maze[cx][cy];\n//                 pen.size = 0.001;\n//                 pen.fillColor = cell.color;\n//                 pen.drawRect(cx*width, cy*width, width, width);\n                \n//                 pen.size = 1;\n//                 var x = cx*width;\n//                 var y = cy*width;\n//                 if (!cell.top) pen.drawLine(x, y, x + width, y);\n//                 if (!cell.right) pen.drawLine(x + width, y, x + width, y + width);\n//                 if (!cell.bottom) pen.drawLine(x, y + width, x + width, y + width);\n//                 if (!cell.left) pen.drawLine(x, y + width, x, y);\n//             }\n//         }\n//     });\n    \n//     var x = 0;\n//     var y = 0;\n//     var steps = [];\n//     maze[0][0].color = 'lightblue';\n    \n//     while(true) {\n//         pen.fillColor = 'red';\n//         pen.drawRect(x*width, y*width, width, width);\n    \n//         var next = getNeighbors();\n//         if (next.length \u003e 0) {\n//             steps.push({x: x, y: y});\n            \n//             var rand = Math.floor(Math.random()*next.length);\n//             if (next[rand] == 'top') {\n//                 maze[x][y].top = true;\n//                 y -= 1;\n//                 maze[x][y].bottom = true;\n//             }\n//             if (next[rand] == 'right') {\n//                 maze[x][y].right = true;\n//                 x += 1;\n//                 maze[x][y].left = true;\n//             }\n//             if (next[rand] == 'bottom') {\n//                 maze[x][y].bottom = true;\n//                 y += 1;\n//                 maze[x][y].top = true;\n//             }\n//             if (next[rand] == 'left') {\n//                 maze[x][y].left = true;\n//                 x -= 1;\n//                 maze[x][y].right = true;\n//             }\n//             maze[x][y].color = 'lightblue';\n//         } else {\n//             maze[x][y].color = 'white';\n//             if (steps.length \u003e 0) {\n//                 var back = steps.pop();\n//                 x = back.x;\n//                 y = back.y;\n//             }\n//         }\n        \n//         var count = 0;\n//         for (var c1 = 0; c1 \u003c row; c1++) {\n//             for (var c2 = 0; c2 \u003c col; c2++) {\n//                 if (maze[c1][c2].color == 'white') {\n//                     count++;\n//                 }\n//             }\n//         }\n//         if (count \u003e= row*col) break;\n//     };\n    \n//     function getNeighbors () {\n//         var arr = [];\n//         if (check(x + 1, y)) {\n//             arr.push('right');\n//         }\n//         if (check(x - 1, y)) {\n//             arr.push('left');\n//         }\n//         if (check(x, y + 1)) {\n//             arr.push('bottom');\n//         }\n//         if (check(x, y - 1)) {\n//             arr.push('top');\n//         }\n//         return arr;\n//     }\n    \n//     function check (x, y) {\n//         return x \u003e= 0 \u0026\u0026 x \u003c row \u0026\u0026\n//               y \u003e= 0 \u0026\u0026 y \u003c col \u0026\u0026\n//               maze[x][y].color == '#ffffff';\n//     }\n// })();","description":null,"note":null,"status":"public","like_student_ids":[],"is_featured":false,"views":278,"hashid":"d5msqw6n","is_content_changed":false,"review_status":"unsubmitted","submitted_at":null,"reviewed_at":null,"advise":null,"is_deleted":false}