这是在 Objective-c 中的 2D 瓦片地图问题上递归回避障碍的正确解决方案。花了我 4.5 小时将动作脚本翻译成 Objective-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
