3
\$\begingroup\$

I am working on a 2D top-down game inspired by Prison Architect. What I just can't wrap my head around is recognizing rooms built by the player.

The game is built on a tilemap, meaning the map is always a rectangle, while the rooms can be of any shape. I'd like to be able to detect whenever walls & doors create a new wall, like in the example below.

Example room partition

Since I have no formal education in CS (yet), I can't think of any algorithm or class of algorithms that might be of use here and also can't figure out one by myself. So if you have any ideas, suggestions or resources, I'd be very thankful!

In case this is relevant, I am using a custom implementation of a tilemap using Monogame, a reimplementation of XNA and Nez.

\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

Here's an example of depth-first search implemented in python, finding all squares of the same type and connected to a given input square:

maze = """\
*********
*    * **
*    D  *
**D*** **
*    * **
*   **  *
**   D  *
*********""".split('\n')

dr = [-1, +1, 0, 0]
dc = [0, 0, -1, +1]

def all_tiles_of_same_type(maze, r, c):
    tile_type = maze[r][c]
    tiles = set()
    todo = [(r, c)]
    while len(todo) > 0:
        cell = todo.pop()
        if cell in tiles:
            continue
        tiles.add(cell)
        r, c = cell
        for i in (0, 1, 2, 3):
            r2 = r + dr[i]
            c2 = c + dc[i]
            add_nbr = (0 <= r2 and r2 < len(maze) and
                       0 <= c2 and c2 < len(maze[r2]) and
                       maze[r2][c2] == tile_type)
            if add_nbr:
                todo.append((r2, c2))
    return tiles

print sorted(all_tiles_of_same_type(maze, 1, 1))
print sorted(all_tiles_of_same_type(maze, 3, 3))

Here are the main ideas:

  • tiles keeps track of the result, adding squares as they are discovered
  • todo holds a list of squares that must be visited in the future
  • When we visit a square, we add all its neighbors to the todo list—or rather, all the relevant (same-type) neighbors. That happens in for i in (0, 1, 2, 3): ....
  • If we have already visited a square we should not visit it again, otherwise we will go into an infinite loop. That's what if cell in tiles: continue does.
  • What makes this a depth-first traversal is our use of a stack: cell = todo.pop() removes from the end of todo, and todo.append(...) adds to the end as well. If instead we had used a queue, we would've done a breadth-first traversal.

Note that we don't explicitly construct a tree—but we could: whenever we add a neighbor of (r, c) to the todo list (and that neighbor hasn't already been visited), add an edge from (r, c) to the neighbor. Use the (r, c) given as inputs as the root of the tree. That would be the DFS traversal tree.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Thank you very much, that did work out! \$\endgroup\$ Jun 9, 2020 at 10:09
  • \$\begingroup\$ You're most welcome :) \$\endgroup\$ Jun 9, 2020 at 16:25
2
\$\begingroup\$

As far as I understand your question, you want to compute the regions of your map that would be flood-filled in a paint program. In that case, I recommend one of the following approaches:

In case of the disjoint set data structure, you would union together each pair of neighboring grid cells. Once you have done that for all pairs, two squares s1 and s2 are in the same room if Find(s1) == Find(s2).

\$\endgroup\$
2
  • \$\begingroup\$ Yes, that is a good way to describe it. But as far as I can tell, the algorithms you've pointed out are all related to trees, while my tilemap is stored in a simple array. How would I go about converting it to a tree, and wouldn't that be very CPU-intensive? \$\endgroup\$ Jun 8, 2020 at 8:03
  • \$\begingroup\$ As I said in my other answer, we don't explicitly construct a tree. The X-first search algorithms run in time proportional to the number of vertices and edges (squares and neighbor-relationships); the disjoint set forest use only marginally more time. With respect to caches, a good rule of thumb is that sequential memory reads are fast compared to reads all over the place; so a simple forward for-loop through an array is fast, where visiting a tree is slow. However, always always always measure when doing performance work, 'cause it's complicated and we don't have good (enough) models. \$\endgroup\$ Jun 11, 2020 at 6:44

You must log in to answer this question.

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