Game tile movement in 2d map

Question

What's the best way to do movement in a 2D square grid system? I have this something that works but it seems wrong/ugly (see below).

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

For example, U is the unit I want to move, and O is an impassable object like another unit or a mountain. If U can move 3 tiles, I want the moveable area (M) to look like this.

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

Here's my code:

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

the data structure of your tileset seems strongly coupled to a "Tile" class that does too many things ; theGrid[X][Y].moveable, theGrid[X][Y].getOccupied... + probably some other methods.

maybe the tileset data structure should only store Boolean values (walkable?true/false) and have a single method to tell wether a tile is walkable or not. in this case, a Vector of Boolean values is enough. testing the 4 ( or 8 with diagonals ) naerby values is pretty fast and spreading the test to the newly found values can be done with a recursive loop.

if you have different types of tiles (walls, objects, characters etc.), you could use a Vector.< int > rather than Booleans ; 0 would be a walkable tile and anything else would be forbidden areas. this allows a Boolean check : as 0 = false and any other value = true.

I've done a sample here http://wonderfl.net/c/bRV8 ; it might be clearer than pasting the code. move the mouse around, you should see a pinky shape the gives you the valid cells.

• l.53 is the "connexity" possible valeus are 4 and 8
• four connected gives

• eight connected

• l.54 is the max recursion depth

as such, the recursion is performed regardless of the starting point. it will spill in a sometimes unexpected way.

if you need to give a specific amount of moves this won't be enough, you'll have to set up some kind of pathfinder.

Edit: It appears that the code provided works, but contains a recursion termination bug that is attempted to be avoided by the following line. This works only in some cases and behaves really weird if you put your character at the edge of the map or give him number of moves other than 5:

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

I checked with different recursion depth, and the bug quickly becomes apparent. Lack of grid and complex map design of this example obscures the bug, but here's a screenshot below - note that if mouse is positioned in the corner like shown, the field extends 6 squares up and 7 squares left, while it should've only been 5.

Answer 2

Here's the correct solution to the recursion to the avoiding obstacles on a 2D tile map problem in objective-c. Took me good 4.5 hours translate action script to objective-c and debug it... almost 3AM now :) To use this, just create a map of X by Y squares, put your model on the map and call

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

The resulting array will give you locations that your character can reach with the given number of moves. You can then use A* pathfinding algorithm to animate movement from the current position to any one of highlighted tiles.

I have attempted to be super-verbose in my names and descriptions, as it was quite difficult to trace these points through all these method calls without it.

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

Answer 3

Your code will work, but is far from elegant. A lot of tiles will be calculated multiple times. You could fix this by caching the results for each gridTile.

Have a look at the Memoization technique.