Determining connectedness of rectangles

Question

I am working on some functions to use in my enemy state machines.

I want to write a function which determines whether the platform the enemy is standing on is connected to the platform the player is standing on.

Platforms have associated rectangles, and by connected, I mean there is a chain of rectangles from the first rectangle to the second rectangle.

Here's an illustration:

Here are my assumptions:

1. The rectangles contain their perimeters.
2. Two rectangles touching only on their perimeter are connected.
3. Two rectangles overlapping are connected.
4. The rectangles are guaranteed to be axis-aligned.
5. The rectangles will be at integer coordinates (the grid is 1x1).
6. Every rectangle has attributes like topleft, bottomright, etc.
7. Directly connected rectangles won't necessarily have any corners in common.

My question: What is an efficient way to determine the connectedness of rectangles in 2D space?

---

NOTE: I asked a more specific version of this question in a Godot forum, but given that this is a general game dev question, I figured I'd ask this variation here.

Answer 1

Construct a graph of which rectangles are connected using collision detection and do a flood-fill.

Answer 2

We can represent connections between platforms using a graph. The nodes of our graph will represent platforms and the edges of our graph will represent direct connections between platforms.

We can represent this graph using an adjacency matrix, that is, a matrix whose indices represent our nodes and which uses 0 or 1 to represent whether there's a direct connection between them.

Here's an illustration:

^{(Note that platforms are directly connected to themselves.)}

In code, we can use a list of lists to represent this final matrix.

So, to build a model of the direct connections between platforms, we can construct a list of lists in the following way (using pseudo-code):

var connection_matrix = []
for platform_1 in platforms:
    var submatrix = []
    for platform_2 in platforms:
        if platform_1.is_directly_connected_to(platform_2):
            submatrix[platform_2] = 1                   # 1 represents an edge on the graph, that is, a connection between platforms
        else:
            submatrix[platform_2] = 0                   # 0 represents absence of an edge, that is, no connection between platforms
        connection_matrix[platform_1] = submatrix

The only tricky thing here is constructing the is_directly_connected_to() function. You can either use the collision resources built into your engine to determine if two platforms are touching, or, use any number of algorithms for determining it two rectangles intersect.

Once we have this graph of the connections between our platforms, we can use one of many algorithms to determine if a path exist between two nodes in the graph.

---

Alternatively, you can represent the graph using a dictionary-type data structure whose keys are platforms and whose values are lists of platforms, those directly connected to the keys.

Here's an illustration:

Constructing this dictionary representation is easy:

var connection_dictionary = []
for platform_1 in platforms:
    var direct_connection_list = []
    for platform_2 in platforms:
        if platform_1.is_directly_connected_to(platform_2):
            direct_connection_list.append(platform_2)
    connection_dictionary[platform_1] = direct_connection_list

Once we have this graph of the direct connections between our platforms, we can use the following depth-first search algorithm to determine if there's a path between any two nodes in the graph.

def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

(This algorithm is from the Python docs, but it can be adapted to other languages.)