【Objective-c算法】 A*自动寻路算法

A*算法适合在静态环境中寻路，也就是说周围的物体不会动态的移动。

需要2个表，分别保存待检测和已检测的格子：

@interface AStarFinder : NSObject {
	
	NSMutableArray *openTable;//尚未走过的格子
	NSMutableArray *closeTable;//已经走过的格子
}

openTable保存的就是当前格子四周的格子（最多为8个），只保存满足条件的格子，不能是障碍物 或者出屏幕了。

你可以这样来初始化它们：

CCTMXTiledMap *map = [CCTMXTiledMap tiledMapWithTMXFile:@"tile_map.tmx"];//加载地图

<pre name="code" class="java">//mapSize是一个CGSize保存的是地图中Tile(格子)的数量

openTable = [[NSMutableArray alloc] initWithCapacity:map.mapSize.width*map.mapSize.height];
closeTable = [[NSMutableArray alloc] initWithCapacity:map.mapSize.width*map.mapSize.height];

看看A*算法的核心代码：

- (void)start:(TilePoint *)startPoint_ EndPoint:(TilePoint *)endPoint_{
	
	[openTable addObject:startPoint_];//一开始就把起始位置放进openTable
        TilePoint *curr=nil;
	while ([openTable count] > 0){//该循环用来找到最短路径,openTable要是没东西了 就表示无法到达目的地！
		curr = [self bestTilePoint:curr];//从openTable找取出最合适的格子，下一步应该向哪里走
		if (curr != nil) {
			
			[closeTable addObject:curr];//检测过了 就放到closeTable
                        
                        if ([self nextTile:curr X:curr.x Y:curr.y-1] == YES) {//该函数用来判断是否到达终点
                return;
               }
                        ......
}

看看 bestTilePoint 函数：

- (TilePoint *)bestTilePoint:(TilePoint *)p{
	
	TilePoint *best = nil;
	
	if ([openTable count] == 0) {
		return nil;
	}else {
		for (NSInteger i = 0; i < [openTable count]; i++) {//遍历openTable
			if (best == nil) {
				best = [openTable objectAtIndex:i];//取出格子
				if (best != nil && [self isComparePoint:best.parent And:p] == NO) {
					best = nil;
				}
			}else {
				TilePoint *best2 = [openTable objectAtIndex:i];
				if ([self isComparePoint:best2.parent And:p] == YES) {
					best = best.f >= best2.f ? best2 : best;//得到f值小的格子,f值越小路线则越可靠
				}
			}		
		}
		[best retain];
		[openTable removeObject:best];//从openTable中删除 一会还要加入到closeTable
		return best;
	}
}

总之 bestTilePoint函数就是用来找到最合适的移动方向。

看看 是如何处理每一个格子的：

- (BOOL)nextTile:(TilePoint *)curr X:(NSInteger)x Y:(NSInteger)y{

	TilePoint *next = [[TilePoint alloc] createTilePoint:x Y:y];
	next.parent = curr;//父亲当然是当前的格子
	
	if ([self isComparePoint:next And:endPoint]) {//先判断是否已到目的地
		[closeTable addObject:next];
		NSLog(@"find end point !!!!!!!\n");
		return YES;	//到了目的地 就不需要在检测其它格子了。。	
	}
	
        //这里检测的是格子是否为有效，包括：障碍物 出屏幕 已经检测过。。
	if ([self isInCloseTable:next] == NO && [self isEnableTile:next.x Y:next.y] == YES) {
		if ([self isInOpenTable:next] == NO) {
			//计算f、g值
			next.g = 14 + next.parent.g;
			next.f = next.g + [self calculateHPower:next];
			
			[openTable addObject:next];//然后就可以加入到openTable了
		}else {
			TilePoint *next2 = [self getFromOpenPath:next];
			if (next2.f > next.f) {
				next2.parent = curr;
				next2.g = 14 + next2.parent.g;
				next2.f = next2.g + [self calculateHPower:next2];
			}
		}		
	}
	return NO;
}

DEMO下载