1

私は iPhone ゲームを作成しており、(x,y) 座標などの独自のプロパティを持つ Line オブジェクトと、現在「この」行に接触している他のすべての行の詳細を示す「接続された」配列を作成しました。

私がやりたいのは、開始行 (Line1) から、他の接続された行の配列を反復処理し、そこから別の行をランダムに選択することです (たとえば、Line2)。次に、このロジックを繰り返して、Line2 に接続されたすべての回線配列を調べ、接続元の回線 (つまり、Line1 ではない) を除いて接続されている別の回線を選択します。要するに、一連の行が「回路」を完成させるかどうか、つまり、最後の行 == 最初の行であるかどうかを調べたいのです。

疑似コード:

Line1->Line1Array->Line2->Line2Array->Line3->Line3Array->Line4->Line4Array->Line1->Stop!

視覚的表現:

行

以下に示すこの特定の視覚的表現をハードコーディングすることで、なんとか機能させることができました。問題は、回路が常に 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;
}}}

私はまだ後半の部分で混乱しています。つまり、YES/NO を返すタイミングと、これがどのように結びついているかです。ライン ID を出力すると、ラインが 3 つある場合、期待どおりにラインがトロールされていることがわかります。3行のフローは次のとおりです。

Line1->Line2->Line1->Line2->line3->Line2

残念ながら、4 行がリンクされると、プログラムが非常に遅くなり (多くのスレッドが作成されていることがわかります)、代わりに次のループが発生します。

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

4

1 に答える 1

4

再帰は正しい方向への一歩です。それを正しく適用する秘訣は、一度に 1 行ずつ作業していると考えて、再帰メソッドが既に完了したふりをすることです。作業が完了する頃には、メソッドが完成しているので、コードが機能します (最初は魔法のように聞こえても問題ありません)。

まず、このメソッドをLineクラスに追加します。

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

circuit配列には、これまでに見つけた行のリストが含まれます。呼び出し元は、最初は空の を関数に渡しNSMutableArrayます。オブジェクト自体は、Line試す必要がある接続された線を提供します。接続された回線にループが発生します。各反復で、コードは

  • 接続された回線が、これまでに見つけた にないことを確認しますcircuit
  • そうでない場合は、接続された回線を の末尾に追加し、circuitそれを呼び出しますfindCircuit。ここで魔法が起こります: メソッドを書き終えていなくても、メソッドを呼び出すことができます!
  • findCircuitを返す場合YES、関数も返されYESます
  • が返された場合NO、ループは に追加した最後の行を削除し、circuit次の行に進みます
  • ループ内のすべての接続された行が をYES返さずに使い果たされると、メソッドはNO呼び出し元に戻ります。

それだけです、本当に！回路を作成する行でこのメソッドを呼び出し、空の を渡しNSMutableArray、メソッドが を返すかどうかを確認しますYES。その場合、渡した配列には回路が含まれます。

于 2013-03-26T00:34:45.950 に答える