0
\$\begingroup\$

I've looked around for an algorithm to solve this problem, but I can't seem to find anything.

In a game I am working on, data is held in a grid. Certain squares within that grid can be set as walls, so that the user can create buildings. What I am wondering is how could I write an algorithm to determine which parts of the grid were indoors, that is to say, within a building, and which parts are outdoors. Thank you in advance for any advice.

\$\endgroup\$
  • \$\begingroup\$ This is 2D we're talking about, right? (Assuming yes because "grid" and "square"—just checking.) \$\endgroup\$ – Anko Mar 5 '15 at 23:47
1
\$\begingroup\$

Essentially you are looking for some sort of graph traversal. In your case, a flood fill may work.

In choosing a starting point, you could either use a point you know is outdoors (if the entire outdoor section is connected, or keep track of all the walls and test their neighbors.

If their neighbor is "not visited," do a flood fill on it and mark all the flooded points with a visited flag. Going through all the neighbors will give me multiple fills, all of which are indoor fills except 1 (or more if you have multiple outdoor sections).

\$\endgroup\$
1
\$\begingroup\$

Draw a straight line from the point of interest to a point of known location (indoor or outdoor) - usually traversing one of the four axes is sufficient. Then simply count the number of wall traversals and modulo it by 2. If the number of wall traversals is even then the point of interest is in the same location; if odd it is in the opposite location.

Note that this will count an enclosed Quadrangle as being outdoors, but usually that is the desired result.

\$\endgroup\$

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