2D 타일지도에서 게임 타일 이동

Question

2D 사각형 격자 시스템에서 이동을 수행하는 가장 좋은 방법은 무엇입니까? 나는이 작품을 가지고 있지만 잘못되었거나 추악한 것 같습니다 (아래 참조). 예를 들어

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] .getOccupied ... + 아마 다른 방법들.

아마도 타일셋 데이터 구조는 부울 값 (walkable? true/false) 만 저장하고 타일이 walkable인지 여부를 알려주는 단일 메서드를 사용해야합니다. 이 경우 부울 값의 Vector이면 충분합니다. 4 개 (또는 대각선을 포함한 8 개)의 naerby 값을 테스트하는 것은 매우 빠르며 새로 발견 된 값으로 테스트를 확산하는 것은 재귀 루프를 사용하여 수행 할 수 있습니다.

다른 유형의 타일 (벽, 물체, 문자 등)을 사용하는 경우 벡터를 사용할 수 있습니다. < int>가 아니라 부울 0은 걸을 수있는 타일이고 다른 것은 금지 된 영역입니다. 이렇게하면 부울 검사가 허용됩니다. 0 = false 및 다른 값 = true입니다.

여기 샘플을 작성했습니다. http://wonderfl.net/c/bRV8; 코드를 붙여 넣는 것보다 명확 할 수 있습니다. 마우스를 움직이면 핑키 모양이 나타나야 유효한 셀을 얻을 수 있습니다.

• l.53는 "connexity"가능한 valeus 4와 접속
• 네 8

• 여덟

,745 접속 제공되어있다

• l.54 1,515,재귀은 시작점에 관계없이 수행되고, 최대 재귀 깊이 등

이다. 때로는 예상치 못한 방식으로 유출 될 것입니다.

특정 양의 움직임을 줄 필요가 있다면 충분하지 않을 것입니다. 어떤 종류의 패스 파인더를 설치해야합니다.

편집 : 제공된 코드가 작동하지만 다음 줄에서 회피하려고 시도하는 재귀 종료 버그가있는 것으로 보입니다.이 경우에만 작동하며지도의 가장자리에 캐릭터를 넣어 또는 그에게 5 이외의 다른 움직임의 수를 줄 경우 정말 이상한 동작 : 나는 다른 재귀 깊이를 확인

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

을하고, 버그를 신속하게 명백한. 이 예제의 그리드 및 복잡한 맵 디자인 부족으로 버그가 가려졌지만 아래 스크린 샷이 있습니다. 마우스가 그림과 같이 모서리에 배치되면 필드는 6 개의 스퀘어를 확장하고 7 개의 스퀘어는 왼쪽으로 확장해야합니다.

Answer 2

귀하의 코드가 작동하지만 우아한 거리가 멀다. 많은 타일이 여러 번 계산됩니다. 각 gridTile에 대한 결과를 캐싱하여이 문제를 해결할 수 있습니다.

Memoization technique을 살펴보십시오.

Answer 3

5. 다음 목표 - 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