Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: AStar Pathfinding with Compass  (Read 3011 times)

0 Members and 1 Guest are viewing this topic.

msteve

  • Newbie
  • *
  • Posts: 25
    • View Profile
    • idevlog
AStar Pathfinding with Compass
« on: November 03, 2014, 03:22:01 pm »
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):

Quote
// 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 :P )

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6286
  • Thor Developer
    • View Profile
    • Bromeon
Re: AStar Pathfinding with Compass
« Reply #1 on: November 03, 2014, 03:30:39 pm »
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 ;)
« Last Edit: November 03, 2014, 03:35:07 pm by Nexus »
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

msteve

  • Newbie
  • *
  • Posts: 25
    • View Profile
    • idevlog
Re: AStar Pathfinding with Compass
« Reply #2 on: November 03, 2014, 03:38:33 pm »
I am happy if my work can be util =)

Quote
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 ;)

Quote
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 =)

Quote
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
« Last Edit: November 03, 2014, 03:50:46 pm by msteve »

Glocke

  • Sr. Member
  • ****
  • Posts: 289
  • Hobby Dev/GameDev
    • View Profile
Re: AStar Pathfinding with Compass
« Reply #3 on: November 04, 2014, 07:02:20 pm »
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.
Current project: Racod's Lair - Rogue-inspired Coop Action RPG

msteve

  • Newbie
  • *
  • Posts: 25
    • View Profile
    • idevlog
Re: AStar Pathfinding with Compass
« Reply #4 on: November 07, 2014, 11:44:06 pm »
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?

 

anything