summaryrefslogtreecommitdiff
path: root/tests/quadtree.scm
diff options
context:
space:
mode:
authorDavid Thompson <dthompson2@worcester.edu>2021-10-06 17:11:01 -0400
committerDavid Thompson <dthompson2@worcester.edu>2021-10-06 17:11:01 -0400
commit15d838868b6dd7993d3f04c0a22bd9addaf731af (patch)
treef06bcbcfaa35eea0bda1a026c5d1e51bcfdb4baa /tests/quadtree.scm
parent03cb76faf452dcf30fe86d6522c1de88ba2fa923 (diff)
Collapse test hierarchy into a single directory.
Diffstat (limited to 'tests/quadtree.scm')
-rw-r--r--tests/quadtree.scm122
1 files changed, 122 insertions, 0 deletions
diff --git a/tests/quadtree.scm b/tests/quadtree.scm
new file mode 100644
index 0000000..fa578cd
--- /dev/null
+++ b/tests/quadtree.scm
@@ -0,0 +1,122 @@
+;;; Chickadee Game Toolkit
+;;; Copyright © 2021 David Thompson <davet@gnu.org>
+;;;
+;;; Chickadee is free software: you can redistribute it and/or modify
+;;; it under the terms of the GNU General Public License as published
+;;; by the Free Software Foundation, either version 3 of the License,
+;;; or (at your option) any later version.
+;;;
+;;; Chickadee is distributed in the hope that it will be useful, but
+;;; WITHOUT ANY WARRANTY; without even the implied warranty of
+;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+;;; General Public License for more details.
+;;;
+;;; You should have received a copy of the GNU General Public License
+;;; along with this program. If not, see
+;;; <http://www.gnu.org/licenses/>.
+
+(define-module (tests quadtree)
+ #:use-module (tests utils)
+ #:use-module (srfi srfi-64)
+ #:use-module (chickadee data quadtree)
+ #:use-module (chickadee math rect))
+
+(define (quadtree)
+ (make-quadtree (make-rect 0 0 100 100) #:max-size 3 #:max-depth 2))
+
+(with-tests "quadtree"
+ (test-group "quadtree-insert!"
+ (test-group "inserting a single object"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (test-equal (quadtree-size q) 1)
+ (test-assert (quadtree-leaf? q))))
+ (test-group "inserting maximum objects for one node"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
+ (test-equal (quadtree-size q) 3)
+ (test-assert (quadtree-leaf? q))))
+ (test-group "splitting where all objects move to child nodes"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'baz)
+ (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'frob)
+ (test-equal (quadtree-size q) 0)
+ (test-assert (not (quadtree-leaf? q)))))
+ (test-group "splitting where all objects stay in parent node"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'baz)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'frob)
+ (test-equal (quadtree-size q) 4)
+ (test-assert (quadtree-leaf? q)))))
+ (test-group "quadtree-delete!"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (test-equal "deleting from a root node with 1 object"
+ (quadtree-size q) 0))
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 30.0 10.0 10.0 10.0) 'baz)
+ (quadtree-delete! q (make-rect 30.0 10.0 10.0 10.0) 'bar)
+ (test-equal "deleting from a root node with multiple objects"
+ (quadtree-size q) 2))
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
+ (quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
+ (test-assert "deleting from a lower node"
+ (quadtree-delete! q (make-rect 25.0 10.0 10.0 10.0) 'frob)))
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (quadtree-insert! q (make-rect 15.0 10.0 10.0 10.0) 'bar)
+ (quadtree-insert! q (make-rect 20.0 10.0 10.0 10.0) 'baz)
+ (quadtree-insert! q (make-rect 25.0 10.0 10.0 10.0) 'frob)
+ (quadtree-delete! q (make-rect 10.0 10.0 10.0 10.0) 'foo)
+ (test-assert "clearing out a level"
+ (quadtree-leaf? (quadtree-q3 q)))))
+ (test-group "quadtree-fold"
+ (test-equal "rect within a single leaf node at level 0"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
+ (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
+ (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
+ (quadtree-fold q (make-rect 0.0 0.0 40.0 40.0) '() cons))
+ '(three five))
+ (test-equal "rect spans multiple nodes at level 1"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'one)
+ (quadtree-insert! q (make-rect 10.0 60.0 10.0 10.0) 'two)
+ (quadtree-insert! q (make-rect 10.0 10.0 10.0 10.0) 'three)
+ (quadtree-insert! q (make-rect 60.0 10.0 10.0 10.0) 'four)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
+ (quadtree-fold q (make-rect 0.0 0.0 60.0 40.0) '() cons))
+ '(four three five))
+ (test-equal "rect within a single leaf node at level 2"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 80.0 80.0 10.0 10.0) 'one)
+ (quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
+ (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
+ (quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
+ (quadtree-insert! q (make-rect 65.0 65.0 10.0 10.0) 'five)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'six)
+ (quadtree-fold q (make-rect 76.0 76.0 20.0 20.0) '() cons))
+ '(one five six))
+ (test-equal "rect spans multiple nodes at level 2"
+ (let ((q (quadtree)))
+ (quadtree-insert! q (make-rect 70.0 70.0 10.0 10.0) 'one)
+ (quadtree-insert! q (make-rect 60.0 80.0 10.0 10.0) 'two)
+ (quadtree-insert! q (make-rect 60.0 60.0 10.0 10.0) 'three)
+ (quadtree-insert! q (make-rect 80.0 60.0 10.0 10.0) 'four)
+ (quadtree-insert! q (make-rect 45.0 45.0 10.0 10.0) 'five)
+ (quadtree-fold q (make-rect 70.0 70.0 20.0 20.0) '() cons))
+ '(four three two one five))))