3

我目前正在开发基于 2D 网格的沙盒类型游戏。从技术上讲，它作为地图的 3D 是一个 3 维数组，其中网格图块可以相互放置。然而，它以 2D 形式呈现。游戏中的所有脚本都需要非常高效，因为我希望为 android 发布它。

游戏将有一个主要的布线机制，允许玩家使用电线将机器连接到电源。我需要一种有效的方法来计算每个电路通过电线连接的所有实体。

我能想到的唯一故障安全方法是使用洪水填充算法从一个点展开并记录所有连接的对象，但我觉得这对于 android 应用程序来说效率太低了。

以下是有关游戏结构和线路的一些信息。

  • 游戏是用java编写的。
  • 所有对象当前都是静态的。
  • 每个对象都保存在一个反映对象位置的数组中。只需引用数组中的 x/y 值即可访问相邻对象及其变量。这意味着可以根据需要更新相邻块。
  • 玩家可以随意放置和移除电线，并且可以遵循任何模式。
  • 电线可以在所有 x/y/z 轴上连接到其他电线和机械。
  • 某些物体会输出能量，而其他物体会使用能量。

我目前正在考虑让wireGroup对象包含一组电线的所有连接对象，包括电线本身。每个连线对象都将包含连线组 ID，从而可以轻松地将新连线（和机器）添加到连线组中。

我真正需要的是一种在移除一根电线时检测连接对象的方法。在放置时检测连接的对象很简单：只需将新线旁边的任何机械添加到相邻线的线组中的列表中。

拆线时出现问题。由于它们可能是将两个对象连接在一起的 7 或 8 条独特的导线路径，因此很难找到移除一根导线的效果。

例如：

EG1

在这里您可以看到连接的对象不会发生任何更改。

EG2

在这里，wireGroup 将被分成两个wireGroup，一个包含蓝色和底部白色，一个包含两个白色。

即使有人可以提出仅二维的算法，那仍然很棒。

对不起，如果我错过了任何重要的事情，请告诉我，以便我可以弥补。

4

2 回答 2

3

将所有“可连接”点（无论是空的、电源还是机器）都视为（断开连接的）图中的节点。一根线可以连接两个节点。假设每个节点跟踪连接到它的电线，并将每条电线视为两种类型之一：“供电”和“未供电”，其中“供电”电线是那些向该节点传输电力的电线。每个节点在一对集合中跟踪这些。如果一个节点在“供电”集中有任何电线，或者它本身就是一个电源，则该节点是“供电”的。

所以有趣的问题是，如何处理添加或移除电线：

当电线放置在两个节点之间时，对于两个节点中的每一个，根据另一个节点的“电源”状态，将其置于通电或未通电组中。如果结果是该节点从未通电变为通电，则通过将电线从“未通电”移动到“通电”来适当地更改节点和电线的状态。

如果移除了一根电线，请将其从它所在的已连接电线集中移除。如果任何一个端点节点现在有一个空的“通电”连接集，则从该节点遍历图表，关闭所有人。

这应该非常有效地处理多个供电输入，只有在状态发生变化时才需要访问多个节点。如果子图中任何节点的状态发生变化，那么子图中所有节点的状态都会发生变化。

于 2013-03-29T04:05:05.993 回答
0

想象一下，每个节点要么提供电力，要么接受电力。每根电线都带有一个或多个电力传输方向（从电源到元件）。两个连接的电源将具有由两个内部连接表示的一根电线。

所以你有一个有向功率图。移除电线后，所有相关的内部连接都将被移除。检查所有受电线移除影响的节点，以查看它们是否有任何传入连接。如果没有，并且该节点先前已通电，则您必须从该点开始遍历图形并为每个节点断电。

添加电线也很简单，您检查两个节点的电源状态。每个通电的节点都会在另一个节点的方向上建立一个内部连接。然后该图必须从在每个节点建立向外连接的其他节点走出来。如果两者都没有通电，则建立一个无方向的连接，该连接可能会在通电时改变。这允许非常有效地使用多个电源。

于 2013-03-29T03:13:49.983 回答