2次元地図のゲームタイルの移動

Question

2次元正方形グリッドシステムでは、どのような動きをするのが最適ですか？私はこれが動作する何かを持っているが、それは間違っている/醜いようです（下記参照）。

x x x x x x x 
x x x x x x x 
x x x O x x x 
x x x U x x x 
x x x x x x x 
x x x x x x x 
x x x x x x x 

例えば、Uは移動したい単位であり、Oは別の単位や山のように通らないオブジェクトです。 Uが3タイルを動かすことができるなら、私は可動エリア（M）をこのように見せたいと思う。

x x x x x x x 
x x M x M x x 
x M M O M M x 
M M M U M M M 
x x M M M M x 
x x M M M x x 
x x x M x x x 

は、ここに私のコードです：

public function possibleMoves(range:uint, cords:Array):void { 
var X:uint = cords[0]; 
var Y:uint = cords[1]; 

if (range > 0) { 
    try { 
     theGrid[X + 1][Y].moveable = true; 
     if (theGrid[X + 1][Y].getOccupied == false) { 
      possibleMoves(range - 1, [X + 1, Y], flag, mtype); 
     } 
    } catch (err:Error) { } 

    try { 
     theGrid[X - 1][Y].moveable = true; 
     if (theGrid[X - 1][Y].getOccupied == false) { 
      possibleMoves(range - 1, [X - 1, Y], flag, mtype); 
     } 
    } catch (err:Error) { } 

    try { 
     theGrid[X][Y + 1].moveable = true; 
     if (theGrid[X][Y + 1].getOccupied == false) { 
      possibleMoves(range - 1, [X, Y + 1], flag, mtype); 
     } 
    } catch (err:Error) { } 

    try { 
     theGrid[X][Y - 1].moveable = true; 
     if (theGrid[X][Y - 1].getOccupied == false) { 
      possibleMoves(range - 1, [X, Y - 1], flag, mtype); 
     } 
    } catch (err:Error) { } 
} 

Answer 1

あなたのタイルセットのデータ構造は、あまりにも多くのことをする「タイル」クラスに強く結合しているようです。 theGrid [X] [Y] .moveable、theGrid [X] [Y] .getOc​​cupied ... +おそらく他のいくつかのメソッド。

おそらく、タイルセットデータ構造はブール値（walkable？true/false）のみを格納し、タイルが歩行可能であるかどうかを伝える単一のメソッドを持つ必要があります。この場合、ブール値のVectorで十分です。 4つ（または8つの対角線付き）のnaerby値をテストするのはかなり速く、新たに見つかった値にテストを広げることは再帰的なループで行うことができます。

タイル（壁、オブジェクト、文字など）の種類が異なる場合は、ベクターを使用できます。 < int>ブーリアンではなく、 0は歩くことができるタイルになり、他のものは禁止されたエリアになります。 これはブールチェックを可能にします：0 =偽と他の値=真です。

ここでサンプルを作成しましたhttp://wonderfl.net/c/bRV8;コードを貼り付けるよりもはっきりしているかもしれません。マウスを動かすと、あなたは有効な細胞を与えるピンク色の形が見えます。

• l.53 "connexity" 可能valeus 4,8
• 4が接続されているが

接続

• 8を与えています
  • l.は、再帰を起点に関係なく行われ、最大の再帰の深さなど

  あります。時には予期しない方法で流出します。

  特定の移動量を与える必要がある場合、これでは不十分な場合は、何らかのパスファインダーを設定する必要があります。

  編集： 提供されたコードは機能しますが、次の行で回避しようとする再帰終了バグが含まれているようです。これは、いくつかのケースでのみ動作し、あなたのキャラクターがマップの端に置くか、彼に5以外の移動回数を与えれば本当に奇妙な振る舞い：

   var max:int = (maxDepth * maxDepth); 
       if(maxDepth % 2 == 0)max--; 
       recursiveCheck(valid, tilesetClone, 0, max, connexity); 
  

  私は別の再帰の深さをチェックし、バグが素早くなり、見かけ上。この例のグリッドと複雑な地図デザインの欠如はバグをあいまいにしていますが、ここではスクリーンショットを示します - マウスが図示のようにコーナーに配置されている場合、フィールドは6つの正方形と7つの四角形を延長します5.

  

Answer 2

あなたのコードは動作しますが、エレガントから遠いです。多くのタイルは複数回計算されます。これを修正するには、各gridTileの結果をキャッシュします。

Memoization techniqueをご覧ください。

Answer 3

ここでObjective-Cので2Dタイルマップ問題の回避障害物への再帰に対する正しい解決策です。私は良いと思っています4.5時間を目標スクリプトに翻訳して、それをデバッグしてください...ほぼ3AMになりました:)これを使うには、XでYの正方形のマップを作成し、マップ上にモデルを置き、

-(NSMutableArray*)possibleMovesFromIndex:(int)tileIndex movesCount:(int)moves allowDiagonalMoves:(BOOL)allowDiagonal 

結果の配列は、あなたのキャラクターが与えられた移動回数で到達できる場所を提供します。 A* pathfinding algorithmを使用すると、現在の位置から強調表示されているタイルのいずれかに移動をアニメートできます。

私は自分の名前と説明にスーパー冗長性を持たせようと試みました。

MapOfTiles.h: 

#import <Foundation/Foundation.h> 

#define tileCountWide 14 
#define tileCountTall 8 

@interface MapOfTiles : NSObject 
@property (nonatomic,strong)NSMutableArray* tilesetWalkable; 

@property (nonatomic)int width; 
@property (nonatomic)int height; 
@property (nonatomic,readonly)int tileCount; 

-(id)initWithXWidth:(int)xWidth yHeight:(int)yHeight; 

-(CGPoint)pointFromIndex:(int)index; 

-(NSMutableArray*)possibleMovesFromIndex:(int)tileIndex movesCount:(int)moves allowDiagonalMoves:(BOOL)allowDiagonal; 

@end 

MapOfTiles.m

#import "MapOfTiles.h" 

@implementation MapOfTiles 

-(id)initWithXWidth:(int)xWidth yHeight:(int)yHeight 
{ 
    self = [super init]; 
    if (self) { 
     self.width = xWidth; 
     self.height = yHeight; 

     int count = xWidth*yHeight; 

     self.tilesetWalkable = [[NSMutableArray alloc] initWithCapacity:count]; 

     for(int i = 0 ; i<count; i++) 
     { 
      //initial map is blank and has no obstacles 
      [self.tilesetWalkable addObject:[NSNumber numberWithBool:YES]]; 
     } 

    } 

    return self; 
} 

-(int)tileCount 
{ 
    return self.width*self.height; 
} 

-(NSMutableArray*)possibleMovesFromIndex:(int)tileIndex movesCount:(int)moves allowDiagonalMoves:(BOOL)allowDiagonal 
{ 
    int connexity = 4; 
    if(allowDiagonal) 
    { 
     connexity = 8; 
    } 

    //check if there is an obstacle at the origin 
    NSNumber* movementOrigin = self.tilesetWalkable[tileIndex]; 


    //if the first tile is walkable, proceed with seeking recursive solutions using 4 or 8 connected tiles 
    if(movementOrigin.boolValue == YES) 
    { 
     //create a copy to avoid messing up the real map 
     NSMutableArray* tilesetClone = [NSMutableArray arrayWithArray:self.tilesetWalkable]; 

     //will contain tileset indices where you can reach in the given number of moves if you can only move in a straight line or straight line and diagonally 
     NSMutableArray* validMoves = [NSMutableArray arrayWithCapacity:10]; 


     //we start building our array of walkable tiles with the origin, because we just tested it 
     NSNumber* originIsWalkable = [NSNumber numberWithInt:tileIndex]; 
     NSMutableArray* initialWalkableTilesArray = [NSMutableArray arrayWithObject:originIsWalkable]; 

     //for the first recursion, we manually set the origin to be not walkable, so recursion cannot return to it 
     [tilesetClone replaceObjectAtIndex:tileIndex withObject:[NSNumber numberWithBool:NO]]; 

     [validMoves addObject:initialWalkableTilesArray]; 



     [self recursiveCheckWithValidMovesArray:validMoves 
             tileset:tilesetClone 
            currentMove:0 
             maxMoves:moves 
             connexity:connexity]; 
     return validMoves; 

    } 

    return nil; 
} 

-(void)recursiveCheckWithValidMovesArray:(NSMutableArray*)validMovesToPopulate tileset:(NSMutableArray*)tileset currentMove:(int)currentDepth maxMoves:(int)maxDepth connexity:(int)connexity 
{ 
    if(currentDepth == maxDepth) 
    { 
     return; 
    }else 
    { 

     NSArray* movesToCheck = [validMovesToPopulate objectAtIndex:currentDepth]; 
     DLog(@"checking moves: %@",movesToCheck); 

     for (NSNumber* walkableMapIndex in movesToCheck) 
     { 

      //check array for valid moves 
      NSMutableArray* validMovesFromPoint = [self getValidMovesFromPoint:[self pointFromIndex:walkableMapIndex.intValue] 
                  lockMovesInTileset:tileset 
                   usingConnexity:connexity]; 


      //remember valid moves, so the next iteration will check them 

      if(validMovesToPopulate.count == currentDepth+1) 
      { 
       //this is the first time we are looking at moves at this depth, so add an array that will hold these moves 
       [validMovesToPopulate addObject:validMovesFromPoint]; 
      }else 
      { 
       //there is already an array at this depth, just add more values to it 
       NSMutableArray* validTilesForThisMove = validMovesToPopulate[currentDepth+1]; 
       [validTilesForThisMove addObjectsFromArray:validMovesFromPoint]; 
      } 
     } 

     if(movesToCheck.count>0) 
     { 
      [self recursiveCheckWithValidMovesArray:validMovesToPopulate 
              tileset:tileset 
             currentMove:++currentDepth 
              maxMoves:maxDepth 
              connexity:connexity]; 
     }else 
     { 
      return; 
     } 

    } 
} 

-(CGPoint)pointFromIndex:(int)index 
{ 
    //for a field that is 8 tall by 12 wide with 0,0 in bottom left 
    //tileCountTall is also number of rows 
    //x is column 
    int x = index/tileCountTall; 

    //y is row 
    int y = index % tileCountTall; 
    CGPoint xyPointInTileset = CGPointMake(x, y); 

    DLog(@"Examing index: %i assigned:x%.0f, y:%.0f",index, xyPointInTileset.x,xyPointInTileset.y); 
    return xyPointInTileset; 
} 





-(int)indexFromPoint:(CGPoint)point 
{ 
    return [self indexFromX:point.x y:point.y]; 
} 

-(int)indexFromX:(int)x y:(int)y 
{ 
    //in my case the map is rectangular 
    if (x < 0) x = 0; 

    int tileWidth = tileCountWide -2 ;//in my case, 2 rows of grid are hidden off screen for recycling of map segments 
    if (x > tileWidth - 1) x = tileWidth - 1; 


    if (y < 0) y = 0; 
    if (y > tileCountTall - 1) y = tileCountTall - 1; 

#warning this might screw up the algorithm, because for me x and y values are mapped differently? 
    return x * tileCountTall + y; 


    return 0; 
} 



-(void)lockTileAtIndex:(int)index forTileset:(NSMutableArray*)tileset rememberValidMovesInThisArray:(NSMutableArray*)tiles 
{ 
    DLog(@"Locking tile: %i",index); 
    //we lock this tile, so it is not checked by future recursions 
    NSNumber* tileIsNotWalkableAtIndex = [NSNumber numberWithBool:NO]; 
    [tileset replaceObjectAtIndex:index withObject:tileIsNotWalkableAtIndex]; 

    //remember that this index is a valid move 
    [tiles addObject:[NSNumber numberWithInt:index]]; 

} 

-(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; 
} 

@end