A* (A star) path finding algorithm is an extension of the famous Dijkstra's path finding algorithm, which is more efficient, but occasionally doesn...
For further actions, you may consider blocking this person and/or reporting abuse
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 ;) )
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!
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.
Hey, what is "world.obstacles.count(id)"?? Where does world and obstacle get defined and what type is it?
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
how we can use this world, can you please out?
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 :)
please what's FLT_MAX ??
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.
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
you can include cfloat lib