[發明專利]一種基于3D隨機Prim迷宮的數字置亂方法

有效

• 申請號: 201410745861.2
• 申請日: 2014-12-08
• 公開（公告）號: CN104376527B
• 公開（公告）日: 2018-10-26
• 發明（設計）人: 邵利平
• 申請（專利權）人: 陜西師范大學
• 主分類號: G06T1/00
• 分類號: G06T1/00
• 代理公司: 西安通大專利代理有限責任公司 61200
• 代理人: 陸萬壽

1.一種基于3D隨機Prim迷宮的數字置亂方法，其特征在于包括以下步驟：

第1步：設定迷宮初始范圍S_init＝()_m×n×l和迷宮有效區域S_maze＝(s_i,j,k)_m×n×l為圖像上的3D局部不規則封閉連通區域，對于若則標記s_i,j,k＝-1，反之則標記s_i,j,k＝0表示該節點s_i,j,k未訪問，若s_i,j,k＞0表示該節點s_i,j,k已訪問；

第2步：記s_i,j,k.d,d＝0,1,2,3,4,5依次為節點s_i,j,k的下方墻、右方墻、上方墻、左方墻、底部墻和頂部墻，對于初始化s_i,j,k.d＝-1,d＝0,1,2,3,4,5，即將S_maze范圍內的所有節點以墻進行分隔，s_i,j,k.d＝-1表示有墻，s_i,j,k.d＝0表示無墻；

第3步：選擇隨機數發生器y＝RG(x)，設定初始值RG.init＝seed；

第4步：隨機選取初始化墻列表L_wall＝Φ和節點更新序列A_update＝Φ；

第5步：將s_x,y,z的有效墻，即當前節點與S_maze范圍內未訪問節點之間的分隔墻加入墻列表L_wall＝L_wall.add(s_x,y,z)，將s_x,y,z的坐標(x,y,z)加入節點更新序列A_update＝A_update.add((x,y,z))，標記s_x,y,z＝1；

第6步：從L_wall中隨機刪除一面墻：index＝RG.random(L_wall.length)，s_x,y,z.d＝L_wall.delete(index)，d∈{0,1,2,3,4,5}；

第7步：若d＝0且s_x+1,y,z＝0，則刪除s_x,y,z和s_x+1,y,z之間的分隔墻，且置s_x+1,y,z＝1,x＝x+1；反之若d＝1且s_x,y+1,z＝0，則刪除s_x,y,z和s_x,y+1,z之間的分隔墻，且置s_x,y+1,z＝1,y＝y+1；反之若d＝2且s_x-1,y,z＝0，則刪除s_x,y,z和s_x-1,y,z之間的分隔墻，且置s_x-1,y,z＝1，x＝x-1；反之若d＝3且s_x,y-1,z＝0則刪除s_x,y,z和s_x,y-1,z之間的分隔墻，且置s_x,y-1,z＝1，y＝y-1；反之若d＝4且s_x,y,z-1＝0，則刪除s_x,y,z和s_x,y,z-1之間的分隔墻，且置s_x,y,z-1＝1，z＝z-1；反之若d＝5且s_x,y,z+1＝0，則刪除s_x,y,z和s_x,y,z+1之間的分隔墻，且置s_x,y,z+1＝1，z＝z+1；若存在以上6種情況之一，則將s_x,y,z的有效墻加入墻列表L_wall＝L_wall.add(s_x,y,z)，將(x,y,z)加入節點更新序列A_update＝A_update.add((x,y,z))；

第8步：反復執行第6～7步，直至L_wall＝Φ；

第9步：利用A_update構造S_maze＝(s_i,j,k)_m×n×l范圍內所有節點間的節點位置映射關系，從而將圖像上3D局部不規則封閉連通區域S_maze＝(s_i,j,k)_m×n×l范圍內所有節點進行整體置亂。