My engine consists of Rooms. Rooms are connected via Portals. Items have a roomNumber field to indicate which room they belong to. And rooms have a linked list of items they have.

How would I achieve inter-room collision detection between items without iterating over each item?

If I have an item that is so big it crosses portals from room A, to room B to room C should be potentially colliding with items from room A,B and C.

Since it's portal based, it is possible that rooms overlap but items on the same 3D coordinate should not collide, so a conventional 3D structure won't fit on the first glance

  • \$\begingroup\$ What objects do you want objects in room A to collide with? Only those reachable via a portal out of room A (or a chain of portals, if the object is long enough to poke through several portals while still counting as "in room A"), or anything they happen to overlap in cartesian coordinates, regardless of portal connections? \$\endgroup\$
    – DMGregory
    Commented Mar 14, 2022 at 11:56
  • \$\begingroup\$ @DMGregory only objects if they "poke through" portals. Edited my Question \$\endgroup\$
    – Raildex
    Commented Mar 14, 2022 at 12:05

1 Answer 1


The naive approach would be to do collision detection by not just querying the room but also the adjacent rooms, but this does not cover the case that an item might be so large that it passes through multiple rooms.

So we need a different solution.

One would be to dissolve the ownership of items by rooms and have an object which intersects multiple rooms owned by all those rooms. But you might have other reasons for maintaining a 1:n relationship between rooms and items. In that case you might need a separate linked list of items per room which are in the room but not owned by the room.

Keep in mind that this will create some redundancies in case of collisions which happen on edges. When both A and B are on the edge between the same two rooms, then they will be found in both rooms. So when you check for collisions with A, you will find B twice. So you might want to use a three-step process for collision detection:

  1. Create a list of potentially colliding items by iterating the "owned" and "inside" lists of all rooms the current item intersects.
  2. Remove all duplicates from that list.
  3. Check for collision.

You could combine 1 and 2 by storing the potentially colliding items in a binary tree instead of a list. That allows you to detect duplicates the moment you try to insert them into the tree and discard them.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .