The key to fast collision detection is doing as small a number of collision tests as possible. In Touhou DS, objects are assigned a collision group (see SpriteType enum). Each group can only collide with objects in specific other groups. This allows us to ignore a very large number of potential collisions. If we store objects by group, we don't even have to iterate over the full list of objects. Another obvious performance enhancement is realizing that colliding(A, B) == colliding(B, A) which saves us half the work.

Grouping objects by type alone isn't enough as most of the objects will belong to the SPRITE_enemyShot group. But it's possible to further trim down the set of collision candidates by using some kind of spacial subdivision (group by position).

Touhou DS uses a uniform grid of (16px x 16px) cells. The full grid is slightly larger than the visible area of the screen (4 cells padding on each side). If we put the objects in cells based on their midpoints, and disregard objects with hitradius > 8px, then we only need to check cells between (x-1, y-1) and (x+1, y+1). Objects with a larger hitradius are rare and stored in a simple list.