Движение на игрални плочки в 2d карта

структурата на данните на вашия набор от елементи изглежда силно свързана с клас "Плочка", който прави твърде много неща; theGrid[X][Y].moveable, theGrid[X][Y].getOccupied... + вероятно някои други методи.

може би структурата на данните за набора от плочки трябва да съхранява само булеви стойности (walkable?true/false) и да има един единствен метод, за да каже дали плочката е проходима или не. в този случай е достатъчен вектор от булеви стойности. тестването на 4 (или 8 с диагонали) стойности на naerby е доста бързо и разпространението на теста към новооткритите стойности може да се направи с рекурсивен цикъл.

ако имате различни видове плочки (стени, обекти, герои и т.н.), можете да използвате Vector.‹ int > вместо Booleans; 0 ще бъде проходима плочка, а всичко останало ще бъде забранена зона. това позволява булева проверка: като 0 = false и всяка друга стойност = true.

Направих пример тук http://wonderfl.net/c/bRV8 ; може да е по-ясно от поставянето на кода. преместете мишката наоколо, трябва да видите форма на розов цвят, която ви дава валидните клетки.

• l.53 е "свързаността", възможните стойности са 4 и 8
• четири свързани дава

• осем свързани

• l.54 е максималната дълбочина на рекурсия

като такава, рекурсията се извършва независимо от началната точка. ще се разлее по понякога неочакван начин.

ако трябва да дадете определено количество ходове, това няма да е достатъчно, ще трябва да настроите някакъв вид пътека.

Редактиране: Изглежда, че предоставеният код работи, но съдържа грешка при прекратяване на рекурсия, която се опитва да бъде избегната от следния ред. Това работи само в някои случаи и се държи наистина странно, ако поставите героя си на ръба на картата или му дадете брой ходове, различен от 5:

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

Проверих с различна дълбочина на рекурсия и грешката бързо става очевидна. Липсата на решетка и сложният дизайн на картата в този пример прикриват грешката, но ето екранна снимка по-долу - имайте предвид, че ако мишката е позиционирана в ъгъла, както е показано, полето се разширява с 6 квадрата нагоре и 7 квадрата наляво, докато трябваше да бъде само 5.

Вашият код ще работи, но далеч не е елегантен. Много плочки ще бъдат изчислени многократно. Можете да коригирате това, като кеширате резултатите за всяка gridTile.

Разгледайте техниката на мемоизация.

Ето правилното решение на рекурсията за избягване на препятствия при проблем с 2D карта с плочки в objective-c. Отне ми добри 4,5 часа, за да преведа скрипта за действие в goal-c и да го отстраня... почти 3 часа сутринта :) За да използвате това, просто създайте карта от 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