DEV Community

A Star (A*) Path Finding C++

Andris Jansons on March 22, 2018

A* (A star) path finding algorithm is an extension of the famous Dijkstra's path finding algorithm, which is more efficient, but occasionally doesn...
Collapse
 
pchinery profile image
Philip

Thank you for sharing your dive into the A* algorithm :)

I always like to think about and discuss algorithms and unfortunately don't find enough time during my regular work.

I'd just like to add one note to what you said: A* will always give the best route (given its constraints) and is like a Dijkstra where the cost function reruns the same value for each estimate. It's important though that the estimated cost has to be equal to or larger than the actual path. This usually is guaranteed by the Manhatten distance, but can bite you in a game where you can teleport (i.e. move to steps in the opposite direction and then skip 10 steps, this will kill the heuristic and can lead to pseudo-optimal paths).

But apart from that: thanks for sharing this (maybe I am repeating myself here ;) )

Collapse
 
jansonsa profile image
Andris Jansons

That is an interesting situation I hadn't thought about before.

A* usually is good enough, but it has these situations where it's just too Greedy, that it misses better options. That is exactly why there are multiple different algorithms out there to explore their trade-offs. This is why developers should work shoulder to shoulder with their level designers, to anticipate these situations and make the better choice.

Either way, a lovely comment Philip, hope to hear from you more!

Collapse
 
sortcare profile image
HudsonJoe

Nice comment but with one minor issue. A-star's(tree version) optimality is guaranteed when using an admissible heuristic, which means the h value never overestimates the actual cost for any node. So, it is important that the estimate has to be equal to or smaller than the actual cost. With no heuristic function given, that's equivalent to h(x)=0 for all x, it will downgrade to Dijkstra.

So the A* algorithm is asking for "some" information about the distance to the goal, but not too aggressive information.

But the author's code is actually a graph version of A*(because there is a closed list maintained), so admissibility is not enough in some situation to guarantee optimality. We need to ensure another property of the heuristic: consistency, which means h(x) <= cost(x,y) + h(y) should be true for all node x.

Collapse
 
stringsofarrays profile image
StringsOfArrays

Hey, what is "world.obstacles.count(id)"?? Where does world and obstacle get defined and what type is it?

Collapse
 
jansonsa profile image
Andris Jansons

Hi, "obstacles" is an std::set object. I'm using .count() to check if the corresponding tile is an obstacle or not. "world" is just a class where I keep it

Collapse
 
muhammadkhan786 profile image
MuhammadKhan786

how we can use this world, can you please out?

Collapse
 
erotokritosvall profile image
erotokritosVall • Edited

You can use a binary heap for the open set makes it way faster. Also you can check my A* implementation on Laser Maze project, in the folder named Pathfinder if you like :)

Collapse
 
ayanasser profile image
aya nasser

please what's FLT_MAX ??

Collapse
 
jansonsa profile image
Andris Jansons

FLT_MAX stands for maximum floating point value. Since we want to initialize every node with a cost of infinity, FLT_MAX is the closest we can get to infinity.

Collapse
 
ayanasser profile image
aya nasser • Edited

But it's undefined here in your code ,, where i should define it ?
and could u send me your email , because i have some question for a small university project

Thread Thread
 
karabas2903 profile image
karabas2903 • Edited

you can include cfloat lib