迷宮與王氏磚

March 25, 2022

迷宮可以視為一種編碼系統,基於迷宮中各細胞被給予的編碼,能進一步地轉換為其他編碼,〈哈密頓路徑〉看過其中一種轉換方式,現在來試試另一種轉換。

細胞通道類型

在之前的迷宮探討中,都是針對迷宮的牆面類型,來看看另一個角度,對於一個迷宮,每個細胞可以擁有的通道類型有哪些呢?如果將遮罩(也就是不能走的細胞)考量進去,總共會有 16 種:

迷宮與王氏磚

在上面的圖中,對於每個細胞的通道類型,給予一個編號,編號的依據是給予四個方向 1、2、4、8 的數字,如果某方向有通道,就累加該方向的數字,例如:

迷宮與王氏磚

在上面的細胞中,有通道的方向分別對應數字 2、4、8,累加結果是 14,因此該細胞編號為 14,如果你有一組細胞的牆面資訊,將之轉換為細胞的通道資訊,依編號畫出各自對應的通道類型,最後當然還是畫出迷宮。

細胞的通道類型編號方式,其實是來自於〈王氏磚〉,它是種密鋪平面的方式,如果你的目的只是密鋪平面,隨機在每個邊上產生 0 與 1,每個邊給予 1、2、4、8 的數字,然後每個磚看看某方向邊是否為 1,若是 1 就累加該邊上的數字就可以了。

然而,如果你的目的是密鋪後要建立迷宮,隨機產生 0 與 1,並不會構成完全迷宮,因為密鋪後的道路可能會產生迴圈,你得對邊上產生 0 與 1 的方式加點限制,方式之一就是生成迷宮資訊,再轉換為邊上的 0 與 1 資訊。

maze_wang_tiles 函式

dotSCAD 的 maze_wang_tiles 函式,可以接受 maze_square 產生的細胞資料,轉換為細胞的通道資訊,傳回的資料是一組 [x, y, n],x、y 是細胞的位置,n 是 0 到 15 的編號,可以根據這組資料來畫出迷宮,一個簡單的實現是:

use <maze/mz_square_initialize.scad>
use <maze/mz_square.scad>
use <maze/mz_wang_tiles.scad>
use <util/rand.scad>

rows = 10;
columns = 10;

cells = mz_square(rows, columns);

tiles = mz_wang_tiles(cells);

tile_width = 30;
for(tile = tiles) {
    translate([tile.x, tile.y] * tile_width)
        tile(tile[2], tile_width);
}

module tile(type, width) {
    // true 表示該方向有通道
    roads = [
        [false, false, false, false],
        [true, false, false, false],
        [false, true, false, false],
        [true, true, false, false],
        [false, false, true, false],
        [true, false, true, false],
        [false, true, true, false],
        [true, true, true, false],
        [false, false, false, true],
        [true, false, false, true],
        [false, true, false, true],
        [true, true, false, true],
        [false, false, true, true],
        [true, false, true, true],
        [false, true, true, true],
        [true, true, true, true]
    ];

    difference() {
        square(width, center = true);
    
        for(i = [0:3]) {
            if(roads[type][i]) {
                rotate(-90 * i)
                translate([-width / 4, -width / 4])
                    square([width / 2, width]);
            }
        }
    }
}

這會畫出以下的結果:

迷宮與王氏磚

誒?這樣畫的意義是?你可以自由地設計 tile 模組的內容,只要每個類型的細胞畫出來後,可以良好銜接,你的迷宮就可以有更多元的變化了,例如,來建立一座〈迷宮城〉?

迷宮與王氏磚

因為迷宮的建立與轉換,分別都封裝在 maze_squaremaze_wang_tiles 函式,你就可以專心地設計每個細胞該怎麼畫,例如,也許每個細胞畫成一種水管,就可以產生迷宮管路了:

迷宮與王氏磚

分享到 LinkedIn 分享到 Facebook 分享到 Twitter