Quadtree in Common Lisp

A quadtree data structure implementation for data that has position and size to it.

Note: Currently only supports integer values for coordinates.

Usage

A common use would anything that operates in cycles with objects possibly colliding in 2D space. At the start of the cycle you'd clear the quadtree, then add every object and their position into it, and check which objects may be intersecting with a given space, like the area taken by another object.

Note that getting the item by giving an area does not ensure that the got item actually does intersect with that area, it simply means that the given area and the item share a node in the quadtree. Any further testing will have to be done by the caller.

Special parameters.

• *initial-item-array-size* rules how many slots each node has for items at creation.
  • The default value is 16.
  • The usual number of items in an array is zero, one, or two at a time.
  • This is to prevent unnecessary creation of new larger arrays if items start stacking.
• *left-is-negative* rules if left is used as the negative x-coordinate direction.
  • The default is T.
  • This is only used with LEFT and RIGHT getter methods for the quadtree.
• *up-is-negative* rules if up is used as the negative y-coordinate direction.
  • The default is T.
  • This is only used with TOP and BOTTOM getter methods for the quadtree.

Creation

The quadtree is created as a standard CLOS object.

Parameters

• :WIDTH: the width of the area of the quadtree.
• :HEIGHT: the height of the area of the quadtree.
• Optional arguments:
  • :X: the x-coordinate of the quadtree.
    • Defaults to 0.
  • :Y: the y-coordinate of the quadtree.
    • Defaults to 0.
  • :MIN-SIZE: the minimum width or height that a node in the tree may have.
    • Defaults to 1.
  • :KEY: a function which returns a unique identifier for any inserted item.
    • Defaults to #'IDENTITY.
  • :TEST: a function that tests the equality of the identifiers of inserted items.
    • Allowed values are 'EQ, 'EQL, 'EQUAL, and 'EQUALP.
    • Defaults to 'EQL
    • This is used internally for hash-tables.
    • Defining your own hash-function is not currently allowed.

(make-instance 'quadtree :width 640 :height 480)

Getters

(x tree) ;; The lowest x-coordinate of the tree.
(y tree) ;; The lowest y-coordinate of the tree.
(width tree) ;; The width of the tree.
(height tree) ;; The height of the tree.
(left tree) ;; The x-coordinate of the tree's left edge. (See *left-is-negative*.)
(right tree) ;; The x-coordinate of the tree's right edge. (See *left-is-negative*.)
(top tree) ;; The y-coordinate of the tree's top edge. (See *up-is-negative*)
(bottom tree) ;; The y-coordinate of the tree's bottom edge. (See *up-is-negative*)
(mid-x tree) ;; The x-coordinate of the tree's middle point.
(mid-y tree) ;; The y-coordinate of the tree's middle point.
(item-count tree) ;; The current number of items in the tree.

DO-QUADTREE

A macro to iterate through every item in the tree.

Returns a passed return-value or NIL.

Parameters

• ITEM: the variable that an item is bound to.
• TREE: the quadtree to iterate.
• Optional arguments:
  • RETURN-VALUE: a form that is evaluated and returned at the end of the iteration.
    • Defaults to NIL.

(do-quadtree (item tree)
 (do-stuff item))

FIND-ITEMS

Iterates through the tree and returns the items that may be in the given area.

Returns the passed output vector.

Parameters

• OUTPUT: a vector that found items are pushed into.
• TREE: the quadtree to iterate.
• X: the x-coordinate of the area to find items for.
• Y: the y-coordinate of the area to find items for.
• WIDTH: the width of the area to find items for.
• HEIGHT: the height of the area to find items for.

(find-items output tree x y width height)

MAPQUADTREE

Iterates through the tree and passes the items that may be in the given area to a callback function.

Returns the number of items that were iterated.

Parameters

• CALLBACK: a callback function that a found item is passed to.
• TREE: the quadtree to iterate.
• X: the x-coordinate of the area to find items for.
• Y: the y-coordinate of the area to find items for.
• WIDTH: the width of the area to find items for.
• HEIGHT: the height of the area to find items for.

(mapquadtree callback tree x y width height)

INSERT-ITEM

Inserts an item into the tree for the given position.

Returns T on success.

Parameters

• TREE: the quadtree to add into.
• ITEM: the item to add into the tree.
• X: the x-coordinate of the item.
• Y: the y-coordinate of the item.
• WIDTH: the width of the item.
• HEIGHT: the height of the item.
• Optional key arguments:
  • :IF-EXISTS: how to handle an item that already exists in the tree.
    • :ERROR throws an error.
    • :IGNORE does nothing and returns NIL.
    • :REPLACE removes the old item first.
    • Defaults to :ERROR.
  • :IF-OUT-OF-BOUNDS: how to handle an item that would be out of the bounds of the tree.
    • :ERROR throws an error.
    • :EXPAND makes the tree's area big enough to fit the new item in it.
    • :IGNORE does nothing and returns NIL.
    • Defaults to :ERROR.

(insert-item tree item x y width height)

REMOVE-ITEM

Removes the given item from the tree.

Returns T on success and NIL if the item was not in the tree.

Parameters

• TREE: the quadtree to remove from.
• ITEM: the item to remove from the tree.

(remove-item tree item)

CLEAR

Removes all the items in the tree.

Returns the passed output vector or NIL.

Parameters

• TREE: the quadtree to clear
• Optional key arguments:
  • :CALLBACK: an optional callback function that all of the removed items are passed to.
  • :OUTPUT: an optional vector that all of the removed items are added into.
    • This vector is returned by the method in the end.

(clear tree)