程序生成Pacman迷宫的算法

生成随机的吃豆人迷宫是一个看似困难的问题，我花了几个月的时间来解决这个问题。这不容易描述清楚。我希望你有耐心。这个页面是为了开始交流算法是如何工作的。它会慢慢改进(感谢您的反馈)，直到它被尽可能清楚地表达出来。

这些迷宫是精心建造的，以与从“吃豆人”和“吃豆人”中发现的原始地图推导出的设计模式紧密匹配：

仅允许I、L、T或+墙造型，包括偶尔出现的矩形墙。

我们首先在5x9的网格上堆放俄罗斯方块。重力把碎片往左拉，而不是往下拉。生成的俄罗斯方块的边缘对应于迷宫中的可行走路径。然后，该栅格沿左侧垂直轴镜像以创建对称贴图，然后缩放3以形成原始大小为28x31的贴图。

为清楚起见，我将初始5x9网格中的方块、单元格和最终28x31网格中的方块称为Tiles。因此，此算法首先创建像元并将其转换为切片。

上面标题为“简单模型”的图表显示的是俄罗斯方块的5x9网格。使用某种算法一次创建一个单元格，以限制某些位置的块类型(它们被编号以显示创建顺序)。

由于Pac-Man的起始位置和鬼笔位置是恒定的，所以幻影笔和列1的第7行和第8行之间的边缘出现在每个地图中。

单元格直接转换为一组3x3的瓷砖。不幸的是，这会创建一个太短1块和太宽1块的结果地图。因此，我们为每列增加一个单元格的高度，为每行减少一个单元格的宽度，允许生成的地图适合原始游戏的精确尺寸。

如上面标题为高度调整和宽度调整的图表所示，突出显示的单元格是可以更改其大小而不会创建难看的墙(即厚度不均匀的墙)的候选单元格。

箭头占据已选择用于大小调整的单元格。注意防止由于大小改变引起的单元移位导致边缘不连续。

我现在不会对这件事做太多解释。但是上面标题为“边界单元和隧道”的图表有箭头指示候选隧道。突出显示的单元格按颜色显示候选隧道的类型。某些单元格边将被擦除，以使墙与贴图边界(以绿色显示)的连接方式有所不同。隧道创建算法在如何选择不同类型的隧道方面非常复杂。

当单元格最终转换为瓷砖时，剩下的内容如上面标题为“最终路径”的图表所示。在这里，您可以将一个单元格直接映射到一组3x3的平铺。你甚至可以在这张地图上挑出高度和宽度都被调整了1块的单元格。

请看上面标题为“最终平铺”的图表与“最终路径”有何不同。路径从平铺边缘向平铺中心移动。具有通过其中心的路径的每个平铺被转换为路径平铺。最后，任何与路径瓷砖接触的瓷砖都将成为墙瓷砖。地图结构现在已完成。