[Tutorial] Path finding for TMX


#1

Hi,

I am sharing my one class called TMXPathFinding which will help you to find Path from start pos to goal pos avoiding obstacles. Its a implementation of A* algo. Hope it will help lot of newbies. Feedback always welcome.

It uses TMXTiledMap object.
It supports orthogonal, hexagonal and isometric tile maps.
During Path finding, it takes current GID values from TMXLayers.

Features:

  • Find Path between two Tile coordinates
  • DIRECTION support :
  1. DIRECTION::FOUR - L, R, U, D
  2. DIRECTION::EIGHT - L, R, U, D, TL, BR, TR, BL
  3. DIRECTION::SIX - For Hexagonal maps
  • You can add multiple Obstacle tiles. e.g.- TILE_WALL, TILE_WATER
  • You can add multiple Walkable tiles. e.g.- TILE_ROAD, TILE_GRASS
  • You can find path using only Obstacle tiles
  • You can find path using only Walkable tiles
  • You can find path for single or combined TMXLayers

Limitations:

  • Multiple path finding is not possible
  • Only one shortest path will return

How to use?

  • You have to pass TMXTiledMap and TMXPathFinding::DIRECTION to create TMXPathFinding object

    TMXTiledMap *tileMap = TMXTiledMap::create(“level_1.tmx”);
    TMXPathFinding *pathFind = new TMXPathFinding(tileMap, TMXPathFinding::DIRECTION::FOUR);

  • Note : For Hexagonal you must pass DIRECTION::SIX
    For Orthogonal & Isometric DIRECTION::FOUR or DIRECTION::EIGHT

  • You can set desired Layers list, [Note: If you don’t call this, it will check for all layers in given TMXTiledMap]
    pathFind->setTileLayers({"Layer_1", "Layer_2", "Layer_3"});

  • If you want to reset tile layers, means algo should check for all layers
    pathFind->setTileLayers( { } );

  • To get path by using Walkable list

     Vec2 startPos(5, 5);
     Vec2 goalPos(10, 10);
    

std::vector<Vec2> path = pathFind->getPathUsingWalkable(startPos, goalPos, { TILE_ROAD, TILE_GRASS });

  • To get path by using Obstacle list
    std::vector<Vec2> path = pathFind->getPathUsingObstacles(startPos, goalPos, { TILE_WALL, TILE_WATER });

  • Note : TILE_ROAD, TILE_GRASS, TILE_WALL, TILE_WATER will be GID as per your tileset define in TMX map.

  • Remeber GID starts with 1 not 0.

  • Once you got path

    if (path.size() == 0)
    log(“No Path is available…”);
    else {
    for (Vec2 tilePos : path)
    log(“x: %f y: %f”, tilePos.x, tilePos.y);
    }

  • Once you finish Delete path finding object
    delete pathFind;

  • HINT :
    If you have less obstacles then use getPathUsingObstacles.
    If you have less walkable tiles then use getPathUsingWalkable

Download here


I want build a AI Library for Coco2dx
#2

something wrong…
i guess that same case code~

case 6: // bottom-right
newNode->setLocX(1);
newNode->setLocY(-1);
break;
case 7: // top-right
newNode->setLocX(1);
newNode->setLocY(-1);
break;


#3

Yes, its wrong.
It should be

case 7: // top-right
newNode->setLocX(1);
newNode->setLocY(1);
break;

Thanks for checking, i never used 8 dir so just did normal testing before posting.
I made changes in repo.


#4

humm…check please 8 dir, unusual result.
top-left, bottom-left, bottom-right, top-right is right.
but left, right, up, down is something wrong.


#5

i checked and It seems to be working fine for me.
can you share your tmx file?


#6

stage.zip (9.8 KB)


#7


#8

Ohk, that result is correct only.
But you want straight line then i think by replacing Euclidean Distance with Manhatten Distance will solve your problem.

Just replace this line in euclideanDistance method

int ans = sqrt(dx * dx + dy * dy);

with

int ans = abs(dx) + abs(dy);

:smile:


#9

thx, nice working~


#10

Hi,
i am a begineer in cocos2d.i am developed a ludo game .i have some doubts about this
is this path finder script useful for ludo game.
how to move startpos to stoppos using this script.
suggest any ideas about developing ludo based game.
pls help me


#11

No, this path-finding is implementation of A* algo.
For Ludo game you have to code your own way.
You can take pre-defined array of pos to navigate through.


#12

Thank you for replying…
is position is taken from TMX object layer or TileGID. pls mention to get pos from TMXobject.i see several times but i didnt get position from TMXObject so pls mention …


#13

As its mentioned by me in original post, it takes TileGID not TMXObject


#14

bro i mean suggest me to get pos from tileGID.i dont know how to get pos fro tile.


#15

But i will suggest you that dont use TMX for Ludo. Its not required, it will make complex for you to deal with.


#16

ok. so you mean all possible position are stored into an array.then move player to that position.


#17

Yes, because that you have to do anyway, if you use TMX or not.