Clojure中适当地表示2D游戏棋盘

Question

我正在用Clojure做一个小游戏，作为学习练习。在任何特定时间点上，我认为已经确定了游戏状态的表示方式是“可移动物”列表和二维向量的向量，用于“地形”（棋盘方块）。

95%的时间，我希望检查特定方格中是否发生碰撞，这时使用二维向量似乎很合适。但在一些情况下，我需要反过来——找到与某些条件匹配的单元格的(x,y)位置。第一次尝试类似于这样：

(defn find-cell-row [fn row x y]
  (if (empty? row) nil
    (if (fn (first row)) [x y]
      (find-cell-row fn (rest row) (inc x) y))))

(defn find-cell [fn grid y]
  (if (empty? grid) nil
    (or (find-cell-row fn (first grid) 0 y)
        (find-cell (rest grid) (inc y)))))

(def sample [[\a \b \c][\d \e \f]])
(find-cell #(= % \c) sample 0) ;; => [2 0]

我尝试了一种更简洁的方法，使用map-indexed，但它很快变得混乱，并且仍然没有完全满足我的需求。是否有更符合惯用法的方式来进行这种搜索？或者我可以使用不同的数据结构来更好地服务于我自己？也许是一个map {[x y] -> cell}？对我来说，使用map来表示矩阵感觉很奇怪 :)

- kylewm

---

你可以使用Map，但是使用不可变数据结构（如cons-cell）的优点之一是它使得执行MINI-MAX（http://en.wikipedia.org/wiki/Minimax）算法变得容易，因为任何操作都会基本上克隆棋盘。另一方面，我发现通过单元格进行car/cons操作很烦人，通常会采用一些索引结构（数组或映射）。 - Adam Gent

Clojure似乎对使用assoc-in“编辑”单元格（即使用新的不可变数据结构更改值）提供了良好的支持。尽管这个游戏中没有AI，但我确实希望能够“倒回”到以前的时间，因此不可变的结构非常有用。 - kylewm

不确定您所说的 assoc-in 是什么意思，但是在Clojure中，“普通”映射是作为函数式（不可变）树实现的，因此当您修改映射时，您会得到一个新实例，它与先前实例共享许多结构。我在dfs中使用了map {[x y] -> cell} 作为一种结构，效果很好。然而，它感觉非常“奇怪”，所以我将此问题加入书签，以查看是否有更好的解决方案... - andrew cooke

我可以调用(assoc-in sample [0 2] \z)来创建一个副本，将样本中的\c更改为\z。感谢你们两个的反馈。 - kylewm

assoc-in 有点奇怪。基本的 assoc 执行我所描述的操作，我认为那是你想要的（我想？！）。 - andrew cooke

assoc-in 允许在嵌套的数据结构中创建路径。它会动态地创建缺失的中间节点，因此 (assoc-in {} [:a :b :c] 3) => {:a {:b {:c 3}}}。 - sw1nn

Answer 1

一个嵌套向量在这种情况下是很常见的，如果使用 for 循环可以轻松而不丑陋地扫描它：

(let [h 5, w 10]
  (first
   (for [y (range h), x (range w)
         :let [coords [y x]]
         :when (f (get-in board coords))]
     coords)))

- amalloy

---

太棒了，谢谢。稍微调整一下，我认为我已经得到了一个非常满意的解决方案。(defn find-cell [pred s] (first (for [[y row] (map-indexed vector s) [x cell] (map-indexed vector row) :when (pred cell)] [x y])))这种语言真是太有趣了。 - kylewm

我猜你在使用map-indexed做一些优化或其他什么事情？在让代码变得更复杂以获得速度之前，我真的建议你进行性能分析或基准测试 - 我非常确定创建所有这些临时集合的成本比索引向量要高得多。 - amalloy

完全不是...只是个人偏好。在Java中，我也使用Iterables而不是for(int i = 0...)。 - kylewm

Answer 2

使用一个简单的向量，就可以使用所有通常的函数，并根据需要提取[x y]。

(def height 3)
(def width 3)

(def s [\a \b \c \d \e \f \g \h \i])

(defn ->xy [i]
    [(mod i height) (int (/ i height))])

(defn find-cell 
    "returns a vector of the [x y] co-ords of cell when
     pred is true"
    [pred s]
    (let [i (first (keep-indexed #(when (pred %2) %1) s))]
      (->xy i)))

(find-cell #(= \h %) s)
;=> [1 2]

(defn update-cells 
    "returns an updated sequence s where value at index i
     is replaced with v. Allows multiple [i v] pairs"
    [s i v & ivs]
    (apply assoc s i v ivs))

(update-cells s 1 \z)
;=> [\a \z \c \d \e \f \g \h \i]

(update-cells s 1 \p 3 \w)
;=> [\a \p \c \w \e \f \g \h \i]

- sw1nn

---

任何想法这种方式与使用副本进行数据共享的映射相比如何？如果您正在处理可能回溯的过程中进行大量小更改，哪种更节省内存？我怀疑两者都将以32个一组的方式块处理，但没有具体数字。 - andrew cooke

据我所知，结构共享适用于所有持久数据结构，不确定向量与映射的低级细节。另一个好处是向量的索引访问被优化了。 - sw1nn

谢谢！这很有道理，看了你的例子，我学到了一些额外的东西 :) - kylewm

没问题。请参考https://dev59.com/a2025IYBdhLWcg3wbVWn以了解更多关于使用简单数据结构的理由... - sw1nn