AStar Pathfinding with Compass

[msteve]

Hello all,

I was developing a little game when I was faced with the problem of pathfinding. So I share my experience for this kind of problems with a small lib that I created. I implemented a function that uses the algorithm AStar.

https://github.com/smagras/Compass

Here a little tutorial, but in french^^"  (More explained than on github)
http://idevlog.atspace.eu/magrasSteve/a-pathfinding-avec-compass/

And here you can see how to use the lib (we have 2d map, start point and a end point):

// Load map from file
Compass::PCore::Matrix<int> mapi = getMapFromFile("mapInput.txt"); // Just to init matrix, do your own code here

// Config parameters for the algorithm
Compass::PPathfinding::AStar  astar;
astar.smoothPath(true); //To have smooth path
astar.init(&mapi);

// Find the path from pend to pstart
Compass::PCore::Point pend(2,2);
Compass::PCore::Point pstart(8,8);
std::list<Compass::PCore::Point> res = astar.run(pstart,pend);

// Save result in file
savePathInFile("outFile.txt",mapi,res); // just show the result

I hope, it could help some peoples =)
(There is no many test for the moment, performances problems could exist )

[Nexus]

Thanks for sharing!

According to your tutorial, smoothPath() seems to remove intermediate nodes that lie on a line between two other points, i.e. they minimize the number of points, correct?

And does your A* implementation always consider 8 directions, or is it also possible to check only horizontally and vertically (4 directions)?

By the way, if you plan to extend your library, you should check out LEMON. They provide quite optimized algorithms for a variety of graph-related problems and they also have a very nice API (as opposed to Boost.Graph). It might be worth having a look to not re-invent the wheel

[msteve]

I am happy if my work can be util =)

According to your tutorial, smoothPath() seems to remove intermediate nodes that lie on a line between two other points, i.e. they minimize the number of points, correct?

Your totaly right

And does your A* implementation always consider 8 directions, or is it also possible to check only horizontally and vertically (4 directions)?

For the moment there is 8 dirrections, but I can add an option to have 4, it's not a big deal =)

By the way, if you plan to extend your library, you should check out LEMON. They provide quite optimized algorithms for a variety of graph-related problems and they also have a very nice API (as opposed to Boost.Graph). It might be worth having a look to not re-invent the wheel

Yes you right, I will read their features ;P

[Glocke]

I was developing a little game when I was faced with the problem of pathfinding. So I share my experience for this kind of problems with a small lib that I created. I implemented a function that uses the algorithm AStar.

Nice idea! In addition to my currently paused rogue-like game, I planned to implement A* in a very generic way. I'll gonna publish my results in a github repository if I have enough time. Then we might help each other. Currently, my plan is building a template-based A* function using a generic grid and a generic actor to move.

[msteve]

Ok But I think this version of the algorithm is very generic. I'm agree whit you, maybe we could help each other, add functionnality? performance?

And like Nexus said, it maybe not necessary to recreate the wheel. So I think it maybe more interresting for my lib to be Game focus. I explain, I think I should focus my works on algorithm usefull for game devellopers and not going in all directions. For the moment, I think that it could be interresting to implement Avoidance Algorithm.

What do you think of that? Maybe some ideas?