arcade製作迷宮，感受試誤學習與頓悟

https://makecode.com/_i5VH6XEsMPyg

最近突然想來做個可以用在動物行為課程的線上迷宮，能夠學習與記憶的動物，在面臨迷宮挑戰時，可以越來越快完成，這個迷宮就是用來體驗這件事。

進入這個迷宮之後，主角會出現在最左邊一欄，而終點會在最右邊一欄，當你費盡心力到達終點後，畫面會顯示你的完成時間，然後就會把你傳送回原來的地點，你必須再度找到終點。

每次完成後，都可以看到你的歷次完成時間。如果你是記性還不錯的動物，你應該可以表現出越來越快完成的趨勢(吧?)

像這類型的活動，以往我是印成紙本發給學生用紙筆完成，但是計時或統計等等都有點麻煩，現在可以用線上完成，真是方便不少。

接下來是程式的部分，這個迷宮是用深度優先搜尋演算法（Depth-First-Search，DFS）來完成的。

首先建立一個填滿0的二維陣列，0代表牆，1代表可移動的空間。未來留下的牆一定在奇數行列的位置，所以接下來任選一個偶數行列的格子開始，選擇任意一個可以打通的方向，把牆打破，能打破代表牆的另一邊還沒有走過，而且不可以把最外圍四周的牆打破。

最後會走到一個格子是完全沒有可以打通的方向，此時就後退到有可以打通方向的格子。

用這個方式就可以建立一個完全歷遍的迷宮，但是這種DFS會產生一條很長一段沒有岔路的通道。所以在建立DFS迷宮之後，再隨機把幾面牆打掉。

最後得到一個處理過的二維陣列，再利用Arcade的內建功能，依據這個陣列建立畫面中的牆或是走道。

迷宮生成還有其他不同的演算法，我也試了用Prim演算法做最小生成樹的，生成一個不同形式的迷宮

https://makecode.com/_J0LMkxHb0Ma1

================

function initializeMaze(rows: number, cols: number): number[][] {

    let maze: number[][] = [];

    for (let i = 0; i < rows; i++) {

        let row: number[] = [];

        for (let j = 0; j < cols; j++) {

            row.push(0); // Fill each cell with 0 (representing a wall)

        }

        maze.push(row);

    }

    return maze;

}

function createVisitedArray(rows: number, cols: number): number[][] {

    let visited: number[][] = [];

    for (let i = 0; i < rows; i++) {

        let row: number[] = [];

        for (let j = 0; j < cols; j++) {

            row.push(0); // Fill each cell with 0 (representing unvisited)

        }

        visited.push(row);

    }

    return visited;

}

// 判斷當前格子是否有路可走

function ifHasRoute(x: number, y: number, maze: number[][], visited: number[][], nr: number, nc: number) {

    let directions = [];

    if (x - 2 > 0  && !visited[y][x - 2]) directions.push([-1,  0]);

    if (x + 2 < nc && !visited[y][x + 2]) directions.push([ 1,  0]);

    if (y - 2 > 0  && !visited[y - 2][x]) directions.push([ 0, -1]);

    if (y + 2 < nr && !visited[y + 2][x]) directions.push([ 0,  1]);

    if (directions.length > 0) {

        // 隨機return一個可走的方向

        return directions[Math.floor(Math.random() * directions.length)];

    } else {

        return [0, 0]; // 沒有可走的路

    }

}

// DFS 生成迷宮的 function

function dfsMaze(maze: number[][], visited: number[][], nr:number, nc:number) {

    let route: number[][] = [];

    // 隨機選擇起始位置

    let x = Math.floor(Math.random() * ((nc - 1) / 2)) * 2 + 1;

    let y = Math.floor(Math.random() * ((nr - 1) / 2)) * 2 + 1;

    route.push([x, y]);

    visited[y][x] = 1;

    maze[y][x] = 1; // 設置起始點為路徑

    let way = ifHasRoute(x, y, maze, visited, nr, nc);

    while (route.length > 0) {

        //console.log("" + x + "_" +y)

        if (way[0] === 0 && way[1] === 0) {

            // 無路可走則回退

            route.pop();

            if (route.length > 0) {

                x = route[route.length - 1][0];

                y = route[route.length - 1][1];

                way = ifHasRoute(x, y, maze, visited, nr, nc);

            }

        } else {

            // 拆除牆並移動

            maze[y + way[1]][x + way[0]] = 1; // 打開牆

            x = x + 2 * way[0];

            y = y + 2 * way[1];

            maze[y][x] = 1; // 新的格子成為路徑

            visited[y][x] = 1;

            route.push([x, y]);

            way = ifHasRoute(x, y, maze, visited, nr, nc); // 繼續新路徑

        }

    }

}

// 隨機打開牆，形成額外的路徑

function openRandomWall(maze: number[][], nr: number, nc: number) {

    let x = Math.floor(Math.random() * ((nc - 1) / 2)) * 2 + 1;

    let y = Math.floor(Math.random() * ((nr - 1) / 2)) * 2 + 1;

    let possibleDirections = [];

    if (x - 2 > 0  && maze[y][x - 1] === 0) possibleDirections.push([-1, 0]); // 左邊

    if (x + 2 < nc && maze[y][x + 1] === 0) possibleDirections.push([1, 0]); // 右邊

    if (y - 2 > 0  && maze[y - 1][x] === 0) possibleDirections.push([0, -1]); // 上邊

    if (y + 2 < nr && maze[y + 1][x] === 0) possibleDirections.push([0, 1]); // 下邊

    if (possibleDirections.length > 0) {

        let direction = possibleDirections[Math.floor(Math.random() * possibleDirections.length)];

        maze[y + direction[1]][x + direction[0]] = 1; // 打開牆

    }

}

function generateMaze(nr: number, nc: number): number[][] {

    let maze: number[][] = initializeMaze(nr, nc);  // Initialize maze (0 means wall, 1 means path)

    let visited: number[][] = createVisitedArray(nr, nc);  // Record whether each cell has been visited

    

    // Generate maze using DFS

    dfsMaze(maze, visited, nr, nc);

    // Open additional walls to create multiple paths

    let additionalPaths = Math.floor((nr/10) * (nc/10));  // Open some additional walls

    for (let i = 0; i < additionalPaths; i++) {

        openRandomWall(maze, nr, nc);

    } 

    return maze;

}

function renderMaze(maze: number[][]){

    for (let y = 0; y < maze.length; y++) {

        for (let x = 0; x < maze[y].length; x++) {

            if(maze[y][x] === 0){

                tiles.setTileAt(tiles.getTileLocation(x, y), sprites.dungeon.floorLight0)

                tiles.setWallAt(tiles.getTileLocation(x, y), true)

            }

            else{

                tiles.setTileAt(tiles.getTileLocation(x, y), assets.tile`transparency16`)

            }

        }

    }

}

function print(array:number[][]){

    for (let i = 0; i < array.length; i++) {

        console.log(array[i])

    }

    console.log("---------------------------")

}

function main(){

    game.showLongText("終點在最右一欄，請快速找到它。\n每次到達之後會被送回原點，再走一次\n試試看你能不能越走越快", DialogLayout.Bottom)

    tiles.setCurrentTilemap(tilemap`map`)

    const nr = 39;

    const nc = 39;

    let maze = generateMaze(nr, nc); 

    let timeArray:number[] = [];

    

    

    renderMaze(maze);

    // 設定主角

    let mySprite = sprites.create(img`

        b b b b b b b b

        1 1 1 5 5 1 1 1

        1 f 1 5 5 1 f 1

        1 1 1 5 5 1 1 1

        5 5 5 5 5 5 5 5

        5 5 5 5 5 5 5 5

        b b 5 5 5 5 b b

        . b b b b b b .

    `, SpriteKind.Player);

    let spritePosY = Math.floor(Math.random() * ((nr - 1) / 2)) * 2 + 1;

    tiles.placeOnTile(mySprite, tiles.getTileLocation(1, spritePosY));

    scene.cameraFollowSprite(mySprite);

    controller.moveSprite(mySprite, 200, 200);

    let startTime = game.runtime();

    let endTime;

    let food = sprites.create(img`

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

        2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

    `, SpriteKind.Food);

    let foodPosY = Math.floor(Math.random() * ((nr - 1) / 2)) * 2 + 1;

    tiles.placeOnTile(food, tiles.getTileLocation(nc - 2, foodPosY));

    //主角到達終點

    sprites.onOverlap(SpriteKind.Player, SpriteKind.Food, function(sprite: Sprite, otherSprite: Sprite) {

        endTime = game.runtime();

        timeArray.push(endTime - startTime);

        tiles.placeOnTile(mySprite, tiles.getTileLocation(1, spritePosY));

        let timeText = "";

        for(let i = 0; i< timeArray.length; i++){

            if (i == 0) { timeText = (1) + "-> " + (timeArray[0]/1000)}

            else{

            timeText +=  "\n" + (i +1) +"-> "  + (timeArray[i]/1000); 

            }

        }

        //game.splash(timeText);

        game.showLongText(timeText, DialogLayout.Bottom)

        startTime = game.runtime();        

    })

    

    

}

main();