0

開始点から一定の距離にある点の配列を作成するより良い方法を探しています。途中、通れない障害物があるかもしれません。

x x x o x x x x
x x o o o x x x
x o o o o o x x
o o o A o o o x
x o B B o o x x
x x x x o x x x
x x x x x x x x

x - 空 // A - 開始 // B - 障害物 // o - 距離 >= 3

したがって、私の現在の実装では再帰を使用し、距離が 3 に達するまで基本的にすべての方向を検索します。次のようになります。

- (NSArray *) findTiles:(CGPoint)position for:(int)area;
{
    // Holding array
    NSMutableArray *array = [NSMutableArray array];

    CGPoint p = ccp(position.x - 1, position.y);
    if ( [self isValidTile:p] && area != 0 )
        if ( ![self isOccupiedTile:p] )
            [array addObjectsFromArray: [self findMoveTiles:p for:area - 1]];

    p = ccp(position.x, position.y - 1);
    if ( [self isValidTile:p] && area != 0 )
        if ( ![self isOccupiedTile:p] )
            [array addObjectsFromArray: [self findMoveTiles:p for:area - 1]];

    p = ccp(position.x + 1, position.y);
    if ( [self isValidTile:p] && area != 0 )
        if ( ![self isOccupiedTile:p] )
            [array addObjectsFromArray: [self findMoveTiles:p for:area - 1]];

    p = ccp(position.x, position.y + 1);
    if ( [self isValidTile:p] && area != 0 )
        if ( ![self isOccupiedTile:p] )
            [array addObjectsFromArray: [self findMoveTiles:p for:area - 1]];

    // Add ourself only if we are empty
    if ( [self isValidTile:position] && ![self isOccupiedTile:position])
        if ( ![array containsObject:[NSValue valueWithCGPoint:position]] )
            [array addObject:[NSValue valueWithCGPoint:position]];

    return [NSArray arrayWithArray:array];
}

誰もそれを行うためのより速い方法を持っていますか? これは問題なく動作しますが、大きな領域では信じられないほど遅くなります。また、返された配列には、containsObject: が機能していないように見えるため、多くの繰り返し座標があります。

PS - ここでグラフ アルゴリズムが適用されるかどうかはわかりません (適用されると思います)。

4

3 に答える 3

0

しばらくしてこれに戻った後、

通常の BFS は実際には機能しないことに気付きました。ルート ノードからどれだけ移動したかを知る方法がないからです。

代わりにスタックを使用して BFS を実装したので、dfs に似ています

于 2013-11-22T00:36:28.277 に答える