Clojure; Разработка исходной структуры данных для объектов в 2D-пространстве для обнаружения столкновений

Я пишу игру в Clojurescript.

  • Он имеет 2D игровую область, например, от 0 до 10000 по осям X и Y.
  • В этой области могут быть точки разных размеров.
  • Если игрок коснется точки, она будет удалена.
  • Может быть до 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 на 10000 и использовал бы указатели как значения x и y / ключи для указателя на мой объект. Таким образом, мне нужно будет только выяснить, насколько велик игрок в данный момент и какие точки игровой зоны покрывает его тело. Тогда мне нужно будет только проверить эти признаки.

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}]))

Возможно ли что-то подобное? (Это только дает мне ноль для печати)

1

Решение

Ваш точка ключа это карта, где каждый ключ также является картой, которая работает. nil что вы видите в своем REPL на самом деле то, что звонит println возвращается в результате. (get-in @state [:food {:x 123 :y 456}]) часть работает нормально; возвращает значение, связанное с ключом {:x 123 :y 456},

Я мог бы придумать три варианта таблицы поиска в CLJS, которые просто реализовать: простой массив JS, вложенные векторы ClojureScript и вложенные карты. Последний вариант вашего «точечного ключа», где первая карта индексируется по номеру строки, а внутренняя вложенная карта по номеру столбца (или наоборот).

Вот пример инициализации каждой из трех структур данных:

; 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 Array (только) немного более эффективен для поиска, чем два других. В следующем коде показано тестирование производительности с поиском 100 КБ:

(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)

Мои результаты повторения каждой серии поисков по 100 тысяч раз в Figwheel REPL:

  • обычный массив JS: ср. 116, минимум 100, максимум 156 (мсек)
  • вложенные векторы: ср. 141, минимум 128, максимум 194
  • вложенные карты: ср. 246, минимум 232, максимум 305

Различия в производительности настолько малы, что я бы выбрал вашу структуру поиска просто исходя из удобства. В этом случае я бы предпочел неизменяемые структуры CLJS (например, векторы) над простым JS. Обратите внимание, что производительность структур данных cljs очень выгодно отличается от Immutable.js. Если вы выполняете что-то только в масштабе 25 поисков на кадр, то использование постоянных структур данных Clojure (Script) мало что дает, и многое можно получить.

1

Другие решения

Других решений пока нет …