一种基于2D Growing Tree 迷宫的数字置乱方法

摘要

本发明提供一种基于2D Growing Tree迷宫的数字置乱方法，预先对Growing Tree迷宫生成区域进行人为限定，从而可用于人为指定的任意2D封闭连通区域，同时按迷宫节点更新顺序对迷宫设定区域的每个节点赋予唯一编号，由此产生迷宫设定区域所有节点的排列，在此基础上构造了基于2D Growing Tree迷宫的节点更新序列和节点更新序列复合的置乱方法，从而可将所有节点置乱。本发明所给出的置乱方法具有普适性和灵活性，在使用过程中不存在任何限制，不仅能用于传统置乱方法所针对的规则区域，例如正方形和矩形区域，也可用于任意选定的2D封闭连通不规则区域置乱。本发明也给出了用于像素矩阵，R、G、B通道矩阵和比特位面的图像置乱方法。

主权项

一种基于2D Growing Tree迷宫的数字置乱方法，其特征在于包括以下步骤：第1步：设定迷宫初始范围S_init＝()_m×n和迷宫有效区域S_maze＝(s_i,j)_m×n，对于i＝0,…,m‑1,j＝0,…,n‑1，若则标记s_i,j＝‑1，反之则标记s_i,j＝0表示该节点未访问，若s_i,j>0表示该节点已访问；第2步：对于i＝0,…,m‑1,j＝0,…,n‑1，记s_i,j.d,d＝0,1,2,3依次为节点s_i,j的下方、右方、上方和左方墙，初始化s_i,j.d＝‑1,d＝0,1,2,3，即将S_maze范围内的所有节点以墙进行分隔，s_i,j.d＝‑1表示有墙，s_i,j.d＝0表示无墙；第3步：选择随机数发生器y＝RG(x)，设定初始值RG.init＝seed，初始化迷宫节点列表A_maze＝Φ，节点更新序列A_update＝Φ，由随机数发生器产生2个概率P_recent,P_oldest∈[0,1)；第4步：选取将s_x,y分别加到A_maze和A_update，即A_maze＝A_maze.add(s_x,y)A_update＝A_update.add(s_x,y)；第5步：若A_maze≠Φ，则循环执行第6步～第8步；第6步：产生1个随机数P∈[0,1)，若P∈[0,P_recent]，则取A_maze尾部元素作为当前节点s_x,y；反之若P∈[P_recent,P_recent+P_oldest]，则取A_maze头部元素作为当前节点s_x,y，反之则从A_maze中随机取一个元素作为当前节点s_x,y，s_x,y＝A_maze(index),index＝random(A_maze.length)；第7步：若s_x,y周围的邻近节点中s_x+1,y,s_x,y+1,s_x‑1,y,s_x,y‑1存在未访问的有效节点s_x′,y′∈S_maze，则将s_x′,y′加入到A_maze，即A_maze＝A_maze.add(s_x′,y′)，A_update＝A_update.add(s_x′,y′)；第8步：若s_x,y周围的邻近节点中s_x+1,y,s_x,y+1,s_x‑1,y,s_x,y‑1不存在未访问的有效节点s_x′,y′∈S_maze，则删除A_maze索引位置为Index位置的元素，即A_maze.delete(index)；第9步：利用A_update构造S_maze＝(s_i,j)_m×n范围内所有节点间的映射关系，从而将S_maze＝(s_i,j)_m×n范围内的所有节点置乱。