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

我认为这可能是一个解决方案。不过不确定

**Quadrant**


       |
   II  |    I
       |
-------A---------
       |
  III  |   IV
       |


       |
   II  |
       |
-------A

**Rotate right**
|
|    II
|
A---------

**Rotate right**
A---------
|
|   II
|
  1. 编写一个逻辑，以在以象限A为中心的第四象限中找到路线。
  2. 编写逻辑将您的点数组拆分A为以 (0,0) 为中心的 4 个象限。确保 2 个象限中不存在轴线。因此，一旦隔离区的一侧必须放置一系列块。
  3. 将每个象限传递logic 1给处理并查找路线长度数组。确保旋转矩阵将原点到达左上角。
  4. 根据象限，您可以计算方向。
于 2013-06-19T04:42:17.920 回答
0

这是BFS的典型应用。我不知道objective-C，但是，您提到了递归，通常是DFS。BFS 的典型实现使用队列。

您可以在每个单元格上设置一个标志，在您访问它时立即设置，如果设置了标志，则不要再次访问该单元格。这将防止任何单元格的重复。

访问标志不会阻止找到所有单元格，因为 BFS 保证找到到任何单元格的最短路径，因为它从一开始就首先访问距离 1、距离 2、距离 3 等所有单元格，因此它将总是在更长的路径之前找到到单元格的更短路径。这与 DFS（使用访问标志）相反，它首先搜索尽可能长的路径，因此它可以将单元格标记为在长度为 3 的路径上访问，即使存在长度为 2 的路径，从而跳过它可以获得的未访问单元格从那个细胞。

于 2013-06-19T07:28:37.320 回答
0

一段时间后回到这个，

我意识到一个普通的 BFS 实际上并不能工作，因为没有办法知道你从根节点走了多远。

我用堆栈实现了一个 BFS，所以它类似于 dfs

于 2013-11-22T00:36:28.277 回答