A quadtree implementation for clojure(script) inspired by this implementation of a quadtree, but with a dash of functional programming flair added by yours truly.
All transform functions take a quadtree and return a new one. There's nothing fancy going on, just good ol' Clojure maps. So you can break the tree if you're not careful. I recommend using the built in functions to create your quadtree and pass it around in a binding.
To start building a quadtree, create a quadtree using ->quadtree with a bounds for the root node.
user> (use 'quadtree-cljc.core)
user> (def tree (-> (->bounds 0 0 800 600)
(->quadtree 5 5)))
#'user/tree
user> tree
{:bounds {:x 0, :y 0, :width 800, :height 600},
:max-objects 5,
:max-levels 5,
:level 0,
:objects [],
:nodes []}
user>Now you can insert a node into the tree like so:
user> (insert tree {:x 5 :y 10 :width 10 :height 10})
{:bounds {:x 0, :y 0, :width 800, :height 600},
:max-objects 1,
:max-levels 10,
:level 0,
:objects [{:x 5, :y 10, :width 10, :height 10}],
:nodes []}
user>Or you can insert multiple with insert-all:
user> (def tree (-> (->bounds 0 0 800 600)
(->quadtree 5 5)
(insert-all [{:x 0 :y 0 :width 10 :height 10}
{:x 0 :y 5 :width 10 :height 10}
{:x 100 :y 150 :width 100 :height 100}
{:x 160 :y 390 :width 10 :height 10}])))
#'user/tree
user>And finally we can even find colliding / intersection objects in the tree:
user> (-> (->bounds 0 0 800 600)
(->quadtree 5 5)
(insert-all [{:x 0 :y 0 :width 10 :height 10}
{:x 0 :y 5 :width 10 :height 10}
{:x 100 :y 150 :width 100 :height 100}
{:x 160 :y 390 :width 10 :height 10}])
(retrieve-intersections {:x 110 :y 160 :width 10 :height 10}))
[{:x 100, :y 150, :width 100, :height 100}]
user>Oh, and quadtree-cljc is fast:
;; Benched with criterium on JDK21/M2 Max MBP
user> (let [entities (generate-entities ->random-large-entity 1000)
player (->random-small-entity)]
(bench/bench (-> (->bounds 0 0 1920 1080)
(->quadtree 1020 100)
(insert-all entities)
(retrieve-intersections player))))
Evaluation count : 155640 in 60 samples of 2594 calls.
Execution time mean : 389.595233 µs
Execution time std-deviation : 2.873750 µs
Execution time lower quantile : 383.609006 µs ( 2.5%)
Execution time upper quantile : 393.246808 µs (97.5%)
Overhead used : 1.666329 ns
Found 1 outliers in 60 samples (1.6667 %)
low-severe 1 (1.6667 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers
nilIf you were using this in a game, you might build up your quadtree on every game frame, inserting all your entities bounds, and then decide if you should update your entities.
I welcome contributions.