1

我正在创建一个 iPhone 游戏，并创建了 Line 对象，每个对象都有自己的属性，例如它们的 (x,y) 坐标和一个“连接”数组，该数组详细说明了当前接触“这条”线的所有其他线。

我想要做的是从一条起始线（Line1）开始，遍历它的其他连接线数组，然后从那里随机选择另一条线（比如 Line2）。然后我想重复这个逻辑并查看所有 Line2s 连接的线阵列并选择另一条连接的线，除了它刚刚来自的线（即不是 Line1）。简而言之，我想知道一组线是否完成了一个'电路'，即最后一行==第一条所以在

伪代码：

Line1->Line1Array->Line2->Line2Array->Line3->Line3Array->Line4->Line4Array->Line1->停止！

视觉表现：

线条

我已经设法通过对我在下面展示的这个特定的视觉表示进行硬编码来让它工作。问题是，一个电路可能并不总是由 4 个面组成，而且这个解决方案似乎不是特别健壮或优雅。如果我有一种方法可以遍历 X 个数组并简单地返回是否检测到电路，那就太好了。我遇到了使用递归，但对如何将它应用于这个特定问题感到困惑。

实际代码：

for(Line* line1 in allLines) {

   // contains all lines connected to this line
   NSMutableArray* connectedTo = [line1 getConnectedTo];

// lets loop through all lines connected to our line1
for(Line* line2 in connectedTo) {

      // contains all lines connected to line2
      NSMutableArray* secondConnectedTo = [line2 getConnectedTo];

// lets loop through all lines connected to line2
for(Line* line3 in secondConnectedTo) {

 // don't look back at line1 from line2
 if([line3 getLineCreationNumber] != [line1 getLineCreationNumber]) {

     // contains all lines connected to the 3rd line
     NSMutableArray* thirdConnectTo = [line3 getConnectedTo];

// lets loop through all lines connected to our 3rd line
for(Line* line4 in thirdConnectTo) {

      // contains all lines connected to the 4th line
      NSMutableArray* fourthConnectTo = [line4 getConnectedTo];

// 'line5' here is actually the same as line1 so check to confirm for circuit
for(Line* line5 in fourthConnectTo) {                   
      if([line5 getLineCreationNumber] == [line1 getLineCreationNumber]) {
       CCLOG(@"CIRCUIT FOUND");
}}}}}}}

更新代码：

嗨@dasblinkenlight 感谢您的回答，它很有用。我觉得我非常接近解决这个问题，但仍然遇到一个问题。这是到目前为止的代码（注意我最初按照指令传递了一个空数组）：

-(bool) findCircuit:(NSMutableArray*) circuit {

for(Line* l in [self getConnectedTo]) {

// ensure line isn't in circuit found so far
if(![circuit containsObject: self]) {
    // add connected line to end of circuit
    [circuit addObject: l];
    // call find circuit on the latest connected line
    if([l findCircuit: circuit])
    return YES;
} else {
    [circuit removeLastObject];
    continue;
}}}

我仍然对后面的部分感到困惑，即何时返回是/否以及这如何联系起来。我可以通过输出行 ID 看到，当有 3 行时，这些行正在按预期被拖网。这是 3 行的流程：

线路1->线路2->线路1->线路2->线路3->线路2

不幸的是，当 4 行链接时，程序变得非常慢（我可以看到创建了许多线程），我得到了以下循环：

Line1->Line2->Line1->Line4->Line3->Line4->Line1

4

1 回答 1

4

递归是朝着正确方向迈出的一步。正确应用它的诀窍是认为您一次使用一行，并假装您的递归方法已经完成。当您完成时，该方法将完成，因此您的代码可以工作（这听起来有点像魔术，一开始是可以的）。

首先，将此方法添加到您的Line类中：

-(BOOL)findCircuit:(NSMutableArray*)circuit {
    ...
}

该circuit数组将包含您到目前为止找到的行列表；调用者会将最初为空的值传递NSMutableArray给您的函数。对象本身将Line提供您需要尝试的连接线。连接线上会有一个循环。在每次迭代中，您的代码将

  • 检查连接的线路是否不在circuit您目前找到的线路上
  • 如果不是，将连接的线添加到 的末尾circuit，然后调用findCircuit它。这就是魔法发生的地方：你还没有写完你的方法，但你可以调用它！
  • 如果findCircuit返回YES，您的函数YES也会返回
  • 如果NO返回，您的循环将删除您添加到的最后一行circuit，然后继续下一行
  • 一旦循环中的所有连接线都用尽而没有返回YES，该方法将返回NO给它的调用者。

就是这样，真的！在要创建电路的行上调用此方法，将其传递给 empty NSMutableArray，然后查看该方法是否返回YES。如果是这样，您传递的数组将包含您的电路。

于 2013-03-26T00:34:45.950 回答