3
\$\begingroup\$

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:

enter image description here

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Do you have any constraints on the rectangles? eg. Do they align to a grid with integer coordinates at all corners? Are they guaranteed to be axis-aligned? \$\endgroup\$ – DMGregory Apr 27 '18 at 23:05
  • \$\begingroup\$ @DMGregory, I added some more info. \$\endgroup\$ – GoldenGremlin Apr 27 '18 at 23:18
1
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ In order to construct this graph, we need a method to determine whether a given pair of rectangles are directly connected. (We'll use that to populate the graph's edges) I think it's this method that OP is looking for. \$\endgroup\$ – DMGregory Apr 27 '18 at 21:13
  • \$\begingroup\$ @DMGregory That's just collision detection \$\endgroup\$ – BlueRaja - Danny Pflughoeft Apr 27 '18 at 22:26
  • 1
    \$\begingroup\$ That sounds like a detail worth adding to your answer. \$\endgroup\$ – DMGregory Apr 27 '18 at 22:27
1
\$\begingroup\$

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:

enter image description here

(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:

enter image description here

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ If you only need to determine whether two platforms are connected by some path, and don't need the path itself, you can use a union-find / disjoint set data structure to cache this connection information for fast lookups. \$\endgroup\$ – DMGregory Apr 28 '18 at 14:30
  • \$\begingroup\$ Thanks for the recommendation, @DMGregory. I will look into it and update my answer in the future. I know what I have so far isn't optimal. Still learning about this stuff. \$\endgroup\$ – GoldenGremlin Apr 28 '18 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.