在LispWorks中进行编程24：逻辑迷宫
Category:UI界面编写逻辑迷宫
逻辑迷宫是一个难题，其任务是根据某些逻辑规则找到通过迷宫的路线。一种流行的逻辑迷宫类型是Jumping Maze（有时也称为数字迷宫），其中每个单元格都包含一个数字，告诉您可以跳到下一个单元格的距离。
这是一个典型的跳跃迷宫，叫做连锁反应。你从左上角开始，你必须找到通过水平或垂直跳跃到右下角的最短路线：
例如，从开头的4开始，您可以跳到第一行中最右边的2，或最左边列中的底部3，依此类推：
在这个项目中，我们将编写一个Lisp程序来解决任意跳跃迷宫。
完整列表
代表迷宫
我们将从左上角的0开始对迷宫中的单元格进行编号，因此在此示例中，最终单元格为35。
迷宫将表示为数字列表; 在这种情况下，迷宫是：
(defparameter maze ‘(4 4 2 2 2 5 5 1 2 3 1 2 3 3 3 2 3 4 2 1 2 2 3 5 3 3 3 3 4 1 4 3 5 2 5 0))
另外四个参数指定迷宫的起点，目标和大小：
(defparameter start 0)(defparameter goal 35)(defparameter width 6)(defparameter height 6)
制定可用的动作
下一步是计算每个方格的可用移动。过程 解析板返回一个可以从迷宫中的每个单元格中获取的单元格列表; 对于这个迷宫，它如下：
CL-USER > (parse-board maze width height)((4 24) (5 25) (0 4 14) (1 5 15) (2 16) (0 35) (11) (6 8 13 1) (6 10 20) (6 27) (9 11 16 4) (9 23) (15 30) (16 31) (17 32) (13 17 27 3) (13 34) (13) (20 30 6) (18 20 25 13) (18 22 32 8) (19 23 33 9) (19 4) (18) (27 6) (28 7) (29 8) (24 9) (24 4) (28 35 23) (34 6) (34 13) (2) (31 35 21) (4) NIL)
例如，此列表中的第一个元素（4 24）表示您可以从起始单元格到达单元格4和24。
该过程扫描迷宫的每一行和每列，并且对于每个单元计算四个方向中的每一个的目标单元。它测试目的地是否是板上的有效方块：
(and (< -1 x) (< x size-x) (< -1 y) (< y size-y))
如果是这样，它会将单元格添加到移动列表中。
我们在全局参数移动中存储这个有效移动列表：
(defparameter moves (parse-board maze width height))
代表当前的状态
当我们通过迷宫搜索路线时，我们将使用列表来存储当前的小区编号以及到目前为止所采用的路线。例如，在访问单元格0 4和16之后，状态将为：
(16 (4 0))
过程 next-moves将当前状态作为参数，并返回与您可以从当前单元格到达的每个单元格对应的状态列表：
(defun next-moves (state) (let* ((cell (first state)) (route (second state)) (result nil)) (dolist (move (nth cell moves)) (setf result (cons (list move (cons cell route)) result))) result))
这是一个例子
CL-USER > (next-moves ‘(16 (4 0)))((34 (16 4 0)) (13 (16 4 0)))
换句话说，我们可以从细胞16到达细胞34或13。
最后，树搜索呼叫接下来移动以跟踪通过迷宫的每条可能路线，直到达到指定目标：
(defun tree-search (states) (if (null states) nil (if (= (first (first states)) goal) (reverse (cons (first (first states)) (second (first states)))) (tree-search (append (rest states) (next-moves (first states)))))))
该程序的逻辑如下：
- 如果状态列表为空则没有解决方案，所以停止。
- 如果州列表中的第一项已达到目标，则返回我们找到的路线。
- 否则继续搜索其余状态，然后搜索您可以从第一个状态到达的单元格。
因为我们首先检查最短的路线，然后在下一次移动中延伸它们，这种方法（称为广度优先搜索）成功地找到通过迷宫的最短路线。
运行程序
最后，我们可以通过调用来运行程序：
CL-USER > (tree-search (list (list start nil)))
这将使用包含起始单元格和空路径的列表开始搜索。结果回来了：
(0 24 6 11 23 18 20 22 19 25 7 1 5 35)
这给了我们迷宫的解决方案！
扩展项目
对角线移动
除了水平或垂直之外，一些跳跃迷宫还允许您沿对角线移动。适应这条规则只是改变解析板中的相应线以包括对角线移动：
(dolist (d ‘((0 -1) (0 1) (1 0) (-1 0) (-1 -1) (-1 1) (1 -1) (1 1))
参考
你可以在我的逻辑迷宫网站Mazelog找到更多跳跃迷宫和其他类型的逻辑迷宫：
一些最令人印象深刻的跳跃迷宫（或数字迷宫）由游戏和迷宫设计师Robert Abbott设计。你可以在他的网站上找到几个; 例如：
http://mip.i3geek.com
