首页 文章

生成具有指定长度路径的迷宫

提问于
浏览
0

我的问题非常简单,但很难做到 . 我有迷宫的大小和路径的长度 . 我需要找到完全指定长度的路径 . 然而,迷宫可以包含有效的较长路径 . 迷宫总是从[0,0]开始,以[尺寸X,尺寸Y]结束 . 路径长度为13的5x5迷宫示例:( X :wall, - :path)

---XX
XX-XX
---XX
-XXXX
-----

6x6迷宫,11路径长度(包含另一条大小为15的路径) - 是有效的

------
XX-XX-
---XX-
-XXXX-
-XXXX-
------

我已经尝试了很多算法,但没有任何效果 . 如果有人能给我一些关于我需要做什么或者我可以在哪里阅读这个问题的提示,那将是很好的 .

1 回答

  • 0

    首先是作为通用概念的逻辑:你从左上角开始,给出单元格0.现在对于所有有效单元格,只需到这个单元格,给它一个1.继续向前移动,始终在所有方向上,将单元格增加1 . 当你在右下方时,你有最短的路线!

    现在我们需要看一下方向性影响 . 当我们离开右下角时,我们必须再向前迈进一步 . 所以最小步数为12,每条较大路径为p 2.在15的路径中,我们从右下方移动2步(步骤5和6),因此路径长度= 12 2 * 2 = 16 .

    生成迷宫必须有点随机,但同时它应该满足路径长度的请求 . 如果我们想要从底部向右移动一个以产生路径长度,我们需要在向前方向上(右上下或右下 - 右)至少进行1次相同的移动 . 如果我们想要移动2,我们需要2 2,等等 .

    如果你真的想要随机,你需要使用回溯,你尝试每个可能性并检查是否仍然可以完成步骤 . 让我们看下面的例子,我们想要14个步骤):当我们放置7时,单元格[2,3]和[4,3]被阻止 . 当我们放置8时,细胞[2,4],[2,5]和[3,5]被阻断 . 现在没有剩余空间向左或向上移动,因此无法在[4,4]上放置8 . 8可以放在[2,4]上 .

相关问题