如何创建随机路径？

Question

我正在寻找一种算法，可以生成类似于这张图片中的内容：

我已经了解了醉汉漫步算法，但它们似乎不太适合我需要的东西。我不确定是否可以通过大量修改醉汉漫步算法来实现我想要的效果，或者是否应该寻找其他算法进行调整。

- Talon876

---

@TedHopp 是的，路径不交叉是很重要的。 - Talon876

您需要的是一种称为自避随机游走（Self Avoiding Random Walk）的方法，通常缩写为SAW。在谷歌上搜索您会发现几种生成方法，因为这是物理学、化学和生物学中研究非常重要的问题。DNA、聚合物及其他现象都与此类事物有关。不要指望找到简单有效的算法…… - Dr. belisarius

就此而言，那张图片看起来像是一个畸形的空间填充曲线。它可能只是一个http://en.wikipedia.org/wiki/Hilbert_curve的映射，就像http://www.worldpopulationatlas.org/上的扭曲地图一样。 - mcdowella

为什么不雇用五岁的孩子——这可能更便宜，并且具有真正的随机来源。 - Lior Kogan

@LiorKogan，确实雇佣5岁的孩子会更便宜，但你确定他们会编程吗？ - Tomas

Answer 1

由于您想避免自相交，随机游走将很难正确执行。您可能会轻易地陷入困境。我建议从一个跨越该区域的单个线段开始，然后在中间某处分割此线段，并将中点移动一些与线段长度成比例的随机量。对于两个新的线段，递归重复此过程。如果您得到一个导致两个新线段之一穿过现有线段的中点，则尝试不同的中点。当您的线段变短（无论您如何定义）时停止递归。

- Vaughn Cato