怎麼玩
- 選迷宮大小與岔路多寡,畫面會馬上換一張新的迷宮。
- 橘色的點是你,要從左上的「入口」走到右下的「出口」(黃色星星)。電腦用方向鍵或 W、A、S、D,手機在迷宮上滑動或按方向鈕。
- 第一次移動時開始計時;走回頭路也算步數,撞牆不算。到出口後會顯示用時、步數和這張迷宮的最短路線步數。
- 走不出來可以按「顯示解答」,紅線就是答案;「重玩這張」從頭再走同一張,「再來一張」換新的。
列印給小朋友
- 按「列印」只會印出迷宮,頁首、說明、廣告都不會印。迷宮是向量圖,放大列印邊線也清楚。
- 想附解答給家長或老師對答案,先勾「列印時一併印出解答」;沒勾的話,列印不會有解答,即使畫面上正在顯示。
- 年紀小的孩子建議選小或中、岔路選少;想挑戰的選大或特大、岔路選多。
- 每按一次「再來一張」都是新的迷宮,可以一次印好幾張。
用什麼方法產生迷宮
本頁使用 Growing Tree(生長樹)演算法:把一個隨機格子放進清單,每一步從清單裡挑一格,打通它任一個「還沒到過」的鄰格並把鄰格加入清單;挑不到未到過的鄰格時,就把這格從清單移除,清單空了就完成。每一步只接上一個新格子,所以不會形成迴圈,得到的是格子圖的一棵生成樹,也就是入口到出口恰好只有一條路的「完美迷宮」。
「岔路多寡」就是調整每一步怎麼從清單挑格子:
- 少:永遠挑最新加入的格子,等同遞迴回溯(recursive backtracker,深度優先)。特性是一路往前挖到走投無路才退回,所以走廊又長又彎、岔路和死路比較少。
- 中:每一步各有一半機會挑最新的格子、一半機會隨機挑一格,走廊長度介於兩者之間。
- 多:每一步都從清單隨機挑一格,特性和 Prim 演算法類似,會長出很多短短的死路、岔路密集,入口到出口的路線也比較短。
本站自行用各 18 張測試迷宮統計:死路盡頭(只有一個出入口的格子)佔全部格子的比例,「少」約一成,「中」與「多」都約三成;同樣大小下,解答路線的長度是「少」最長、「多」最短。這是本站實測的平均值,不是演算法的保證,每張迷宮會有出入。
起點的隨機格子、每一步的挑選與打通方向,都用瀏覽器的 crypto.getRandomValues 取亂數。入口固定在左上格、出口固定在右下格;顯示的解答是用廣度優先搜尋從入口找到出口的路線,完美迷宮只有這一條。
限制
- 只做方格迷宮(入口在左上、出口在右下),沒有圓形、六角形等其他形狀,也沒有多樓層。
- 本頁沒有排行榜、連線對戰,也不儲存成績。
- 特大(40×40)在手機上格子很小,用手指滑動玩起來比較吃力,建議電腦使用或列印後用筆走。
- 列印的實際大小依印表機與紙張設定而定;建議紙張選 A4 直式、縮放 100%。
常見問題
怎麼在畫面上玩?電腦和手機有什麼不同?
電腦:先用滑鼠點一下迷宮(或按「再來一張」),讓迷宮框取得焦點,再用方向鍵或 W、A、S、D 移動;也可以用滑鼠在迷宮上往想去的方向拖曳。手機:在迷宮上往想去的方向滑動,滑過約一格的距離就走一步,也可以按下方的方向鈕。撞到牆不會動,也不算一步。
為什麼按方向鍵頁面沒有捲動,或是反過來?
只有迷宮框取得焦點時(框外會出現藍色外框),方向鍵才會用來移動,這時頁面不會被方向鍵捲動。想用方向鍵捲動頁面時,按 Tab 離開迷宮框或點一下頁面空白處即可。
怎麼算時間和步數?
第一次成功移動時開始計時,走到出口時停止。每成功走進相鄰的一格算一步,走回頭路也算;撞牆不算。切到別的分頁時計時會暫停,回來後繼續。「重玩這張」會把位置、時間、步數歸零,迷宮不變;「再來一張」會產生新的迷宮。到出口後會告訴你這張迷宮的最短路線是幾步,可以和自己走的步數比一比。
「岔路」少、中、多有什麼差別?
岔路少的迷宮是長長彎彎的走廊,死路比較少、比較長;岔路多的迷宮有很多短短的死路,每走幾步就要選一次方向。三種都保證從入口到出口只有一條路。哪一種比較難沒有定論,要看個人習慣,可以都試試看。
怎麼保證只有一條路?
產生迷宮的方法是從一格開始,每次把一格「還沒到過的鄰格」打通接進來,已經在迷宮裡的格子之間不會再打通,所以不會出現繞圈。這樣得到的迷宮,任何兩格之間恰好只有一條不重複的路,也沒有走不到的格子;數學上這叫格子圖的「生成樹」,這類迷宮在英文裡稱為 perfect maze。
怎麼列印給小朋友玩?
先選好大小,按「再來一張」換到想要的迷宮,再按「列印」。列印時只會印出迷宮本身,不會印頁首、說明或廣告。如果想給家長或老師一張附解答的版本,先勾選「列印時一併印出解答」再列印;沒勾選時,就算畫面上正在顯示解答,列印出來也不會有解答。列印版是向量圖形,放大印也不會糊。特大的迷宮格子很密,給年紀小的孩子建議選小或中。
會存我的資料或紀錄嗎?
不會。迷宮在你的瀏覽器裡產生,沒有排行榜、沒有連線,也沒有把成績存到伺服器或瀏覽器;重新整理頁面就是新的迷宮。和其他頁面一樣,網站有用 Google Analytics 記錄按鈕點擊等使用情形,但不含迷宮內容與你的步數、時間。
規格與來源
- 迷宮、遊戲與列印畫面由本站自行用原生 JavaScript 與 SVG 實作,沒有載入外部程式庫、圖片或字型(全站的統計與廣告腳本除外)。
- 大小:小 10×10、中 15×15、大 25×25、特大 40×40 格。
- 演算法:Growing Tree,作者 Jamis Buck 在部落格有詳細說明:Maze Generation: Growing Tree algorithm(網路上的技術文章,屬二手整理來源,非標準文件)。
- 迷宮產生演算法的分類與特性:Wikipedia Maze generation algorithm(深度優先、Prim 等;Wikipedia 屬二手整理來源)。
- 完美迷宮與生成樹的關係:Wikipedia Maze generation algorithm。