diff options
Diffstat (limited to 'tests')
| -rw-r--r-- | tests/data/quadtree.scm | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/tests/data/quadtree.scm b/tests/data/quadtree.scm new file mode 100644 index 0000000..1dd37cc --- /dev/null +++ b/tests/data/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 data 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)))) |