nah*_*147 5 java algorithm android
我有一堆物体(气球)向上移动,撞到屋顶(即object.yPos <= 0),然后停下来.跟随他们的气球击中现有的气球并停下来.现在,我在气球上射击并移除那些被击中的球......如果它们已经在底部那么容易.然而,我还必须移除那些在其支撑锚被击中并被移除后悬挂的气球,即它们不再连接到屋顶或任何其他球.与此相关,我在我的Balloon对象中有以下支持方法:
balloon.getAdjacentList() - >返回附加到气球的所有气球的ArrayList
balloon.getX() - >返回气球的X Pos
balloon.getY() - >返回气球的Y Pos
我能想到的一种检测"悬空"气球的方法是使用DFS或BFS的"图形遍历",其中原点将是被击中(并被移除)的一个相邻球,目的地将是...如果任何相邻的球(或"相邻的相邻"球或"相邻的相邻"球等)具有getY()<= 0,即找到通向屋顶的路径.
这项检查似乎非常昂贵,特别是在移除一个或两个吊球时,我必须进行数十次搜索.还要记住,从理论上讲,一个气球可能还有许多其他气球,并且仍然有它的锚(支撑它们全部到屋顶的那个)撞击和移除,因此所有它们都必须......所以... if(getAdjacent().size()== 0)不起作用.
1-有什么更好的想法,看起来很容易想象,并在如此多的游戏中实现？2-我可以添加哪些支持方法来帮助我检测球？
在此先感谢您的帮助
这是一个简单的算法，可能可以很好地满足您的目的：只需从锚点开始，并将从锚点到达的每个节点标记为可到达。完成后，弹出所有未标记为可达的气球。其成本将与气球加上连接的数量成线性关系，我认为这对于这个问题来说接近最佳（因为一次射击可能会弹出图中的每个气球，所以你至少需要做 O(balloons) 工作） 。