语言;在 2D Space 中为 objects 设计用于碰撞检测的高性能数据结构

Question

我正在用 clojurescript 编写游戏。

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

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

if if 哪里有这个数据结构：

(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 value/keys 指向我的 object 的指针。这样我只需要弄清楚玩家当前有多大以及他的 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

查找的三个选项table

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

我可以想到在 CLJS 中查找 table 的三个选项，它们可以直接实现：普通 JS 数组、嵌套的 ClojureScript 向量和嵌套映射。后者是 "point key" 的变体，其中第一个地图按行号索引，内部嵌套地图按列号索引（反之亦然）。

下面是三个数据结构的初始化示例：

; 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 数组的 mutable 状态如何强制代码不那么惯用。

已测量查找性能

一项快速而肮脏的性能测试表明，普通 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（毫秒）
嵌套向量：平均。 141，最小 128，最大 194
嵌套地图：平均。 246，最小 232，最大 305

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

语言;在 2D Space 中为 objects 设计用于碰撞检测的高性能数据结构

Clojure; Design performant data structure for objects in 2D Space for collision detection

c++

performance

data-structures

clojurescript

查找的三个选项table

已测量查找性能