迷宫生成算法的惯用语Clojure实现

Question

我正在实现算法来创建和解决Python和Clojure中的迷宫.我有Python的经验,正在努力学习Clojure.我可能在从Python到Clojure的转换过程中,我正在寻找一种更惯用的方式来实现Clojure中的代码.

首先是有效的Python实现

import random

N, S, E, W = 1, 2, 4, 8
DX = {E: 1, W: -1, N: 0, S: 0}
DY = {E: 0, W: 0, N: -1, S: 1}
OPPOSITE = {E: W, W: E, N: S, S: N}


def recursive_backtracker(current_x, current_y, grid):
    directions = random_directions()
    for direction in directions:
        next_x, next_y = current_x + DX[direction], current_y + DY[direction]
        if valid_unvisited_cell(next_x, next_y, grid):
            grid = remove_walls(current_y, current_x, next_y, next_x, direction, grid)
            recursive_backtracker(next_x, next_y, grid)
    return grid


def random_directions():
    directions = [N, S, E, W]
    random.shuffle(directions)
    return directions


def valid_unvisited_cell(x, y, grid):
    return (0 <= y <= len(grid) - 1) and (0 <= x <= len(grid[y]) - 1) and grid[y][x] == 0


def remove_walls(cy, cx, ny, nx, direction, grid):
    grid[cy][cx] |= direction
    grid[ny][nx] |= OPPOSITE[direction]
    return grid

现在是我到目前为止的Clojure版本.目前我认为它不起作用,因为我正在使用for宏,它在需要传递向量时将符号传递给recur.当我试图找到这个问题的解决方案时,我觉得我太努力强迫代码成为Python,这促使了这个问题.任何指导表示赞赏.

(ns maze.core)

(def DIRECTIONS { :N 1, :S 2, :E 4, :W 8})
(def DX { :E 1, :W -1, :N 0, :S 0})
(def DY { :E 0, :W 0, :N -1, :S 1})
(def OPPOSITE { :E 8, :W 4, :N 2, :S 1})

(defn make-empty-grid
  [w h]
  (vec (repeat w (vec (repeat h 0)))))

(defn valid-unvisited-cell?
  [x y grid]
  (and
    (<= 0 y (- (count grid) 1)) ; within a column
    (<= 0 x (- (count (nth grid y)) 1)) ; within a row
    (= 0 (get-in grid [x y])))) ; unvisited

(defn remove-walls
  [cy, cx, ny, nx, direction, grid]
  (-> grid
    (update-in [cy cx] bit-or (DIRECTIONS direction))
    (update-in [ny nx] bit-or (OPPOSITE direction))))

(defn recursive-backtracker
  [current-x current-y grid]
  (loop [current-x current-x current-y current-x grid grid]
    (let [directions (clojure.core/shuffle [:N :S :E :W])]
      (for [direction directions]
        (let [next-x (+ current-x (DX direction))
              next-y (+ current-y (DY direction))]
          (if (valid-unvisited-cell? next-x next-y grid)
            (loop next-x next-y (remove-walls current-x current-y next-x next-y direction grid)))))
      grid)))

Answer 1

这似乎是一个基本上合理的Python代码转换为Clojure(包括一些初学者经常错过的东西 - 很好地完成)......直到我们到达recursive-backtracker,问题的核心.你不能在这里音译Python,因为你的算法假设可变grid:你在for循环内递归四次,并且需要对网格进行更改才能反映出来.这不是Clojure的工作方式,所以这一切都行不通.你得到的实际错误是一个不相关的语法错误(仔细检查接口到循环/重复),但它在这里并不真正相关,因为你必须重写函数,所以我会留下它.

现在,如何在不改变的情况下重写此函数grid？通常情况下,您可以使用reduce:对于四个方向中的每个方向,调用recursive-backtracker,返回修改后的网格,并确保使用该修改后的网格进行下一次递归调用.总体大纲如下所示:

(defn recursive-backtracker
  [current-x current-y grid]
  (reduce (fn [grid direction]
            (let [next-x (+ current-x (DX direction))
                  next-y (+ current-y (DY direction))]
              (if (valid-unvisited-cell? next-x next-y grid)
                (recursive-backtracker next-x next-y
                                       (remove-walls current-x current-y next-x next-y
                                                     direction grid))
                grid)))
          grid, (clojure.core/shuffle [:N :S :E :W])))

有了这个定义,(recursive-backtracker 0 0 (make-empty-grid 5 5))产生[[2 5 6 3 5] [4 10 9 6 9] [14 3 1 12 4] [12 6 3 9 12] [10 11 3 3 9]]- 是一个有效的迷宫吗？看起来没问题,但我不知道.你可能也没有.这让我想到另一点:使用整数和按位算法是无意义优化的练习.相反,让网格中的每个条目都是一个地图或一组,其中包含说明哪些方向是开放的关键字.然后在检查时,您至少可以了解迷宫是否自洽.