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

发布时间：2010-05-30 05:31:10 文章来源：www.iduyao.cn 采编人员：星星草

【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下载

上一篇：移动开发之小弟我见-“Android开发生涯”
下一篇：matrix施用：平移

友情提示：
信息收集于互联网，如果您发现错误或造成侵权，请及时通知本站更正或删除，具体联系方式见页面底部联系我们，谢谢。

其他相似内容：

【IOS】高仿糗事百科客户端（根本实现了除注册，评论之外的功能）

【IOS】高仿糗事百科客户端（基本实现了除注册，评论之外的功能）【原创作品，欢迎转载，转载请在明显处注明！谢谢。原文地址：h...
数独游戏（一）之绘制九宫格，并初始化数据

数独游戏（1）之绘制九宫格，并初始化数据 <数独游戏>之绘制九宫格，并初始化数据 1.在工程里的res/values目录下新建一个colors....
关于listview的setAdapter跟notifyDataSetChanged

关于listview的setAdapter和notifyDataSetChanged 做了个需要更新listview的项目，在listview更新时遇到问题，抓耳挠腮半天仍未能解...
最完整的让cocos2d游戏适配IPAD Retina的课程

最完整的让cocos2d游戏适配IPAD Retina的教程暂时在网上还没找到一个让cocos2d开发的IPhone游戏快速地适应IPAD2 Retina模式的教...
应用ContentObserver监听ContentProvider中数据的变化

使用ContentObserver监听ContentProvider中数据的变化如果ContentProvider的访问者需要知道ContentProvider中的数据发生了变化，...
Andriod 兑现可拖动列表

Andriod 实现可拖动列表在做一个应用时，有一个需求，需要实现像iphone天气的城市列表界面的可拖动功能。其实android已...
相仿APP大厅程序的实现

类似APP大厅程序的实现由于Android可以按照一定的规则，启动另外一个应用程序的Activity，并可以传递一些数据，因此下面的需求，在原则...
编纂小程序查看CSDN博客信息(ASIHTTPRequest+TFHpple)

编写小程序查看CSDN博客信息(ASIHTTPRequest+TFHpple) 作为一个iOS练习，使用ASIHTTPRequest+TFHpple写了个小程序读取CSDN博客...
Objective-C中nil与release的差别与用法

Objective-C中nil与release的区别与用法做IOS开发的估计都对Objective-C的内存管理机制很头疼，一不小心程序就会出内存泄露...
联想匹敌苹果之路：用苹果的方式打败苹果

联想抗衡苹果之路：用苹果的方式打败苹果？联想教父柳传志说过，联想历史上曾经历三次生死危机，但都死里逃生，并一次次验证着“大难不...

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

其他相似内容：

热门推荐：