Building placement in a 2D discrete game

Question

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.

If you can precisely describe the problem with the last example then you will probably have your answer. — Michael McGowan, Mar 22 '11 at 18:04
@Michael Yep. I can't think of how to describe the problem with the last examples, though. At least, not in a way that doesn't involve extravagant brute force. — T.K., Mar 22 '11 at 18:20

score 1 · Answer 1 · answered Mar 22 '11 at 18:29

1

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.

answered Mar 22 '11 at 18:29

user538917

41
1

@user5389167 Thanks for the input. The seem very sound at first glance, but I may have found a few holes. Problem case 3 is a situation in which you'd need to violate your first rule - the solution to that situation involves orthogonal constructions. Also, I'm editing the question to include this aspect, but I'd also like it to be able to determine if I am more constricted - I'm not guaranteed to be in a situation in which I can successfully do this, at which point, I want to not-try. – T.K. Mar 22 '11 at 18:40
Problem case 3 isn't a solution that would be generated. The chosen location doesn't have three adjacent traversable squares. That said, I see now that I can construct a situation that would be problematic, but it would require that the builder start trapped in. Can we safely assume that the builder doesn't start in an unsolvable location? – user538917 Mar 22 '11 at 19:05
@user538917 Ah, my mistake. I'll go ahead and edit that case. And yes, we can assume that the builder will not start trapped in. – T.K. Mar 22 '11 at 19:08

score 1 · Answer 2 · answered Mar 22 '11 at 18:42

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.

I'm afraid that situation is entirely possible. To make matters worse, I'm in an uninformed state - I don't know the traversability of squares outside a certain range of my builder. The reason I gave a 3-square buffer around the center 4 buildings is because I'm not guaranteed much more than that information. With that having been said, if I can simply get to the third-layer of squares away from my center buildings, I'd be content with calling that an answer. — T.K., Mar 22 '11 at 18:48

score 1 · Answer 3 · answered Mar 31 '11 at 15:38

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.

Yeah, this sounds quite similar to what I was brainstorming a little while ago about - I could take all boundary traversable squares, and make a list of all reachable locations. Then, if my list of reachable locations after-building-build is shorter, I know I messed up, and I scrap that location. This is rather computationally inefficient, but I'm sure that one could take advantage of the "needing any path, rather than the best path" aspect of the problem, and trim down the runtime quite a bit. — T.K., Mar 31 '11 at 15:59

Building placement in a 2D discrete game

3 Answers3