Building placement in a 2D discrete game

I am working in a grid-universe - objects only exist at integer locations in a 2 dimensional matrix.

Some terms:

Square - a discrete location. Each square has an int x and int y coordinate, and no two squares have the same x and y pair.

Adjacent: A square X is adjacent to another square Y if the magnitude of the difference in either their x or y coordinate is no greater than 1. Put more simply, all squares immediately in the N, NE, E, SE, S, SW, W, and NW directions are adjacent.

Legend:
'?' - Unknown Traversibility
'X' - Non Traversable Square
'O' - Building (Non Traversable)
' ' - Traversable Square

The problem:

Given the following generic situation:

? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? O O ? ? ?
? ? ? O O ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?

where the builder is adjacent to one of the four buildings, I want to build two buildings such that they both share a common adjacent square that is also adjacent to at least one of the four existing buildings, and this common adjacent square is not blocked in.

Basic Valid solutions:

X X X X X X X X          X X X     X X X          X X X X X X X X
开发者_高级运维X X X X X X X X          X X X     X X X          X X X X X X X X
X X X X X X X X          X X X     X X X          X X X X X X X X
X X X O O X X X          X X X O O X X X          X X X O O X X X
X X X O O X X X          X X X O O X X X          X X O O O X X X
                         X X X O   X X X                O X X X X
      O O                X X X O   X X X                X X X X X
                         X X X     X X X                X X X X X 

Currently, I iterate through all traversable square adjacent to the four buildings, and look for squares that have 3 adjacent traversable squares, but this sometimes produces situations such as:

X X X X X X X X          X X X X X X X X          X X X X X X X X
X X X X X X X X          X X X X X X X X          X X X X X   X X
X X X X X X X X          X X   O     X X          X     X X   O X
X X X O O X X X          X X   O O O X X          X     O O O X X
X X X O O X X X          X X   O O   X X          X X   O O   X X
X X X     X X X          X X         X X          X X         X X
X X X O O X X X          X X X     X X X          X X X     X X X
X X X     X X X          X X X     X X X          X X X     X X X 

Any thoughts on how I can refine my algorithm?

EDIT: Added another failing case.

EDIT: I'd also like to be able to know if there isn't a possible configuration in which these conditions could be met. I'm not guaranteed a viable solution, and would like to not-try if there isn't a way to do this successfully.

---

Checking to ensure your new buildings aren't orthogonally adjacent will eliminate cases such as your problem case 1, and checking to ensure not more than one of your new buildings is adjacent to any of the originals will clear up problem case 2.

This should work if you can safely assume you are no more constricted than in problem case 2. If there is only one square of exit, then the only solutions will need to violate the "not more than one" condition proposed above.

---

Your invalid cases are due to the splitting of the free space into 2 parts right? In that case, a crude method would be to flood-fill the free space after building placement and see if the connected space has the correct size (2 squares less than prior to building placement). That seems excessive. You really want to know if the graph of the free-space squares is still connected. More specifically, you want to know if all the free-space squares around the new buildings are still connected. Do they have to be locally connected, or can the path be arbitrarily long? i.e. is this valid:

X X X X X X X X
X           X X
X   X X X   X X
X   X X X   X X
X     O     X X
X X   O O O X X
X X   O O   X X
X X         X X
X X X     X X X
X X X     X X X

If that is OK, this is a hard problem because that path could be very long.

---

The only solution I can think of is to do pathfinding from the common adjacent square out to the edge of the map. It looks to me like all the problem cases boil down to "the adjacent square is blocked in" so the way to ensure it isn't blocked in is to find a path from that square to an open edge of the map.

I don't know if that's the most efficient approach but it would be fairly simple to implement, since A* pathfinding routines are pretty widely implemented. And actually since you don't need the shortest path, just a path, you could simply do a flood-fill of free spaces starting from the adjacent square until you hit the edge of the map.