Движение игровых плиток на 2-й карте

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

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

возможно, структура данных набора плиток должна хранить только логические значения (пригодно для ходьбы? Истина / ложь) и иметь единственный метод, позволяющий определить, является ли плитка доступной или нет. в этом случае вектор булевых значений достаточно. тестирование 4-х (или 8-ти по диагонали) значений Naerby довольно быстрое, и распространение теста на вновь найденные значения можно выполнить с помощью рекурсивного цикла.

если у вас есть разные типы плиток (стены, объекты, персонажи и т. Д.), Вы можете использовать Vector. вместо Booleans; 0 будет плиткой, которую можно пройти, а все остальное будет запрещено. это допускает логическую проверку: 0 = false и любое другое значение = true.

Я сделал образец здесь http://wonderfl.net/c/bRV8; это может быть понятнее, чем вставка кода. переместите мышь, вы увидите розовую фигуру, которая дает действительные ячейки.

• l.53 - это «связность» возможных значений valeus 4 и 8
• четыре подключенных дает

• восемь подключенных

• l.54 - максимальная глубина рекурсии

рекурсия как таковая выполняется независимо от начальной точки. иногда это произойдет неожиданным образом.

если вам нужно дать определенное количество ходов, этого будет недостаточно, вам придется установить какой-то указатель пути.

Edit: Представляется, что предоставленный код работает, но содержит ошибку завершения рекурсии, которую попытается избежать в следующей строке. Это работает только в некоторых случаях и ведет себя очень странно, если вы поместите своего персонажа на краю карты или дадите ему количество ходов, отличных от 5:

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

Я проверил с разной глубиной рекурсии, и ошибка быстро становится очевидной. Отсутствие сетки и сложный дизайн карты в этом примере скрывают ошибку, но вот снимок экрана ниже - обратите внимание, что если мышь расположена в углу, как показано, поле расширяется на 6 квадратов вверх и 7 квадратов влево, в то время как это должно было быть только 5.

Answer 2

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

Взгляните на Технику запоминания .

Answer 3

Вот правильное решение рекурсии избегания препятствий на задаче 2D-карты тайлов в target-c .Мне понадобилось 4,5 часа, чтобы перевести сценарий действия в target-c и отладить его ... почти в 3 часа ночи :). Чтобы использовать это, просто создайте карту квадратов X на Y, поместите вашу модель на карту и позвоните

* 1004.*

Полученный массив даст вам местоположения, которые ваш персонаж может достичь с заданным количеством ходов.Затем вы можете использовать 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