[多圖] 點解Windows 3D迷宮 係一定會搵到終點.

呢個相信 都係大家既回憶黎.
走迷官既 螢幕保護程式.

每次迷官都係隨機生成,
但佢點解 一定會搵到 終點呢?

1. 首先講下 我會點樣generate一個maze (Simply connected space)
去放入Houdini做simulation.
同一個目標 可以用唔同既演算法.
試下簡單既Recursive Backtracking algorithm
backtracking意思係試一試既心態
睇下搵唔搵到一個有效既解答.
如果中途 解決唔到 就取消上一步/上幾步既計算.
再次嘗試尋找問題的答案.

例子: 整個5x5既maze熱身先.
現在位置 Current 藍色
未去過既位置 Available 綠色
去左既位置 visited 紅色

上面係一開波, 下面係結果.


首先, 每一步隨機會選擇一個方向.
如果該方向係有牆擋著, 而且係Available既.
照行啦, 再mark低已經去左visited 同埋路線既記錄.
(佢有牆擋著 + 牆既下一格又無野, 姐係無效 )


死 行行下無路走.
好彩我有行既記錄 = [ 0, 0, 5, 6, 1, 2, 3, 8, 13, 14, 9 ]


重頭戲Backtrack. 行返轉頭,
又係隨機選擇一個方向 如果係未行過Available
就繼續照行落去.


結局: 最後會返去 最先頭既位置. 所以我地可以確定 全部cell係一定行過既.
迷宮完成. 到解題.
其實個螢幕保護程式 搵路走唔難
每次都會用沿牆法 (左/右手法則)
下圖係用右手法則.

我印像, 一開波係左手, 但遇到石頭 會上下調轉, 變右手.


只要靠著迷宮的一側牆不斷前進
每次遇到岔路都轉向同個方向，如每次遇岔路都右轉或都左轉）
就一定行得晒條迷官, 而代表終點既公仔 一定係隨機既一個位置.
結論: 因為行得晒條迷官, 所以一定會經過終點公仔既位置.

呢一個algorithm缺點 (20x20)
已經開始聞到Big(O)既味道.



我本人唔太好algorithm.
但佢會幫你有系統 有條理地 實現好多野.

大學上堂既功課

寫完之後
即刻後生幾年.

睇黎大家都有返咁上下年紀

左手定律

如果個出口係中間咁點算

成日以為係doom個地圖

講呢D 60歲先係中年.
大家青年姐.

我真係冇印象係會完
上Youtube睇返先記得搵完係再loop

有興趣就上下堂
https://cs50.harvard.edu/ai/2024/weeks/0/

又係喎
你岩

最有趣螢幕保護程式

唔記得左
仲有code.

用返houdini solver node
對比prev-frame同current frame
容易控制同visualize D.

int currentPt = -1;
int nextPt = -1;

int lastPt = point(1, "id", 0);

if (@group_current == 1) {
    currentPt = @ptnum;
}


if (npointsgroup(0, "available") > 0) {
    int nPts[] = nearpoints(0, "available" , @P, 3.1);
    
    if (len(nPts) > 0){
        if(@ptnum == currentPt) {
            nextPt = nPts[floor(rand(@Frame*chi("seed")) * len(nPts))];
        }
        
        if (@group_visited == 0) {
            push(i[]@stack, lastPt);
        }
        
    } else {
        // backtrack;
        if(@group_current == 1) {
            nextPt = pop(i[]@stack);
        }
    }
}

vector currentPos, nextPos;
currentPos = point(0, "P", currentPt);
nextPos = point(0, "P", nextPt);

vector direction = normalize(nextPos - currentPos);

if (direction == set(-1,0,0)) {
    setpointattrib(0, "left", currentPt, 0, "set");
    setpointattrib(0, "right", nextPt, 0, "set");
}
if (direction == set(1,0,0)) {
    setpointattrib(0, "right", currentPt, 0, "set");
    setpointattrib(0, "left", nextPt, 0, "set");
}
if (direction == set(0,0,-1)) {
    setpointattrib(0, "top", currentPt, 0, "set");
    setpointattrib(0, "bottom", nextPt, 0, "set");
}
if (direction == set(0,0,1)) {
    setpointattrib(0, "bottom", currentPt, 0, "set");
    setpointattrib(0, "top", nextPt, 0, "set");
}


setpointgroup(0, "current", currentPt, 0, "set");
setpointgroup(0, "current", nextPt, 1, "set");

setpointgroup(0, "available", currentPt, 0, "set");
setpointgroup(0, "available", nextPt, 0, "set");

setpointgroup(0, "visited", currentPt, 1, "set");
setpointgroup(0, "visited", nextPt, 1, "set");

我記得會有老鼠出現
細個有比佢嚇過,攪到依家都仲記得

確認下先. 睇下我有無get錯.
你出口既意思.
應該係指Windows 3D迷宮個出口公仔?


咁理論上 我由邊一點開始. 公仔只要係tile上面
佢係中間 應該都無問題?

拆牆算法應該冇問題
如果isolated 咗 有路但冇牆連住入口

睇黎都差唔多年紀.

正確.
當去到14 有效既格仔 只係得19.
去到19 下一個有效既格仔 可以係18或者24.
所以可以加一個random seed比佢.
令到佢每一次gen出黎都唔一樣.

nextPt = nPts[floor(rand(@Frame*chi("seed")) * len(nPts))];

樓豬仲有幾條頭髮

揀靠左行 一定行到個迷宮

咁就神仙難救了.

竟然有公仔
原來咁多人會睇住佢

大量頭髮.