Level Generator Update 1 Level Generator - Pastebin.com Level Data - Pastebin.com

大家好,

关于箭头逃脱迷宫的过程生成器，有一个小更新。经过阅读大量的评论和建议，我成功重新设计了生成器算法，结果比之前好多了。之前的版本分为两个独立阶段：

• 将选定的区域分成类似Tetris的形状/链条。
• 然后尝试为每个箭头分配方向和“拉出顺序”以使级别可解。

问题在于这种方法在更大的网格上变得极其缓慢，因为生成器花费了大量时间创建和拒绝了大量无效的布局。生成时间几乎呈指数增长。

新的方法简单得多，令人惊讶地快得多。现在，在放置每个新箭头之前，生成器会立即检查级别是否仍然可解。如果放置创建了一个不可解的状态，它就会尝试另一个箭头。这种方法大大改善了性能，因为：

• 生成器专注于构建一个有效的级别，而不是穷尽数千个破坏的级别。
• 死锁被避免得更早。
• 生成在更大的网格上 scales得更好。

一个有趣的基准事实：旧算法生成一个50x50级别大约比新算法生成一个100x100级别慢5倍。

我最惊讶的事情是，即使是非常大的网格，如100x100或150x150，也在之前的生成速度上极大地加快了。我附上了：

• 更新的代码，
• 一段视频，
• 和一些小基准统计数据，以供感兴趣的人参考。

我仍然觉得还有很多优化的空间，特别是在移动设备上。我的目标是使生成足够快，以便在手机上没有明显的冻结。诚然，我认为这个算法还不是“完美的”。有可能存在更聪明和更快的方法，我很想听听更多的想法。

再次感谢所有对第一篇帖子的反馈——一些评论真的帮助我重新思考整个生成器的结构。另外，我已经决定将之前讨论中的一些人加入游戏的贡献者名单，因为他们帮助解决了这些生成问题。任何人都可以帮助改进这个版本的人将会被百分之百的提名到贡献者名单中。