just pushed a CCTMXTiledMap A* pathfinding class to github

cocos2d for iPhone » Programming » cocos2d 3rd party extensions

just pushed a CCTMXTiledMap A* pathfinding class to github

(55 posts) (18 voices)

Started 9 months ago by sqlboy
Latest reply from rakkarage

Tags:

12 Next »

sqlboy
Member
Was looking around and couldn't find one that wasn't ridiculously slow...granted I didn't look to hard and I felt like trying it out. This class give you the ability to highlight a path or move a sprite along the path at a given speed.

Code:
https://github.com/sqlboy/tiled-games/tree/master/src

Quick video of path highlight option:

Get the Video Plugin

Code is pretty easy. Pass in a map and the name of the layer that has your collision tiles.
```
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 1

// 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];
```
Enjoy and thanks to everyone for Cocos2D
Posted 9 months ago #
hm50
Member

Nice work! Looks great! I've a similar class which also allows for no diagonal jumping, makes the path look a little neater. But I really like your map integration. Cool!

Posted 9 months ago #
wilczarz
Member

This is great, thanks! I have two questions, though:
1) why aren't the corners of the path included in result?
2) does the class work for isometric maps too?

EDIT: and two more:
3) what if my collidable tiles are just non-empty tiles, will it work?
4) did you test it with a moving target? How fast is the algorirhm?

Posted 9 months ago #
jandujar
Member

Thank's for sharing!!

Posted 9 months ago #
cocojoe
Member

Nice work

Posted 9 months ago #
sqlboy
Member

The corners of the path are not included because A* sees diagonal movement as quicker in some cases. I added a flag to disable it:

[pathFinder setConsiderDiagonalMovement:NO]

That will give you better looking paths.

If your collidable tiles are non-empty you have a problem. Assuming these non empty tiles are on their own layer, just add a layer property called "COLLIDE" with a value of anything. Alternatively, right click on the tile in the tilesets area of Tiled and go to properties, then add a COLLIDE = 1 property for each tile. Its faster to use the first method which is just making the whole layer a collide layer.

It would need a new API method to handle a moving target properly since you would want to change direction and possibly walk on tiles you've already walked on. I can put that in next week.

As for speed, a lot of the example code I saw had multiple O(N) portions that I replaced with O(1) by using sets rather than arrays.

Posted 9 months ago #

voidstar
Member

Hey sqlboy, thanks for sharing this!

I noticed that when you look for adjacent nodes in the findPathFrom function that you are missing a bounds check that leads to an exception.

I rectified this by adding the following and it seems to work:

...

      for (int y=-1; y<=1; y++)
      {
        for(int x=-1; x<=1; x++)
        {
          // Skip over self
          if (x == 0 && y == 0)
            continue;

          int adjacentX = currentX+x;
          int adjacentY = currentY+y;

          if(adjacentX < 0 || adjacentX >= collideLayer.layerSize.width)
              continue;

          if(adjacentY < 0 || adjacentY >= collideLayer.layerSize.height)
              continue;

          ...

Thanks once again!

Posted 9 months ago #

rakkarage
Member

thanks a lot! real nice!

edit: but why does it go (4 squares) around behind the pillar in this case instead of (2 squares) in front?

thanks!

Posted 9 months ago #
Gray Olson
Member

Because it's seeing diagonal movement so therefore thats less distance.

Posted 9 months ago #
rakkarage
Member

its not shorter, it could get there in two moves, instead it uses 4 moves to go around the back of the pillar

here is more strange behavior... diag movement is on but it only make one diag move at corner so it takes 9 moves instead of 5
maybe it has not been tuned for open areas yet?

i am still reading and playing around with! not complaining just curious

thanks

Posted 9 months ago #
slycrel
Member

For anyone looking to tweak this stuff, this guy has a ton of resources here.

http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

Posted 9 months ago #
rakkarage
Member
thanks for that stanford link

i added a method (or message?) to this class called stepSprite

- (void) stepSprite:(CCSprite*)sprite from:(CGPoint)src to:(CGPoint)dst;

which does the same as moveSprite except it just moves it one tile along the path
```
- (void) stepSprite:(CCSprite*)sprite from:(CGPoint)src to:(CGPoint)dst
	AStarNode *node = [self findPathFrom:src to:dst];
	if (node == nil)
		return;
	int tileWidthOffset = [tileMap tileSize].width / 2;
	int tileHeightOffset = [tileMap tileSize].height / 2;
	while(node->parent != nil && node->parent->parent != nil)
	{
		node = node->parent;
	}
    CGPoint p1 = [collideLayer positionAt:node->point];
    p1.x = p1.x + tileWidthOffset;
    p1.y = p1.y + tileHeightOffset;
	sprite.position = p1;
}
```
which i call from my update every x per second

and ya the path it shows is not always the path it takes especially when you ask for recalc after each square... it sometimes chooses to jut out right and other times left flipping the path at each step

(edit: maybe i should cache the path and read a step from it each time... no i cant do that because the path is being constantly (usually) updated with touches and moves and ends... hrm.)

but its an excellent class it worked so easy and taught me so much already

thanks
Posted 9 months ago #
rakkarage
Member

why is it not possible to change the color of the path?
i noticed your comment but it seems like
CGImageRef pathImage = [self makePathTile];
is called each time... so i changed the color but it still uses the old one
just wondering if there is some other or technical reason the color cannot be changed or i am just doing something wrong? thanks :)

Posted 9 months ago #
rakkarage
Member

i found the place where diagonal weight is applied and it works more according to my expectations now thanks

// Calculate G
// G cost is 10 for adjacent and 14 for a diagonal move.
// We use these numbers because the distance to move diagonally
// is the square root of 2, or 1.414 the cost of moving
// horizontally or vertically.

Posted 9 months ago #
rakkarage
Member
the code can sometimes assert that the gid its looking up for adjacent node is outside map, if you click outside the map (i keep player centered even near 'edges')
```
// Skip over this node if outside map.
if ((adjacentNode->point.x >= tileMap.mapSize.width) || (adjacentNode->point.y >= tileMap.mapSize.height))
	continue;
```
i also added this code to prevent the assert where you do your other skip if checks

thanks

EDIT: i mean you dont even have to click outside map, i just move next to edge and click back towards middle of map and it tests outside map and asserts
Posted 9 months ago #
rakkarage
Member

CCSprite *spr = [CCSprite spriteWithCGImage:pathImage key:nil];
aha set key to nill to generate new texture with new color :)

Posted 9 months ago #
sqlboy
Member

Just got back from vacation guys, thank you for all the comments. I'll check out some of your patches and ideas and work on getting them integrated.

The path finding code is actually missing a part of A* I haven't implemented yet, once I have that in then it should work fine in open areas.

Thanks everyone again for the bug fixes and comments.

Posted 9 months ago #
sqlboy
Member

why is it not possible to change the color of the path?
i noticed your comment but it seems like
CGImageRef pathImage = [self makePathTile];
is called each time... so i changed the color but it still uses the old one
just wondering if there is some other or technical reason the color cannot be changed or i am just doing something wrong? thanks :)

Rakkarage: look in the header file and change the #define ASTAR_PATH_COLOR to whatever color you want. In the future I'll just make this part of the public API.

Posted 9 months ago #
sqlboy
Member

Ok, just pushed a couple patches to git which fixes the bounds checking voidstar reported and rakkarage's path finding issue so it works MUCH better on open maps.

Next feature is an additional A star feature which should handle some rare corner cases better.

Posted 9 months ago #
zhaopinping
Member

Can share out the project study

Posted 9 months ago #
sqlboy
Member

I'm not sure what that is but this is what I used as a guide.
http://www.policyalmanac.org/games/aStarTutorial.htm

Posted 9 months ago #
zhaopinping
Member

Thank you

Posted 9 months ago #
zhaopinping
Member

That is another problem i want your help.Could you please tell me if A has the function to forecast its next action ,that means if it will encounter the trap in the march process ,it can choose another path in advance .

Posted 9 months ago #
sqlboy
Member

zhaopinping: The code is located here

https://github.com/sqlboy/tiled-games/tree/master/src

Posted 9 months ago #
zhaopinping
Member

Thank you

Posted 9 months ago #
zhaopinping
Member

thank u for your help, I am clear about "A*" algorithm now

Posted 9 months ago #
penth
Member

Has anyone done timing on this with a good sized map and path?

Posted 9 months ago #
Xyun
Member
First of all, great work on this sqlboy!

I do have something to report though. I have not fully figured out what is causing it, but while the pathfinder works absolutely perfect in the simulator, it fizzes out on an actual device (tested on iPhone 3G) in specific situations. Specifically, when the path seems to navigate around a large number of obstructions, the final path generated sometimes just ignores the obstacles.

An example (sorry if my ASCII art is bad):
Legend:
# = obstruction
@ = start
X = end
```
##############
        #X   #
############ ##########
#      @   # #
########## # #
       #   # #
       # ### ##########
       #
       ################
```
On the simulator, the path generated is correct:
```
##############
        #X...#
############.##########
#      @...#.#
##########.#.#
       #...#.#
       #.###.##########
       #.....
       ################
```
But on the device, it first takes a left, then skips to the right through the obstacle:
```
##############
        #X...#
############.##########
#   ...@   #.#
########## # #
       #   # #
       # ### ##########
       #
       ################
```
I'm still puzzled as to why this is happening! :(
Posted 8 months ago #
rakkarage
Member

haha i just recently got my app on a device for the first time and noticed the same thing... it only seems to happen in certain parts of the map? like he teleports

i do not know what is causing it tho or what causes it to only happen on a real device...

Posted 8 months ago #
rakkarage
Member

only seems to happen when i try to go east or south east? yours west?

Posted 8 months ago #

RSS feed for this topic

12 Next »

Reply »

You must log in to post.