c++ - 语言;为二维空间中的对象设计用于碰撞检测的高性能数据结构

Question

我正在用 clojurescript 编写游戏。

• 它有一个 2D 游戏区域，例如 x 和 y 轴上从 0 到 10000。
• 在这个区域可以有不同大小的点。
• 如果玩家触摸到一个点，它将被删除。
• 最多可以有 2500 个点，甚至更多。

由于玩家可以移动每一帧，我必须每秒检查所有 ~2500 个点 60 次。

如果如果哪里有这个数据结构:

(defonce state (atom {:food [{:center {:x 19 :y 51} :radius 1.78 :area 10}
                             {:center {:x 12 :y 34} :radius 1.78 :area 10}]}))

我认为它非常缓慢且效率低下。

在 C/C++ 中，我可能会创建一个 10000 x 10000 的数组，并将索引用作指向我的对象的指针的 x 和 y 值/键。这样我只需要弄清楚玩家目前有多大以及他的 body 覆盖了游戏区域的哪些点。然后我只需要检查那些指标。

dot dots[10000][10000];
// if player where a square of 5 at the moment at x=123 y=456
for (int i = 0; i < 5; i++) {
  for (int j = 0; j < 5; j++) {
    isDot(dots[123+i][456+j]);
  }
}

Clojure 及其数据结构是否有类似的方法？

---

我试图拥有一个“点键”并试图像这样检索它的值:

(def state (atom {:food { {:x 123 :y 456}{:radius 1.783 :area 9.9}
                          {:x 321 :y 654}{:radius 1.784 :area 10}}}))

(println (get-in @state [:food {:x 123 :y 456}]))

这样的事情可能吗？ (这只会给我零打印)

Answer 1

查找表的三个选项

您的点键是一个 map ，其中每个键也是一个 map ，这确实有效。您在 REPL 中看到的 nil 实际上是调用 println 返回的结果。 (get-in @state [:food {:x 123 :y 456}]) 部分工作正常；它返回与键 {:x 123 :y 456} 关联的值。

我可以想到 CLJS 中查找表的三个选项，这些选项可以直接实现:普通 JS 数组、嵌套的 ClojureScript vector 和嵌套映射。后者是“点键”的变体，其中第一个 map 按行号索引，内部嵌套 map 按列号索引(反之亦然)。

下面是初始化三种数据结构的例子:

; plain JS Array
(def js-array (reduce (fn [acc _] (do (.push acc (make-array 10000)) acc)) (array) (range 10000)))

; nested CLJS vectors
(def vec-array (->> false (repeat 10000) vec (repeat 10000) vec))

; nested CLJS map
(def map-grid (reduce #(assoc-in % [(rand-int 10000) (rand-int 10000)] {:radius 1.78 :area 10}) {} (range 2500)))

请注意普通 JS 数组的可变状态如何强制代码不那么惯用。

查找性能测量

快速而肮脏的性能测试表明，普通 JS 数组(仅)在查找方面比其他两个更有效。以下代码显示了 100k 次查找的性能测试:

(defn exec-time [get-fn n]
  (do (time (reduce (fn [x y] (or x y)) ;; stop compiler from optimizing lookups away :-)
                    (repeatedly n get-fn)))
   nil)) ;; Suppress output

(exec-time #(aget js-array (rand-int 10000) (rand-int 10000))
           100000)

(exec-time #(-> (nth vec-array (rand-int 10000))
                (nth (rand-int 10000)))
           100000)

(exec-time #(get-in map-grid [(rand-int 10000) (rand-int 10000)])
           100000)

我在 Figwheel REPL 中重复每个系列 100k 查找 10 次的结果:

• 普通 JS 数组:平均。 116，最小 100，最大 156(毫秒)
• 嵌套 vector :平均。 141，最小 128，最大 194
• 嵌套 map :平均。 246，最少 232，最多 305

性能差异非常小，我会根据方便选择您的查找结构。在这种情况下，我更喜欢 CLJS 不可变结构(例如 vector )而不是普通 JS。另请注意 the performance of cljs data structures compares very favourably to Immutable.js 。如果您只执行每帧 25 次查找的规模，那么使用 Clojure(Script) 的持久数据结构几乎没有什么损失，而且可以获得很多。