I have an A* class that I wrote earlier this year I could probably share as well, if nothing else to compare the algorithm and maybe find the bug. If anyone wants to go down that road let me know, I'm happy to share. (Don't have it here with me or I'd just post it...)
just pushed a CCTMXTiledMap A* pathfinding class to github
(55 posts) (18 voices)-
Xyun
MemberIt varies really. I don't believe direction matters.
Anyhow, I stopped getting these wierd pathing behaviors after I modified the code such that the CCTMXTiledMap is not retained. I figured that for my case, the tiled map should be weak referenced instead. But I can't really confirm that just this change truly fixes the issue.
YMMV.
Posted 8 months ago # -
goodeats2009
Memberhi, noob here :), im trying to integrate this with the app im building but i cannot seem to make it work
can you please verify if im doing this correctly? referencing the code below:
tileMap = the tilemap you are using, i replaced it with mine 'bgMap'.
srcTile = is a CGPoint which you can replace like ccp(x,x)? in my case, this is the 'playerLocationPoint'
dstTile = is a CGPoint which you can replace also? in my case, this is the 'touchedPoint'
player = this is your sprite? i replaced it with my sprite like 'pandaSprite'.i placed this in the init method:
AStarPathFinder pathFinder = [[AStarPathFinder alloc] initWithTileMap:tileMap collideLayer:@"collide"]; // Optionally, you can set the name of the collide property key and the value it expects. [pathFinder setCollideKey:@"collidable"] // defaults to COLLIDE [pathFinder setCollideValue:@"True"] // defaults to 1and i placed these in the CCtouchended method:
// highlight a path (src and dst are tile coorindates) [pathFinder highlightPathFrom:srcTile to:dstTile]; // move a sprite [pathFinder moveSprite:player from:srcTile to:dstTile atSpeed:0.1f];is this correct? please help. thanks
Posted 8 months ago # -
sqlboy
MemberI rolled out an update, not sure if it will help with this issue. There is a minor API change to the constructor. I need to get the iPad off my wife to check it on the hardware. Instead of passing in a collide layer name, you pass in a ground layer name. Then with some methods on the class you can add multiple collide layers. Example:
NSString *mapName = [NSString stringWithFormat:@"ipad_level_%d.tmx", level]; tileMap = [[CCTMXTiledMap tiledMapWithTMXFile:mapName] retain]; [[tileMap layerNamed:@"Collide"] setVisible:NO]; // I make a special layer in Tiled for collision tiles. // Initialize the A* pathfinder. pathFinder = [[AStarPathFinder alloc] initWithTileMap:tileMap groundLayer:@"Ground"]; [pathFinder addCollideLayer:@"Collide"]; [pathFinder addCollideLayer:@"FOG"];One thing to note that might fix all of your problems. It expects the sprites your moving around the map to be a child of the tileMap object. So, when I addd my player, I do this:
[tileMap addChild:player.sprite z:1000]Please give this latest class a try, I've been using it without any problems for a month now.
Posted 8 months ago # -
Zerpico
MemberThought this might be useful to anyone wanting to know more about pathfinding with other AI pathfinding aspects covered in links at the end of the article.
http://gamecareerguide.com/features/996/getting_there_from_here_an_.php?page=1Posted 8 months ago # -
goodeats2009
Memberhi, i still cannot get the path to HIGHLIGHT, i tried changing the method to just add a sprite but it does not show also? help please thanks
- (void) highlightPathFrom:(CGPoint)src to:(CGPoint)dst { [self clearHighlightPath]; NSArray *nodes = [self getPath:src to:dst]; if ([nodes count] == 0) return; int tileWidthOffset = [tileMap tileSize].width / 2; int tileHeightOffset = [tileMap tileSize].height / 2; for(AStarNode *node in nodes) { CGPoint p1 = [groundLayer positionAt:node->point]; p1.x = p1.x + tileWidthOffset; p1.y = p1.y + tileHeightOffset; CCSprite *spr = [CCSprite spriteWithFile:@"tile.png"]; spr.position = p1; [self addChild:spr]; CCLOG(@"p1 position:%f,%f",p1.x,p1.y); } }Posted 8 months ago # -
iCocos
Member@goodeats2009 did you add the the pathfinder as a child to your scene? did work for me ;)
Posted 8 months ago # -
goodeats2009
Memberhi iCocos
yes i did add it. everything works except for the HIGHLIGHT path. i changed it a bit and instead of a sprite, i toggled the visibility of certain tiles and that one works
- (void) highlightPathFrom:(CGPoint)src to:(CGPoint)dst { [self clearHighlightPath]; NSArray *nodes = [self getPath:src to:dst]; if ([nodes count] == 0) return; for(AStarNode *node in nodes) { CGPoint p1 = [groundLayer positionAt:node->point]; p1.x = p1.x/tileMap.tileSize.width; p1.y = (tileMap.mapSize.height - (p1.y/tileMap.tileSize.height))-1; [groundLayer tileAt:ccp(p1.x,p1.y)].visible=NO; } }did you do anything different and if you did, can you show me your code implementation?
Also, I noticed that after touching the desired tile, it takes a second before my sprite starts moving. is the Algorithm heavy in cpu? the emulator lags just a bit BUT when i tried it on the iPhone 4 the lag is noticeable. anyone has a tip to speed it up? thanks
Posted 8 months ago # -
iCocos
MemberSo this is what comes in my init of the GameScene:
-(id) init { if( (self=[super init])) { self.isTouchEnabled = YES; self.tileMap = [CCTMXTiledMap tiledMapWithTMXFile:@"TileMap.tmx"]; self.background = [_tileMap layerNamed:@"Background"]; self.meta = [_tileMap layerNamed:@"Meta"]; _meta.visible = NO; self.player = [CCSprite spriteWithFile:@"Player.png"]; _player.position = ccp(x, y); [self addChild:_player]; [self addChild:_tileMap z:-1]; pathFinder = [[AStarPathFinder alloc] initWithTileMap:self.tileMap collideLayer:@"Meta"]; [pathFinder setCollideKey:@"Collidable"]; // defaults to COLLIDE [pathFinder setCollideValue:@"True"]; // defaults to 1 [pathFinder setConsiderDiagonalMovement:NO]; [self addChild:pathFinder]; } return self; }and in my ccTouchEnded:
-(void) ccTouchEnded:(UITouch *)touch withEvent:(UIEvent *)event { CGPoint touchLocation = [touch locationInView: [touch view]]; touchLocation = [[CCDirector sharedDirector] convertToGL: touchLocation]; touchLocation = [self convertToNodeSpace:touchLocation]; // highlight a path (src and dst are tile coorindates) [pathFinder highlightPathFrom:[self tileCoordForPosition:self.player.position] to:[self tileCoordForPosition:touchLocation]]; [pathFinder moveSprite:self.player from:[self tileCoordForPosition:self.player.position] to:[self tileCoordForPosition:touchLocation] atSpeed:0.1f]; ....Haven't tried on actual device yet, but on simulator performance is great
Posted 8 months ago # -
goodeats2009
Memberhi, it worked! i added it as a child of the tile map instead of the layer, thanks. the response time though is still my issue. i wonder if using the tileAt is causing the lag. i mean the fps is great still at 60fps, its just the time to go over the map is what's taking time, it feels like the app has stalled or froze.
also, anybody tried to have the highlighted path tiles to disappear after the sprite went pass it? thanks so much
Posted 8 months ago # -
goodeats2009
Memberhi again, just curious how long it takes to execute this A* algorithm in your tile map? i have a 64x64 tile size in a 15x10 tilemap. After selecting my target node which is only 3 tiles in any direction, it takes about 1-1.5 seconds before the sprite starts moving to the node. i also added a method that highlights a 3 tile node radius around the sprite. the method gets called when i click on the sprite so it shows the options on where the sprite can go. it also takes about 1-1.5 seconds after clicking the sprite for the highlighted nodes to show up. the lag is evident when using it on the phone. anybody else have this issue? any tips? thanks
Posted 8 months ago # -
goodeats2009
Memberhi again,
the collideLayers are all set in the tile map like:
[_pathFinder addCollideLayer:@"Collide"]; [_pathFinder setCollideKey:@"Collide"]; [_pathFinder setCollideValue:@"True"];but how do i add a sprite (e.g. enemySprite) to the list so that the pathfinder detects the sprite as a collision and avoids it also?
Right now if i have my enemySprite in between the source point and destination point, the A*star just goes through it, i want the algorithm to avoid the sprite if it is blocking the way.thanks for the help.
Posted 7 months ago # -
rakkarage
Memberhttp://www.cocos2d-iphone.org/forum/topic/21042
the astar version posted here demonstrates a delegate which allows you to let the calling object respond to messages from the pathfinder
here is my delegatei use both because i do not care if a mob is at the end point of the path... just if a mob is in the middle somewhere to avoid
@protocol AStarDelegate <NSObject>
- (BOOL)AStarBlocked:(CGPoint)p;
- (BOOL)AStarBlockedIgnoreMobs:(CGPoint)p;
- (CGPoint)AStarPositionAt:(CGPoint)p;
@endPosted 7 months ago # -
goodeats2009
Memberhi rakkarage, did you happen to compare that A*star versus the one posted here if they perform about the same with regards to performance/response time or if the resulting paths are the same? and if not which one is better? I was able to add a sprite's position into the collision by creating a CGPoint accessor and passing the value of the CGPoint to the isCollision method of the A*.
@interface
@property CGPoint playerPosition;@implementation
`- (BOOL) isCollision:(CGPoint)point
{
if (point.x == playerPosition.x && point.y == playerPosition.y)
return YES;
'
I called the playerPosition from the gamePlayLayer which sets the playerPosition, in my case its the touch location
[_pathFinder setPlayerPosition:tileTouchedPoint];it works for one sprite but I'm not sure if its a good solution for multiple sprites. so the one you posted sounds great if they perform about the same. thanks
Posted 7 months ago # -
rakkarage
Memberyou do not need to copy the whole algorithm you can just add a delegate with methods to retrieve any information you need...
astar knows exactly when it needs a mob position and can ask for it at that time instead of assuming someone else set it correctly at the right timePosted 7 months ago # -
Sorry to semi-necro this thread, but has anyone managed to optimize the code? It's an awesome tool, and it works great on the simulator... But on the device it skips. I have the path set update every five seconds, and everything freezes until if finishes picking the path. I assume there's some need to add another thread for the pathFinder to work on, but I'm not certain.
Posted 5 months ago # -
This code is still the best code for pathfinding? Is there another option? Is the issue pointed by @XenElement valid? Thanks
Posted 2 months ago # -
There are lots of ways to do A* pathfinding. If the one in this thread doesn't work for you you could try looking at the one rakkarage posted about above, do a search on these forums (there are more posted to the forums I think) or write your own. I haven't used SQLBoy's implementation, but if it's having issues you may try sampling it with instruments and seeing where the time is being taken. If you do this please post the results here.
Posted 2 months ago # -
rakkarage
Member
if you add some debug drawing code inside find path like this
you can tell if your algorithm is working correctly and only visiting nodes it needs to and not exploring the whole screen for a simple line
and you can trace the path back from anywhere with the parent arrows
CGPoint p0 = [_delegate AStarPositionAt:adjacentNode->point]; CCSprite *arrow; if (x > 0 && y > 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow3"]; // nw else if (x < 0 && y < 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow7"]; // se else if (x > 0 && y < 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow1"]; // sw else if (x < 0 && adjacentTiles[i][1] > 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow5"]; // ne else if (x > 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow2"]; // w else if (x < 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow6"]; // e else if (y > 0) arrow = [CCSprite spriteWithSpriteFrameName:@"arrow4"]; // n else arrow = [CCSprite spriteWithSpriteFrameName:@"arrow0"]; // s arrow.position = ccp(p0.x + _width / 2, p0.y + _height / 2); arrow.anchorPoint = ccp(0.5f, 0.5f); arrow.color = colorYellow; [self addChild:arrow]; NSString *gstring = [NSString stringWithFormat:@"%d", adjacentNode->g]; NSString *hstring = [NSString stringWithFormat:@"%d", adjacentNode->h]; NSString *coststring = [NSString stringWithFormat:@"%d", adjacentNode.cost]; CCLabelBMFont *dcost = [CCLabelBMFont labelWithString:gstring fntFile:pixelFont]; dcost.color = colorDekoBlueDark; dcost.position = ccp(p0.x, p0.y); dcost.anchorPoint = ccp(0.0f, 0.0f); dcost.scale = 0.5f; [self addChild:dcost]; CCLabelBMFont *hcost = [CCLabelBMFont labelWithString:hstring fntFile:pixelFont]; hcost.color = colorDekoRedDark; hcost.position = ccp(p0.x + _height, p0.y); hcost.anchorPoint = ccp(1.0f, 0.0f); hcost.scale = 0.5f; [self addChild:hcost]; CCLabelBMFont *cost = [CCLabelBMFont labelWithString:coststring fntFile:pixelFont]; cost.color = colorDekoGreenDark; cost.position = ccp(p0.x + _width, p0.y + _height); cost.anchorPoint = ccp(1.0f, 1.0f); cost.scale = 0.5f; [self addChild:cost];here is my AStarPathFinder
it is just a modified version / combination of sqlboy's and slycrel's
which keeps track of direction and can take one step at a time and can draw debug information
i guess i am not caching the path as well as i could be... but recalculating it makes it swerve around moving mobs and follow moving mob targets
might not be exactly plug and play but maybe someone will find some of it useful
https://gist.github.com/2017874Posted 2 months ago #
Reply
You must log in to post.