求符合指定规则的infinite perfect maze生成算法及f(s,x,y)查询函数

我查找过相关资料，甚至访问过专门的迷宫算法收集网站，但没有找到满足以下所有要求的算法。现明确需求，需寻找符合下述规则的无限迷宫生成算法：

核心规则 #

• 生成完美迷宫（perfect maze），需满足：
  • 基于二维网格实现
  • 每个网格仅为space（空地）或wall（墙体）两种类型
  • 任意两个空地之间连通且仅存在唯一路径
  • 不存在全为空地/全为墙体的2x2网格块，保证视觉效果
• 需可提供形如f(s, x, y)的查询函数，其中s为random seed（随机种子）或同类随机参数：
  • 函数返回坐标(x, y)处的网格类型
  • 当s取值在0~32768左右区间时，不同s值对应生成不同的迷宫
• 迷宫为无限属性，实际可受64位整数取值范围限制
• 允许算法占用额外的程序运行空间

补充说明 #

• 此处无限的定义参考如下示例逻辑：

function f(s, x, y){
    // 对任意输入的x,y都能返回对应结果，因此认为其具备“无限”属性
    return (s*x+y)%32768<30 ? "wall" : "space";
}

• 下述为满足完美迷宫生成规则的有限迷宫生成算法，可供参考：

初始化：所有网格填充为墙体
选择一个网格，标记后加入列表
当列表不为空时
{
    从列表中随机选择节点<x>
    将<x>从列表中移除
    如果<x>已被标记
    {
        删除<x>，跳过本次循环
    }
    标记<x>
    如果<x>周围的墙体数量≤1
    {
        将四周的4个墙体加入列表
    }
}

• 下述为同时满足完美迷宫规则、无限属性的实现思路，基于Eller算法改造：

逐行生成迷宫，同时保存区域集合
第一行：所有区域加入集合，区域间随机生成墙体
当未生成到最后一行时 {
    遍历所有相邻区域 {
        如果不属于同一个集合 {
            随机打通间隔的墙体并合并区域
        }
    }
    遍历所有区域 {
        随机打通向下的墙体，每个区域至少打通一个
    }
    生成下一行
    对当前行执行：{
        遍历所有区域 {
            如果和上方区域连通
            {
                合并到上一行的集合
            }
        }
        丢弃上上行的集合数据
    }
}
最后一行：连通所有不属于同一集合的区域

如果从中心开始逐层环形生成可以实现无限效果，但该思路无法满足随机种子查询函数的要求。

内容的提问来源于stack exchange，提问作者Rratic