Objective-C 实现的 A* 寻路算法，用于 iOS 和 OS X 游戏。
HUMAStarPathfinder 在 iOS 6 和 iOS 7 上进行了测试，并需要 ARC。
该寻路算法是通用的，可以与任何游戏引擎一起使用（我已经测试过 Cocos2d 和 SpriteKit），但假设游戏引擎的坐标系原点在屏幕左下角时，它将返回路径。
查看包含的 Xcode 项目，其中有一个示例 Cocos2d 游戏。由于我还没有时间创建视网膜瓷砖地图，因此该示例将只能在不带视网膜的设备/模拟器上正确运行。点击任何地方可以移动图标，它将避开用红色标记的任何砖块。
// initialize a pathfinder. Store as an instance variable so you can reference it on touches later. Optionally set a delegate. The tileMap object can be any tile map implementation. In the example, it is a CCTMXTiledMap, but can be anything. The mapSize is the size of the map in tiles. The tileSize is the size of each tile.
self.pathfinder = [HUMAStarPathfinder pathfinderWithTileMapSize:tileMap.mapSize
tileSize:tileMap.tileSize
delegate:self];
// find a path from the start point to the target point. The target could be where a tap occured or some other point determined programmatically. Returned is an array of NSValue-wrapped CGPoints that describe the path. From here you can create a CGPath or UIBezier path for a sprite to follow, move a sprite from point to point, etc.
NSArray *path = [self.pathfinder findPathFromStart:startPoint
toTarget:targetPoint];
...
// elsewhere, you must implement the delegate method to determine if a node is walkable. For example, a mountain may not be walkable but grass is
- (BOOL)pathfinder:(HUMAStarPathfinder *)pathFinder canWalkToNodeAtTileLocation:(CGPoint)tileLocation {
CCTMXLayer *meta = [self.tileMap layerNamed:@"Meta"];
uint8_t gid = [meta tileGIDAt:tileLocation];
BOOL walkable = YES;
if (gid) {
NSDictionary *properties = [self.tileMap propertiesForGID:gid];
walkable = [properties[@"walkable"] boolValue];
}
return walkable;
}
// optionally, you can implement the delegate method to alter the cost to move from one node to another
- (NSUInteger)pathfinder:(HUMAStarPathfinder *)pathfinder costForNodeAtTileLocation:(CGPoint)tileLocation {
CCTMXLayer *ground = [self.tileMap layerNamed:@"Ground"];
uint32_t gid = [ground tileGIDAt:tileLocation];
NSUInteger cost = pathfinder.baseMovementCost;
if (gid) {
NSDictionary *properties = [self.tileMap propertiesForGID:gid];
if (properties[@"cost"]) {
cost = [properties[@"cost"] integerValue];
}
}
return cost;
}HUMAStarPathfinder 有以下属性
@property (nonatomic, weak) id<HUMAStarPathfinderDelegate> delegate;
遵循 HUMAStarPathfinderDelegate 协议的对象。用于查询有关特定节点的信息。如果为 nil，则假定所有节点均可通行，并将使用基础移动成本 10。默认值为 nil。
@property (nonatomic, assign) CGSize tileMapSize;
瓷砖地图的砖块大小。例如，CGSize 15, 10 表示宽度为 15 砖块、高度为 10 砖块的地图。
@property (nonatomic, assign) CGSize tileSize;
瓷砖地图中每个砖块的大小（以点为单位）。
@property (nonatomic, assign) HUMAStarDistanceType distanceType;
用于计算节点启发式（从节点到目标的移动成本）的距离公式。默认为 HUMAStarDistanceTypeManhattan。
@property (nonatomic, assign) HUMCoodinateSystemOrigin coordinateSystemOrigin;
使用的坐标系的原点。用于确定返回路径的 CGPoint 值。起始点、目标点和路径点都将相对于此原点。例如，UIKit 的原点 (0, 0) 位于右上角，而 SpriteKit 和 Cocos2d 的原点位于左下角。默认值为 HUMCoodinateSystemOriginBottomLeft。
@property (nonatomic, assign) BOOL pathDiagonally;
如果是 YES，计算出的路径可以包含对角路径。如果是 NO，路径仅包含水平和垂直路径。默认值为 YES。
@property (nonatomic, assign) BOOL ignoreDiagonalBarriers;
如果是 YES 且 pathDiagonally 为 YES，则如果砖块有效（例如，NE 有效如果砖块有效，忽略 N 或 E 是否有效），则允许对角砖块。默认值为 NO。
@property (nonatomic, assign) BOOL pathCanCrossBorders;
如果为YES，计算路径能够跨越任何障碍物边缘，前提是在四个基本方位（例如：如果北或东是有效的，那么东北就是有效的）。如果为NO，计算路径将在两个基本方位都有效的情况下沿着障碍物边缘移动。例如，如果北和东都有效，那么东北就是有效的。如果ignoreDiagonalBarriers为YES，则忽略。默认值为YES。
HUMAStarPathfinder有以下方法
- (NSArray *)findPathFromStart:(CGPoint)start toTarget:(CGPoint)target;
寻找从起点到目标点的最短路径，避开任何不可通过节点。返回的CGPoints是相对于指定的coordinateSystemOrigin值。如果为HUMCoodinateSystemOriginTopLeft，则位置相对屏幕的左上角。如果为HUMCoodinateSystemOriginBottomLeft，则位置相对屏幕的左下角。
- (CGPoint)positionForTileLocation:(CGPoint)tileLocation;
将瓦片位置转换为屏幕上的位置。提供CGPoint相对于指定的coordinateSystemOrigin值。如果为HUMCoodinateSystemOriginTopLeft，则位置相对于屏幕的左上角。如果为HUMCoodinateSystemOriginBottomLeft，则位置相对于屏幕的左下角。
- (CGPoint)tileLocationForPosition:(CGPoint)position;
将屏幕上的位置转换为瓦片位置。返回CGPoint相对于指定的coordinateSystemOrigin值。如果为HUMCoodinateSystemOriginTopLeft，则位置相对于屏幕的左上角。如果为HUMCoodinateSystemOriginBottomLeft，则位置相对于屏幕的左下角。
HUMAStarPathfinder提供了一个代理协议。HUMAStarPathfinderDelegate有以下必需方法
- (BOOL)pathfinder:(HUMAStarPathfinder*)pathFinder canWalkToNodeAtTileLocation:(CGPoint)tileLocation;
确定某个节点是否可通过。可通过性由应用程序/游戏决定。例如，山脉可能不可通过，而沼泽可能可通过。如果节点可通过，则返回YES，否则返回NO。
HUMAStarPathfinderDelegate有以下可选方法
- (NSUInteger)pathfinder:(HUMAStarPathfinder *)pathfinder costForNodeAtTileLocation:(CGPoint)tileLocation
要求代理提供在指定瓦片上水平行走的成本。例如，某些节点可能需要更高的成本才能到达。一个沼泽的成本可能比草地高。如果瓦片没有移动信息，你应该返回提供的路径搜索实例的baseMovementCost。如果不实现，则以水平行走到一个瓦片的基成本是10，以对角行走为14.14（10x10三角形的斜边）。
只需将HUMAStarPathfinder中的四个文件添加到您的项目中
或者如果您使用CocoaPods，请添加HUMAStarPathfinder到您的Podfile。
在MIT许可证下发布。