StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POBuilding placement in a 2D discrete game
text
Body
copied!<p>I am working in a grid-universe - objects only exist at integer locations in a 2 dimensional matrix.</p> <p><strong>Some terms:</strong></p> <p>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.</p> <p>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.</p> <pre><code>Legend: '?' - Unknown Traversibility 'X' - Non Traversable Square 'O' - Building (Non Traversable) ' ' - Traversable Square </code></pre> <p><strong>The problem:</strong></p> <p>Given the following generic situation:</p> <pre><code>? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? O O ? ? ? ? ? ? O O ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? </code></pre> <p>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.</p> <p>Basic Valid solutions:</p> <pre><code>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 </code></pre> <p>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:</p> <pre><code>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 </code></pre> <p>Any thoughts on how I can refine my algorithm?</p> <p><strong>EDIT:</strong> Added another failing case.</p> <p><strong>EDIT:</strong> 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.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload