objective-c - 算法 - 如何使用 2D Flood Fill with terrain cost？

Question

我的游戏中有两种移动算法 - one displays possible moves using Flood Fill ，另一个使用 A* 计算如何到达任何可能的位置。

现在flood fill返回的信息格式如下

• [来源]
• [一步可及的方 block 数组]
• [2 步内可到达的方 block 数组]

我对每个方 block 的移动/地形成本可变时如何使用洪水填充很感兴趣。

这是我当前的实现，没有移动成本:

-(NSMutableArray*)getValidMovesFromPoint:(CGPoint)p lockMovesInTileset:(NSMutableArray*)tileset usingConnexity:(int)connexity
{
    int i = 0;
    NSMutableArray* validMovesFromThisPoint = [NSMutableArray array];//these tiles are valid moves from point

    NSNumber* tileIsWalkable = nil;

    //using (x,y) (0,0) as bottom left corner, Y axis pointing up, X axis pointing right
    i = [self indexFromPoint:CGPointMake(p.x-1, p.y)];//left
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES)
    {
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x+1, p.y)];//right
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES)
    {
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x, p.y-1)];//bottom
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES)
    {
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x, p.y+1)];//top
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES)
    {
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    if(connexity == 4){
        return validMovesFromThisPoint;//if we want a connexity 4, no need to go further
    }

    i = [self indexFromPoint:CGPointMake(p.x-1, p.y-1)];//bottom left
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES){
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x+1, p.y-1)];//bottom right
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES){
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x-1, p.y+1)];//top left
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES){
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    i = [self indexFromPoint:CGPointMake(p.x+1, p.y+1)];///top right
    tileIsWalkable = tileset[i];
    if(tileIsWalkable.boolValue == YES){
        [self lockTileAtIndex:i forTileset:tileset rememberValidMovesInThisArray:validMovesFromThisPoint];
    };

    return validMovesFromThisPoint;
}

Answer 1

显然不能使用泛洪填充，相反我实现了Breadth First Search, as described in this post.这允许将地形成本包含在计算中