2D 离散游戏中的建筑布局
我正在网格宇宙中工作 - 对象仅存在于二维矩阵中的整数位置。
一些术语：
Square - 一个离散的位置。每个方块都有一个 int x 和 int y 坐标，并且没有两个方块具有相同的 x 和 y 对。
相邻：如果一个方格 X 的 x 或 y 坐标差值不大于 1，则该方格 X 与另一个方格 Y 相邻。更简单地说，所有方格都紧邻 N、NE、E、SE、S、SW 、W 和NW 方向相邻。
Legend:
'?' - Unknown Traversibility
'X' - Non Traversable Square
'O' - Building (Non Traversable)
' ' - Traversable Square
问题：
考虑到以下一般情况：
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ?
? ? ? O O ? ? ?
? ? ? 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 X X X X X X X X X X X
X 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
目前，我迭代与四栋建筑物相邻的所有可遍历正方形，并查找具有 3 个相邻可遍历正方形的正方形，但这有时会产生诸如此类的情况：
X X X X X X X X X X X X X X X X X X X X X X X X
X X X X X X X X X 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
关于如何改进我的算法有什么想法吗？
编辑：添加了另一个失败案例。
编辑：我还想知道是否存在可以满足这些条件的可能配置。我不能保证有一个可行的解决方案，并且如果没有办法成功地做到这一点，我不想尝试。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
检查以确保您的新建筑物不正交相邻将消除诸如问题案例 1 之类的情况，并进行检查以确保不超过一栋新建筑物与任何原始建筑物相邻将消除问题案例 2。
这应该可行如果您可以放心地假设您并不比问题情况 2 中的情况更受限制。如果出口只有一格，那么唯一的解决方案将需要违反上面提出的“不超过一个”条件。
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.
您的无效案例是由于可用空间分成两部分所致，对吧？在这种情况下，一种粗略的方法是在建筑物放置后淹没自由空间，并查看连接的空间是否具有正确的尺寸（比建筑物放置之前小 2 个平方）。这似乎太过分了。您确实想知道自由空间正方形的图是否仍然连通。更具体地说，您想知道新建筑物周围的所有自由空间广场是否仍然相连。它们是否必须在本地连接，或者路径可以任意长？即，这是有效的：
如果可以的话，这是一个难题，因为该路径可能很长。
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:
If that is OK, this is a hard problem because that path could be very long.
我能想到的唯一解决方案是从公共相邻方块到地图边缘进行寻路。在我看来，所有问题案例都可以归结为“相邻方块被阻挡”，因此确保它不被阻挡的方法是找到从该方块到地图开放边缘的路径。
我不知道这是否是最有效的方法，但实施起来相当简单，因为 A* 寻路例程已得到相当广泛的实施。实际上，由于您不需要最短路径，只需要一条路径，因此您可以简单地从相邻方块开始大量填充可用空间，直到到达地图边缘。
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.