A*Star PathFinding « cocos2d for iPhone

cocos2d for iPhone » Programming » Programming - Everything else

A*Star PathFinding

(18 posts) (12 voices)

Started 1 year ago by pagex
Latest reply from RishabhShah

Tags:

No tags yet.

pagex
Member

Just curious if anyone has successfully implemented any sort of A*Star PathFinding logic using cocos2d?

Posted 1 year ago #
Ben Kraus
Member

This bonus chapter goes over A* using cocos2d with source. It is great!

http://apress.com/book/downloadfile/4448

Posted 1 year ago #
pagex
Member

Yes I read over that a while back. It's a good read but doesn't really provide any working examples with regards to actual pathfinding... more of a conceptual read.

Although, I have been looking at this source code here...

http://cvs.codeyard.net/svn/Sokoban3D/source/PathFinding.h

It would be great to try to modify that code to pass back a CGPoint array that could then easily be used to move sprites.

I'm just not sure how I'd go about turning that code into a working example.

Ideas welcome!

Posted 1 year ago #
Kitsune
Member

I've implemented A* in my project by literally just translating the pseudocode(from link below) to Obj-C. It'll take some time to read and understand the whole concept but it's actually pretty easy once you do. Good luck.

Pseudocode here:

A*_search_algorithm

edit: it seems you can't click on the link because of the (*) character. Just copy and paste it onto your browser.

Posted 1 year ago #
Codemattic
Moderator

fixed the link

Posted 1 year ago #
Omegas7
Member

I've been in need of a good A* pathfinding tutorial for a long time as well, not really for cocos2d, but studying these might be pretty helpful actually =D

Posted 1 year ago #
pagex
Member

I have a woking A*Star PathFinding class I'm just now testing... I'll post the code soon.

Posted 1 year ago #

pagex
Member

I have this working somewhat fast but my gut is telling me it's NOT fast enough. I'm thinking it could be so much faster if possibly the arrays were handled differently.. maybe converted to C Arrays or something.

I'm wondering if anyone out there could help me optimize this so it runs blazing fast!

I've been testing it on an odd shaped tilemap with 2,090 nodes (38 x 55) where each tilesize is 10x4 and I'm calling the findPath method every 2 seconds.

I have a class called GameMap which is a subclassed CCTMXTiledMap.... here's the rough logic of how I'm testing everything....

(Please forgive any typos or mistakes here, I'm out of town at the moment and have all this on a USB drive and using a PC with textpad to posting all of this... I'll try to just post a project file later but wanted to get it up.)

/************************************************
 *
 *  GameMap.h
 *
 ************************************************/

#import "AStarGenerator.h"

@interface GameMap : CCTMXTiledMap {

	AStarMap *mapdata;
	AStarGenerator *generator;
	CCSprite *spite1, *sprite2;

}

/************************************************
 *
 *  GameMap.m
 *
 ************************************************/

#import "GameMap.h"

- (id)init {
	if((self = [super initWithTMXFile:@"tilemap.tmx"])) {

	  // load pathfinding
	  [self initPathFinding];

	  // load tiles into 'mapdata' from a layer in the tilemap called 'blocked'
	  [self initBlockedTiles]; 

	  // load 2 sprites and move them endlessly around the screen
	  [self initSprites];

	  // schedule to find the shortest path between 2
	  // sprites every 2 seconds. I'm doing this to test speed.
	  // The FPS currently dips down a bit each call
	  // my goal is to optimize it so runs with zero lag time

	  [self schedule:@selector(updatePath:) interval:2];

	}
	return self;
}

- (void) initPathFinding {
	CGSize xsize = CGSizeMake(mapSize_.width,mapSize_.height);
	generator = [[AStarGenerator alloc] loadWithMapSize:xsize];
	mapdata = generator.mapdata;
}

- (void) initBlockedTiles {
	CCTMXLayer *blocked = [self layerNamed:@"blocked"];
	CGSize size = [blocked layerSize];
	for(int x=0;x<size.width;x++){
	   for(int y=0;y<size.height;y++){
		CGPoint p = ccp(x,y);
		int gid = [blocked tileGIDAt:p];
		if(gid > 0){
			[mapdata blockPoint:point];
		}
	   }
	}
}

- (CGPoint) coordsAt:(CGPoint)position {
    int x = position.x/tileSize_.width;
    int y = mapSize_.height-(position.y/tileSize_.height);
    return ccp(x,y);
}

- (void) updatePath:(ccTime)dt {

	// Update Path between sprites and draw on blank
	// Tilemap layer called 'path'

	/*** clear tilemap 'path' layer ***/
	CCTMXLayer *pathLayer = [self layerNamed:@"path"];
	CGSize size = [pathLayer layerSize];
	for(int x=0;x<size.width;x++){
		for(int y=0;y<size.height;y++){
		  [pathLayer removeTileAt:ccp(x,y)];
		}
	}
	/*** Get Sprite Coordinates from position ***/
	CGPoint point1 = [self coordsAt:sprite1.position];
	CGPoint point2 = [self coordsAt:sprite2.position];

	/*** Generate Path and draw on pathLayer ***/
	NSMutableArray *newPath = [generator findPath:point1:point2];
	for(int i=0; i<[newPath count]; i++) {
		AStarNode *aNode = [newPath objectAtIndex:i];
		[pathLayer setTileGID:14 at:ccp(aNode->nodeX,aNode->nodeY)];
	}
}

/************************************************
 *
 *  AStarGenerator.h
 *
 ************************************************/

#import "cocos2d.h"
#import "AStarNode.h"
#import "AStarMap.h"

@interface AStarGenerator : NSObject {
	AStarMap *mapdata;
}
@property (assign, nonatomic) AStarMap *mapdata;

+(id) loadWithMapSize:(CGSize)dim;
-(id) initWithMapSize:(CGSize)dim;

/* returns an array of tilemap points */
-(id) findPath:(CGPoint)start:(CGPoint)end;

/* Manhattan Algorithm, cost is distance from x to end */
-(float) heuristic:(CGPoint)pos0:(CGPoint)pos1;

/* Quickie method to find given node in the array from x,y value */
-(AStarNode*) nodeInArray:(NSMutableArray*)a withPoint:(CGPoint)point;

/* Finds the node in a given array which has the lowest cost */
-(AStarNode*) findLowestCostNode:(NSMutableArray*)a;

@end

/************************************************
 *
 *  AStarGenerator.m
 *
 ************************************************/

#import "AStarGenerator.h"

@implementation AStarGenerator

@synthesize mapdata;

+(id) loadWithMapSize:(CGSize)mapsize{
	return [[[self alloc] initWithMapSize:mapsize] autorelease];
}

-(id) initWithMapSize:(CGSize)mapsize{
	if( (self=[super init])) {
		mapdata = [[AStarMap alloc] initWithMapSize:mapsize];
	}
	return self;
}

-(void)dealloc {
    [super dealloc];
}

-(float)heuristic:(CGPoint)pos0:(CGPoint)pos1{
	float d1 = abs(pos1.x - pos0.x);
	float d2 = abs(pos1.y - pos0.y);
	return d1 + d2;
}

-(AStarNode*)nodeInArray:(NSMutableArray*)a withPoint:(CGPoint)point {
	NSEnumerator *e = [a objectEnumerator];
	AStarNode *n;
	if(e){
		while((n = [e nextObject])){
			if((n->nodeX == point.x) && (n->nodeY == point.y)){
				return n;
			}
		}
	}
	return nil;
}

-(AStarNode*)findLowestCostNode:(NSMutableArray*)a {
	AStarNode *n, *lowest=nil;
	NSEnumerator *e = [a objectEnumerator];
	if(e){
		while((n = [e nextObject])){
			if(lowest == nil){
				lowest = n;
			}else{
				if(n->f < lowest->f){
					lowest = n;
				}
			}
		}
		return lowest;
	}
	return nil;
}

-(id) findPath:(CGPoint)start:(CGPoint)end {

	if((start.x == end.x) && (start.y == end.y)) return nil;

	// neighbors
	static CGPoint positionOffsets[4];
	positionOffsets[0] = ccp(1,0);	// east
	positionOffsets[1] = ccp(-1,0); // west
	positionOffsets[2] = ccp(0,1);	// south
	positionOffsets[3] = ccp(0,-1); // north

	AStarNode *current, *neighbor, *aNode;
	NSMutableArray *ret, *openList, *closedList;
	int posX,posY,gScoreIsBest;
	CGPoint newP;

	ret = [NSMutableArray array];
	openList = [NSMutableArray array];
	closedList = [NSMutableArray array];

	// Add Starting Node to openList

	aNode = [AStarNode node];
	aNode->nodeX = start.x;
	aNode->nodeY = start.y;
	aNode->parentNode = nil;
	aNode->f = 0;

	[openList addObject:aNode];

	while([openList count]) {

		current = [self findLowestCostNode: openList];

		if((current->nodeX == end.x) && (current->nodeY == end.y)){

			/***
			PATH FOUND, Return an array based on parentNode
			that was set below when gScore was best
			***/

			[ret addObject: current];
			aNode = current->parentNode;
			while(aNode->parentNode != nil){
				[ret addObject: aNode];
				aNode = aNode->parentNode;
			}
			ret = [[ret reverseObjectEnumerator] allObjects];
			return ret;
		}

		[closedList addObject: current];
		[openList removeObject: current];

		// look at nodes around current (neighbors)

		NSUInteger i;
		for (i=0; i<4; i++) {

			posX = current->nodeX+positionOffsets[i].x;
			posY = current->nodeY+positionOffsets[i].y;
			newP = ccp(posX,posY);

			// check that map coordinates aren't blocked 

			if(![mapdata isBlockedAt:newP]){ 

				if(![self nodeInArray:closedList withPoint:newP]) {

					// valid neighbor, keep going

					neighbor = [AStarNode node];
					neighbor->nodeX = posX;
					neighbor->nodeY = posY;

					// g score is the shortest distance from start to current node,
					// check if the path to neighbor is the shortest one, +1
					// 1 is the distance from a node to it's neighbor

					int gScore = current->g + 1;

					gScoreIsBest = 0;

					if(![self nodeInArray:openList withPoint:newP]) {

						// First time arrived at node, it must be the best.
						// Take the h (heuristic) score since we haven't done so yet

						gScoreIsBest = 1;

						neighbor->h += [self heuristic:newP:end];

						[openList addObject: neighbor];

					}else if(gScore < neighbor->g) {

						// seen already, but last time node had a worse g score (distance from start)

						gScoreIsBest = 1;
					}

					if(gScoreIsBest) {

						// Found optimal path to this node so far. Store info
						// on how we got here and just how good it really is

						neighbor->parentNode = current;
						neighbor->g = gScore;
						neighbor->f = neighbor->g + neighbor->h;

					}

				}

			}

		}

	}

	// NO PATH FOUND

	return nil;

}

@end

/*******************************************************
 *
 *  AStarNode.h
 *
 *  autorelease node holds node info (cost, x, y, etc.)
 *  AStarNode is a data container for a
 *  single node in an AStar Path
 *
 *******************************************************/

@interface AStarNode : NSObject {
@public
	int nodeX;
	int nodeY;
	int f;
	int g;
	int h;
	AStarNode *parentNode;
}

+(id)node;

@end

/*******************************************************
 *
 *  AStarNode.m
 *
 *******************************************************/

#import "AStarNode.h"

@implementation AStarNode

+(id)node {
	return [[[AStarNode alloc] init] autorelease]; // autorelease
}

@end

/*******************************************************
 *
 *  AStarMap.h
 *
 *  Map is class to keep track of blocked
 *  tiles on a map by coordinate
 *  if a node is blocked, type=TILE_BLOCKED it's skipped.
 *
 *******************************************************/

#import "AStarTile.h"

@interface AStarMap : NSObject {
	int width, height;
	NSMutableArray *tiles;
	AStarTile *emptyTile;
}

@property (nonatomic) int width, height;
@property (nonatomic, retain) NSMutableArray *tiles;

-(id) initWithMapSize:(CGSize)size;
-(void) blockPoint:(CGPoint)point;
-(void) freePoint:(CGPoint)point;
-(bool) isBlockedAt:(CGPoint)point;
-(AStarTile *) getTileAt:(CGPoint)point;
-(bool) validPoint:(CGPoint)point;

@end

/*******************************************************
 *
 *  AStarMap.m
 *
 *******************************************************/

#import "AStarMap.h"

@implementation AStarMap
@synthesize width, height;
@synthesize tiles;

-(id) initWithMapSize:(CGSize)size {
	self = [super init];
	if(self){
		width = (int)size.width;
		height = (int)size.height;
		tiles = [[NSMutableArray arrayWithCapacity:(width * height)] retain];
		for(int x=0;x<width;x++){
		   for(int y=0;y<height;y++){
			[tiles addObject:[[AStarTile alloc] init]];
		   }
		}
		emptyTile = [[AStarTile alloc] init];
	}
	return self;
}
-(void) blockPoint:(CGPoint)point {
	[self getTileAt:point].type = TILE_BLOCKED;
}
-(void) freePoint:(CGPoint)point{
	[self getTileAt:point].type = TILE_FREE;
}
-(bool) isBlockedAt:(CGPoint)point {
	if(![self validPoint:point]){
		return true;
	}
	if([self getTileAt:point].type == TILE_BLOCKED){
		return true;
	}
	return false;
}
-(AStarTile *) getTileAt:(CGPoint)point {
	if(![self validPoint:point]){
	   return emptyTile;
	}else{
	   return [tiles objectAtIndex:(point.y*width+point.x)];
	}
}
-(bool) validPoint:(CGPoint)point {
	if(point.x < 0 || point.x >= width || point.y < 0 || point.y >= height){
		return false;
	}
	return true;
}

@end

/*******************************************************
 *
 *  AStarTile.h
 *
 *******************************************************/

#define TILE_FREE 0
#define TILE_BLOCKED 1
#define TILE_MARKED 2

@interface AStarTile : NSObject {
	int type;
}
@property (nonatomic) int type;
@end

*******************************************************
 *
 *  AStarTile.m
 *
 *******************************************************/

#import "AStarTile.h"

@implementation AStarTile
@synthesize type;

@end

I know this is a large post but it would be awesome to have someone look at this and post ideas or code modifications to make this run faster!

Thanks in advance!

Posted 1 year ago #

Maciej Swic
Member

@pagex Can i use your A* code in my upcoming iTouch project please? You will be credited accordingly if you provide me with your full name.

Posted 1 year ago #
eoin
Member

@pagex

You could use instruments to work out if it is slow where you think it is slow ( NSArrays) or elsewhere. Alternatively post a test project and let the community take a look. Thats what this place is about. I will definitely look at it, and I have used Instruments is plenty of commercial releases. It's essential.

( of course we may find out the problem is the algorithm).

Posted 1 year ago #
azzoor10
Member

I am a noob at this but i am getting an error in the GameMap.m file. Just at the first {, error is "expected ; before {"

Does anyone have the code in a project that i can download and test?

Posted 1 year ago #
azzoor10
Member

double post sorry

Posted 1 year ago #
azzoor10
Member

triple post, sorry. dam wireless internet

Posted 1 year ago #
macgeo
Member

This is a great start on a*, thanks for this post. Did you wind up finding a way to speed it up? Couple thoughts:
I've written similar approach but am using CGPoint inside astar to track coordinates of nodes. Not sure if it's faster but works the same.

ret = [[ret reverseObjectEnumerator] allObjects]; is suspect for me. I think this might be slowing things down?

Posted 6 months ago #
abitofcode
Moderator

As we're resurrecting this post it's probably worth pointing out the following links for anyone new to a*

http://www.raywenderlich.com/4946/introduction-to-a-pathfinding

http://www.raywenderlich.com/4970/how-to-implement-a-pathfinding-with-cocos2d-tutorial

Posted 6 months ago #
RishabhShah
Member

Does this method is useful for Non-Tiled based application? I am using simple cocos2d and i don't want to use tile map. so how is it possible?

Posted 3 months ago #
slycrel
Member

I made a more generic one that is not TMX based that I posted to the forums a few months back. You can find it here:

http://www.cocos2d-iphone.org/forum/topic/21042

Posted 3 months ago #
RishabhShah
Member

@slycrel: thanks man. that was awesome.

Posted 3 months ago #

RSS feed for this topic

Reply

You must log in to post.