安卓游戏开发（编程/算法）问题

Question

我有一堆物品（气球），它们向上移动并撞到屋顶（即object.yPos <= 0），停止运动。跟随它们的气球会撞到现有气球并停止运动。现在，我射击气球并删除被击中的气球...如果它们已经在底部，则很容易。但是，如果支撑它们的锚点被打中并且被删除，我还必须删除那些仍然悬挂的气球，也就是说，它们不再连接到屋顶或任何其他气球。与此相关，我的Balloon对象有以下支持方法：

balloon.getAdjacentList() -> 返回附加到气球的所有气球的ArrayList

balloon.getX() -> 返回气球的X位置

balloon.getY() -> 返回气球的Y位置

我能想到的检测“悬挂在空中”的气球的一种方法是使用DFS或BFS进行“图遍历”，其中原点将是被击中（并删除）的所有相邻球，目标将是...如果任何相邻的球（或“相邻的相邻”球或“相邻的相邻的相邻”等）具有getY()<=0，即找到通向屋顶的路径。

这个检查似乎非常昂贵，特别是当我必须运行数十次搜索来删除一两个悬挂的球时。还要记住，在理论上，一个气球可能连接许多其他气球，仍然具有其锚点（支撑它们全部到达屋顶）被打中并且被删除，因此它们全部都必须离开......所以...如果(getAdjacent().size()==0)将不起作用。

1- 有更好的想法吗？这似乎很容易想象，并在许多游戏中实现了吗？ 2- 是否有任何支持方法可以帮助我检测气球？

提前感谢您的帮助。

- nah147

Answer 1

这里有一个简单的算法，可能对您的目的表现良好：从锚点开始，标记每个从锚点到达的节点为可达。完成后，弹出所有未被标记为可达的气球。这样做的成本将与气球和连接数成线性关系，我认为这对于这个问题来说是接近最优的（因为一枪可能会爆掉图中的每个气球，所以您至少需要做O（气球）的工作）。

- jacobm

---

谢谢jacobm...看起来这是正确的方法。有趣的是，解决方案是如此简单，而我却在从“要删除的节点”而不是从锚点思考问题上卡了几天。 - nah147

Answer 2

你为什么不直接告诉我们你在制作一个Frozen Bubbles克隆版？这样问题就会简单得多 :)

如果你想避免搜索，可以使用某种引用计数方案：

对于每个气球，维护子气球列表（附加）和一个整数计数父气球数量（锚定）。当一个气球破裂时，遍历其所有子气球并减少它们的锚定计数。如果子气球在此之后没有剩余的父气球，则将其弹出（递归执行或将其添加到某个队列中...）

只要不存在循环依赖，这应该是有效的。（我认为这是情况。但是，如果存在循环依赖，则图搜索是唯一的解决方案）

---

顺便说一下 - 进行全面搜索以查找连接的气球仅为O（气球数量）。我严重怀疑你的游戏有那么多气球，这将成为一个真正的问题。毕竟，首先渲染气球应该具有相同的复杂性...

- hugomg

---

我相信循环依赖是可能的。考虑两个互相接触的气球，每个气球都接触着一个（不同的）独立锚定的气球。 - jacobm

Answer 3

当气球找到锚点时，让它告诉其锚点它正在锚定。 在锚点上保留已锚定的气球列表 在找到锚点的气球上保留锚点列表 当锚点消失时，告诉已锚定的气球它已经离开。 然后，您可以使用锚点列表来确定是否需要向上移动。

假设您可以堆叠多个气球，您还应该遍历下降并仅将最后一个气球向上移动相应的距离，而不是逐个移动每个气球。

- Sumit