Skip to content

fastquadtree.pygame

fastquadtree.pygame is an optional pygame integration for games and simulations with many sprite rects. It provides:

  • Group, a mostly drop-in replacement for pygame.sprite.Group
  • spritecollide(...), spritecollideany(...), and groupcollide(...) helpers shaped like pygame's collision APIs
  • Group.query_rect(...) for viewport culling or broadphase rectangle queries without creating a temporary sprite

The group keeps a RectQuadTreeObjects index of each sprite's rect. Collision helpers use that index as a broadphase, so queries can skip most sprites before running the final pygame rectangle collision check.

Optional dependency

Core fastquadtree APIs do not require pygame. This page documents the optional fastquadtree.pygame integration, which requires pygame or a compatible package such as pygame-ce when imported at runtime.

pip install fastquadtree pygame-ce

API Reference

pygame sprite-group integration backed by a rectangle quadtree.

This module provides fastquadtree.pygame.Group, a replacement for pygame.sprite.Group that keeps a RectQuadTreeObjects index of each sprite's rect. The collision helpers mirror pygame's sprite collision APIs and use the index as a broadphase when it is safe to do so.

When the accelerated broadphase is used, collision result order follows the quadtree query traversal and is not guaranteed to match pygame group iteration order.

Core fastquadtree APIs do not require pygame. Importing this integration module does require pygame or a compatible package such as pygame-ce.

Example 
import fastquadtree.pygame as fpygame

enemies = fpygame.Group(bounds=(0, 0, 2000, 2000))
enemies.add(enemy_sprites)

hits = fpygame.spritecollide(player, enemies, dokill=False)
first_hit = fpygame.spritecollideany(player, enemies)

Group(*sprites, bounds=None, capacity=16, max_depth=None, dtype='f32', rebuild_on_update=False)

Bases: Group

pygame sprite group with a RectQuadTreeObjects broadphase index.

Group behaves like pygame.sprite.Group for normal operations such as add, remove, empty, iteration, membership checks, update, and draw. In parallel, it indexes sprites with usable rect bounds so the module-level collision helpers can avoid scanning every sprite.

For stable runtime behavior, pass explicit world bounds. If bounds is omitted, the group infers bounds from initial sprites and expands/rebuilds when later sprites fall outside the current index.

Parameters:

Name Type Description Default
*sprites Any

Initial sprites, pygame groups, or sprite iterables to add.

 ()
bounds Bounds | None

Optional world bounds as (min_x, min_y, max_x, max_y).

 None
capacity int

Maximum indexed rectangles per quadtree node before splitting.

 16
max_depth int | None

Optional maximum quadtree depth.

 None
dtype QuadTreeDType

Coordinate data type ("f32", "f64", "i32", "i64"). Default: "f32".

 'f32'
rebuild_on_update bool

When true, Group.update(...) rebuilds the whole index after updating sprites instead of incrementally syncing each sprite. This is useful when most indexed sprites move every frame.

 False
Example 
import fastquadtree.pygame as fpygame
group = fpygame.Group(bounds=(0, 0, 1000, 1000))
group.add(enemies)
hits = fpygame.spritecollide(player, group, dokill=False)

bounds property

Current quadtree bounds, or None before an index is built.

indexed_count property

Number of sprites currently indexed by usable rect bounds.

copy()

Return a new indexed group with the same sprites and index settings.

add(*sprites)

Add sprites and synchronize the quadtree index once for the batch.

add_internal(sprite, layer=None)

Add one sprite through pygame's internal group hook and sync the index.

remove_internal(sprite)

Remove one sprite through pygame's internal group hook and unindex it.

empty()

Remove all sprites and clear the quadtree index.

update(*args, **kwargs)

Run sprite updates, then synchronize or rebuild the quadtree index.

set_bounds(bounds, rebuild=True)

Replace the group's world bounds.

Parameters:

Name Type Description Default
bounds Bounds | Rect

New world bounds as (min_x, min_y, max_x, max_y) or a pygame.Rect.

 required
rebuild bool

When true, rebuild the index immediately from current group membership.

 True

rebuild()

Rebuild the quadtree from current group membership and sprite rects.

sync(sprite=None)

Synchronize the quadtree with sprite rect changes.

Pass one sprite to sync only that sprite, or omit sprite to sync the full group. Group.update(...) automatically calls sync() after pygame updates the sprites.

Sprites without a usable rect remain in the pygame group but are not indexed. Collision helpers fall back to pygame-compatible behavior when needed to preserve pygame semantics.

Parameters:

Name Type Description Default
sprite Sprite | None

Optional sprite to sync. If omitted, all group sprites are synced.

 None

query_rect(rect, *, sync=True)

Return indexed sprites whose rects intersect rect.

Parameters:

Name Type Description Default
rect Rect | Bounds

Query rectangle. Accepts a pygame.Rect or a bounds tuple (min_x, min_y, max_x, max_y).

 required
sync bool

When true, synchronize the group before querying.

 True

Returns:

Type Description
list[Any]

list[Any]: Sprites whose indexed rects intersect rect. Returns an empty list if the query rectangle cannot be interpreted or does not overlap the current world bounds. Queries that partially extend outside the world bounds are clamped before searching.

spritecollide(sprite, group, dokill, collided=None, *, sync=True)

Find sprites in a group that collide with another sprite.

This mirrors pygame.sprite.spritecollide. When group is a fastquadtree.pygame.Group, collided is None, and sprite.rect is a usable pygame.Rect, the helper queries the quadtree for rect-overlap candidates before applying the final pygame rect collision check.

Plain pygame.sprite.Group instances, custom collided callbacks, and sprites without usable pygame.Rect attributes fall back to pygame's native implementation.

Parameters:

Name Type Description Default
sprite Sprite

Sprite to test against group.

 required
group Any

Target sprite group.

 required
dokill bool

If true, kill each collided target sprite.

 required
collided _Collided | None

Optional custom collision callback.

 None
sync bool

When true, synchronize indexed groups before querying. Set to false only if you have already called Group.sync(...) after the latest sprite rect changes.

 True

Returns:

Type Description
list[Any]

list[Any]: Collided sprites. When the quadtree broadphase is used, result order is not deterministic and may differ from pygame group iteration order.

spritecollideany(sprite, group, collided=None, *, sync=True)

Return one sprite in a group that collides with another sprite.

This mirrors pygame.sprite.spritecollideany. When group is a fastquadtree.pygame.Group, collided is None, and sprite.rect is a usable pygame.Rect, indexed groups use the quadtree to narrow candidates before checking collisions. Plain pygame groups, custom collided callbacks, and sprites without usable pygame.Rect attributes fall back to pygame's native behavior.

Parameters:

Name Type Description Default
sprite Sprite

Sprite to test against group.

 required
group Any

Target sprite group.

 required
collided _Collided | None

Optional custom collision callback.

 None
sync bool

When true, synchronize indexed groups before querying. Set to false only if you have already called Group.sync(...) after the latest sprite rect changes.

 True

Returns:

Type Description
Any | None

Any | None: The first collided sprite, or None. When the quadtree broadphase is used, "first" means first in quadtree query order, not pygame group iteration order.

groupcollide(groupa, groupb, dokilla, dokillb, collided=None, *, sync=True)

Detect collisions between two sprite groups.

This mirrors pygame.sprite.groupcollide. The indexed broadphase is used when groupb is a fastquadtree.pygame.Group, collided is None, and each queried sprite has a usable rect attribute.

Plain pygame groups, custom collided callbacks, sprites without usable rect attributes, and target groups containing unindexed sprites fall back to pygame's native implementation.

Parameters:

Name Type Description Default
groupa Any

Source sprite group.

 required
groupb Any

Target sprite group.

 required
dokilla bool

If true, kill collided sprites from groupa.

 required
dokillb bool

If true, kill collided sprites from groupb.

 required
collided _Collided | None

Optional custom collision callback.

 None
sync bool

When true, synchronize indexed groups before querying. Set to false only if you have already called Group.sync(...) after the latest sprite rect changes.

 True

Returns:

Type Description
dict[Any, list[Any]]

dict[Any, list[Any]]: Mapping from each collided sprite in groupa to its collided sprites from groupb. When the quadtree broadphase is used, each list follows quadtree query order, not pygame group iteration order.
Example 
hits = fpygame.groupcollide(players, enemies, False, False)