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}]))
Возможно ли что-то подобное? (Это только дает мне ноль для печати)
Решение
Ваш точка ключа это карта, где каждый ключ также является картой, которая работает. 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) мало что дает, и многое можно получить.
Другие решения
Других решений пока нет …